001    /**
002     * 
003     */
004    package edu.wwu.tobikley.acgc.mc;
005    
006    import cern.jet.random.engine.RandomEngine;
007    import edu.wwu.tobikley.acgc.graphcoloring.ColoredGraph;
008    
009    /**
010     * The Markov Chain is designed to almost uniformly sample proper q-Colorings,
011     * as suggested by Jerrum. It implements the following transition mechanism:
012     * 
013     * <ol>
014     * <li>Pick a vertex v from V uniformly at random.
015     * <li>Pick a color c from C uniformly at random.
016     * <li>Recolor vertex v with color c, if the resulting q-Coloring is proper.
017     *     If it is not, undo the recoloring.
018     * </ol>
019     *  
020     * For further information, refer to
021     * 
022     * <ul>
023     * <li> Jerrum, M.: A Very Simple Algorithm for Estimating the Number
024     *      of k-Colorings of a Low-Degree Graph.
025     *      In: Random Structures and Algorithms, 7 (1995) 2, pp. 157–165.
026     * </ul>
027     * 
028     * @version 1.0
029     * @author  Tobias Kley
030     */
031    public class JerrumChain extends HomogeneousMarkovChain {
032            
033            protected int numberOfColors = 0;
034            
035            /**
036             * Creates a new instance of the jerrum markov chain.
037             * 
038             * @param randomEngine Pseudo random number generator. 
039             * @param initialState State to initialise the markov chain at time t = 0.
040             */
041            public JerrumChain(RandomEngine randomEngine, ColoredGraph initialState, int numberOfColors) {
042                    super(randomEngine, initialState);
043                    this.numberOfColors = numberOfColors;
044            }
045    
046            /* (non-Javadoc)
047             * @see edu.wwu.tobikley.acgc.mc.MarkovChain#update(java.lang.Object)
048             */
049            @Override
050            public ColoredGraph update(Object fromState) {
051                    ColoredGraph g = (ColoredGraph)fromState;
052                    int vSelected = (int)Math.ceil((double)g.numVertices() * randomEngine.raw());
053                    int newColor = (int)Math.ceil((double)numberOfColors * randomEngine.raw());
054                    int oldColor = g.getVertexColor(vSelected); 
055                    g.setColor(g.getVertex(vSelected), newColor);
056                    if (!g.isProperVertexColoring()) {
057                            g.setColor(g.getVertex(vSelected), oldColor);
058                    }
059                    return g;
060            }
061    }