KickJava   Java API By Example, From Geeks To Geeks.

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


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 JavaDoc (
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 JavaDoc o, String JavaDoc what) {
139         if (o == null) {
140             throw new IllegalArgumentException JavaDoc ("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 JavaDoc ("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 JavaDoc ("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 }
274
Popular Tags