Clover coverage report - baseCode - 0.2.5 Coverage timestamp: Tue Apr 12 2005 11:31:58 EDT FRAMES NO FRAMES |
file stats: | LOC: | 260 |  | Methods: | 13
| NCLOC: | 160 |  | Classes: | 1
30 day Evaluation Version distributed via the Maven Jar Repository. Clover is not free. You have 30 days to evaluate it. Please visit http://www.thecortex.net/clover to obtain a licensed version of Clover
Source file | Conditionals | Statements | Methods | TOTAL
DirectedGraph.java | 59.1% | 63.7% | 61.5% | 62.2% |

1 |  |
     package baseCode.dataStructure.graph;
2 |  |
3 |  |
     import java.util.ArrayList;
4 |  |
     import java.util.Collections;
5 |  |
     import java.util.HashMap;
6 |  |
     import java.util.Iterator;
7 |  |
     import java.util.LinkedHashMap;
8 |  |
     import java.util.List;
9 |  |
     import java.util.Map;
10 |  |
     import java.util.Set;
11 |  |
12 |  |
     import javax.swing.JTree;
13 |  |
     import javax.swing.tree.DefaultMutableTreeNode;
14 |  |
15 |  |
     import baseCode.dataStructure.Queue;
16 |  |
17 |  |
     /**
18 |  |
      * A graph that contains DirectedGraphNodes. It can be cyclic. Small unconnected parts of the graph will be ignored for
19 |  |
      * many operation. Tree traversals start from the root node, which is defined as the node with the most children.
20 |  |
      * <p>
21 |  |
      * Copyright (c) Columbia University
22 |  |
      *
23 |  |
      * @todo do something about cyclicity; make this a dag or a subclass...
24 |  |
      * @author Paul Pavlidis
25 |  |
      * @version $Id: DirectedGraph.java,v 1.8 2004/07/27 03:18:58 pavlidis Exp $
26 |  |
      */
27 |  |
     public class DirectedGraph extends AbstractGraph {
28 |  |
29 | 8 |
        public DirectedGraph() {
30 | 8 |
           super();
31 |  |
        }
32 |  |
33 |  |
        /**
34 |  |
         * @param nodes Set of DirectedGraphNodes
35 |  |
         */
36 | 0 |
        public DirectedGraph( Set nodes ) {
37 | 0 |
           items = new LinkedHashMap();
38 | 0 |
           for ( Iterator it = nodes.iterator(); it.hasNext(); ) {
39 | 0 |
              DirectedGraphNode a = ( DirectedGraphNode ) it.next();
40 | 0 |
              this.addNode( a );
41 |  |
           }
42 |  |
        }
43 |  |
44 |  |
        /**
45 |  |
         * @param key Object
46 |  |
         * @param item Object
47 |  |
         */
48 | 113 |
        public void addNode( Object key, Object item ) {
49 | 113 |
           if ( !items.containsKey( key ) ) {
50 | 113 |
              items.put( key, new DirectedGraphNode( key, item, this ) );
51 |  |
           }
52 |  |
        }
53 |  |
54 |  |
        /**
55 |  |
         * Add a child to a particualar node identified by key.
56 |  |
         *
57 |  |
         * @param key Object
58 |  |
         * @param newChildKey Object
59 |  |
         * @param newChild Object
60 |  |
         */
61 | 0 |
        public void addChildTo( Object key, Object newChildKey, Object newChild ) {
62 | 0 |
           if ( !items.containsKey( newChild ) ) {
63 | 0 |
              this.addNode( newChildKey, newChild );
64 |  |
           }
65 |  |
66 | 0 |
           this.addChildTo( key, newChildKey );
67 | 0 |
           this.addParentTo( newChildKey, key );
68 |  |
        }
69 |  |
70 |  |
        /**
71 |  |
         * Add a child to a particular node identified by key; if the node is not in the graph, an exception is thrown.
72 |  |
         *
73 |  |
         * @param key Object
74 |  |
         * @param newChildKey Object
75 |  |
         * @throws IllegalStateException if the graph doesn't contain the child node.
76 |  |
         */
77 | 24 |
        public void addChildTo( Object key, Object newChildKey )
78 |  |
              throws IllegalStateException {
79 | 24 |
           if ( !items.containsKey( newChildKey ) ) {
80 | 0 |
              throw new IllegalStateException(
81 |  |
                    "Attempt to add link to node that is not in the graph" );
82 |  |
           }
83 |  |
84 | 24 |
           if ( items.containsKey( key ) ) {
85 | 24 |
              ( ( DirectedGraphNode ) items.get( key ) ).addChild( newChildKey );
86 | 24 |
              ( ( DirectedGraphNode ) items.get( newChildKey ) ).addParent( key );
87 |  |
           }
88 |  |
89 |  |
        }
90 |  |
91 |  |
        /**
92 |  |
         * @param key Object
93 |  |
         * @param newParentKey Object
94 |  |
         * @param newParent Object
95 |  |
         */
96 | 0 |
        public void addParentTo( Object key, Object newParentKey, Object newParent ) {
97 | 0 |
           if ( !items.containsKey( newParent ) ) {
98 | 0 |
              this.addNode( newParentKey, newParent );
99 |  |
           }
100 |  |
101 | 0 |
           this.addChildTo( key, newParentKey );
102 | 0 |
           this.addParentTo( newParentKey, key );
103 |  |
        }
104 |  |
105 |  |
        /**
106 |  |
         * @param key Object
107 |  |
         * @param newParentKey Object
108 |  |
         * @throws IllegalStateException
109 |  |
         */
110 | 99 |
        public void addParentTo( Object key, Object newParentKey )
111 |  |
              throws IllegalStateException {
112 | 99 |
           if ( !items.containsKey( newParentKey ) ) {
113 | 0 |
              throw new IllegalStateException(
114 |  |
                    "Attempt to add link to node that is not in the graph" );
115 |  |
           }
116 |  |
117 | 99 |
           if ( items.containsKey( key ) ) {
118 | 99 |
              ( ( DirectedGraphNode ) items.get( key ) ).addParent( newParentKey );
119 | 99 |
              ( ( DirectedGraphNode ) items.get( newParentKey ) ).addChild( key );
120 |  |
           }
121 |  |
122 |  |
        }
123 |  |
124 |  |
        /**
125 |  |
         * Shows the tree as a tabbed list. Items that have no parents are shown at the 'highest' level.
126 |  |
         *
127 |  |
         * @return String
128 |  |
         */
129 | 3 |
        public String toString() {
130 | 3 |
           prune();
131 | 3 |
           this.topoSort();
132 | 3 |
           List nodes = new ArrayList( items.values() );
133 | 3 |
           Collections.sort( nodes );
134 | 3 |
           DirectedGraphNode root = ( DirectedGraphNode ) nodes.get( 0 );
135 | 3 |
           StringBuffer buf = new StringBuffer();
136 | 3 |
           int tablevel = 0;
137 | 3 |
           makeString( root, buf, tablevel );
138 | 3 |
           return ( buf.toString() );
139 |  |
        }
140 |  |
141 |  |
        /*
142 |  |
         * Helper for toString. Together with toString, demonstrates how to iterate over the tree
143 |  |
         */
144 | 76 |
        private String makeString( DirectedGraphNode startNode, StringBuffer buf,
145 |  |
              int tabLevel ) {
146 |  |
147 | 76 |
           if ( buf == null ) {
148 | 0 |
              buf = new StringBuffer();
149 |  |
           }
150 |  |
151 | 76 |
           Set children = startNode.getChildNodes();
152 |  |
153 | 76 |
           if ( !startNode.isVisited() ) {
154 | 3 |
              buf.append( startNode + "\n" );
155 | 3 |
              startNode.mark();
156 |  |
           }
157 | 76 |
           tabLevel++;
158 | 76 |
           for ( Iterator it = children.iterator(); it.hasNext(); ) {
159 | 73 |
              DirectedGraphNode f = ( DirectedGraphNode ) it.next();
160 | 73 |
              if ( !f.isVisited() ) {
161 | 73 |
                 for ( int i = 0; i < tabLevel; i++ ) {
162 | 283 |
                    buf.append( "\t" );
163 |  |
                 }
164 | 73 |
                 buf.append( f + "\n" );
165 | 73 |
                 f.mark();
166 | 73 |
                 this.makeString( f, buf, tabLevel );
167 |  |
              }
168 |  |
           }
169 |  |
170 | 76 |
           return buf.toString();
171 |  |
        }
172 |  |
173 |  |
        /**
174 |  |
         * Remove vertices to nodes that aren't in the graph.
175 |  |
         */
176 | 4 |
        public void prune() {
177 | 4 |
           for ( Iterator it = this.items.keySet().iterator(); it.hasNext(); ) {
178 | 91 |
              DirectedGraphNode v = ( DirectedGraphNode ) items.get( it.next() );
179 | 91 |
              v.prune();
180 |  |
           }
181 |  |
        }
182 |  |
183 |  |
        /**
184 |  |
         * Fills in the topoSortOrder for each node.
185 |  |
         */
186 | 4 |
        public void topoSort() {
187 | 4 |
           Queue q = new Queue();
188 | 4 |
           int counter = 0;
189 | 4 |
           DirectedGraphNode v;
190 | 4 |
           Map degrees = new HashMap();
191 |  |
192 |  |
           /* Get the degrees of all items, and enqueue zero-indegree nodes */
193 | 4 |
           for ( Iterator it = this.items.keySet().iterator(); it.hasNext(); ) {
194 | 93 |
              v = ( DirectedGraphNode ) items.get( it.next() );
195 | 93 |
              degrees.put( v, new Integer( v.inDegree() ) );
196 | 93 |
              if ( ( ( Integer ) degrees.get( v ) ).intValue() == 0 ) {
197 | 15 |
                 q.enqueue( v );
198 |  |
              }
199 |  |
           }
200 |  |
201 | 4 |
           while ( !q.isEmpty() ) {
202 | 93 |
              v = ( DirectedGraphNode ) q.dequeue();
203 | 93 |
              v.setTopoSortOrder( ++counter );
204 | 93 |
              for ( Iterator vit = v.getChildNodes().iterator(); vit.hasNext(); ) {
205 | 91 |
                 DirectedGraphNode w = ( DirectedGraphNode ) vit.next();
206 |  |
                 /* decrement the degree of this node */
207 | 91 |
                 int inDegree = ( ( Integer ) degrees.get( w ) ).intValue();
208 | 91 |
                 inDegree--;
209 | 91 |
                 degrees.put( w, new Integer( inDegree ) );
210 |  |
211 |  |
                 /* see if this now is one of the zero-indegree nodes */
212 | 91 |
                 if ( inDegree == 0 ) {
213 | 78 |
                    q.enqueue( w );
214 |  |
                 }
215 |  |
              }
216 |  |
           }
217 |  |
218 | 4 |
           if ( counter != items.size() ) {
219 | 0 |
              throw new IllegalStateException( "Graph contains a cycle; " + counter
220 |  |
                    + " items found, " + items.size() + " expected" );
221 |  |
           }
222 |  |
223 |  |
        }
224 |  |
225 |  |
        /**
226 |  |
         * Generate a JTree corresponding to this graph.
227 |  |
         *
228 |  |
         * @todo note that nodes are only allowed to have one parent in DefaultMutableTreeNodes
229 |  |
         * @return javax.swing.JTree
230 |  |
         */
231 | 0 |
        public JTree treeView() {
232 | 0 |
           this.topoSort();
233 | 0 |
           List nodes = new ArrayList( items.values() );
234 | 0 |
           Collections.sort( nodes );
235 | 0 |
           DirectedGraphNode root = ( DirectedGraphNode ) nodes.get( 0 );
236 | 0 |
           DefaultMutableTreeNode top = new DefaultMutableTreeNode( root );
237 | 0 |
           root.mark();
238 | 0 |
           addJTreeNode( top, root );
239 | 0 |
           JTree tree = new JTree( top );
240 | 0 |
           return tree;
241 |  |
        }
242 |  |
243 | 0 |
        private void addJTreeNode( DefaultMutableTreeNode startJTreeNode,
244 |  |
              DirectedGraphNode startNode ) {
245 | 0 |
           Set children = startNode.getChildNodes();
246 |  |
247 | 0 |
           for ( Iterator it = children.iterator(); it.hasNext(); ) {
248 | 0 |
              DirectedGraphNode nextNode = ( DirectedGraphNode ) it.next();
249 | 0 |
              if ( !nextNode.isVisited() ) {
250 | 0 |
                 DefaultMutableTreeNode newJTreeNode = new DefaultMutableTreeNode(
251 |  |
                       nextNode );
252 | 0 |
                 startJTreeNode.add( newJTreeNode );
253 | 0 |
                 nextNode.mark();
254 | 0 |
                 this.addJTreeNode( newJTreeNode, nextNode );
255 |  |
              }
256 |  |
           }
257 |  |
258 |  |
        }
259 |  |
260 |  |
     }