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.JerrumChain;
012 import edu.wwu.tobikley.acgc.mc.HomogeneousMarkovChain;
013
014 /**
015 * Implements the fully polynomial randomized approximation scheme, specified
016 * by Marc Jerrum, as a <code>CountingAlgorithm</code>.
017 * To determine an approximation for 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 C uniformly at random.
024 * <li>Recolor vertex v with color c, if the resulting q-Coloring is proper.
025 * If it is not, undo the recoloring.
026 * </ol>
027 *
028 * For further information, refer to
029 *
030 * <ul>
031 * <li> Häggström, O.: Finite Markov Chains and Algorithmic Applications,
032 * Cambridge u. a.: Cambridge Univ. Press 2002, pp. 45-75.
033 * <li> Jerrum, M.: A Very Simple Algorithm for Estimating the Number
034 * of k-Colorings of a Low-Degree Graph.
035 * In: Random Structures and Algorithms, 7 (1995) 2, pp. 157–165.
036 * </ul>
037 *
038 * @version 1.0
039 * @author Tobias Kley
040 */
041 public class JerrumCountingAlgorithm extends ApproximateCountingAlgorithm {
042
043 protected String progressTextSubgraph = null;
044 /**
045 *
046 */
047 public JerrumCountingAlgorithm(Graph g, int numberOfColors, double epsilon) {
048 super(g, numberOfColors, epsilon);
049 N = (int)Math.ceil((q * k * Math.log(4.0 * k * l / epsilon)) / (q - 2.0 * Delta));
050 t = (int)Math.ceil(37.0 * l / (epsilon * epsilon));
051 T = 1;
052 initializeInitialState();
053 }
054
055 /**
056 *
057 */
058 public JerrumCountingAlgorithm(Graph g, int numberOfColors, double epsilon, double alpha) {
059 super(g, numberOfColors, epsilon);
060 N = (int)Math.ceil((q * k * Math.log(4.0 * k * l / epsilon)) / (q - 2.0 * Delta));
061 t = (int)Math.ceil(37.0 * l / (epsilon * epsilon));
062 T = (int)Math.ceil(-1*Math.log(alpha))*12+1;
063 initializeInitialState();
064 }
065
066 /**
067 *
068 */
069 public JerrumCountingAlgorithm(Graph g, int numberOfColors, double epsilon, int T) {
070 super(g, numberOfColors, epsilon);
071 N = (int)Math.ceil((q * k * Math.log(4.0 * k * l / epsilon)) / (q - 2.0 * Delta));
072 t = (int)Math.ceil(37.0 * l / (epsilon * epsilon));
073 this.T = T;
074 initializeInitialState();
075 }
076
077 protected BigInteger algorithmIteration() {
078 returnVal = BigInteger.valueOf(numberOfColors);
079 returnVal = returnVal.pow((int)k);
080
081 for (int i = 1; i <= l; i++) {
082 graphWorkingCopy.removeEdge(graphWorkingCopy.getEdge(i));
083 int properColorings = 0;
084 for (int j = 1; j <= t; j++) {
085 graphWorkingCopy.setVertexColoring(initialState);
086 HomogeneousMarkovChain gd = new JerrumChain(mt, graphWorkingCopy, numberOfColors);
087 ColoredGraph sample = (ColoredGraph)gd.next(N);
088 int c1 = sample.getColor((Vertex)sample.getEdge(i).getEndpoints().getFirst());
089 int c2 = sample.getColor((Vertex)sample.getEdge(i).getEndpoints().getSecond());
090 if (c1 != c2) {
091 properColorings++;
092 }
093 double p = (iterationAlgorithm * l * t + (i-1)*t + (j-1))/(t*T*l);
094 setProgress((int)(100*p));
095 setProgressText("Calculating "+(int)(iterationAlgorithm+1)+". of "+T+" iteration(s) / "+ (int)i + ". of "+(int)l+" subgraph(s)"+" ("+100*(j-1)/t+"%).");
096 }
097 returnVal = returnVal.multiply(new BigInteger(String.valueOf(properColorings)));
098 }
099 returnVal = returnVal.divide(new BigInteger(String.valueOf(t)).pow((int)l));
100 return returnVal;
101 }
102
103 /**
104 * @param progress the progress to set
105 */
106 private synchronized void setProgress(int progress) {
107 this.progress = progress;
108 }
109
110 /**
111 * @param progressText the progressText to set
112 */
113 private synchronized void setProgressText(String progressText) {
114 this.progressText = progressText;
115 }
116
117 }