edu.wwu.tobikley.acgc.algorithms
Class NaiveCountingAlgorithm

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

All Implemented Interfaces:

Callable<BigInteger>

public class NaiveCountingAlgorithm
extends CountingAlgorithm

Implements a Naive Counting Algorithm as a CountingAlgorithm. To determine the exact number of proper q-Colorings the following steps are performed:

1. Collect all vertices in an ordered fashion.
2. Then go throught the induced list of alle q-Colorings (there are q^k of them) in lexicographic order.
3. For each q-Coloring decide if it is proper and count it, if it is.

For further information, refer to

• Häggström, O.: Finite Markov Chains and Algorithmic Applications, Cambridge u. a.: Cambridge Univ. Press 2002, p. 65.

Version:

1.0

Author:

Tobias Kley

Field Summary

private int[]	coloring The current coloring checked by the algorithm.
protected HashMap<Vertex,Integer>	verticeNames Mapping the graphs vertices to Integer ids.
private int	watchedColor Color previously watched at the watchIndex of coloring.
private int	watchIndex Specified position in coloring to watch for changes to report progress.

Fields inherited from class edu.wwu.tobikley.acgc.algorithms.CountingAlgorithm

detailedResults, endTime, graphBackup, graphWorkingCopy, numberOfColors, progress, progressText, returnVal, startTime

Constructor Summary

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

Method Summary

void	algorithm() Iterates through all possible q-Colorings and calls isValid to determine if it is proper.
private boolean	isProperVertexColoring() Checks if a q-Coloring is proper regarding the graphWorkingCopy.
private void	setProgress() If necessary progress and progressText are updated.
private void	setProgressText(String progressText)

Methods inherited from class edu.wwu.tobikley.acgc.algorithms.CountingAlgorithm

call, getDetailedResults, getGraph, getNumberOfColors, getProgress, getProgressText, getRunTime, setNumberOfColors

Methods inherited from class java.lang.Object

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

Field Detail

coloring

private int[] coloring

The current coloring checked by the algorithm.

watchIndex

private int watchIndex

Specified position in coloring to watch for changes to report progress. The position is chosen, so that there are least possible but at last 100 changes in color.

watchedColor

private int watchedColor

Color previously watched at the watchIndex of coloring.

verticeNames

protected HashMap<Vertex,Integer> verticeNames

Mapping the graphs vertices to Integer ids.

Constructor Detail

NaiveCountingAlgorithm

public NaiveCountingAlgorithm(Graph g,
                              int numberOfColors)

Creates a new instance of a naive counting algorithm. Invokes the constructor of CountingAlgorithm and initializes verticeNames and the watchIndex.

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

isProperVertexColoring

private boolean isProperVertexColoring()

Checks if a q-Coloring is proper regarding the graphWorkingCopy. To determine if it is a proper q-Colorings, each edge in the graph is examined. A coloring is proper if the endnodes of all edges are of different colors.

Returns:

true if coloring is a proper q-Coloring, and false if it is not.

algorithm

public void algorithm()

Iterates through all possible q-Colorings and calls isValid to determine if it is proper. Before the coloring is checked, setProgress is called, to propagate the progress of the calculation.

Specified by:

algorithm in class CountingAlgorithm

setProgress

private void setProgress()

If necessary progress and progressText are updated. The progressText is set to the text: "Calculation is xx% finished.".

setProgressText

private void setProgressText(String progressText)

Parameters:

progressText -