001 package edu.wwu.tobikley.acgc.algorithms;
002
003 import java.math.BigInteger;
004 import java.util.Collection;
005 import java.util.Collections;
006 import java.util.List;
007 import java.util.Vector;
008 import java.util.concurrent.Callable;
009
010 import edu.uci.ics.jung.graph.Graph;
011 import edu.wwu.tobikley.acgc.graphcoloring.ColoredGraph;
012
013 /**
014 * Basic functionality of an algorithm to count the q-Colorings of a
015 * graph. The following aspects are addresed:
016 *
017 * <ul>
018 * <li>preparing a copy of the graph,
019 * <li>returning intermediate results,
020 * <li>tracking the runtime,
021 * <li>storing / providing the progress of the calculations, and
022 * <li>storing / providing the result itself.
023 * </ul>
024 *
025 * Concrete counting algorithms, that inherit the functionality provided
026 * have to implement the abstract method <code>algorithm</code>.
027 *
028 * @version 1.0
029 * @author Tobias Kley
030 */
031 public abstract class CountingAlgorithm implements Callable<BigInteger>{
032
033 /** A backup copy of the input graph. */
034 protected Graph graphBackup = null;
035
036 /** A copy of the graph the algorithm will work with.*/
037 protected ColoredGraph graphWorkingCopy = null;
038
039 /** The integer q, as the question is: How many q-Colorings are there. */
040 protected int numberOfColors;
041
042 /** The number of q-Colorings of the graph. */
043 protected BigInteger returnVal = null;
044
045 /** Time the algorithm was started in ms. */
046 protected long startTime = 0;
047
048 /** Time the algorithm ended in ms. */
049 protected long endTime = 0;
050
051 /** Proportion of the task finished so far (per hundred). */
052 protected int progress = 0;
053
054 /** Description of the current task being performed. */
055 protected String progressText = null;
056
057 /** Description, Result and Runtime for each iteration done of the algorithm. */
058 protected Vector<CountingResult> detailedResults = null;
059
060 /**
061 * Creates a new instance of a counting algorithm.
062 * The backup copy, the working copy of the graph, as well as the
063 * other fields are initialised.
064 *
065 * @param g The graph to calculate the number of q-Colorings from.
066 * @param numberOfColors The number q as the question is: How many q-Colorings are there.
067 */
068 public CountingAlgorithm(Graph g, int numberOfColors) {
069 this.numberOfColors = numberOfColors;
070 detailedResults = new Vector<CountingResult>();
071
072 this.graphBackup = (Graph)g.copy();
073 this.graphWorkingCopy = new ColoredGraph(graphBackup);
074 }
075
076
077 /**
078 * Returns the time the time the algorithm ran for calculation.
079 *
080 * @return the runtime in milliseconds.
081 */
082 public long getRunTime() {
083 return endTime - startTime;
084 }
085
086 /**
087 * Specifies the counting algorithm. Any implementation may use the
088 * <code>graphWorkingCopy</code>. A copy is provided, because some
089 * algorithms might e.g. require adding or removing elements.
090 *
091 * The algorithm is required to store its result to
092 * <code>returnVal</code>, hence there is no result to this method.
093 */
094 protected abstract void algorithm();
095
096 /**
097 * Called from outside when the algorithm is executed.
098 * Before starting and after finishing the algorithm the time
099 * is recorded, so the run time can be calculated afterwards.
100 * The runtime and overall result (in case there is more than one,
101 * the median of the results) is added to the
102 * <code>detailedResults</code>.
103 *
104 * @return the result of the algorithm
105 */
106 @SuppressWarnings("unchecked")
107 public BigInteger call() {
108 startTime = System.currentTimeMillis();
109 algorithm();
110 endTime = System.currentTimeMillis();
111 BigInteger med = null;
112 if (detailedResults.size() > 1) {
113 List<CountingResult> sortedRes = (List<CountingResult>)detailedResults.clone();
114 Collections.sort(sortedRes);
115 med = ((CountingResult)sortedRes.toArray()[(sortedRes.toArray().length-1)/2]).getResult();
116 } else {
117 med = returnVal;
118 }
119 detailedResults.add(new CountingResult("Overall",med,endTime-startTime));
120 return med;
121 }
122
123 /**
124 * Sets the number q as the question is: How many q-Colorings are there.
125 *
126 * @param numberOfColors the numberOfColors to set
127 */
128 public synchronized void setNumberOfColors(int numberOfColors) {
129 this.numberOfColors = numberOfColors;
130 }
131
132 /**
133 * Returns the number q as the question is: How many q-Colorings are there.
134 *
135 * @return the numberOfColors
136 */
137 public synchronized int getNumberOfColors() {
138 return numberOfColors;
139 }
140
141 /**
142 * Returns the working copy of the graph.
143 *
144 * @return working copy of the graph.
145 */
146 public synchronized Graph getGraph() {
147 return (Graph)graphWorkingCopy;
148 }
149
150
151
152 /**
153 * Returns the proportion of the task finished so far (per hundred).
154 *
155 * @return the progress
156 */
157 public synchronized int getProgress() {
158 return progress;
159 }
160
161
162 /**
163 * Description of the current task being performed.
164 *
165 * @return the progressText
166 */
167 public synchronized String getProgressText() {
168 return progressText;
169 }
170
171 /**
172 * Description, Result and Runtime for each iteration done of the algorithm.
173 *
174 * @return the detailedResults
175 */
176 public Collection<CountingResult> getDetailedResults() {
177 return detailedResults;
178 }
179 }