edu.wwu.tobikley.acgc.algorithms
Class CountingAlgorithm

java.lang.Object
  edu.wwu.tobikley.acgc.algorithms.CountingAlgorithm

All Implemented Interfaces:

Callable<BigInteger>

Direct Known Subclasses:

ApproximateCountingAlgorithm, NaiveCountingAlgorithm

public abstract class CountingAlgorithm
extends Object
implements Callable<BigInteger>

Basic functionality of an algorithm to count the q-Colorings of a graph. The following aspects are addresed:

• preparing a copy of the graph,
• returning intermediate results,
• tracking the runtime,
• storing / providing the progress of the calculations, and
• storing / providing the result itself.

Concrete counting algorithms, that inherit the functionality provided have to implement the abstract method algorithm.

Version:

1.0

Author:

Tobias Kley

Field Summary

protected Vector<CountingResult>	detailedResults Description, Result and Runtime for each iteration done of the algorithm.
protected long	endTime Time the algorithm ended in ms.
protected Graph	graphBackup A backup copy of the input graph.
protected ColoredGraph	graphWorkingCopy A copy of the graph the algorithm will work with.
protected int	numberOfColors The integer q, as the question is: How many q-Colorings are there.
protected int	progress Proportion of the task finished so far (per hundred).
protected String	progressText Description of the current task being performed.
protected BigInteger	returnVal The number of q-Colorings of the graph.
protected long	startTime Time the algorithm was started in ms.

Constructor Summary

CountingAlgorithm(Graph g, int numberOfColors)
Creates a new instance of a counting algorithm.

Method Summary

protected abstract void	algorithm() Specifies the counting algorithm.
BigInteger	call() Called from outside when the algorithm is executed.
Collection<CountingResult>	getDetailedResults() Description, Result and Runtime for each iteration done of the algorithm.
Graph	getGraph() Returns the working copy of the graph.
int	getNumberOfColors() Returns the number q as the question is: How many q-Colorings are there.
int	getProgress() Returns the proportion of the task finished so far (per hundred).
String	getProgressText() Description of the current task being performed.
long	getRunTime() Returns the time the time the algorithm ran for calculation.
void	setNumberOfColors(int numberOfColors) Sets the number q as the question is: How many q-Colorings are there.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

graphBackup

protected Graph graphBackup

A backup copy of the input graph.

graphWorkingCopy

protected ColoredGraph graphWorkingCopy

A copy of the graph the algorithm will work with.

numberOfColors

protected int numberOfColors

The integer q, as the question is: How many q-Colorings are there.

returnVal

protected BigInteger returnVal

The number of q-Colorings of the graph.

startTime

protected long startTime

Time the algorithm was started in ms.

endTime

protected long endTime

Time the algorithm ended in ms.

progress

protected int progress

Proportion of the task finished so far (per hundred).

progressText

protected String progressText

Description of the current task being performed.

detailedResults

protected Vector<CountingResult> detailedResults

Description, Result and Runtime for each iteration done of the algorithm.

Constructor Detail

CountingAlgorithm

public CountingAlgorithm(Graph g,
                         int numberOfColors)

Creates a new instance of a counting algorithm. The backup copy, the working copy of the graph, as well as the other fields are initialised.

Parameters:

g - The graph to calculate the number of q-Colorings from.

numberOfColors - The number q as the question is: How many q-Colorings are there.

Method Detail

getRunTime

public long getRunTime()

Returns the time the time the algorithm ran for calculation.

Returns:

the runtime in milliseconds.

algorithm

protected abstract void algorithm()

Specifies the counting algorithm. Any implementation may use the graphWorkingCopy. A copy is provided, because some algorithms might e.g. require adding or removing elements. The algorithm is required to store its result to returnVal, hence there is no result to this method.

call

public BigInteger call()

Called from outside when the algorithm is executed. Before starting and after finishing the algorithm the time is recorded, so the run time can be calculated afterwards. The runtime and overall result (in case there is more than one, the median of the results) is added to the detailedResults.

Specified by:

call in interface Callable<BigInteger>

Returns:

the result of the algorithm

setNumberOfColors

public void setNumberOfColors(int numberOfColors)

Sets the number q as the question is: How many q-Colorings are there.

Parameters:

numberOfColors - the numberOfColors to set

getNumberOfColors

public int getNumberOfColors()

Returns the number q as the question is: How many q-Colorings are there.

Returns:

the numberOfColors

getGraph

public Graph getGraph()

Returns the working copy of the graph.

Returns:

working copy of the graph.

getProgress

public int getProgress()

Returns the proportion of the task finished so far (per hundred).

Returns:

the progress

getProgressText

public String getProgressText()

Description of the current task being performed.

Returns:

the progressText

getDetailedResults

public Collection<CountingResult> getDetailedResults()

Description, Result and Runtime for each iteration done of the algorithm.

Returns:

the detailedResults