edu.wwu.tobikley.acgc.algorithms
Class JerrumCountingAlgorithm

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

All Implemented Interfaces:

Callable<BigInteger>

public class JerrumCountingAlgorithm
extends ApproximateCountingAlgorithm

Implements the fully polynomial randomized approximation scheme, specified by Marc Jerrum, as a CountingAlgorithm. To determine an approximation for number of proper q-Colorings a Markov Chain is run to randomly generate proper q-Colorings from a equidistribution. The Markov Chain is characterized by the following transition mechanism:

1. Pick a vertex v from V uniformly at random.
2. Pick a color c from C uniformly at random.
3. Recolor vertex v with color c, if the resulting q-Coloring is proper. If it is not, undo the recoloring.

For further information, refer to

• Häggström, O.: Finite Markov Chains and Algorithmic Applications, Cambridge u. a.: Cambridge Univ. Press 2002, pp. 45-75.
• Jerrum, M.: A Very Simple Algorithm for Estimating the Number of k-Colorings of a Low-Degree Graph. In: Random Structures and Algorithms, 7 (1995) 2, pp. 157–165.

Version:

1.0

Author:

Tobias Kley

Field Summary

protected String

progressTextSubgraph

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

alpha, Delta, epsilon, initialState, iterationAlgorithm, k, l, mt, N, q, t, T

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

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

Constructor Summary

JerrumCountingAlgorithm(Graph g, int numberOfColors, double epsilon)

JerrumCountingAlgorithm(Graph g, int numberOfColors, double epsilon, double alpha)

JerrumCountingAlgorithm(Graph g, int numberOfColors, double epsilon, int T)

Method Summary

protected BigInteger	algorithmIteration() Specifies one iteration of the randomized approximation scheme.
private void	setProgress(int progress)
private void	setProgressText(String progressText)

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

algorithm, initializeInitialState

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

progressTextSubgraph

protected String progressTextSubgraph

Constructor Detail

JerrumCountingAlgorithm

public JerrumCountingAlgorithm(Graph g,
                               int numberOfColors,
                               double epsilon)

JerrumCountingAlgorithm

public JerrumCountingAlgorithm(Graph g,
                               int numberOfColors,
                               double epsilon,
                               double alpha)

JerrumCountingAlgorithm

public JerrumCountingAlgorithm(Graph g,
                               int numberOfColors,
                               double epsilon,
                               int T)

Method Detail

algorithmIteration

protected BigInteger algorithmIteration()

Description copied from class: ApproximateCountingAlgorithm

Specifies one iteration of the randomized approximation scheme. 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.

Specified by:

algorithmIteration in class ApproximateCountingAlgorithm

setProgress

private void setProgress(int progress)

Parameters:

progress - the progress to set

setProgressText

private void setProgressText(String progressText)

Parameters:

progressText - the progressText to set