001 package edu.wwu.tobikley.acgc.algorithms;
002
003 import java.math.BigInteger;
004
005 import java.util.HashMap;
006 import java.util.Iterator;
007
008 import edu.uci.ics.jung.graph.Edge;
009 import edu.uci.ics.jung.graph.Graph;
010 import edu.uci.ics.jung.graph.Vertex;
011
012
013 /**
014 * Implements a Naive Counting Algorithm as a <code>CountingAlgorithm</code>.
015 * To determine the exact number of proper q-Colorings the following steps
016 * are performed:
017 *
018 * <ol>
019 * <li>Collect all vertices in an ordered fashion.
020 * <li>Then go throught the induced list of alle q-Colorings
021 * (there are q^k of them) in lexicographic order.
022 * <li>For each q-Coloring decide if it is proper and count it,
023 * if it is.
024 * </ol>
025 *
026 * For further information, refer to
027 *
028 * <ul>
029 * <li> Häggström, O.: Finite Markov Chains and Algorithmic Applications,
030 * Cambridge u. a.: Cambridge Univ. Press 2002, p. 65.
031 * </ul>
032 *
033 * @version 1.0
034 * @author Tobias Kley
035 */
036 public class NaiveCountingAlgorithm extends CountingAlgorithm {
037
038 /** The current coloring checked by the algorithm. */
039 private int[] coloring = null;
040
041 /** Specified position in <code>coloring</code> to watch for changes
042 * to report progress. The position is chosen, so that there are least
043 * possible but at last 100 changes in color. */
044 private int watchIndex = 0;
045
046 /** Color previously watched at the <code>watchIndex</code> of
047 * <code>coloring</code>.*/
048 private int watchedColor = 0;
049
050 /** Mapping the graphs vertices to Integer ids. */
051 protected HashMap<Vertex,Integer> verticeNames = null;
052
053 /**
054 * Creates a new instance of a naive counting algorithm.
055 * Invokes the constructor of <code>CountingAlgorithm</code> and
056 * initializes <code>verticeNames</code> and the <code>watchIndex</code>.
057 *
058 * @param g The graph to calculate the number of q-Colorings from.
059 * @param numberOfColors The number q as the question is: How many q-Colorings are there.
060 */
061 public NaiveCountingAlgorithm(Graph g, int numberOfColors) {
062 super(g, numberOfColors);
063
064 // Knoten durchnummerieren.
065 this.verticeNames = new HashMap<Vertex,Integer>(g.numVertices());
066 Integer i = 0;
067 Iterator verticeIterator = g.getVertices().iterator();
068 while (verticeIterator.hasNext()) {
069 verticeNames.put((Vertex)verticeIterator.next(), i++);
070 }
071
072 if(Math.ceil(Math.log(100)/Math.log(numberOfColors)) > 0) {
073 watchIndex = Math.max(0,g.numVertices() - (int)Math.ceil(Math.log(100)/Math.log(numberOfColors)));
074 }
075 }
076
077 /**
078 * Checks if a q-Coloring is proper regarding the
079 * <code>graphWorkingCopy</code>.
080 * To determine if it is a proper q-Colorings, each edge in the graph is
081 * examined. A coloring is proper if the endnodes of all edges are of
082 * different colors.
083 *
084 * @return <code>true</code> if <code>coloring</code> is a proper q-Coloring, and
085 * <code>false</code> if it is not.
086 */
087 private boolean isProperVertexColoring() {
088 boolean result = true;
089 Iterator edgeIterator = graphWorkingCopy.getEdges().iterator();
090 while (edgeIterator.hasNext()) {
091 Edge e = (Edge)edgeIterator.next();
092 int i = verticeNames.get(e.getEndpoints().getFirst()).intValue();
093 int j = verticeNames.get(e.getEndpoints().getSecond()).intValue();
094 if (coloring[i] == coloring[j]) {
095 result = false;
096 }
097 }
098 return result;
099 }
100
101 /**
102 * Iterates through all possible q-Colorings and calls <code>isValid</code>
103 * to determine if it is proper. Before the coloring is checked,
104 * <code>setProgress</code> is called, to propagate the progress of the
105 * calculation.
106 */
107 public void algorithm() {
108 //lokale Variablen initialisieren
109 returnVal = new BigInteger("0");
110 coloring = new int[graphWorkingCopy.numVertices()];
111 for (int i = 0; i < coloring.length; i++) {
112 coloring[i] = 1;
113 }
114 coloring[0]=0;
115 int i = 0;
116
117 do {
118 if (coloring[i] < numberOfColors) {
119
120 coloring[i]++;
121 while(i > 0){
122 i--;
123 coloring[i]=1;
124 }
125 setProgress();
126 boolean isValid = isProperVertexColoring();
127 if (isValid) {
128 returnVal = returnVal.add(BigInteger.ONE);
129 }
130 } else {
131 i++;
132 }
133
134 } while (i < coloring.length);
135 detailedResults.add(new CountingResult("Exact",returnVal,System.currentTimeMillis()-startTime));
136 }
137
138 /**
139 * If necessary <code>progress</code> and <code>progressText</code> are updated.
140 * The <code>progressText</code> is set to the text: "Calculation is xx% finished.".
141 */
142 private synchronized void setProgress() {
143 if(coloring[watchIndex] != watchedColor) {
144 watchedColor = coloring[watchIndex];
145 progress = 0;
146 for (int i = watchIndex; i < coloring.length; i++) {
147 progress += (coloring[i]-1)*(Math.pow(numberOfColors,(i-watchIndex)));
148 }
149 progress = (int) (100*progress/(Math.pow(numberOfColors,coloring.length-watchIndex)));
150 setProgressText("Calculation is "+progress+"% finished.");
151 }
152 }
153
154 /**
155 * @param progressText
156 */
157 private synchronized void setProgressText(String progressText){
158 this.progressText = progressText;
159 }
160
161
162 }