001: /* Directed.java */
002: package org.quilt.graph;
003:
004: /**
005: * A graph consisting of vertices connected by directed, weighted edges.
006: * The graph is guaranteed to have at least an entry and an exit point
007: * and to always be well-formed, in the sense that
008: * <ul>
009: * <li>there will be a path from the entry vertex to any other vertex
010: * in the graph, and </li>
011: * <li>there will be a path from any vertex in the graph to the exit
012: * vertex</li>
013: * </ul>
014: *
015: * These graphs may be nested. In such a case
016: * <ul>
017: * <li>both graphs will be well-formed
018: * <li>the entry and exit points of the subgraph are in the graph
019: * <li>all paths from the entry point of the parent to a point in the
020: * subgraph will pass through the entry point of the subgraph
021: * <li>all paths from a vertex within the subgraph to a vertex in the
022: * parent graph will pass through the exit vertex of the subgraph
023: * </ul>
024: *
025: * @author <a href="jddixon@users.sourceforge.net">Jim Dixon</a>
026: */
027: public class Directed {
028:
029: /** Entry vertex. */
030: private Entry entry = null;
031: /** Exit vertex. */
032: private Exit exit = null;
033:
034: /** Index of most recently built graph. */
035: protected static int graphIndex = 0;
036: /** Index of this graph. */
037: private int index = 0;
038:
039: /** Parent graph, if any */
040: private Directed parent_ = null;
041: private int depth = 0;
042: private int vCount = 0; // number of vertices in graph
043: private int eCount = 0;
044:
045: // CONSTRUCTORS /////////////////////////////////////////////////
046: /**
047: * Builds a root directed graph with two vertices and two edges. The
048: * two vertices are Entry and Exit types. There is an edge from
049: * entry to exit and another from exit back to entry. Each is
050: * constained in a UnaryConnector. Vertices are added to the graph
051: * by inserting them along the entry-to-exit edge.
052: *
053: * @see Connector
054: * @see Edge
055: */
056: public Directed() {
057: index = graphIndex = 0;
058: entry = new Entry(this ); // creates Exit
059: exit = (Exit) entry.getTarget();
060: }
061:
062: /** @return The parent graph to this graph, or null if there is none. */
063: public Directed getParent() {
064: return parent_;
065: }
066:
067: /** @return The zero-based index of this graph. */
068: public int getIndex() {
069: return index;
070: }
071:
072: // SUBGRAPHS //////////////////////////////////////////
073: /**
074: * Subgraph constructor; will have depth one more than parent.
075: *
076: * @param parent Graph in which this is a subgraph.
077: * @param n Number of extra edges
078: */
079: protected Directed(Directed parent) {
080: index = ++graphIndex;
081: entry = new Entry(this ); // creates Exit
082: exit = (Exit) entry.getTarget();
083: checkForNull(parent, "parent");
084: depth = parent.getDepth() + 1;
085: parent_ = parent;
086: }
087:
088: /**
089: * Inserts a subgraph into an edge, putting the entry and exit points
090: * on the edge presented. On exit the original edge has been
091: * retargeted to the Entry of the subgraph.
092: *
093: * @param e An edge in the parent graph.
094: * @return A reference to the subgraph.
095: */
096: final static protected Directed connectSubgraph(
097: final Directed subgraph, final Edge e, final int n) {
098: checkForNull(e, "edge");
099: if (n < 1) {
100: throw new IllegalArgumentException("out of range argument");
101: }
102: // Directed sub = new Directed(this);
103: Entry subEntry = subgraph.getEntry();
104: subEntry.setConnector(new ComplexConnector(subEntry
105: .getConnector(), n));
106:
107: // connect graph to parent - first the entry
108: Vertex target = e.getTarget(); // current target
109: e.setTarget(subEntry); // retarget e to subgraph entry
110:
111: // then the exit edge is retargeted to the original target
112: subgraph.getExit().getEdge().setTarget(target);
113: return subgraph;
114: }
115:
116: /**
117: * Constructs a subgraph and inserts it into the parent graph
118: * on the edge presented. This is a wrapper around the method
119: * that does the connecting; when extending the class, override
120: * the wrapper.
121: *
122: * @param e An edge in the parent graph.
123: * @return A reference to the subgraph.
124: */
125: public Directed subgraph(final Edge e, final int n) {
126: return connectSubgraph(new Directed(this ), e, n);
127: }
128:
129: // ACCESSOR METHODS /////////////////////////////////////////////
130: /** @return The depth of this graph. */
131: public int getDepth() {
132: return depth;
133: }
134:
135: /** @return The entry vertex of this graph. */
136: public Entry getEntry() {
137: return entry;
138: }
139:
140: /** @return The exit vertex of this graph. */
141: public Exit getExit() {
142: return exit;
143: }
144:
145: // OTHER METHODS ////////////////////////////////////////////////
146: public static void checkForNull(Object o, String what) {
147: if (o == null) {
148: throw new IllegalArgumentException("null " + what);
149: }
150: }
151:
152: /**
153: * Step edge count.
154: * @param e Edge being added. Ignored at the moment.
155: */
156: public int anotherEdge(Edge e) {
157: return (eCount++);
158: }
159:
160: /**
161: * Step count of vertices .
162: * @param v Vertex being added. Being ignored at the moment.
163: */
164: public int anotherVertex(Vertex v) {
165: return (vCount++);
166: }
167:
168: /**
169: * Insert a (new) Vertex into the graph along the edge provided.
170: * After this operation the target of the edge will be the new
171: * vertex.
172: *
173: * @param v Vertex to be inserted.
174: * @param e Edge it is to be inserted along.
175: */
176: final protected Vertex insertVertex(Vertex v, Edge e) {
177: checkForNull(e, "edge");
178: Vertex source = e.getSource();
179: if (!(source instanceof Exit) && source.getGraph() != this ) {
180: // DEBUG
181: System.out.println("Directed.insertVertex:"
182: + "\n vertex: " + v + "\n edge: " + e);
183: // END
184: throw new IllegalArgumentException("edge not in this graph");
185: }
186: Vertex target = e.getTarget();
187: e.setTarget(v);
188: v.setConnector(new UnaryConnector(new Edge(v, target)));
189: return v;
190: }
191:
192: /**
193: * Create a new Vertex with a Unary connector and insert into
194: * this graph's edge e.
195: */
196: public Vertex insertVertex(Edge e) {
197: return insertVertex(new Vertex(this ), e);
198: }
199:
200: /** */
201: private class Sizer implements Visitor {
202: private int graphCount = 0;
203: private int maxDepth = -1;
204: private int vertexCount = 0;
205: private int edgeCount = 0;
206:
207: public Sizer() {
208: }
209:
210: public void discoverGraph(Directed g) {
211: checkForNull(g, "graph");
212: int depth = g.getDepth() + 1;
213: graphCount++;
214: if (depth > maxDepth) {
215: maxDepth = depth;
216: }
217: }
218:
219: public void finishGraph(Directed g) {
220: }
221:
222: public void discoverVertex(Vertex v) {
223: checkForNull(v, "vertex");
224: vertexCount++;
225: }
226:
227: public void finishVertex(Vertex v) {
228: }
229:
230: public void discoverEdge(Edge e) {
231: checkForNull(e, "edge");
232: edgeCount++;
233: }
234:
235: public void finishEdge(Edge e) {
236: }
237:
238: // ACCESSOR METHODS ///////////////////////////////
239: public int getGraphCount() {
240: return graphCount;
241: }
242:
243: public int getMaxDepth() {
244: return maxDepth;
245: }
246:
247: public int getVertexCount() {
248: return vertexCount;
249: }
250:
251: public int getEdgeCount() {
252: return edgeCount;
253: }
254: }
255:
256: public int size() {
257: Walker johnny = new Walker();
258: Sizer counter = new Sizer();
259: // Exit ignored =
260: johnny.visit(this , counter);
261: return counter.getVertexCount();
262: }
263:
264: /**
265: * If the edge points towards a vertex in a graph which is enclosed
266: * within the current graph, return a reference to the closest Entry.
267: * The vertex might be within a nested subgraph. If it is not in a
268: * descendent graph, return null.
269: *
270: * @param e Edge towards vertex in lower-level graph.
271: * @param g Candidate lower-level graph.
272: * @return A reference to the nearest Entry point or null.
273: */
274: public Entry closestEntry(final Directed g) {
275: // DEBUG
276: //System.out.println ("Directed.closestEntry for " + g.getIndex()
277: // + " from " + getIndex() );
278: // END
279: if (g == null) {
280: throw new IllegalArgumentException("null argument");
281: }
282: if (g == this ) {
283: return null;
284: }
285: Directed hisGraph;
286: for (hisGraph = g; hisGraph != null; hisGraph = hisGraph
287: .getParent()) {
288: // // DEBUG
289: // if (hisGraph.getParent() != null) {
290: // System.out.println(" checking graph "
291: // + hisGraph.getParent().getIndex() );
292: // } else {
293: // System.out.println(" checking null graph ;-) ");
294: // }
295: // // END
296: if (hisGraph.getParent() == this ) {
297: // // DEBUG
298: // System.out.println(
299: // " match at graph " + hisGraph.getIndex());
300: //
301: // // END
302: return hisGraph.getEntry();
303: }
304: }
305: return null;
306: }
307: }
|