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   (
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 }
274
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags