1
2
3
4 package jwutil.graphs;
5
6 import java.util.Collection;
7 import java.util.Collections;
8 import java.util.HashMap;
9 import java.util.HashSet;
10 import java.util.Iterator;
11 import java.util.LinkedList;
12 import java.util.List;
13 import java.util.Map;
14 import java.util.Set;
15 import jwutil.collections.Pair;
16 import jwutil.util.Assert;
17
18 /***
19 * @author John Whaley <jwhaley@alum.mit.edu>
20 * @version $Id: Traversals.java 1934 2004-09-27 22:42:35Z joewhaley $
21 */
22 public abstract class Traversals {
23
24 public static void test(Navigator nav, Collection roots) {
25 HashSet visitedNodes = new HashSet();
26 for (Iterator i=roots.iterator(); i.hasNext(); ) {
27 Object o = i.next();
28 test_helper1(nav, o, visitedNodes);
29 }
30 visitedNodes.clear();
31 for (Iterator i=roots.iterator(); i.hasNext(); ) {
32 Object o = i.next();
33 test_helper2(nav, o, visitedNodes);
34 }
35 }
36 public static void test_helper1(Navigator nav, Object o, Set m) {
37 for (Iterator j=nav.next(o).iterator(); j.hasNext(); ) {
38 Object p = j.next();
39 if (!nav.prev(p).contains(o)) {
40 Assert.UNREACHABLE(o+"->"+p);
41 }
42 if (m.add(p))
43 test_helper1(nav, o, m);
44 }
45 }
46 public static void test_helper2(Navigator nav, Object o, Set m) {
47 for (Iterator j=nav.prev(o).iterator(); j.hasNext(); ) {
48 Object p = j.next();
49 if (!nav.next(p).contains(o)) {
50 Assert.UNREACHABLE(p+"<-"+o);
51 }
52 if (m.add(p))
53 test_helper2(nav, o, m);
54 }
55 }
56
57 public static Set getAllEdges(Navigator nav, Collection roots) {
58 HashSet visitedNodes = new HashSet();
59 HashSet visitedEdges = new HashSet();
60 for (Iterator i=roots.iterator(); i.hasNext(); ) {
61 Object o = i.next();
62 getAllEdges_helper(nav, o, visitedNodes, visitedEdges);
63 }
64 return visitedEdges;
65 }
66 private static void getAllEdges_helper(Navigator nav, Object o, HashSet visitedNodes, HashSet visitedEdges) {
67 if (visitedNodes.contains(o)) return;
68 visitedNodes.add(o);
69 for (Iterator j=nav.next(o).iterator(); j.hasNext(); ) {
70 Object p = j.next();
71 visitedEdges.add(new Pair(o, p));
72 getAllEdges_helper(nav, p, visitedNodes, visitedEdges);
73 }
74 }
75
76 public static Map buildPredecessorMap(Navigator nav, Collection roots) {
77 HashMap m = new HashMap();
78 for (Iterator i=roots.iterator(); i.hasNext(); ) {
79 Object o = i.next();
80 if (m.containsKey(o)) continue;
81 m.put(o, new HashSet());
82 buildPredecessorMap_helper(nav, o, m);
83 }
84 return m;
85 }
86 public static void buildPredecessorMap_helper(Navigator nav, Object o, Map m) {
87 for (Iterator j=nav.next(o).iterator(); j.hasNext(); ) {
88 Object p = j.next();
89 HashSet s = (HashSet) m.get(p);
90 boolean visited;
91 if (s == null) {
92 m.put(p, s = new HashSet());
93 visited = false;
94 } else {
95 visited = true;
96 }
97 s.add(o);
98 if (!visited)
99 buildPredecessorMap_helper(nav, p, m);
100 }
101 }
102
103 public static Map buildSuccessorMap(Navigator nav, Collection roots) {
104 HashMap m = new HashMap();
105 for (Iterator i=roots.iterator(); i.hasNext(); ) {
106 Object o = i.next();
107 if (m.containsKey(o)) continue;
108 HashSet s;
109 m.put(o, s = new HashSet());
110 buildSuccessorMap_helper(nav, o, s, m);
111 }
112 return m;
113 }
114 public static void buildSuccessorMap_helper(Navigator nav, Object o, HashSet s, Map m) {
115 for (Iterator j=nav.next(o).iterator(); j.hasNext(); ) {
116 Object p = j.next();
117 s.add(p);
118 HashSet s2 = (HashSet) m.get(p);
119 if (s2 != null) continue;
120 m.put(p, s2 = new HashSet());
121 buildSuccessorMap_helper(nav, p, s2, m);
122 }
123 }
124
125 public static List preOrder(Navigator nav, Object root) {
126 return traversal_helper(nav, Collections.singleton(root), PREORDER);
127 }
128 public static List preOrder(Navigator nav, Collection roots) {
129 return traversal_helper(nav, roots, PREORDER);
130 }
131
132 public static List reversePreOrder(Navigator nav, Object root) {
133 return traversal_helper(nav, Collections.singleton(root), REVERSE_PREORDER);
134 }
135 public static List reversePreOrder(Navigator nav, Collection roots) {
136 return traversal_helper(nav, roots, REVERSE_PREORDER);
137 }
138
139 public static List inOrder(Navigator nav, Object root) {
140 return traversal_helper(nav, Collections.singleton(root), INORDER);
141 }
142 public static List inOrder(Navigator nav, Collection roots) {
143 return traversal_helper(nav, roots, INORDER);
144 }
145
146 public static List reverseInOrder(Navigator nav, Object root) {
147 return traversal_helper(nav, Collections.singleton(root), REVERSE_INORDER);
148 }
149 public static List reverseInOrder(Navigator nav, Collection roots) {
150 return traversal_helper(nav, roots, REVERSE_INORDER);
151 }
152
153 public static List postOrder(Navigator nav, Object root) {
154 return traversal_helper(nav, Collections.singleton(root), POSTORDER);
155 }
156 public static List postOrder(Navigator nav, Collection roots) {
157 return traversal_helper(nav, roots, POSTORDER);
158 }
159
160 public static List reversePostOrder(Navigator nav, Object root) {
161 return traversal_helper(nav, Collections.singleton(root), REVERSE_POSTORDER);
162 }
163 public static List reversePostOrder(Navigator nav, Collection roots) {
164 return traversal_helper(nav, roots, REVERSE_POSTORDER);
165 }
166
167 private static final byte PREORDER = 1;
168 private static final byte REVERSE_PREORDER = 2;
169 private static final byte INORDER = 3;
170 private static final byte REVERSE_INORDER = 4;
171 private static final byte POSTORDER = 5;
172 private static final byte REVERSE_POSTORDER = 6;
173
174 private static final List traversal_helper(Navigator nav, Collection roots,
175 byte type) {
176 HashSet visited = new HashSet();
177 LinkedList result = new LinkedList();
178 for (Iterator i=roots.iterator(); i.hasNext(); ) {
179 Object root = i.next();
180 traversal_helper(nav, root, visited, result, type);
181 }
182 return result;
183 }
184
185 /*** Helper function to compute reverse post order. */
186 private static final void traversal_helper(
187 Navigator nav,
188 Object node,
189 HashSet visited,
190 LinkedList result,
191 byte type) {
192 if (visited.contains(node)) return; visited.add(node);
193 if (type == PREORDER) result.add(node);
194 else if (type == REVERSE_PREORDER) result.addFirst(node);
195 Collection bbs = nav.next(node);
196 Iterator bbi = bbs.iterator();
197 while (bbi.hasNext()) {
198 Object node2 = bbi.next();
199 traversal_helper(nav, node2, visited, result, type);
200 if (type == INORDER) {
201 result.add(node);
202 type = 0;
203 } else if (type == REVERSE_INORDER) {
204 result.addFirst(node);
205 type = 0;
206 }
207 }
208 if (type == POSTORDER) result.add(node);
209 else if (type == REVERSE_POSTORDER) result.addFirst(node);
210 }
211
212 }