1
2
3
4
5
6
7 package jwutil.graphs;
8
9 import java.util.AbstractList;
10 import java.util.Arrays;
11 import java.util.Collection;
12 import java.util.Comparator;
13 import java.util.HashMap;
14 import java.util.HashSet;
15 import java.util.Iterator;
16 import java.util.LinkedList;
17 import java.util.List;
18 import java.util.Map;
19 import java.util.Set;
20 import java.util.SortedSet;
21 import java.util.TreeSet;
22 import java.util.Map.Entry;
23 import java.io.IOException;
24 import java.math.BigInteger;
25 import jwutil.collections.IndexMap;
26 import jwutil.collections.Pair;
27 import jwutil.collections.UnmodifiableIterator;
28 import jwutil.strings.Strings;
29 import jwutil.util.Assert;
30
31 /***
32 * SCCPathNumbering
33 *
34 * @author jwhaley
35 */
36 public class SCCPathNumbering extends PathNumbering {
37 public static final boolean PRINT_BIGGEST = false;
38 public static
39 public static final boolean TRACE_PATH = false;
40 public static final boolean VERIFY_ASSERTIONS = false;
41
42 public SCCPathNumbering() {}
43
44 public SCCPathNumbering(Selector s) {
45 this.selector = s;
46 }
47
48 public SCCPathNumbering(Graph g) {
49 countPaths(g);
50 }
51
52 /*** Navigator for the graph. */
53 Navigator navigator;
54
55 /*** Cache of topologically-sorted SCC graph. */
56 SCCTopSortedGraph graph;
57
58 /*** Map from a node to its SCC. */
59 Map nodeToScc = new HashMap();
60
61 /*** Map from SCCs to Ranges. */
62 Map sccNumbering = new HashMap();
63
64 /*** Map from pairs of SCCs to the set of edges between them. */
65 Map sccEdges = new HashMap();
66
67 /*** Map from edges to ranges. */
68 Map edgeNumbering = new HashMap();
69
70 /*** Select important edges. */
71 Selector selector;
72
73 /*** Counts the number of paths in the given graph. */
74 Set unimportant = new HashSet();
75
76 /*** Counts the number of paths from the given root set, using the given graph navigator. */
77 public BigInteger countPaths(Collection roots, Navigator navigator, Map initialMap) {
78 BigInteger max_paths = BigInteger.ZERO;
79
80 int max_scc = 0;
81 int num_scc = 0;
82
83 if (TRACE_NUMBERING) System.out.print("Building and sorting SCCs...");
84 Set sccs = SCComponent.buildSCC(roots, navigator);
85 this.navigator = navigator;
86 graph = SCCTopSortedGraph.topSort(sccs);
87 if (TRACE_NUMBERING) System.out.print("done.");
88 if (TRACE_NUMBERING) System.out.print("Root SCCs: " + sccs);
89
90
91
92
93
94
95
96
97
98
99 SCComponent scc = graph.getFirst();
100 while (scc != null) {
101 initializeSccMap(scc);
102 max_scc = Math.max(scc.getId(), max_scc);
103 scc = scc.nextTopSort();
104 ++num_scc;
105 }
106 if (TRACE_NUMBERING) System.out.println("Max SCC="+max_scc+", Num SCC="+num_scc);
107
108 if (TRACE_NUMBERING) {
109 for(Iterator iter = this.nodeToScc.entrySet().iterator(); iter.hasNext();) {
110 Map.Entry e = (Entry) iter.next();
111 System.out.println(e.getKey() + "\t->\t" + e.getValue());
112 }
113 }
114
115
116 scc = graph.getFirst();
117 if (VERIFY_ASSERTIONS) Assert._assert(scc.prevLength() == 0);
118 while (scc != null) {
119
120 if (TRACE_NUMBERING)
121 System.out.println("Visiting SCC"+scc.getId()+(scc.isLoop()?" (loop)":" (non-loop)"));
122 BigInteger total = BigInteger.ZERO;
123 if (initialMap != null && !scc.isLoop())
124 total = toBigInt((Number) initialMap.get(scc.nodes()[0]));
125 recordEdgesFromSCC(scc);
126 for (Iterator i=Arrays.asList(scc.prev()).iterator(); i.hasNext(); ) {
127 SCComponent pred = (SCComponent) i.next();
128 Pair edge = new Pair(pred, scc);
129
130 int nedges = ((Collection) sccEdges.get(edge)).size();
131 Range r = (Range) sccNumbering.get(pred);
132
133 BigInteger t1 = toBigInt(r.high).add(BigInteger.ONE);
134
135 BigInteger newtotal = total.add(t1.multiply(BigInteger.valueOf(nedges)));
136 if (isImportant(pred, scc, newtotal)) {
137 total = newtotal;
138 } else {
139 unimportant.add(edge);
140 if (total.compareTo(t1) < 0) total = t1;
141 }
142 }
143 if (scc.prevLength() == 0)
144 total = total.add(BigInteger.ONE);
145 Range r = new Range(fromBigInt(total), fromBigInt(total.subtract(BigInteger.ONE)));
146 if (TRACE_NUMBERING ||
147 (PRINT_BIGGEST && total.compareTo(max_paths) == 1))
148 System.out.println("Paths to SCC"+scc.getId()+(scc.isLoop()?" (loop)":" (non-loop)")+"="+total);
149 sccNumbering.put(scc, r);
150 max_paths = max_paths.max(total);
151 scc = scc.nextTopSort();
152 }
153
154 scc = graph.getFirst();
155 while (scc != null) {
156 addEdges(scc);
157 scc = scc.nextTopSort();
158 }
159
160 scc = graph.getFirst();
161 while (scc != null) {
162 Range r = (Range) sccNumbering.get(scc);
163 if (TRACE_NUMBERING) System.out.println("Range for SCC"+scc.getId()+(scc.isLoop()?" (loop)":" (non-loop)")+"="+r);
164 if (r.low.longValue() != 0L) {
165 r.low = new Integer(0);
166 }
167 scc = scc.nextTopSort();
168 }
169
170 return max_paths;
171 }
172
173 /*** Initialize the mapping from nodes to their SCCs. */
174 protected void initializeSccMap(SCComponent scc1) {
175 Object[] nodes1 = scc1.nodes();
176 for (int i=0; i<nodes1.length; ++i) {
177 Object node = nodes1[i];
178 nodeToScc.put(node, scc1);
179 }
180 }
181
182 /*** Record the outgoing edges between nodes in the given SCC. */
183 private void recordEdgesFromSCC(SCComponent scc1) {
184 Object[] nodes = scc1.nodes();
185 for (int i=0; i<nodes.length; ++i) {
186 Object exit = nodes[i];
187 Collection targets = navigator.next(exit);
188 for (Iterator j=targets.iterator(); j.hasNext(); ) {
189 Object target = j.next();
190 SCComponent scc2 = (SCComponent) nodeToScc.get(target);
191 Pair edge = new Pair(scc1, scc2);
192 if (TRACE_NUMBERING) System.out.println("Edge SCC"+scc1.getId()+" to SCC"+scc2.getId()+": "+target);
193 Collection value = (Collection) sccEdges.get(edge);
194 if (value == null) sccEdges.put(edge, value = new LinkedList());
195 value.add(new Pair(exit, target));
196 }
197 }
198 }
199
200 private void addEdges(SCComponent scc1) {
201 if (TRACE_NUMBERING) System.out.println("Adding edges SCC"+scc1.getId());
202 Range r1 = (Range) sccNumbering.get(scc1);
203 if (scc1.prevLength() == 0) {
204 if (TRACE_NUMBERING) System.out.println("SCC"+scc1.getId()+" is in the root set");
205 if (VERIFY_ASSERTIONS) Assert._assert(r1.low.longValue() == 1L && r1.high.longValue() == 0L);
206 r1.low = new Integer(0);
207 }
208 if (scc1.isLoop()) {
209 Collection internalEdges = (Collection) sccEdges.get(new Pair(scc1, scc1));
210 for (Iterator i = internalEdges.iterator(); i.hasNext(); ) {
211 Pair edge = (Pair) i.next();
212 if (TRACE_NUMBERING) System.out.println("Range for "+edge+" = "+r1+" "+Strings.hex(r1));
213 edgeNumbering.put(edge, r1);
214 }
215 }
216 for (Iterator i=Arrays.asList(scc1.next()).iterator(); i.hasNext(); ) {
217 SCComponent scc2 = (SCComponent) i.next();
218 Pair e = new Pair(scc1, scc2);
219 boolean important = !unimportant.contains(e);
220 Range r2 = (Range) sccNumbering.get(scc2);
221 Collection calls = (Collection) sccEdges.get(e);
222 for (Iterator k=calls.iterator(); k.hasNext(); ) {
223 Pair edge = (Pair) k.next();
224 Range r3;
225 if (important) {
226
227 BigInteger newlow = toBigInt(r2.low).subtract(toBigInt(r1.high).add(BigInteger.ONE));
228 Assert._assert(newlow.signum() != -1);
229 r2.low = fromBigInt(newlow);
230 if (TRACE_NUMBERING) System.out.println("External edge! New range for SCC"+scc2.getId()+" = "+r2);
231 r3 = new Range(newlow, newlow.add(toBigInt(r1.high)));
232 } else {
233
234 BigInteger newlow = BigInteger.ZERO;
235 r3 = new Range(newlow, newlow.add(toBigInt(r1.high)));
236 }
237 if (TRACE_NUMBERING) System.out.println("Range for "+edge+" = "+r3+" "+Strings.hex(r3));
238 edgeNumbering.put(edge, r3);
239 }
240 }
241 }
242
243 public boolean isImportant(SCComponent scc1, SCComponent scc2, BigInteger num) {
244 if (selector == null) return true;
245 return selector.isImportant(scc1, scc2, num);
246 }
247
248 public Range getRange(Object o) {
249 SCComponent scc = (SCComponent) nodeToScc.get(o);
250 return getSCCRange(scc);
251 }
252
253 public Range getSCCRange(SCComponent scc) {
254 Range r = (Range) sccNumbering.get(scc);
255 return r;
256 }
257
258 public Number numberOfPathsTo(Object o) {
259 SCComponent scc = (SCComponent) nodeToScc.get(o);
260 return numberOfPathsToSCC(scc);
261 }
262
263 public Number numberOfPathsToSCC(SCComponent scc) {
264 Range r = (Range) sccNumbering.get(scc);
265 if (r == null) return null;
266 Number n = fromBigInt(toBigInt(r.high).add(BigInteger.ONE));
267 return n;
268 }
269
270 public Range getEdge(Object from, Object to) {
271 return getEdge(new Pair(from, to));
272 }
273
274 public Range getEdge(Pair edge) {
275 Range r = (Range) edgeNumbering.get(edge);
276 return r;
277 }
278
279 public Collection
280 return getSCCEdges(new Pair(from, to));
281 }
282
283 public Collection
284 Collection c = (Collection) sccEdges.get(edge);
285 return c;
286 }
287
288 public SCComponent getSCC(Object node) {
289 return (SCComponent) nodeToScc.get(node);
290 }
291
292 /*** Comparator used to put nodes in post order according to the SCC post order. */
293 static class PostOrderComparator implements Comparator {
294
295 private final Map nodeToScc;
296 private final IndexMap postOrderNumberingOfSccs;
297
298 /*** Construct a post-order comparator with the given node-to-scc mapping and
299 * topologically-sorted SCC graph.
300 */
301 public PostOrderComparator(Map nodeToScc, SCCTopSortedGraph g) {
302 this.nodeToScc = nodeToScc;
303 List list = g.list();
304 postOrderNumberingOfSccs = new IndexMap("PostOrderNumbering", list.size());
305 postOrderNumberingOfSccs.addAll(list);
306 }
307
308
309
310
311 public int compare(Object arg0, Object arg1) {
312 if (arg0.equals(arg1)) return 0;
313 SCComponent scc0 = (SCComponent) nodeToScc.get(arg0);
314 SCComponent scc1 = (SCComponent) nodeToScc.get(arg1);
315 int a = postOrderNumberingOfSccs.get(scc0);
316 int b = postOrderNumberingOfSccs.get(scc1);
317 if (a < b) return -1;
318 if (a > b) return 1;
319
320 a = Arrays.asList(scc0.nodes()).indexOf(arg0);
321 b = Arrays.asList(scc1.nodes()).indexOf(arg1);
322 if (a < b) return -1;
323 if (VERIFY_ASSERTIONS) Assert._assert(a != b);
324 return 1;
325 }
326 }
327
328 /*** Represents a path through the graph as an immutable linked structure. */
329 public static class Path extends AbstractList {
330
331 private final Object o;
332 private final int length;
333 private final Path next;
334
335 /*** Construct a path with exactly one element: the given one. */
336 public Path(Object o) {
337 this.o = o;
338 this.length = 1;
339 this.next = null;
340 }
341
342 /*** Construct a path by prepending an element to an existing path. */
343 public Path(Object o, Path next) {
344 this.o = o;
345 this.length = next.length+1;
346 this.next = next;
347 }
348
349 /*** Return the length of this path. */
350 public int size() {
351 return this.length;
352 }
353
354 /*** Return a certain element of this path. */
355 public Object get(int i) {
356 Path p = this;
357 for (;;) {
358 if (i == 0) return p.o;
359 p = p.next;
360 --i;
361 }
362 }
363
364
365
366
367 public Iterator iterator() {
368 return new UnmodifiableIterator() {
369 Path p = Path.this;
370
371 public boolean hasNext() {
372 return p != null;
373 }
374
375 public Object next() {
376 Object o = p.o;
377 p = p.next;
378 return o;
379 }
380 };
381 }
382
383 /*** Return a string representation of this path. */
384 public String toString() {
385 StringBuffer sb = new StringBuffer();
386 sb.append("\t<");
387 sb.append(o);
388 Path p = next;
389 while (p != null) {
390 sb.append(',');
391 sb.append(Strings.lineSep);
392 sb.append('\t');
393 sb.append(p.o);
394 p = p.next;
395 }
396 sb.append('>');
397 return sb.toString();
398 }
399 }
400
401 public Path getPath(Object callee, Number context) {
402 BigInteger c = toBigInt(context);
403 Range range = (Range) sccNumbering.get(nodeToScc.get(callee));
404 if (c.compareTo(toBigInt(range.high)) > 0) {
405 if (TRACE_PATH) System.out.println("Out of range (high)");
406 return null;
407 }
408
409 Path result = new Path(callee);
410
411
412 PostOrderComparator po_comparator = new PostOrderComparator(nodeToScc, graph);
413 SortedSet worklist = new TreeSet(po_comparator);
414 Map contexts = new HashMap();
415 Map results = new HashMap();
416
417 worklist.add(callee);
418 contexts.put(callee, c);
419 results.put(callee, result);
420
421 while (!worklist.isEmpty()) {
422 callee = worklist.last(); worklist.remove(callee);
423 c = (BigInteger) contexts.get(callee);
424 result = (Path) results.get(callee);
425 if (TRACE_PATH) System.out.println("Getting context "+c+" at "+callee);
426 for (Iterator i=navigator.prev(callee).iterator(); i.hasNext(); ) {
427 Object caller = i.next();
428 Range r = getEdge(caller, callee);
429 if (TRACE_PATH) System.out.println("Edge "+caller+" to "+callee+": "+r);
430 if (c.compareTo(toBigInt(r.high)) > 0) {
431 if (TRACE_PATH) System.out.println("Out of range (high)");
432 continue;
433 }
434 BigInteger c2 = c.subtract(toBigInt(r.low));
435 if (c2.signum() < 0) {
436 if (TRACE_PATH) System.out.println("Out of range (low)");
437 continue;
438 }
439 if (contexts.containsKey(caller)) {
440
441 if (TRACE_PATH) System.out.println("Recursive cycle");
442 } else {
443 if (TRACE_PATH) System.out.println("Matches! Adding to worklist.");
444 worklist.add(caller);
445 contexts.put(caller, c2);
446 results.put(caller, new Path(caller, result));
447 }
448 }
449 }
450 return result;
451 }
452
453 public SCCTopSortedGraph getSCCGraph() {
454 return graph;
455 }
456
457 }