edu.wwu.tobikley.acgc.algorithms
Class ApproximateCountingAlgorithm

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

All Implemented Interfaces:

java.util.concurrent.Callable<java.math.BigInteger>

Direct Known Subclasses:

DyerGreenhillCountingAlgorithm, JerrumCountingAlgorithm, JerrumHeatBathCountingAlgorithm

public abstract class ApproximateCountingAlgorithm
extends CountingAlgorithm

Basic functionality of a randomized approximation scheme for the q-Colorings of a graph. By definition the Overall result has to comply with the following condition:



where Z is the true result.

The implementation addresses the following aspects:

• providing a Mersenne Twister MT19937,
• storing / providing the parameters, and
• storing intermediate results while running iterations of the algorithm.

Concrete randomized approximation schemes, that inherit the functionality provided have to implement the abstract method algorithmIteration. The algorithmIteration will be called T times by the implementation of algorithm that adds the intermediate results to detailedResults.

Version:

1.0

Author:

Tobias Kley

Field Summary

protected double	alpha The probability alpha.
protected double	delta The minimum degree delta.
protected double	Delta The maximum degree Delta.
protected double	epsilon The precision epsilon.
protected int[]	initialState A proper q-Coloring used to initialise the Markov Chains.
protected int	iterationAlgorithm Iteration of the algorithm currently being run.
protected double	k The number of vertices k.
protected double	l The number of edges l.
protected cern.jet.random.engine.MersenneTwister	mt Instance of the Mersenne Twister MT19937, used for the generation of pseudo-random-numbers.
protected int	N The number of steps N the Markov Chain will be run.
protected double	q The number of colors q.
protected int	t The number of samples t taken from the set of all proper q-Colorings.
protected int	T The number of iterations the iterationAlgorithm will be run.

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

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

Constructor Summary

ApproximateCountingAlgorithm(edu.uci.ics.jung.graph.Graph graph, int numberOfColors, double epsilon)
Creates a new instance of a randomized approximation scheme.

Method Summary

protected void	algorithm() Called by CountingAlgorithm.call() when the algorithm is executed.
protected abstract java.math.BigInteger	algorithmIteration() Specifies one iteration of the randomized approximation scheme.
protected void	initializeInitialState() Determines a proper q-Coloring to initialize the Markov Chains with.

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

mt

protected cern.jet.random.engine.MersenneTwister mt

Instance of the Mersenne Twister MT19937, used for the generation of pseudo-random-numbers.

initialState

protected int[] initialState

A proper q-Coloring used to initialise the Markov Chains.

epsilon

protected double epsilon

The precision epsilon.

alpha

protected double alpha

The probability alpha.

q

protected double q

The number of colors q.

k

protected double k

The number of vertices k.

l

protected double l

The number of edges l.

Delta

protected double Delta

The maximum degree Delta.

delta

protected double delta

The minimum degree delta.

N

protected int N

The number of steps N the Markov Chain will be run. It has to be chosen large enough to ensure that the distribution is satisfyingly close to the equidistribution on the set of all proper q-Colorings.

t

protected int t

The number of samples t taken from the set of all proper q-Colorings. It has to be taken large enough so the calculated arithmetic mean will be satisfyingly close to the expectation.

T

protected int T

The number of iterations the iterationAlgorithm will be run. It has to be chosen large enough to ensure the condition (*) holds.

iterationAlgorithm

protected int iterationAlgorithm

Iteration of the algorithm currently being run.

Constructor Detail

ApproximateCountingAlgorithm

public ApproximateCountingAlgorithm(edu.uci.ics.jung.graph.Graph graph,
                                    int numberOfColors,
                                    double epsilon)
                             throws java.lang.IllegalArgumentException

Creates a new instance of a randomized approximation scheme. Invokes the constructor of CountingAlgorithm and initializes epsilon and the Mersenne Twister MT19937.

Parameters:

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

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

epsilon - The precision parameter as specified in (*).

Throws:

java.lang.IllegalArgumentException - if epsilon <= 0.

Method Detail

initializeInitialState

protected void initializeInitialState()

Determines a proper q-Coloring to initialize the Markov Chains with.

algorithmIteration

protected abstract java.math.BigInteger algorithmIteration()

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.

algorithm

protected void algorithm()

Called by CountingAlgorithm.call() when the algorithm is executed. Before starting and after finishing an iteration of the algorithm the time is recorded, so the run time can be calculated afterwards. The runtime and result of the iteration is added to the detailedResults.

Specified by:

algorithm in class CountingAlgorithm