View Javadoc

1   // GlobalPathNumbering.java, created Aug 4, 2004 8:56:01 PM 2004 by jwhaley
2   // Copyright (C) 2004 John Whaley <jwhaley@alum.mit.edu>
3   // Licensed under the terms of the GNU LGPL; see COPYING for details.
4   package jwutil.graphs;
5   
6   import java.util.Collection;
7   import java.util.HashMap;
8   import java.util.Iterator;
9   import java.util.Map;
10  import java.math.BigInteger;
11  import jwutil.collections.Pair;
12  import jwutil.util.Assert;
13  
14  /***
15   * GlobalPathNumbering
16   * 
17   * @author jwhaley
18   * @version $Id: GlobalPathNumbering.java 1934 2004-09-27 22:42:35Z joewhaley $
19   */
20  public class GlobalPathNumbering extends PathNumbering {
21      
22      public GlobalPathNumbering() {
23      }
24      
25      public GlobalPathNumbering(Selector s) {
26          this.selector = s;
27      }
28      
29      Selector selector;
30      
31      /*** Navigator for the graph. */
32      Navigator navigator;
33      
34      /*** Map from nodes to numbers. */
35      Map nodeNumbering = new HashMap();
36      
37      /*** Map from edges to ranges. */
38      Map edgeNumbering = new HashMap();
39      
40      /* (non-Javadoc)
41       * @see jwutil.graphs.PathNumbering#countPaths(java.util.Collection, jwutil.graphs.Navigator, java.util.Map)
42       */
43      public BigInteger countPaths(Collection roots, Navigator navigator, Map initialMap) {
44          for (Iterator i = roots.iterator(); i.hasNext(); ) {
45              Object o = i.next();
46              BigInteger total = BigInteger.ONE;
47              if (initialMap != null)
48                  total = toBigInt((Number) initialMap.get(o));
49              nodeNumbering.put(o, total);
50              Assert._assert(!total.equals(BigInteger.ZERO), o.toString());
51          }
52          BigInteger max = BigInteger.ZERO;
53          Iterator rpo = Traversals.reversePostOrder(navigator, roots).iterator();
54          while (rpo.hasNext()) {
55              Object o = rpo.next();
56              BigInteger pathsToNode = (BigInteger) nodeNumbering.get(o);
57              if (pathsToNode == null) {
58                  // This node is not a root.
59                  pathsToNode = BigInteger.ONE;
60              }
61              Collection prev = navigator.prev(o);
62              for (Iterator i = prev.iterator(); i.hasNext(); ) {
63                  Object p = i.next();
64                  BigInteger pathsToPred = (BigInteger) nodeNumbering.get(p);
65                  if (pathsToPred == null) {
66                      // We haven't visited this predecessor yet.
67                      // Because this is topological, it must be a loop edge.
68                      //System.out.println("Loop edge: "+p+" -> "+o+" current target num="+val);
69                      pathsToPred = BigInteger.ONE;
70                  }
71                  BigInteger newPathsToNode = pathsToNode.add(pathsToPred);
72                  Object edge = new Pair(p, o);
73                  if (!isImportant(p, o, newPathsToNode)) {
74                      // Unimportant edge.
75                      Range range = new Range(pathsToNode.subtract(BigInteger.ONE),
76                                              pathsToNode.subtract(BigInteger.ONE));
77                      edgeNumbering.put(edge, range);
78                      //System.out.println("Putting unimportant Edge ("+edge+") = "+range);
79                  } else {
80                      Range range = new Range(pathsToNode.subtract(BigInteger.ONE),
81                                              newPathsToNode.subtract(BigInteger.valueOf(2)));
82                      edgeNumbering.put(edge, range);
83                      //System.out.println("Putting important Edge ("+edge+") = "+range);
84                      pathsToNode = newPathsToNode;
85                  }
86              }
87              //Assert._assert(!val.equals(BigInteger.ZERO), o.toString());
88              if (!prev.isEmpty()) pathsToNode = pathsToNode.subtract(BigInteger.ONE);
89              nodeNumbering.put(o, pathsToNode);
90              if (pathsToNode.compareTo(max) > 0) max = pathsToNode;
91          }
92          return max;
93      }
94  
95      public boolean isImportant(Object a, Object b, BigInteger num) {
96          if (selector == null) return true;
97          return selector.isImportant(a, b, num);
98      }
99      
100     /* (non-Javadoc)
101      * @see jwutil.graphs.PathNumbering#getRange(java.lang.Object)
102      */
103     public Range getRange(Object o) {
104         BigInteger b = (BigInteger) nodeNumbering.get(o);
105         if (b == null) return null;
106         return new Range(BigInteger.ZERO, b.subtract(BigInteger.ONE));
107     }
108 
109     /* (non-Javadoc)
110      * @see jwutil.graphs.PathNumbering#getEdge(java.lang.Object, java.lang.Object)
111      */
112     public Range getEdge(Object from, Object to) {
113         Object key = new Pair(from, to);
114         Range r = (Range) edgeNumbering.get(key);
115         //System.out.println("Edge ("+key+") = "+r);
116         return r;
117     }
118     
119 }