1 /* Walker.java */
2
3 package org.quilt.graph;
4
5 import java.util.HashSet;
6
7 /***
8 * Walks a Visitor through a Quilt directed graph, visiting each
9 * vertex and edge once and only once. Any subgraphs are visited
10 * with the same guarantee.
11 *
12 * @author <a href="jdd@dixons.org">Jim Dixon</a>
13 */
14
15 public class Walker {
16
17 private Directed graph = null;
18 private Entry entry = null;
19 private Exit exit = null;
20 private Visitor visitor = null;
21 private HashSet vertices = new HashSet();
22 private HashSet edges = new HashSet();
23
24 /*** No-arg constructor. */
25 public Walker() { }
26
27 // METHODS //////////////////////////////////////////////////////
28 /***
29 * Walk through the entire graph.
30 *
31 * @param graph The graph we are walking.
32 * @param guest Agent which does something as we walk the graph.
33 * @return Reference to the exit Vertex of the graph.
34 */
35 public Exit visit (Directed g, Visitor guest) {
36 Directed.checkForNull(g, "graph");
37 Directed.checkForNull(guest, "Visitor");
38 graph = g;
39 entry = g.getEntry();
40 exit = g.getExit();
41 visitor = guest;
42 visitor.discoverGraph(graph);
43 visitVertex( (Vertex) graph.getEntry() );
44 visitor.finishGraph(graph);
45 return exit;
46 }
47
48 /***
49 * Visit a vertex, and in so doing visit all attached edges.
50 *
51 * @param v A vertex in that graph.
52 */
53 private void visitVertex (Vertex v) {
54 Directed.checkForNull(v, "vertex");
55 if (vertices.contains(v)) {
56 // we have already been here
57 return;
58 }
59 vertices.add(v); // mark this node as visited
60
61 if ( v == exit) {
62 visitor.discoverVertex(v); // let guest do his business
63
64 // Allow Walker to visit Edge to graph Entry. Can have no
65 // practical benefit; added primarily for aesthetic reasons.
66 // Used to cause an infinite loop.
67 Edge e = v.getEdge();
68 if (e.getTarget().getGraph() == graph) {
69 visitEdge (v.getEdge());
70 }
71 visitor.finishVertex(v);
72 } else {
73 if (v != entry && v instanceof Entry) {
74 // it's the entry point into a subgraph
75 Walker subWalker = new Walker();
76 Exit subExit = subWalker.visit (v.getGraph(), visitor);
77 visitVertex (
78 ((UnaryConnector)subExit.getConnector())
79 .getEdge().getTarget() );
80 } else {
81 // it's a vertex in this graph
82 visitor.discoverVertex(v); // let guest do his business
83 // get outbound edges and visit each in turn; the
84 // preferred edge is always visited first
85 Connector conn = v.getConnector();
86 // visit the preferred edge
87 visitEdge ( conn.getEdge() );
88 if (conn instanceof BinaryConnector) {
89 visitEdge ( ((BinaryConnector)conn).getOtherEdge());
90 } else if (conn instanceof ComplexConnector) {
91 int size = conn.size();
92 for (int i = 0; i < size; i++) {
93 visitEdge ( ((ComplexConnector)conn).getEdge(i));
94 }
95 } else if (conn instanceof UnaryConnector) {
96 // do nothing
97 } else if (conn instanceof MultiConnector) {
98 // preferred edge 0 already visited
99 for (int i = 1; i < conn.size(); i++) {
100 visitEdge ( ((MultiConnector)conn).getEdge(i));
101 }
102 } else {
103 System.out.println (
104 "Walker.visitVertex: INTERNAL ERROR\n" +
105 " don't know how to handle this kind of connection");
106 }
107 visitor.finishVertex(v);
108 }
109 }
110 }
111 /***
112 * @param e An edge in this graph.
113 */
114 private void visitEdge(Edge e) {
115 Directed.checkForNull(e, "edge");
116 if (edges.contains(e)) {
117 return; // already been here
118 }
119 edges.add(e); // mark as visited
120
121 visitor.discoverEdge(e);
122 Vertex target = e.getTarget();
123 Directed.checkForNull(target, "edge target");
124
125 // XXX CODE NEEDS REWORKING /////////////////////////////////
126 if ( target instanceof Entry ) {
127 // if the target is an Entry vertex, visit it only if it is
128 // in a different graph which is not the parent of this graph
129 Vertex source = e.getSource();
130 Directed sourceGraph = source.getGraph();
131 Directed targetGraph = e.getTarget().getGraph();
132 if (sourceGraph != targetGraph
133 && targetGraph != sourceGraph.getParent() ) {
134 visitVertex(target);
135 }
136 } else if ( target instanceof Exit ) {
137 // if the target is an Exit vertex, visit it only if it is
138 // in the same graph
139 Directed sourceGraph = e.getSource().getGraph();
140 Directed targetGraph = e.getTarget().getGraph();
141 if (sourceGraph == targetGraph ) {
142 visitVertex(target);
143 }
144 } else {
145 visitVertex(target);
146 }
147 visitor.finishEdge(e);
148 }
149 }
150
This page was automatically generated by Maven