001: package uk.org.ponder.intutil;
002:
003: /** Class dfmaxstate embodies the state of the clique-finding algorithm, together
004: * with lower-level logic.
005: */
006:
007: class dfmaxstate {
008: private intVector vertexstack;
009: private intVector stacklevellimits;
010: private intVector activepointers;
011: private intVector currentclique;
012:
013: /** Initialize state with a complete level of all vertices at the bottom of the stack.
014: * @param size the number of vertices in the graph.
015: */
016: dfmaxstate(int size) {
017: vertexstack = new intVector(size * size / 4);
018: stacklevellimits = new intVector(size);
019: activepointers = new intVector(size);
020: currentclique = new intVector(size);
021:
022: for (int i = 0; i < size; ++i) {
023: vertexstack.addElement(i);
024: }
025: stacklevellimits.addElement(size);
026: activepointers.addElement(0);
027: currentclique.addElement(0);
028: }
029:
030: /** Dump the stack to System.out for debugging purposes
031: */
032:
033: void diagnose() {
034: for (int depth = 0; depth < stacklevellimits.size(); ++depth) {
035: System.out.print("Depth " + depth + ": ");
036: int vertexstart = depth == 0 ? 0 : stacklevellimits
037: .intAt(depth - 1);
038: int vertexend = stacklevellimits.intAt(depth);
039: int activevertex = activepointers.intAt(depth);
040: for (int vertex = vertexstart; vertex < vertexend; ++vertex) {
041: System.out.print((vertex == activevertex ? "*" : "")
042: + vertexstack.intAt(vertex) + " ");
043: }
044: System.out.println();
045: }
046: }
047:
048: /** Attempts to push a new frame on the stack, composed of vertices that
049: * form a clique together with currentclique. If none are found, state is
050: * left unchanged.
051: * @param adjacent The adjacency matrix specifying the graph. Must be square
052: * and symmetric.
053: * @return <code>true</code> if any new vertices were found.
054: */
055:
056: boolean push(boolean[][] adjacent) {
057: int topvertex = vertexstack.intAt(activepointers.peek());
058: int currentcliquesize = currentclique.size();
059: int oldstacktop = vertexstack.size();
060: int size = adjacent.length;
061: System.out.print("Push scanning from current clique: "
062: + currentclique + ": ");
063: // seek out all new vertices that can form a clique with the existing currentclique,
064: // and push them onto the stack one by one.
065: for (int scan = topvertex + 1; scan < size; ++scan) {
066: boolean formedclique = true; // this ensures that 1 vertex is always a clique.
067: for (int check = 0; check < currentcliquesize; ++check) {
068: if (!adjacent[scan][currentclique.intAt(check)]) {
069: formedclique = false;
070: break;
071: }
072: }
073: if (formedclique) {
074: System.out.print(scan + " ");
075: vertexstack.addElement(scan);
076: }
077: }
078: System.out.println();
079: // if we found no vertices, push failed.
080: if (vertexstack.size() == oldstacktop)
081: return false;
082: // otherwise, adjust the stack pointers to the new state and return.
083: stacklevellimits.addElement(vertexstack.size());
084: activepointers.addElement(oldstacktop);
085: currentclique.addElement(vertexstack.intAt(oldstacktop));
086: return true;
087: }
088:
089: /** Attempt to find a new clique by incrementing the active pointer into the top
090: * stack frame.
091: * @return <code>true</code> if a new clique was found in this way. Otherwise,
092: * return <code>false</code> if the top stack frame was exhausted.
093: */
094: boolean shove() {
095: if (activepointers.peek() < vertexstack.size() - 1) {
096: int topindex = activepointers.size() - 1;
097: activepointers.setIntAt(topindex, activepointers
098: .intAt(topindex) + 1);
099: currentclique.setIntAt(topindex, vertexstack
100: .intAt(activepointers.intAt(topindex)));
101: return true;
102: } else
103: return false;
104: }
105:
106: /** Removes a frame from the stack, reducing clique size by one.
107: * @return the new stack frame level.
108: */
109:
110: int pop() {
111: stacklevellimits.popElement();
112: activepointers.popElement();
113: currentclique.popElement();
114: vertexstack.setSize(stacklevellimits.isEmpty() ? 0
115: : stacklevellimits.peek());
116: return currentclique.size();
117: }
118:
119: /** Tests whether the current clique is a new best clique, and also determines whether
120: * the pruning criterion has been met.
121: * @param bestcliquesofar The best clique that has been found so far. If the newly presented
122: * clique is larger, this vector will be overwritten with the new clique.
123: * @return <code>true</code> if it is worthwhile continuing to expand the newly
124: * presented clique
125: */
126:
127: boolean check(intVector bestcliquesofar) {
128: if (currentclique.size() > bestcliquesofar.size()) {
129: System.out.println("New biggest clique found of size: "
130: + currentclique.size());
131: System.out.println(currentclique);
132: bestcliquesofar.assign(currentclique);
133: return true;
134: }
135: // the pruning condition is d + ( m - i ) <= bestcliquesize.
136: else
137: return currentclique.size()
138: + (stacklevellimits.peek() - activepointers.peek()) > bestcliquesofar
139: .size();
140: }
141:
142: }
143:
144: /** Class dfmax embodies the main logic loop of the clique-finding algorithm,
145: * implemented as a state machine with 4 states.
146: */
147:
148: class dfmax {
149: private static final int STATE_SHOVE = 0;
150: private static final int STATE_POP = 1;
151: private static final int STATE_CHECK = 2;
152: private static final int STATE_PUSH = 3;
153:
154: public static intVector bestClique(boolean[][] adjacent) {
155: if (adjacent.length != adjacent[0].length) {
156: System.out
157: .println("Supply a square adjacency matrix you numskull");
158: System.exit(1); // since I am no longer writing WaX I can use this fine exception
159: // handling strategy.
160: }
161:
162: dfmaxstate dfmaxstate = new dfmaxstate(adjacent.length);
163: intVector bestcliquesofar = new intVector(adjacent.length);
164: int state = STATE_CHECK;
165: outer: while (true) {
166: dfmaxstate.diagnose();
167: switch (state) {
168: case STATE_CHECK:
169: System.out.println("STATE_CHECK: ");
170: if (dfmaxstate.check(bestcliquesofar)) {
171: // check says we may continue trying to expand the clique.
172: state = STATE_PUSH;
173: } else {
174: System.out.println("PRUNE!!!");
175: // clique was pruned - pop off this stack frame.
176: // in order to revert to exhaustive search, convert this line to
177: // state = STATE_PUSH.
178: state = STATE_POP;
179: }
180: break;
181: case STATE_PUSH:
182: System.out.println("STATE_PUSH: ");
183: if (dfmaxstate.push(adjacent)) {
184: // we got a new stack frame, check it.
185: state = STATE_CHECK;
186: } else {
187: // we didn't, try to step along one in this one.
188: state = STATE_SHOVE;
189: }
190: break;
191: case STATE_POP:
192: System.out.println("STATE_POP: ");
193: if (dfmaxstate.pop() != 0) {
194: // popped off a stack frame, and still something left.
195: state = STATE_SHOVE;
196: } else
197: break outer;
198: case STATE_SHOVE:
199: System.out.println("STATE_SHOVE: ");
200: if (dfmaxstate.shove()) {
201: // we got a new clique, check it.
202: state = STATE_CHECK;
203: } else {
204: // no more cliques left in this frame, pop.
205: state = STATE_POP;
206: }
207: }
208: }
209: System.out.println("Clique found: " + bestcliquesofar);
210: System.out.println("===============================");
211: return bestcliquesofar;
212: }
213:
214: public static void main(String[] argv) {
215: boolean[][] simple02 = new boolean[][] { { true, false, true },
216: { false, true, false }, { true, false, true } };
217: dfmax.bestClique(simple02);
218: boolean[][] simple012 = new boolean[][] { { true, true, true },
219: { true, true, true }, { true, true, true } };
220: dfmax.bestClique(simple012);
221: boolean[][] simpledis = new boolean[][] {
222: { true, false, false }, { false, true, false },
223: { false, false, true } };
224: dfmax.bestClique(simpledis);
225:
226: boolean[][] example = new boolean[][] {
227: { true, true, false, false, true, true, false, false },
228: { true, true, false, false, false, true, true, false },
229: { false, false, true, true, false, true, true, false },
230: { false, false, true, true, true, true, false, true },
231: { true, false, false, true, true, true, true, true },
232: { true, true, true, true, true, true, true, true },
233: { false, true, true, false, true, true, true, true },
234: { false, false, false, true, true, true, true, true } };
235: dfmax.bestClique(example);
236: }
237: }
238:
239: /* Index mapping table:
240: * Example Ours Ours Example
241: * 1 0 0 1
242: * 5 1 4 2
243: * 8 2 3 3
244: * 3 3 5 4
245: * 2 4 1 5
246: * 4 5 6 6
247: * 6 6 7 7
248: * 7 7 2 8
249: *
250: * 1 ->245 = 0 ->451 2 ->17643 = 4 ->07653 3 ->2874 = 3 ->4275
251: * 4 ->3218765 = 5 ->3402761 5 ->416 = 1 ->506 6 ->54827 = 6 ->15247
252: * 7 ->6432 = 7 ->6534 8 ->346 = 2 ->356
253: *
254: * 01234567 Symmetric, checked.
255: * 0@@..@@..
256: * 1@@...@@.
257: * 2..@@.@@.
258: * 3..@@@@.@
259: * 4@..@@@@@
260: * 5@@@@@@@@
261: * 6.@@.@@@@
262: * 7...@@@@@
263:
264: * 3457 = 3247, correct.
265: */
266:
267: /** D a b 0111 dual graph
268: g g d 1011
269: A a B b C 1101
270: d 1111
271: E
272: */
273:
274: /* AB C DE matches AB Q DE, but AB and DE are not connected. */
|