1 /* Directed.java */
2 package org.quilt.graph;
3
4 /***
5 * A graph consisting of vertices connected by directed, weighted edges.
6 * The graph is guaranteed to have at least an entry and an exit point
7 * and to always be well-formed, in the sense that
8 * <ul>
9 * <li>there will be a path from the entry vertex to any other vertex
10 * in the graph, and </li>
11 * <li>there will be a path from any vertex in the graph to the exit
12 * vertex</li>
13 * </ul>
14 *
15 * These graphs may be nested. In such a case
16 * <ul>
17 * <li>both graphs will be well-formed
18 * <li>the entry and exit points of the subgraph are in the graph
19 * <li>all paths from the entry point of the parent to a point in the
20 * subgraph will pass through the entry point of the subgraph
21 * <li>all paths from a vertex within the subgraph to a vertex in the
22 * parent graph will pass through the exit vertex of the subgraph
23 * </ul>
24 *
25 * @author <a href="jddixon@users.sourceforge.net">Jim Dixon</a>
26 */
27 public class Directed {
28
29 /*** Entry vertex. */
30 private Entry entry = null;
31 /*** Exit vertex. */
32 private Exit exit = null;
33
34 /*** Index of most recently built graph. */
35 protected static int graphIndex = 0;
36 /*** Index of this graph. */
37 private int index = 0;
38
39 /*** Parent graph, if any */
40 private Directed parent_ = null;
41 private int depth = 0;
42 private int vCount = 0; // number of vertices in graph
43 private int eCount = 0;
44
45 // CONSTRUCTORS /////////////////////////////////////////////////
46 /***
47 * Builds a root directed graph with two vertices and two edges. The
48 * two vertices are Entry and Exit types. There is an edge from
49 * entry to exit and another from exit back to entry. Each is
50 * constained in a UnaryConnector. Vertices are added to the graph
51 * by inserting them along the entry-to-exit edge.
52 *
53 * @see Connector
54 * @see Edge
55 */
56 public Directed ( ) {
57 index = graphIndex = 0;
58 entry = new Entry(this); // creates Exit
59 exit = (Exit) entry.getTarget();
60 }
61 /*** @return The parent graph to this graph, or null if there is none. */
62 public Directed getParent() {
63 return parent_;
64 }
65 /*** @return The zero-based index of this graph. */
66 public int getIndex() {
67 return index;
68 }
69 // SUBGRAPHS //////////////////////////////////////////
70 /***
71 * Subgraph constructor; will have depth one more than parent.
72 *
73 * @param parent Graph in which this is a subgraph.
74 * @param n Number of extra edges
75 */
76 protected Directed (Directed parent) {
77 index = ++ graphIndex;
78 entry = new Entry(this); // creates Exit
79 exit = (Exit) entry.getTarget();
80 checkForNull (parent, "parent");
81 depth = parent.getDepth() + 1;
82 parent_ = parent;
83 }
84 /***
85 * Inserts a subgraph into an edge, putting the entry and exit points
86 * on the edge presented. On exit the original edge has been
87 * retargeted to the Entry of the subgraph.
88 *
89 * @param e An edge in the parent graph.
90 * @return A reference to the subgraph.
91 */
92 final static protected Directed connectSubgraph (final Directed subgraph,
93 final Edge e, final int n) {
94 checkForNull(e, "edge");
95 if ( n < 1 ) {
96 throw new IllegalArgumentException (
97 "out of range argument");
98 }
99 // Directed sub = new Directed(this);
100 Entry subEntry = subgraph.getEntry();
101 subEntry.setConnector(
102 new ComplexConnector ( subEntry.getConnector(), n) );
103
104 // connect graph to parent - first the entry
105 Vertex target = e.getTarget(); // current target
106 e.setTarget(subEntry); // retarget e to subgraph entry
107
108 // then the exit edge is retargeted to the original target
109 subgraph.getExit().getEdge().setTarget(target);
110 return subgraph;
111 }
112 /***
113 * Constructs a subgraph and inserts it into the parent graph
114 * on the edge presented. This is a wrapper around the method
115 * that does the connecting; when extending the class, override
116 * the wrapper.
117 *
118 * @param e An edge in the parent graph.
119 * @return A reference to the subgraph.
120 */
121 public Directed subgraph (final Edge e, final int n) {
122 return connectSubgraph (new Directed(this), e, n);
123 }
124 // ACCESSOR METHODS /////////////////////////////////////////////
125 /*** @return The depth of this graph. */
126 public int getDepth() {
127 return depth;
128 }
129 /*** @return The entry vertex of this graph. */
130 public Entry getEntry () {
131 return entry;
132 }
133 /*** @return The exit vertex of this graph. */
134 public Exit getExit() {
135 return exit;
136 }
137 // OTHER METHODS ////////////////////////////////////////////////
138 public static void checkForNull (Object o, String what) {
139 if (o == null) {
140 throw new IllegalArgumentException ("null " + what);
141 }
142 }
143 /***
144 * Step edge count.
145 * @param e Edge being added. Ignored at the moment.
146 */
147 public int anotherEdge ( Edge e ) {
148 return (eCount++);
149 }
150 /***
151 * Step count of vertices .
152 * @param v Vertex being added. Being ignored at the moment.
153 */
154 public int anotherVertex( Vertex v ) {
155 return (vCount++);
156 }
157 /***
158 * Insert a (new) Vertex into the graph along the edge provided.
159 * After this operation the target of the edge will be the new
160 * vertex.
161 *
162 * @param v Vertex to be inserted.
163 * @param e Edge it is to be inserted along.
164 */
165 final protected Vertex insertVertex (Vertex v, Edge e) {
166 checkForNull (e, "edge");
167 Vertex source = e.getSource();
168 if ( ! (source instanceof Exit) && source.getGraph() != this) {
169 // DEBUG
170 System.out.println("Directed.insertVertex:"
171 + "\n vertex: " + v
172 + "\n edge: " + e);
173 // END
174 throw new IllegalArgumentException ("edge not in this graph");
175 }
176 Vertex target = e.getTarget();
177 e.setTarget(v);
178 v.setConnector ( new UnaryConnector (new Edge(v, target)));
179 return v;
180 }
181 /***
182 * Create a new Vertex with a Unary connector and insert into
183 * this graph's edge e.
184 */
185 public Vertex insertVertex (Edge e) {
186 return insertVertex (new Vertex(this), e);
187 }
188 /*** */
189 private class Sizer implements Visitor {
190 private int graphCount = 0;
191 private int maxDepth = -1;
192 private int vertexCount = 0;
193 private int edgeCount = 0;
194
195 public Sizer() { }
196
197 public void discoverGraph (Directed g) {
198 checkForNull (g, "graph");
199 int depth = g.getDepth() + 1;
200 graphCount++;
201 if (depth > maxDepth) {
202 maxDepth = depth;
203 }
204 }
205 public void finishGraph (Directed g) { }
206 public void discoverVertex(Vertex v) {
207 checkForNull(v, "vertex");
208 vertexCount++;
209 }
210 public void finishVertex (Vertex v) { }
211 public void discoverEdge (Edge e) {
212 checkForNull (e, "edge");
213 edgeCount++;
214 }
215 public void finishEdge (Edge e) { }
216 // ACCESSOR METHODS ///////////////////////////////
217 public int getGraphCount () { return graphCount; }
218 public int getMaxDepth () { return maxDepth; }
219 public int getVertexCount () { return vertexCount; }
220 public int getEdgeCount () { return edgeCount; }
221 }
222 public int size() {
223 Walker johnny = new Walker();
224 Sizer counter = new Sizer();
225 // Exit ignored =
226 johnny.visit (this, counter);
227 return counter.getVertexCount();
228 }
229
230 /***
231 * If the edge points towards a vertex in a graph which is enclosed
232 * within the current graph, return a reference to the closest Entry.
233 * The vertex might be within a nested subgraph. If it is not in a
234 * descendent graph, return null.
235 *
236 * @param e Edge towards vertex in lower-level graph.
237 * @param g Candidate lower-level graph.
238 * @return A reference to the nearest Entry point or null.
239 */
240 public Entry closestEntry (final Directed g) {
241 // DEBUG
242 //System.out.println ("Directed.closestEntry for " + g.getIndex()
243 // + " from " + getIndex() );
244 // END
245 if (g == null) {
246 throw new IllegalArgumentException ("null argument");
247 }
248 if ( g == this ) {
249 return null;
250 }
251 Directed hisGraph;
252 for (hisGraph = g; hisGraph != null;
253 hisGraph = hisGraph.getParent() ) {
254 // // DEBUG
255 // if (hisGraph.getParent() != null) {
256 // System.out.println(" checking graph "
257 // + hisGraph.getParent().getIndex() );
258 // } else {
259 // System.out.println(" checking null graph ;-) ");
260 // }
261 // // END
262 if (hisGraph.getParent() == this) {
263 // // DEBUG
264 // System.out.println(
265 // " match at graph " + hisGraph.getIndex());
266 //
267 // // END
268 return hisGraph.getEntry();
269 }
270 }
271 return null;
272 }
273 }
This page was automatically generated by Maven