edu.wwu.tobikley.acgc.mc
Class JerrumChain

java.lang.Object
  edu.wwu.tobikley.acgc.mc.HomogeneousMarkovChain
      edu.wwu.tobikley.acgc.mc.JerrumChain

public class JerrumChain
extends HomogeneousMarkovChain

The Markov Chain is designed to almost uniformly sample proper q-Colorings, as suggested by Jerrum. It implements 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

• 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 int

numberOfColors

Fields inherited from class edu.wwu.tobikley.acgc.mc.HomogeneousMarkovChain

currentState, randomEngine, t

Constructor Summary

JerrumChain(RandomEngine randomEngine, ColoredGraph initialState, int numberOfColors)
Creates a new instance of the jerrum markov chain.

Method Summary

ColoredGraph

update(Object fromState) Spezifies the transition mechanism of the markov chain.

Methods inherited from class edu.wwu.tobikley.acgc.mc.HomogeneousMarkovChain

next, next

Methods inherited from class java.lang.Object

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

Field Detail

numberOfColors

protected int numberOfColors

Constructor Detail

JerrumChain

public JerrumChain(RandomEngine randomEngine,
                   ColoredGraph initialState,
                   int numberOfColors)

Creates a new instance of the jerrum markov chain.

Parameters:

randomEngine - Pseudo random number generator.

initialState - State to initialise the markov chain at time t = 0.

Method Detail

update

public ColoredGraph update(Object fromState)

Description copied from class: HomogeneousMarkovChain

Spezifies the transition mechanism of the markov chain. The implementation has is to simulate the state at time t+1 given the current time is t. Updating the state of the markovchain will use always use random numbers invoking randomEngine.raw().

Specified by:

update in class HomogeneousMarkovChain

Parameters:

fromState - State at time t.

Returns:

State at time t+1.