edu.wwu.tobikley.acgc.algorithms
Class JerrumHeatBathCountingAlgorithm

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

All Implemented Interfaces:

Callable<BigInteger>

public class JerrumHeatBathCountingAlgorithm
extends ApproximateCountingAlgorithm

Implements a variant of the fully polynomial randomized approximation scheme, specified by Marc Jerrum, as a CountingAlgorithm. To determine an approximation for the 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 the set of all colors that will reveil a proper q-Coloring if vertex v is colored with color c, uniformly at random.
3. Recolor vertex v with color c.

For further information, refer to

• Dyer, M.; Greenhill, C.: A More Rapidly Mixing Markov Chain for Graph Colorings. In: Random Structures and Algorithms, 13 (1998) 3-4, pp. 285–317.
• 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

JerrumHeatBathCountingAlgorithm(Graph g, int numberOfColors, double epsilon)

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

JerrumHeatBathCountingAlgorithm(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

JerrumHeatBathCountingAlgorithm

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

JerrumHeatBathCountingAlgorithm

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

JerrumHeatBathCountingAlgorithm

public JerrumHeatBathCountingAlgorithm(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