1 salcianu 1.1 // DiGraph.java, created Tue May 6 10:53:15 2003 by salcianu
2 salcianu 1.1 // Copyright (C) 2003 Alexandru Salcianu <salcianu@MIT.EDU>
3 salcianu 1.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 salcianu 1.1 package harpoon.Util.Graphs;
5 salcianu 1.1
6 salcianu 1.3 import java.util.Collections;
7 salcianu 1.4 import java.util.Collection;
8 salcianu 1.1 import java.util.Set;
9 salcianu 1.3 import java.util.HashSet;
10 cananian 1.7 import java.util.HashMap;
11 salcianu 1.3 import java.util.List;
12 salcianu 1.3 import java.util.LinkedList;
13 cananian 1.7 import java.util.Map;
14 salcianu 1.3 import java.util.Iterator;
15 salcianu 1.3
16 salcianu 1.3 import harpoon.Util.DataStructs.Relation;
17 salcianu 1.3 import harpoon.Util.DataStructs.RelationImpl;
18 salcianu 1.1
19 salcianu 1.1 /**
20 salcianu 1.3 * <code>DiGraph</code> models a directed graph. A directed graph is
21 salcianu 1.10 * defined by a set of <i>root</i> vertices and a <i>navigator</i>.
22 salcianu 1.10 * The navigator is an iterator over the graph: given a vertex
23 salcianu 1.10 * <code>v</code>, it gives <code>v</code>'s direct successors (i.e.,
24 salcianu 1.10 * vertices pointed to by arcs that start in <code>v</code>), and
25 salcianu 1.10 * (optionally), the <code>v</code>'s direct predecessors. The
26 salcianu 1.10 * digraph contains all (transitive and reflexive) successors of the
27 salcianu 1.10 * root vertices.
28 salcianu 1.3 *
29 salcianu 1.3 * <p>There are two kinds of navigators:
30 salcianu 1.10 * <code>ForwardNavigator</code>s (gives only successors) and
31 salcianu 1.3 * bi-directional <code>Navigator</code> (both successors and
32 salcianu 1.3 * predecessors). For a given graph you should define at least one of
33 salcianu 1.3 * them, i.e., you should override at least one of the methods
34 salcianu 1.10 * <code>getNavigator</code> and <code>getForwardNavigator</code> from
35 salcianu 1.10 * <code>DiGraph</code>. The standard implementation of these methods
36 salcianu 1.10 * in this class is able to construct the other navigator: a
37 salcianu 1.10 * bi-directional navigator is trivially a forward one too. Also, if
38 salcianu 1.10 * we know the root vertices and the successor relation, we can
39 salcianu 1.10 * produce the predecessor relation (although it's quite costly, and
40 salcianu 1.10 * may not terminate for digraphs with an infinite set of vertices).
41 salcianu 1.10 *
42 salcianu 1.10 * If you decide to implement both (eg, for efficiency) you should
43 salcianu 1.10 * make sure the two navigators are consistent. To see what this
44 salcianu 1.10 * means, let <code>fnav</code> and <code>nav</code> be the forward,
45 salcianu 1.10 * and the full navigator associated with a digraph. For any vertex
46 salcianu 1.10 * <code>v</code>, <code>fnav.next(v)</code> should returns the same
47 salcianu 1.10 * nodes as <code>nav.next(v)</code>. In addition, <code>nav</code>
48 salcianu 1.10 * itself should be consistent, i.e., for any vertices
49 salcianu 1.10 * <code>v1</code>, <code>v2</code> from the digraph, if
50 salcianu 1.10 * <code>v1</code> appears in <code>nav.next(v2)</code>, then
51 salcianu 1.10 * <code>v2</code> should appear in <code>nav.prev(v1)</code>.
52 salcianu 1.3 *
53 salcianu 1.3 * @see ForwardNavigator
54 salcianu 1.3 * @see Navigator
55 salcianu 1.3 *
56 salcianu 1.3 * Created: Sun May 4 20:56:57 2003
57 salcianu 1.1 *
58 salcianu 1.1 * @author Alexandru Salcianu <salcianu@mit.edu>
59 salcianu 1.10 * @version $Id: DiGraph.java,v 1.10 2004/03/05 22:18:36 salcianu Exp $ */
60 cananian 1.7 public abstract class DiGraph<Vertex extends Object> {
61 salcianu 1.1
62 salcianu 1.1 /** Returns a set that includes (but is not necessarily limited
63 salcianu 1.1 to) the roots of <code>this</code> directed graph. By
64 salcianu 1.3 "roots of a digraph" we mean any set of vertices such
65 salcianu 1.1 that one can explore the entire graph by (transitively)
66 salcianu 1.3 navigating on their outgoing arcs (using the
67 salcianu 1.1 <code>next</code> method of the navigator). It is OK to
68 salcianu 1.3 return ALL the vertices from the digraph. */
69 salcianu 1.8 public abstract Set<Vertex> getRoots();
70 salcianu 1.3
71 salcianu 1.10 /** Returns the (bi-directional) navigator for <code>this</code>
72 salcianu 1.10 digraph. The default implementation gets the forward
73 salcianu 1.10 navigator by calling <code>getForwardNavigator</code>,
74 salcianu 1.10 explores the entire digraph and constructs the predecessor
75 salcianu 1.10 relation. Clearly, this is quite costly, and does not
76 salcianu 1.10 terminate for infinite digraphs.
77 salcianu 1.3
78 salcianu 1.3 <p><strong>Note:</strong> You MUST overwrite at least one of
79 salcianu 1.8 <code>getNavigator</code> and
80 salcianu 1.8 <code>getForwardNavigator</code>. */
81 salcianu 1.8 public Navigator<Vertex> getNavigator() {
82 salcianu 1.3 final Relation/*<Vertex,Vertex>*/ prevRel =
83 salcianu 1.3 new RelationImpl/*<Vertex,Vertex>*/();
84 salcianu 1.8 final ForwardNavigator<Vertex> fnav = getForwardNavigator();
85 salcianu 1.3
86 cananian 1.7 for(Vertex vertex : allVertices())
87 cananian 1.7 for (Vertex next : fnav.next(vertex))
88 salcianu 1.3 prevRel.add(next, vertex);
89 salcianu 1.1
90 cananian 1.7 return new Navigator<Vertex>() {
91 cananian 1.7 public Vertex[] next(Vertex vertex) { return fnav.next(vertex); }
92 cananian 1.7 public Vertex[] prev(Vertex vertex) {
93 salcianu 1.3 Set prev = prevRel.getValues(vertex);
94 cananian 1.7 return (Vertex[]) prev.toArray(new Object[prev.size()]);
95 salcianu 1.3 }
96 salcianu 1.3 };
97 salcianu 1.3 }
98 salcianu 1.3
99 salcianu 1.10 /** Returns the forward navigator for <code>this</code> digraph.
100 salcianu 1.10 The default implementations returns the bi-directional
101 salcianu 1.10 navigator (obtained by calling <code>getNavigator</code>).
102 salcianu 1.3
103 salcianu 1.3 <p><strong>Note:</strong> You MUST overwrite at least one of
104 salcianu 1.8 <code>getNavigator</code> and
105 salcianu 1.8 <code>getForwardNavigator</code>. */
106 salcianu 1.8 public ForwardNavigator<Vertex> getForwardNavigator() {
107 salcianu 1.8 return getNavigator();
108 salcianu 1.8 }
109 salcianu 1.8
110 salcianu 1.8
111 salcianu 1.8 /** Constructs a <code>DiGraph</code> object.
112 salcianu 1.8 @param roots set of root vertices
113 salcianu 1.10 @param navigator bi-directional digraph navigator
114 salcianu 1.8 */
115 salcianu 1.8 public static <Vertex> DiGraph<Vertex> diGraph
116 salcianu 1.8 (final Set<Vertex> roots, final Navigator<Vertex> navigator) {
117 salcianu 1.8 return new DiGraph<Vertex>() {
118 salcianu 1.8 public Set<Vertex> getRoots() { return roots; }
119 salcianu 1.8 public Navigator<Vertex> getNavigator() { return navigator; }
120 salcianu 1.8 };
121 salcianu 1.3 }
122 salcianu 1.3
123 salcianu 1.3
124 salcianu 1.10 /** Constructs a <code>DiGraph</code> object.
125 salcianu 1.10 @param roots set of root vertices
126 salcianu 1.10 @param navigator forward digraph navigator
127 salcianu 1.10 */
128 salcianu 1.10 public static <Vertex> DiGraph<Vertex> diGraph
129 salcianu 1.10 (final Set<Vertex> roots, final ForwardNavigator<Vertex> fnavigator) {
130 salcianu 1.10 return new DiGraph<Vertex>() {
131 salcianu 1.10 public Set<Vertex> getRoots() { return roots; }
132 salcianu 1.10 public ForwardNavigator<Vertex> getForwardNavigator() {
133 salcianu 1.10 return fnavigator;
134 salcianu 1.10 }
135 salcianu 1.10 };
136 salcianu 1.10 }
137 salcianu 1.10
138 salcianu 1.10 /** @return Set of all vertices from <code>this</code> digraph. */
139 salcianu 1.10 public Set<Vertex> vertices() {
140 salcianu 1.10 return transitiveSucc(getRoots());
141 salcianu 1.10 }
142 salcianu 1.10
143 salcianu 1.3 /** @return Set of all transitive and reflexive successors of
144 salcianu 1.3 <code>vertex</code>. */
145 cananian 1.7 public Set<Vertex> transitiveSucc(Vertex vertex) {
146 salcianu 1.5 return transitiveSucc(Collections.singleton(vertex));
147 salcianu 1.3 }
148 salcianu 1.3
149 salcianu 1.10 /** @return Set of all transitive and reflexive successors of
150 salcianu 1.4 vertices from <code>roots</code>. */
151 cananian 1.7 public Set<Vertex> transitiveSucc(Collection<Vertex> roots) {
152 salcianu 1.8 return reachableVertices(roots, getForwardNavigator());
153 salcianu 1.3 }
154 salcianu 1.3
155 salcianu 1.3 /** @return Set of all transitive and reflexive
156 salcianu 1.3 predecessors of <code>vertex</code> */
157 cananian 1.7 public Set<Vertex> transitivePred(Vertex vertex) {
158 salcianu 1.5 return transitivePred(Collections.singleton(vertex));
159 salcianu 1.3 }
160 salcianu 1.3
161 salcianu 1.3 /** @return Set of all transitive and reflexive predecessors of
162 salcianu 1.4 the vertices from <code>roots</code>. */
163 cananian 1.7 public Set<Vertex> transitivePred(Collection<Vertex> roots) {
164 salcianu 1.8 return reachableVertices
165 salcianu 1.8 (roots,
166 salcianu 1.8 new ReverseNavigator<Vertex>(getNavigator()));
167 salcianu 1.3 }
168 salcianu 1.3
169 salcianu 1.3
170 salcianu 1.10 /** @return Set of all transitive and reflexive successors of the
171 salcianu 1.10 vertices from <code>roots</code>, where the successors of a
172 salcianu 1.10 vertex are given by method <code>next</code> of
173 salcianu 1.10 <code>fnavigator</code>. */
174 cananian 1.7 public static <Vertex> Set<Vertex> reachableVertices
175 cananian 1.7 (Collection<Vertex> roots,
176 salcianu 1.10 ForwardNavigator<Vertex> fnavigator) {
177 salcianu 1.10 return
178 salcianu 1.10 (new ClosureDFS()).doIt(roots, fnavigator, null, null);
179 salcianu 1.3 }
180 salcianu 1.1
181 salcianu 1.6
182 salcianu 1.6 /** @return one shortest path of vertices from <code>source</code>
183 salcianu 1.6 to <code>dest</code>, along edges indicated by
184 salcianu 1.6 <code>navigator</code>; returns <code>null</code> if no such
185 salcianu 1.6 path exists. */
186 salcianu 1.10 public static <Vertex> List<Vertex> findPath
187 salcianu 1.10 (Vertex source, Vertex dest, ForwardNavigator<Vertex> navigator) {
188 salcianu 1.10
189 cananian 1.7 Map<Vertex,Vertex> pred = new HashMap<Vertex,Vertex>();
190 cananian 1.7 Set<Vertex> reachables = new HashSet<Vertex>();
191 cananian 1.7 LinkedList<Vertex> w = new LinkedList<Vertex>();
192 salcianu 1.6
193 salcianu 1.6 reachables.add(source);
194 salcianu 1.6 w.addLast(source);
195 salcianu 1.6
196 salcianu 1.6 boolean found = false;
197 salcianu 1.6 while(!w.isEmpty() && !found) {
198 cananian 1.7 Vertex vertex = w.removeFirst();
199 cananian 1.7 for (Vertex succ : navigator.next(vertex) ) {
200 salcianu 1.6 if(!pred.containsKey(succ)) {
201 salcianu 1.6 pred.put(succ, vertex);
202 salcianu 1.6 if(succ.equals(dest)) {
203 salcianu 1.6 found = true;
204 salcianu 1.6 break;
205 salcianu 1.6 }
206 salcianu 1.6 }
207 salcianu 1.6 if(reachables.add(succ))
208 salcianu 1.6 w.addLast(succ);
209 salcianu 1.6 }
210 salcianu 1.6 }
211 salcianu 1.6
212 salcianu 1.6 if(!found) return null;
213 salcianu 1.6
214 cananian 1.7 LinkedList<Vertex> path = new LinkedList<Vertex>();
215 salcianu 1.6 path.addFirst(dest);
216 cananian 1.7 Vertex curr = dest;
217 salcianu 1.6 while(true) {
218 cananian 1.7 Vertex vertex = pred.get(curr);
219 salcianu 1.6 path.addFirst(vertex);
220 salcianu 1.6 curr = vertex;
221 salcianu 1.6 if(source.equals(curr))
222 salcianu 1.6 break;
223 salcianu 1.6 }
224 salcianu 1.6 return path;
225 salcianu 1.6 }
226 salcianu 1.6
227 salcianu 1.6 /** @return one shortest path of vertices from <code>source</code>
228 salcianu 1.6 to <code>dest</code>, along edges from <code>this</code>
229 salcianu 1.6 graph; returns <code>null</code> if no such path exists. */
230 cananian 1.7 public List<Vertex> findPath(Vertex source, Vertex dest) {
231 salcianu 1.8 return findPath(source, dest, getForwardNavigator());
232 salcianu 1.6 }
233 salcianu 1.1
234 salcianu 1.4 /** Interface for passing a method as parameter to a
235 salcianu 1.4 * <code>forAllReachableVertices</code> object.
236 salcianu 1.4 * @see forAllReachableVertices */
237 salcianu 1.8 public static interface VertexVisitor<Vertex> {
238 cananian 1.7 public void visit(Vertex obj);
239 salcianu 1.4 }
240 salcianu 1.4
241 salcianu 1.8 /** DFS traversal of <code>this</code> digraph.
242 salcianu 1.8
243 salcianu 1.8 @param onEntry action executed when a node is first time
244 salcianu 1.8 visited by the DFS traversal
245 salcianu 1.8
246 salcianu 1.8 @param onExit action executed after the DFS traversal of a
247 salcianu 1.8 node finished */
248 salcianu 1.8 public void dfs(VertexVisitor<Vertex> onEntry,
249 salcianu 1.8 VertexVisitor<Vertex> onExit) {
250 salcianu 1.8 DiGraph.dfs(getRoots(), getForwardNavigator(),
251 salcianu 1.8 onEntry, onExit);
252 salcianu 1.8 }
253 salcianu 1.8
254 salcianu 1.8 /** DFS traversal of a (sub) digraph.
255 salcianu 1.8
256 salcianu 1.8 @param roots set of root vertices, starting points for the traversal
257 salcianu 1.8
258 salcianu 1.8 @param navigator forward navigator through the digraph
259 salcianu 1.8
260 salcianu 1.8 @param onEntry action executed when a node is first time
261 salcianu 1.8 visited by the DFS traversal
262 salcianu 1.8
263 salcianu 1.8 @param onExit action executed after the DFS traversal of a
264 salcianu 1.8 node finished */
265 salcianu 1.8 public static <Vertex> void dfs(Collection<Vertex> roots,
266 salcianu 1.8 ForwardNavigator<Vertex> navigator,
267 salcianu 1.8 VertexVisitor<Vertex> onEntry,
268 salcianu 1.8 VertexVisitor<Vertex> onExit) {
269 salcianu 1.8 (new ClosureDFS<Vertex>()).doIt(roots, navigator, onEntry, onExit);
270 salcianu 1.8 }
271 salcianu 1.8
272 salcianu 1.8 private static class ClosureDFS<Vertex> {
273 salcianu 1.10 public Set<Vertex> visited;
274 salcianu 1.9 private VertexVisitor<Vertex> onEntry;
275 salcianu 1.9 private VertexVisitor<Vertex> onExit;
276 salcianu 1.8 private ForwardNavigator<Vertex> fnav;
277 salcianu 1.8
278 salcianu 1.10 public Set<Vertex> doIt(Collection<Vertex> roots,
279 salcianu 1.10 ForwardNavigator<Vertex> fnav,
280 salcianu 1.10 VertexVisitor<Vertex> onEntry,
281 salcianu 1.10 VertexVisitor<Vertex> onExit) {
282 salcianu 1.8 this.fnav = fnav;
283 salcianu 1.8 this.onEntry = onEntry;
284 salcianu 1.8 this.onExit = onExit;
285 salcianu 1.8 this.visited = new HashSet();
286 salcianu 1.8
287 salcianu 1.8 for(Vertex root : roots ) {
288 salcianu 1.8 dfs_visit(root);
289 salcianu 1.8 }
290 salcianu 1.10
291 salcianu 1.10 return visited;
292 salcianu 1.8 }
293 salcianu 1.8
294 salcianu 1.8 private void dfs_visit(Vertex v) {
295 salcianu 1.8 // skip already visited nodes
296 salcianu 1.9 if(!visited.add(v)) return;
297 salcianu 1.8
298 salcianu 1.8 if(onEntry != null)
299 salcianu 1.8 onEntry.visit(v);
300 salcianu 1.8
301 salcianu 1.10 for(Vertex v2 : fnav.next(v))
302 salcianu 1.10 dfs_visit(v2);
303 salcianu 1.8
304 salcianu 1.8 if(onExit != null)
305 salcianu 1.8 onExit.visit(v);
306 salcianu 1.8 }
307 salcianu 1.8 }
308 salcianu 1.8
309 salcianu 1.4
310 salcianu 1.4 /** Executes an action exactly once for each vertex from
311 salcianu 1.4 <code>this</code> directed graph. */
312 salcianu 1.8 public void forAllVertices(VertexVisitor<Vertex> action) {
313 salcianu 1.8 dfs(action, null);
314 salcianu 1.4 }
315 salcianu 1.4
316 salcianu 1.4
317 salcianu 1.4 /** Performs an action exactly once on each vertex reachable from
318 salcianu 1.4 the set of vertices <code>roots</code>, via the navigator
319 salcianu 1.4 <code>navigator</code>. This method is supposed to be called
320 salcianu 1.4 if:
321 salcianu 1.4
322 salcianu 1.4 <ol>
323 salcianu 1.4
324 salcianu 1.4 <li>you are interested only in a subgraph or
325 salcianu 1.4
326 salcianu 1.4 <li>you have a set of roots and a navigator but didn't package
327 salcianu 1.4 them in a digraph.
328 salcianu 1.4
329 salcianu 1.4 </ol>
330 salcianu 1.4
331 salcianu 1.4 If you want to execute an action for all vertices from a
332 salcianu 1.4 digraph, use the non-static version of this method. */
333 cananian 1.7 public static <Vertex> void forAllReachableVertices
334 cananian 1.7 (Collection<Vertex> roots,
335 cananian 1.7 ForwardNavigator<Vertex> navigator,
336 salcianu 1.8 VertexVisitor<Vertex> action) {
337 cananian 1.7
338 salcianu 1.8 (new ClosureDFS()).doIt(roots, navigator, action, null);
339 salcianu 1.4 }
340 salcianu 1.4
341 salcianu 1.4
342 salcianu 1.1 /** Returns the component graph for <code>this</code> graph. The
343 salcianu 1.1 "component graph" of a graph <code>G</code> is the
344 salcianu 1.1 directed, acyclic graph consisting of the strongly connected
345 salcianu 1.1 components of <code>G</code>. */
346 salcianu 1.8 public DiGraph<SCComponent/*<Vertex>*/> getComponentDiGraph() {
347 cananian 1.7 final Set<SCComponent/*<Vertex>*/> sccs = SCComponent.buildSCC(this);
348 cananian 1.7 return new DiGraph<SCComponent/*<Vertex>*/>() {
349 salcianu 1.8 public Set<SCComponent/*<Vertex>*/> getRoots() {
350 salcianu 1.1 return sccs;
351 salcianu 1.1 }
352 salcianu 1.8 public Navigator<SCComponent/*<Vertex>*/> getNavigator() {
353 salcianu 1.1 return SCComponent.SCC_NAVIGATOR;
354 salcianu 1.1 }
355 salcianu 1.1 };
356 salcianu 1.1 }
357 salcianu 1.1
358 salcianu 1.3
359 salcianu 1.3 /** @return set of vertices from <code>this</code> directed graph. */
360 cananian 1.7 public Set<Vertex> allVertices() {
361 salcianu 1.8 return transitiveSucc(getRoots());
362 salcianu 1.3 }
363 salcianu 1.3
364 salcianu 1.3
365 salcianu 1.3 /** @return reverse of <code>this</code> directed graph: a
366 salcianu 1.3 directed graph with the same set of vertices, that contains an
367 salcianu 1.3 arc from <code>v1</code> to <code>v2</code> iff
368 salcianu 1.3 <code>this</code> graph contains an arc from <code>v2</code>
369 salcianu 1.3 to <code>v1</code>. */
370 cananian 1.7 public DiGraph<Vertex> reverseGraph() {
371 salcianu 1.8 final DiGraph<Vertex> origDiGraph = this;
372 cananian 1.7 return new DiGraph<Vertex>() {
373 salcianu 1.8 public Set<Vertex> getRoots() {
374 salcianu 1.8 return origDiGraph.allVertices();
375 salcianu 1.3 }
376 salcianu 1.8 public Navigator<Vertex> getNavigator() {
377 salcianu 1.8 return
378 salcianu 1.8 new ReverseNavigator<Vertex>
379 salcianu 1.8 (origDiGraph.getNavigator());
380 salcianu 1.3 }
381 salcianu 1.3 };
382 salcianu 1.9 }
383 salcianu 1.9
384 salcianu 1.9 public String toString() {
385 salcianu 1.9 return getRoots().toString();
386 salcianu 1.3 }
387 salcianu 1.3 }