edu.wwu.tobikley.acgc.mc
Class JerrumHeatBathChain

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

public class JerrumHeatBathChain
extends HomogeneousMarkovChain

The Markov Chain is a variant of the JerrumChain. It implements 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 Vector<Integer>	allColors
protected int	numberOfColors

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

currentState, randomEngine, t

Constructor Summary

JerrumHeatBathChain(RandomEngine randomEngine, ColoredGraph initialState, int numberOfColors)
Creates a new instance of the jerrum heat bath 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

allColors

protected Vector<Integer> allColors

Constructor Detail

JerrumHeatBathChain

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

Creates a new instance of the jerrum heat bath 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.