Clover coverage report - baseCode - 0.2.5 Coverage timestamp: Tue Apr 12 2005 11:31:58 EDT FRAMES NO FRAMES |
file stats: | LOC: | 303 |  | Methods: | 27
| 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
DirectedGraphNode.java | 67.6% | 69.5% | 59.3% | 67.1% |

1 |  |
     package baseCode.dataStructure.graph;
2 |  |
3 |  |
     import java.util.Iterator;
4 |  |
     import java.util.LinkedHashSet;
5 |  |
     import java.util.Set;
6 |  |
7 |  |
     /**
8 |  |
      * A graph node that has the concept of parents and children. Keys can be anything, but probably Strings or Integers.
9 |  |
      * <p>
10 |  |
      * Copyright (c) Columbia University
11 |  |
      *
12 |  |
      * @author Paul Pavlidis
13 |  |
      * @version $Id: DirectedGraphNode.java,v 1.10 2004/07/27 03:18:58 pavlidis Exp $
14 |  |
      */
15 |  |
     public class DirectedGraphNode extends AbstractGraphNode implements Comparable {
16 |  |
17 |  |
        protected Set parents;
18 |  |
        // immeddiate parents, references to other GraphNodes by keys.
19 |  |
        protected Set children;
20 |  |
        // immediate children, references to other GraphNodes by keys.
21 |  |
22 |  |
        protected int topoSortOrder = 0;
23 |  |
24 |  |
        /**
25 |  |
         * @param key Object
26 |  |
         * @param value Object
27 |  |
         * @param graph Graph
28 |  |
         */
29 | 117 |
        public DirectedGraphNode( Object key, Object value, Graph graph ) {
30 | 117 |
           super( key, value, graph );
31 | 117 |
           parents = new LinkedHashSet();
32 | 117 |
           children = new LinkedHashSet();
33 |  |
        }
34 |  |
35 |  |
        /**
36 |  |
         * @param i int
37 |  |
         */
38 | 93 |
        public void setTopoSortOrder( int i ) {
39 | 93 |
           topoSortOrder = i;
40 |  |
        }
41 |  |
42 |  |
        /**
43 |  |
         * @return int
44 |  |
         */
45 | 359 |
        public int getTopoSortOrder() {
46 | 359 |
           return topoSortOrder;
47 |  |
        }
48 |  |
49 |  |
        /**
50 |  |
         * @param newChildKey Object
51 |  |
         */
52 | 126 |
        public void addChild( Object newChildKey ) {
53 | 126 |
           children.add( newChildKey );
54 |  |
        }
55 |  |
56 |  |
        /**
57 |  |
         * @param newParentKey Object
58 |  |
         */
59 | 127 |
        public void addParent( Object newParentKey ) {
60 | 127 |
           parents.add( newParentKey );
61 |  |
        }
62 |  |
63 |  |
        /**
64 |  |
         * @return Object
65 |  |
         */
66 | 0 |
        public Object getParentKeys() {
67 | 0 |
           return parents;
68 |  |
        }
69 |  |
70 |  |
        /**
71 |  |
         * @return Object
72 |  |
         */
73 | 0 |
        public Object getChildKeys() {
74 | 0 |
           return children;
75 |  |
        }
76 |  |
77 |  |
        /**
78 |  |
         * Get the immediate children of this node. References to the DirectedGraphNodes are given, as opposed to key values.
79 |  |
         *
80 |  |
         * @return Set containing the child nodes of this node.
81 |  |
         */
82 | 169 |
        public Set getChildNodes() {
83 | 169 |
           Set f = new LinkedHashSet();
84 | 169 |
           for ( Iterator i = this.getChildIterator(); i.hasNext(); ) {
85 | 164 |
              Object k = i.next();
86 | 164 |
              f.add( getGraph().get( k ) );
87 |  |
           }
88 | 169 |
           return f;
89 |  |
        }
90 |  |
91 |  |
        /**
92 |  |
         * Get the immediate parents of this node. References to the DirectedGraphNodes are given, as opposed to key values.
93 |  |
         *
94 |  |
         * @return Set
95 |  |
         */
96 | 0 |
        public Set getParentNodes() {
97 | 0 |
           Set f = new LinkedHashSet();
98 | 0 |
           for ( Iterator i = this.getParentIterator(); i.hasNext(); ) {
99 | 0 |
              Object k = i.next();
100 | 0 |
              f.add( getGraph().get( k ) );
101 |  |
           }
102 | 0 |
           return f;
103 |  |
        }
104 |  |
105 |  |
        /**
106 |  |
         * Get the subgraph starting from this node, including this node.
107 |  |
         *
108 |  |
         * @return Graph
109 |  |
         */
110 | 1 |
        public Graph getChildGraph() {
111 | 1 |
           Set k = this.getAllChildNodes();
112 | 1 |
           k.add( this );
113 |  |
114 | 1 |
           DirectedGraph returnVal = new DirectedGraph();
115 | 1 |
           for ( Iterator it = k.iterator(); it.hasNext(); ) {
116 | 4 |
              DirectedGraphNode m = ( DirectedGraphNode ) it.next();
117 | 4 |
              returnVal.addNode( ( DirectedGraphNode ) m.clone() );
118 |  |
           }
119 | 1 |
           returnVal.prune(); // failing to do this will cause all kinds of problems
120 | 1 |
           return returnVal;
121 |  |
        }
122 |  |
123 |  |
124 |  |
125 |  |
        /**
126 |  |
         * @return
127 |  |
         */
128 | 0 |
        public boolean isLeaf() {
129 | 0 |
           return children.size() == 0;
130 |  |
        }
131 |  |
132 |  |
        /**
133 |  |
         * @return int number of immediate children this node has.
134 |  |
         */
135 | 0 |
        public int outDegree() {
136 | 0 |
           return children.size();
137 |  |
        }
138 |  |
139 |  |
        /**
140 |  |
         * @return int number of immediate parents this node has.
141 |  |
         */
142 | 93 |
        public int inDegree() {
143 | 93 |
           return parents.size();
144 |  |
        }
145 |  |
146 |  |
        /**
147 |  |
         * @return int how many children this node has, determined recursively.
148 |  |
         */
149 | 0 |
        public int numChildren() {
150 | 0 |
           return getAllChildNodes( null ).size();
151 |  |
        }
152 |  |
153 |  |
        /**
154 |  |
         * @return int how many parents this node has, determined recursively.
155 |  |
         */
156 | 0 |
        public int numParents() {
157 | 0 |
           return getAllParentNodes( null ).size();
158 |  |
        }
159 |  |
160 |  |
        /**
161 |  |
         * Get all the children of this node, recursively.
162 |  |
         */
163 | 1 |
        public Set getAllChildNodes() {
164 | 1 |
           return this.getAllChildNodes( null );
165 |  |
        }
166 |  |
167 |  |
        /**
168 |  |
         * Get all the parents of this node, recursively.
169 |  |
         *
170 |  |
         * @return
171 |  |
         */
172 | 0 |
        public Set getAllParentNodes() {
173 | 0 |
           return this.getAllParentNodes( null );
174 |  |
        }
175 |  |
176 |  |
        /**
177 |  |
         * Check to see if this node has a particular immediate child.
178 |  |
         *
179 |  |
         * @param j Object
180 |  |
         * @return boolean
181 |  |
         */
182 | 0 |
        public boolean hasChild( Object j ) {
183 | 0 |
           return children.contains( j );
184 |  |
        }
185 |  |
186 |  |
        /**
187 |  |
         * Check to see if this node has a particular immediate parent.
188 |  |
         *
189 |  |
         * @param j Object
190 |  |
         * @return boolean
191 |  |
         */
192 | 0 |
        public boolean hasParent( Object j ) {
193 | 0 |
           return parents.contains( j );
194 |  |
        }
195 |  |
196 | 83 |
        public String toString() {
197 | 83 |
           return this.getItem().toString();
198 |  |
        }
199 |  |
200 |  |
        /**
201 |  |
         * Remove connections that are to nodes not contained in this graph
202 |  |
         */
203 | 91 |
        public void prune() {
204 | 91 |
           for ( Iterator it = this.getChildIterator(); it.hasNext(); ) {
205 | 89 |
              Object j = it.next();
206 | 89 |
              DirectedGraphNode k = ( DirectedGraphNode ) getGraph().get( j );
207 | 89 |
              if ( k == null ) {
208 | 0 |
                 if ( log.isDebugEnabled() ) {
209 | 0 |
                    log.debug( "Pruned child " + j + " from " + this );
210 |  |
                 }
211 | 0 |
                 children.remove( j );
212 |  |
              }
213 |  |
214 |  |
           }
215 |  |
216 | 91 |
           for ( Iterator it = this.getParentIterator(); it.hasNext(); ) {
217 | 90 |
              Object j = it.next();
218 | 90 |
              DirectedGraphNode k = ( DirectedGraphNode ) getGraph().get( j );
219 | 90 |
              if ( k == null ) {
220 | 1 |
                 if ( log.isDebugEnabled() ) {
221 | 1 |
                    log.debug( "Pruned parent " + j + " from " + this );
222 |  |
                 }
223 | 1 |
                 parents.remove( j );
224 |  |
              }
225 |  |
226 |  |
           }
227 |  |
228 |  |
        }
229 |  |
230 |  |
        /** ************* private methods *************** */
231 |  |
232 | 4 |
        private Set getAllChildNodes( Set list ) {
233 | 4 |
           if ( list == null ) {
234 | 1 |
              list = new LinkedHashSet();
235 |  |
           }
236 |  |
237 | 4 |
           for ( Iterator it = this.getChildIterator(); it.hasNext(); ) {
238 | 3 |
              Object j = it.next();
239 | 3 |
              list.add( getGraph().get( j ) );
240 | 3 |
              ( ( DirectedGraphNode ) getGraph().get( j ) ).getAllChildNodes( list );
241 |  |
           }
242 | 4 |
           return list;
243 |  |
        }
244 |  |
245 | 0 |
        private Set getAllParentNodes( Set list ) {
246 | 0 |
           if ( list == null ) {
247 | 0 |
              list = new LinkedHashSet();
248 |  |
           }
249 |  |
250 | 0 |
           for ( Iterator it = this.getParentIterator(); it.hasNext(); ) {
251 | 0 |
              Object j = it.next();
252 | 0 |
              list.add( getGraph().get( j ) );
253 | 0 |
              ( ( DirectedGraphNode ) getGraph().get( j ) ).getAllParentNodes( list );
254 |  |
           }
255 | 0 |
           return list;
256 |  |
        }
257 |  |
258 | 268 |
        private Iterator getChildIterator() {
259 | 268 |
           return children.iterator();
260 |  |
        }
261 |  |
262 | 95 |
        private Iterator getParentIterator() {
263 | 95 |
           return parents.iterator();
264 |  |
        }
265 |  |
266 |  |
        /**
267 |  |
         * Uses the topological sort order.
268 |  |
         *
269 |  |
         * @param o Object
270 |  |
         * @return int
271 |  |
         */
272 | 359 |
        public int compareTo( Object o ) {
273 | 359 |
           DirectedGraphNode k = ( DirectedGraphNode ) o;
274 | 359 |
           int ord = k.getTopoSortOrder();
275 | 359 |
           if ( ord < this.topoSortOrder ) {
276 | 168 |
              return 1;
277 | 191 |
           } else if ( ord > this.topoSortOrder ) {
278 | 191 |
              return -1;
279 |  |
           }
280 | 0 |
           return 0;
281 |  |
        }
282 |  |
283 |  |
        /**
284 |  |
         * Makes a copy of this node. It does not make a deep copy of the contents. This should be used when making
285 |  |
         * subgraphs.
286 |  |
         *
287 |  |
         * @return Object
288 |  |
         */
289 | 4 |
        public Object clone() {
290 | 4 |
           DirectedGraphNode r = new DirectedGraphNode( key, item, graph );
291 | 4 |
           for ( Iterator it = this.getParentIterator(); it.hasNext(); ) {
292 | 4 |
              Object j = it.next();
293 | 4 |
              r.addParent( j );
294 |  |
           }
295 |  |
296 | 4 |
           for ( Iterator it = this.getChildIterator(); it.hasNext(); ) {
297 | 3 |
              Object j = it.next();
298 | 3 |
              r.addChild( j );
299 |  |
           }
300 | 4 |
           return r;
301 |  |
        }
302 |  |
303 |  |
     }