KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > quilt > graph > Walker


1 /* Walker.java */
2
3 package org.quilt.graph;
4
5 import java.util.HashSet JavaDoc;
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 JavaDoc vertices = new HashSet JavaDoc();
22     private HashSet JavaDoc edges = new HashSet JavaDoc();
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
151
Popular Tags