001: /* Walker.java */
002:
003: package org.quilt.graph;
004:
005: import java.util.HashSet;
006:
007: /**
008: * Walks a Visitor through a Quilt directed graph, visiting each
009: * vertex and edge once and only once. Any subgraphs are visited
010: * with the same guarantee.
011: *
012: * @author <a href="jdd@dixons.org">Jim Dixon</a>
013: */
014:
015: public class Walker {
016:
017: private Directed graph = null;
018: private Entry entry = null;
019: private Exit exit = null;
020: private Visitor visitor = null;
021: private HashSet vertices = new HashSet();
022: private HashSet edges = new HashSet();
023:
024: /** No-arg constructor. */
025: public Walker() {
026: }
027:
028: // METHODS //////////////////////////////////////////////////////
029: /**
030: * Walk through the entire graph.
031: *
032: * @param graph The graph we are walking.
033: * @param guest Agent which does something as we walk the graph.
034: * @return Reference to the exit Vertex of the graph.
035: */
036: public Exit visit(Directed g, Visitor guest) {
037: Directed.checkForNull(g, "graph");
038: Directed.checkForNull(guest, "Visitor");
039: graph = g;
040: entry = g.getEntry();
041: exit = g.getExit();
042: visitor = guest;
043: visitor.discoverGraph(graph);
044: visitVertex((Vertex) graph.getEntry());
045: visitor.finishGraph(graph);
046: return exit;
047: }
048:
049: /**
050: * Visit a vertex, and in so doing visit all attached edges.
051: *
052: * @param v A vertex in that graph.
053: */
054: private void visitVertex(Vertex v) {
055: Directed.checkForNull(v, "vertex");
056: if (vertices.contains(v)) {
057: // we have already been here
058: return;
059: }
060: vertices.add(v); // mark this node as visited
061:
062: if (v == exit) {
063: visitor.discoverVertex(v); // let guest do his business
064:
065: // Allow Walker to visit Edge to graph Entry. Can have no
066: // practical benefit; added primarily for aesthetic reasons.
067: // Used to cause an infinite loop.
068: Edge e = v.getEdge();
069: if (e.getTarget().getGraph() == graph) {
070: visitEdge(v.getEdge());
071: }
072: visitor.finishVertex(v);
073: } else {
074: if (v != entry && v instanceof Entry) {
075: // it's the entry point into a subgraph
076: Walker subWalker = new Walker();
077: Exit subExit = subWalker.visit(v.getGraph(), visitor);
078: visitVertex(((UnaryConnector) subExit.getConnector())
079: .getEdge().getTarget());
080: } else {
081: // it's a vertex in this graph
082: visitor.discoverVertex(v); // let guest do his business
083: // get outbound edges and visit each in turn; the
084: // preferred edge is always visited first
085: Connector conn = v.getConnector();
086: // visit the preferred edge
087: visitEdge(conn.getEdge());
088: if (conn instanceof BinaryConnector) {
089: visitEdge(((BinaryConnector) conn).getOtherEdge());
090: } else if (conn instanceof ComplexConnector) {
091: int size = conn.size();
092: for (int i = 0; i < size; i++) {
093: visitEdge(((ComplexConnector) conn).getEdge(i));
094: }
095: } else if (conn instanceof UnaryConnector) {
096: // do nothing
097: } else if (conn instanceof MultiConnector) {
098: // preferred edge 0 already visited
099: for (int i = 1; i < conn.size(); i++) {
100: visitEdge(((MultiConnector) conn).getEdge(i));
101: }
102: } else {
103: System.out
104: .println("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: /**
113: * @param e An edge in this graph.
114: */
115: private void visitEdge(Edge e) {
116: Directed.checkForNull(e, "edge");
117: if (edges.contains(e)) {
118: return; // already been here
119: }
120: edges.add(e); // mark as visited
121:
122: visitor.discoverEdge(e);
123: Vertex target = e.getTarget();
124: Directed.checkForNull(target, "edge target");
125:
126: // XXX CODE NEEDS REWORKING /////////////////////////////////
127: if (target instanceof Entry) {
128: // if the target is an Entry vertex, visit it only if it is
129: // in a different graph which is not the parent of this graph
130: Vertex source = e.getSource();
131: Directed sourceGraph = source.getGraph();
132: Directed targetGraph = e.getTarget().getGraph();
133: if (sourceGraph != targetGraph
134: && targetGraph != sourceGraph.getParent()) {
135: visitVertex(target);
136: }
137: } else if (target instanceof Exit) {
138: // if the target is an Exit vertex, visit it only if it is
139: // in the same graph
140: Directed sourceGraph = e.getSource().getGraph();
141: Directed targetGraph = e.getTarget().getGraph();
142: if (sourceGraph == targetGraph) {
143: visitVertex(target);
144: }
145: } else {
146: visitVertex(target);
147: }
148: visitor.finishEdge(e);
149: }
150: }
|