001 /**
002 *
003 */
004 package edu.wwu.tobikley.acgc.algorithms;
005
006 import java.math.BigInteger;
007
008 import edu.uci.ics.jung.graph.Graph;
009 import edu.uci.ics.jung.graph.Vertex;
010 import edu.wwu.tobikley.acgc.graphcoloring.ColoredGraph;
011 import edu.wwu.tobikley.acgc.mc.JerrumHeatBathChain;
012 import edu.wwu.tobikley.acgc.mc.HomogeneousMarkovChain;
013
014 /**
015 * Implements a variant of the fully polynomial randomized approximation scheme, specified
016 * by Marc Jerrum, as a <code>CountingAlgorithm</code>.
017 * To determine an approximation for the number of proper q-Colorings, a Markov Chain
018 * is run to randomly generate proper q-Colorings from a equidistribution.
019 * The Markov Chain is characterized by the following transition mechanism:
020 *
021 * <ol>
022 * <li>Pick a vertex v from V uniformly at random.
023 * <li>Pick a color c from the set of all colors that will reveil
024 * a proper q-Coloring if vertex v is colored with color c,
025 * uniformly at random.
026 * <li>Recolor vertex v with color c.
027 * </ol>
028 *
029 * For further information, refer to
030 *
031 * <ul>
032 * <li> Dyer, M.; Greenhill, C.: A More Rapidly Mixing Markov Chain
033 * for Graph Colorings. In: Random Structures and Algorithms,
034 * 13 (1998) 3-4, pp. 285–317.
035 * <li> Jerrum, M.: A Very Simple Algorithm for Estimating the Number
036 * of k-Colorings of a Low-Degree Graph.
037 * In: Random Structures and Algorithms, 7 (1995) 2, pp. 157–165.
038 * </ul>
039 *
040 * @version 1.0
041 * @author Tobias Kley
042 */
043 public class JerrumHeatBathCountingAlgorithm extends ApproximateCountingAlgorithm {
044
045 protected String progressTextSubgraph = null;
046 /**
047 *
048 */
049 public JerrumHeatBathCountingAlgorithm(Graph g, int numberOfColors, double epsilon) {
050 super(g, numberOfColors, epsilon);
051 if (q > 2.0 * Delta) {
052 N = (int)Math.ceil(((q - Delta) * k * Math.log(4.0 * k * l / epsilon)) / (q - 2.0 * Delta));
053 } else {
054 N = (int)Math.ceil(6.0 * Delta * Math.pow(k,3) * Math.log(4.0 * l / epsilon));
055 }
056 t = (int)Math.ceil(37.0 * l / (epsilon * epsilon));
057 T = 1;
058 initializeInitialState();
059 }
060
061 /**
062 *
063 */
064 public JerrumHeatBathCountingAlgorithm(Graph g, int numberOfColors, double epsilon, double alpha) {
065 super(g, numberOfColors, epsilon);
066 if (q > 2.0 * Delta) {
067 N = (int)Math.ceil(((q - Delta) * k * Math.log(4.0 * k * l / epsilon)) / (q - 2.0 * Delta));
068 } else {
069 N = (int)Math.ceil(6.0 * Delta * Math.pow(k,3) * Math.log(4.0 * l / epsilon));
070 }
071 t = (int)Math.ceil(37.0 * l / (epsilon * epsilon));
072 T = (int)Math.ceil(-1*Math.log(alpha))*12+1;
073 initializeInitialState();
074 }
075
076 /**
077 *
078 */
079 public JerrumHeatBathCountingAlgorithm(Graph g, int numberOfColors, double epsilon, int T) {
080 super(g, numberOfColors, epsilon);
081 if (q > 2.0 * Delta) {
082 N = (int)Math.ceil(((q - Delta) * k * Math.log(4.0 * k * l / epsilon)) / (q - 2.0 * Delta));
083 } else {
084 N = (int)Math.ceil(6.0 * Delta * Math.pow(k,3) * Math.log(4.0 * l / epsilon));
085 }
086 t = (int)Math.ceil(37.0 * l / (epsilon * epsilon));
087 this.T = T;
088 initializeInitialState();
089 }
090
091 protected BigInteger algorithmIteration() {
092 returnVal = BigInteger.valueOf(numberOfColors);
093 returnVal = returnVal.pow((int)k);
094
095 for (int i = 1; i <= l; i++) {
096 graphWorkingCopy.removeEdge(graphWorkingCopy.getEdge(i));
097 int properColorings = 0;
098 for (int j = 1; j <= t; j++) {
099 graphWorkingCopy.setVertexColoring(initialState);
100 HomogeneousMarkovChain gd = new JerrumHeatBathChain(mt, graphWorkingCopy, numberOfColors);
101 ColoredGraph sample = (ColoredGraph)gd.next(N);
102 int c1 = sample.getColor((Vertex)sample.getEdge(i).getEndpoints().getFirst());
103 int c2 = sample.getColor((Vertex)sample.getEdge(i).getEndpoints().getSecond());
104 if (c1 != c2) {
105 properColorings++;
106 }
107 double p = (iterationAlgorithm * l * t + (i-1)*t + (j-1))/(t*T*l);
108 setProgress((int)(100*p));
109 setProgressText("Calculating "+(int)(iterationAlgorithm+1)+". of "+T+" iteration(s) / "+ (int)i + ". of "+(int)l+" subgraph(s)"+" ("+100*(j-1)/t+"%).");
110 }
111 returnVal = returnVal.multiply(new BigInteger(String.valueOf(properColorings)));
112 }
113 returnVal = returnVal.divide(new BigInteger(String.valueOf(t)).pow((int)l));
114 return returnVal;
115 }
116
117 /**
118 * @param progress the progress to set
119 */
120 private synchronized void setProgress(int progress) {
121 this.progress = progress;
122 }
123
124 /**
125 * @param progressText the progressText to set
126 */
127 private synchronized void setProgressText(String progressText) {
128 this.progressText = progressText;
129 }
130
131 }