View Javadoc
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