001    /**
002     * 
003     */
004    package edu.wwu.tobikley.acgc.mc;
005    
006    import java.util.Iterator;
007    import java.util.Vector;
008    
009    import cern.jet.random.engine.RandomEngine;
010    import edu.uci.ics.jung.graph.Vertex;
011    import edu.wwu.tobikley.acgc.graphcoloring.ColoredGraph;
012    
013    /**
014     * The Markov Chain is a variant of the <code>JerrumChain</code>.
015     * It implements the following transition mechanism:
016     * 
017     * <ol>
018     * <li>Pick a vertex v from V uniformly at random.
019     * <li>Pick a color c from the set of all colors that will reveil
020     *     a proper q-Coloring if vertex v is colored with color c,
021     *     uniformly at random.
022     * <li>Recolor vertex v with color c.
023     * </ol>
024     *  
025     * For further information, refer to
026     * 
027     * <ul>
028     * <li> Dyer, M.; Greenhill, C.: A More Rapidly Mixing Markov Chain
029     *              for Graph Colorings. In: Random Structures and Algorithms,
030     *              13 (1998) 3-4, pp. 285–317.
031     * <li> Jerrum, M.: A Very Simple Algorithm for Estimating the Number
032     *      of k-Colorings of a Low-Degree Graph.
033     *      In: Random Structures and Algorithms, 7 (1995) 2, pp. 157–165.
034     * </ul>
035     * 
036     * @version 1.0
037     * @author  Tobias Kley
038     */
039    public class JerrumHeatBathChain extends HomogeneousMarkovChain {
040            
041            protected int numberOfColors = 0;
042            protected Vector<Integer> allColors = new Vector<Integer>();
043            
044            /**
045             * Creates a new instance of the jerrum heat bath markov chain.
046             * 
047             * @param randomEngine Pseudo random number generator. 
048             * @param initialState State to initialise the markov chain at time t = 0.
049             */
050            public JerrumHeatBathChain(RandomEngine randomEngine, ColoredGraph initialState, int numberOfColors) {
051                    super(randomEngine, initialState);
052                    this.numberOfColors = numberOfColors;
053                    for(int i = 1; i <= numberOfColors; i++) {
054                            allColors.add(i);
055                    }
056            }
057            
058            /* (non-Javadoc)
059             * @see edu.wwu.tobikley.acgc.mc.MarkovChain#update(java.lang.Object)
060             */
061            @SuppressWarnings("unchecked")
062            @Override
063            public ColoredGraph update(Object fromState) {
064                    ColoredGraph g = (ColoredGraph)fromState;
065                    int vSelected = (int)Math.ceil((double)g.numVertices() * randomEngine.raw());
066                    
067                    Vector<Integer> possibleColors = (Vector<Integer>)allColors.clone();
068    
069                    Iterator neighborIterator = g.getVertex(vSelected).getNeighbors().iterator();
070                    while (neighborIterator.hasNext()) {
071                            Vertex v = (Vertex)neighborIterator.next();
072                            Integer color = g.getColor(v);
073                            possibleColors.remove(color);
074                    }
075                    int newColorIndex = (int)Math.ceil((double)possibleColors.size() * randomEngine.raw());
076                    g.setColor(g.getVertex(vSelected), possibleColors.elementAt(newColorIndex-1));
077                    return g;
078            }
079    }