KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > prefuse > data > Tree


1 package prefuse.data;
2
3 import java.util.Iterator JavaDoc;
4 import java.util.logging.Logger JavaDoc;
5
6 import prefuse.util.PrefuseConfig;
7 import prefuse.util.collections.IntIterator;
8
9 /**
10  * <p>Graph subclass that models a tree structure of hierarchical
11  * parent-child relationships. For each edge, the source node is considered
12  * the parent, and the target node is considered the child. For the tree
13  * structure to be valid, each node can have at most one parent, and hence
14  * only one edge for which that node is the target. In addition to the methods
15  * of the Graph class, the tree also supports methods for navigating the tree
16  * structure, such as accessing parent or children nodes and next or previous
17  * sibling nodes (siblings are children nodes with a shared parent). Unlike the
18  * graph class, the default source and target key field names are renamed to
19  * {@link #DEFAULT_SOURCE_KEY} and {@link #DEFAULT_TARGET_KEY}.
20  * Like the {@link Graph} class, Trees are backed by node and edge
21  * tables, and use {@link prefuse.data.Node} and
22  * {@link prefuse.data.Edge} instances to provide object-oriented access
23  * to nodes and edges.</p>
24  *
25  * <p>The Tree class does not currently enforce that the graph structure remain
26  * a valid tree. This is to allow a chain of editing operations that may break
27  * the tree structure at some point before repairing it. Use the
28  * {@link #isValidTree()} method to test the validity of a tree.</p>
29  *
30  * <p>By default, the {@link #getSpanningTree()} method simply returns a
31  * reference to this Tree instance. However, if a spanning tree is created at a
32  * new root u sing the {@link #getSpanningTree(Node)} method, a new
33  * {@link SpanningTree} instance is generated.</p>
34  *
35  * @author <a HREF="http://jheer.org">jeffrey heer</a>
36  */

37 public class Tree extends Graph {
38
39     private static final Logger JavaDoc s_logger
40         = Logger.getLogger(Tree.class.getName());
41     
42     /** Default data field used to denote the source node in an edge table */
43     public static final String JavaDoc DEFAULT_SOURCE_KEY
44         = PrefuseConfig.get("data.tree.sourceKey");
45     /** Default data field used to denote the target node in an edge table */
46     public static final String JavaDoc DEFAULT_TARGET_KEY
47         = PrefuseConfig.get("data.tree.targetKey");
48     
49     // implement as graph with limitations on edge settings
50
// catch external modification events and throw exceptions as necessary
51

52     /** The node table row number for the root node of the tree. */
53     protected int m_root = -1;
54     
55     // ------------------------------------------------------------------------
56
// Constructors
57

58     /**
59      * Create a new, empty Tree.
60      */

61     public Tree() {
62         super(new Table(), false);
63     }
64     
65     /**
66      * Create a new Tree.
67      * @param nodes the backing table to use for node data.
68      * Node instances of this graph will get their data from this table.
69      * @param edges the backing table to use for edge data.
70      * Edge instances of this graph will get their data from this table.
71      */

72     public Tree(Table nodes, Table edges) {
73         this(nodes, edges, DEFAULT_SOURCE_KEY, DEFAULT_TARGET_KEY);
74     }
75
76     /**
77      * Create a new Tree.
78      * @param nodes the backing table to use for node data.
79      * Node instances of this graph will get their data from this table.
80      * @param edges the backing table to use for edge data.
81      * Edge instances of this graph will get their data from this table.
82      * @param sourceKey data field used to denote the source node in an edge
83      * table
84      * @param targetKey data field used to denote the target node in an edge
85      * table
86      */

87     public Tree(Table nodes, Table edges, String JavaDoc sourceKey, String JavaDoc targetKey) {
88         this(nodes, edges, DEFAULT_NODE_KEY, sourceKey, targetKey);
89     }
90     
91     /**
92      * Create a new Tree.
93      * @param nodes the backing table to use for node data.
94      * Node instances of this graph will get their data from this table.
95      * @param edges the backing table to use for edge data.
96      * Edge instances of this graph will get their data from this table.
97      * @param nodeKey data field used to uniquely identify a node. If this
98      * field is null, the node table row numbers will be used
99      * @param sourceKey data field used to denote the source node in an edge
100      * table
101      * @param targetKey data field used to denote the target node in an edge
102      * table
103      */

104     public Tree(Table nodes, Table edges, String JavaDoc nodeKey,
105             String JavaDoc sourceKey, String JavaDoc targetKey)
106     {
107         super(nodes, edges, false, nodeKey, sourceKey, targetKey);
108         
109         for ( IntIterator rows = nodes.rows(); rows.hasNext(); ) {
110             int n = rows.nextInt();
111             if ( getParent(n) < 0 ) {
112                 m_root = n;
113                 break;
114             }
115         }
116     }
117     
118     /**
119      * Internal method for setting the root node.
120      * @param root the root node to set
121      */

122     void setRoot(Node root) {
123         m_root = root.getRow();
124     }
125         
126     /**
127      * @see prefuse.data.Graph#createLinkTable()
128      */

129     protected Table createLinkTable() {
130         Table links = super.createLinkTable();
131         links.addColumns(TREE_LINKS_SCHEMA);
132         return links;
133     }
134     
135     /**
136      * @see prefuse.data.Graph#updateDegrees(int, int, int, int)
137      */

138     protected void updateDegrees(int e, int s, int t, int incr) {
139         super.updateDegrees(e, s, t, incr);
140         int od = getOutDegree(s);
141         if ( incr > 0 ) {
142             // if added, child index is the last index in child array
143
m_links.setInt(t, CHILDINDEX, od-1);
144         } else if ( incr < 0 ) {
145             // if removed, we renumber each child in the array
146
int[] links = (int[])m_links.get(s, OUTLINKS);
147             for ( int i=0; i<od; ++i ) {
148                 int n = getTargetNode(links[i]);
149                 m_links.setInt(n, CHILDINDEX, i);
150             }
151             m_links.setInt(t, CHILDINDEX, -1);
152         }
153     }
154     
155     // ------------------------------------------------------------------------
156
// Tree Mutators
157

158     /**
159      * Add a new root node to an empty Tree.
160      * @return the node id (node table row number) of the new root node.
161      */

162     public int addRootRow() {
163         if ( getNodeCount() != 0 ) {
164             throw new IllegalStateException JavaDoc(
165                     "Can only add a root node to an empty tree");
166         }
167         return (m_root = addNodeRow());
168     }
169     
170     /**
171      * Add a new root node to an empty Tree.
172      * @return the newly added root Node
173      */

174     public Node addRoot() {
175         return getNode(addRootRow());
176     }
177     
178     /**
179      * Add a child node to the given parent node. An edge between the two
180      * will also be created.
181      * @param parent the parent node id (node table row number)
182      * @return the added child node id
183      */

184     public int addChild(int parent) {
185         int child = super.addNodeRow();
186         addChildEdge(parent, child);
187         return child;
188     }
189     
190     /**
191      * Add a child node to the given parent node. An edge between the two
192      * will also be created.
193      * @param parent the parent node
194      * @return the added child node
195      */

196     public Node addChild(Node parent) {
197         nodeCheck(parent, true);
198         return getNode(addChild(parent.getRow()));
199     }
200     
201     /**
202      * Add a child edge between the given nodes.
203      * @param parent the parent node id (node table row number)
204      * @param child the child node id (node table row number)
205      * @return the added child edge id
206      */

207     public int addChildEdge(int parent, int child) {
208         return super.addEdge(parent, child);
209     }
210
211     /**
212      * Add a child edge between the given nodes.
213      * @param parent the parent node
214      * @param child the child node
215      * @return the added child edge
216      */

217     public Edge addChildEdge(Node parent, Node child) {
218         nodeCheck(parent, true);
219         nodeCheck(child, true);
220         return getEdge(addChildEdge(parent.getRow(), child.getRow()));
221     }
222     
223     /**
224      * Remove a child edge from the Tree. The child node and its subtree
225      * will also be removed from the Tree.
226      * @param edge the edge id (edge table row number) of the edge to remove
227      * @return true if the edge and attached subtree is successfully removed,
228      * false otherwise
229      */

230     public boolean removeChildEdge(int edge) {
231         return removeChild(getTargetNode(edge));
232     }
233
234     /**
235      * Remove a child edge from the Tree. The child node and its subtree
236      * will also be removed from the Tree.
237      * @param e the edge to remove
238      * @return true if the edge and attached subtree is successfully removed,
239      * false otherwise
240      */

241     public boolean removeChildEdge(Edge e) {
242         edgeCheck(e, true);
243         return removeChild(getTargetNode(e.getRow()));
244     }
245     
246     /**
247      * Remove a node and its entire subtree rooted at the node from the tree.
248      * @param node the node id (node table row number) to remove
249      * @return true if the node and its subtree is successfully removed,
250      * false otherwise
251      */

252     public boolean removeChild(int node) {
253         while ( getChildCount(node) > 0 ) {
254             removeChild(getLastChildRow(node));
255         }
256         return removeNode(node);
257     }
258     
259     /**
260      * Remove a node and its entire subtree rooted at the node from the tree.
261      * @param n the node to remove
262      * @return true if the node and its subtree is successfully removed,
263      * false otherwise
264      */

265     public boolean removeChild(Node n) {
266         nodeCheck(n, true);
267         return removeChild(n.getRow());
268     }
269     
270     // ------------------------------------------------------------------------
271
// Tree Accessors
272

273     /**
274      * Get the root node id (node table row number).
275      * @return the root node id
276      */

277     public int getRootRow() {
278         return m_root;
279     }
280     
281     /**
282      * Get the root node.
283      * @return the root Node
284      */

285     public Node getRoot() {
286         return (Node)m_nodeTuples.getTuple(m_root);
287     }
288
289     /**
290      * Get the child node id at the given index.
291      * @param node the parent node id (node table row number)
292      * @param idx the child index
293      * @return the child node id (node table row number)
294      */

295     public int getChildRow(int node, int idx) {
296         int cc = getChildCount(node);
297         if ( idx < 0 || idx >= cc ) return -1;
298         int[] links = (int[])m_links.get(node, OUTLINKS);
299         return getTargetNode(links[idx]);
300     }
301     
302     /**
303      * Get the child node at the given index.
304      * @param node the parent Node
305      * @param idx the child index
306      * @return the child Node
307      */

308     public Node getChild(Node node, int idx) {
309         int c = getChildRow(node.getRow(), idx);
310         return ( c<0 ? null : getNode(c) );
311     }
312     
313     /**
314      * Get the child index (order number of the child) for the given parent
315      * node id and child node id.
316      * @param parent the parent node id (node table row number)
317      * @param child the child node id (node table row number)
318      * @return the index of the child, or -1 if the given child node is not
319      * actually a child of the given parent node, or either node is
320      * invalud.
321      */

322     public int getChildIndex(int parent, int child) {
323         if ( getParent(child) != parent )
324             return -1;
325         return m_links.getInt(child, CHILDINDEX);
326     }
327     
328     /**
329      * Get the child index (order number of the child) for the given parent
330      * and child nodes.
331      * @param p the parent Node
332      * @param c the child Node
333      * @return the index of the child, or -1 if the given child node is not
334      * actually a child of the given parent node, or either node is
335      * invalud.
336      */

337     public int getChildIndex(Node p, Node c) {
338         return getChildIndex(p.getRow(), c.getRow());
339     }
340     
341     /**
342      * Get the node id of the first child of the given parent node id.
343      * @param node the parent node id (node table row number)
344      * @return the node id of the first child
345      */

346     public int getFirstChildRow(int node) {
347         return getChildRow(node, 0);
348     }
349
350     /**
351      * Get the first child node of the given parent node.
352      * @param node the parent Node
353      * @return the first child Node
354      */

355     public Node getFirstChild(Node node) {
356         return getChild(node, 0);
357     }
358     
359     /**
360      * Get the node id of the last child of the given parent node id.
361      * @param node the parent node id (node table row number)
362      * @return the node id of the last child
363      */

364     public int getLastChildRow(int node) {
365         return getChildRow(node, getChildCount(node)-1);
366     }
367     
368     /**
369      * Get the last child node of the given parent node.
370      * @param node the parent Node
371      * @return the last child Node
372      */

373     public Node getLastChild(Node node) {
374         return getChild(node, node.getChildCount()-1);
375     }
376     
377     /**
378      * Get the node id of the previous sibling of the given node id.
379      * @param node a node id (node table row number)
380      * @return the node id of the previous sibling, or -1 if there
381      * is no previous sibling.
382      */

383     public int getPreviousSiblingRow(int node) {
384         int p = getParent(node);
385         if ( p < 0 )
386             return -1;
387         int[] links = (int[])m_links.get(p, OUTLINKS);
388         int idx = m_links.getInt(node, CHILDINDEX);
389         return ( idx<=0 ? -1 : getTargetNode(links[idx-1]));
390     }
391     
392     /**
393      * Get the previous sibling of the given node.
394      * @param node a node
395      * @return the previous sibling, or null if there is no previous sibling
396      */

397     public Node getPreviousSibling(Node node) {
398         int n = getPreviousSiblingRow(node.getRow());
399         return ( n<0 ? null : getNode(n) );
400     }
401     
402     /**
403      * Get the node id of the next sibling of the given node id.
404      * @param node a node id (node table row number)
405      * @return the node id of the next sibling, or -1 if there
406      * is no next sibling.
407      */

408     public int getNextSiblingRow(int node) {
409         int p = getParent(node);
410         if ( p < 0 )
411             return -1;
412         int[] links = (int[])m_links.get(p, OUTLINKS);
413         int idx = m_links.getInt(node, CHILDINDEX);
414         int max = getChildCount(p)-1;
415         return ( idx<0 || idx>=max ? -1 : getTargetNode(links[idx+1]));
416     }
417     
418     /**
419      * Get the next sibling of the given node.
420      * @param node a node
421      * @return the next sibling, or null if there is no next sibling
422      */

423     public Node getNextSibling(Node node) {
424         int n = getNextSiblingRow(node.getRow());
425         return ( n<0 ? null : getNode(n) );
426     }
427     
428     /**
429      * Get the depth of the given node id in the tree.
430      * @param node a node id (node table row number)
431      * @return the depth of the node in tree. The root node
432      * is at a depth level of 0, with each child at a greater
433      * depth level. -1 is returned if the input node id is not
434      * in the tree.
435      */

436     public int getDepth(int node) {
437         if ( !getNodeTable().isValidRow(node) )
438             return -1;
439         
440         int depth = 0;
441         for ( int i=node; i!=m_root && i>=0; ++depth, i=getParent(i) );
442         return depth;
443     }
444     
445     /**
446      * Get the number of children of the given node id.
447      * @param node a node id (node table row number)
448      * @return the number of child nodes for the given node
449      */

450     public int getChildCount(int node) {
451         return getOutDegree(node);
452     }
453     
454     /**
455      * Get the edge id of the edge to the given node's parent.
456      * @param node the node id (node table row number)
457      * @return the edge id (edge table row number) of the parent edge
458      */

459     public int getParentEdge(int node) {
460         if ( getInDegree(node) > 0 ) {
461             int[] inlinks = (int[])m_links.get(node, INLINKS);
462             return inlinks[0];
463         } else {
464             return -1;
465         }
466     }
467     
468     /**
469      * Get the edge to the given node's parent.
470      * @param n a Node instance
471      * @return the parent Edge connecting the given node to its parent
472      */

473     public Edge getParentEdge(Node n) {
474         nodeCheck(n, true);
475         int pe = getParentEdge(n.getRow());
476         return ( pe < 0 ? null : getEdge(pe) );
477     }
478     
479     /**
480      * Get a node's parent node id
481      * @param node the child node id (node table row number)
482      * @return the parent node id, or -1 if there is no parent
483      */

484     public int getParent(int node) {
485         int pe = getParentEdge(node);
486         return ( pe < 0 ? -1 : getSourceNode(pe) );
487     }
488
489     /**
490      * Get a node's parent node
491      * @param n the child node
492      * @return the parent node, or null if there is no parent
493      */

494     public Node getParent(Node n) {
495         int p = getParent(n.getRow());
496         return ( p < 0 ? null : getNode(p) );
497     }
498     
499     // ------------------------------------------------------------------------
500
// Iterators
501

502     /**
503      * Get an iterator over the edge ids for edges connecting child nodes to
504      * a given parent
505      * @param node the parent node id (node table row number)
506      * @return an iterator over the edge ids for edges conencting child nodes
507      * to a given parent
508      */

509     public IntIterator childEdgeRows(int node) {
510         return super.outEdgeRows(node);
511     }
512     
513     /**
514      * Get an iterator over the edges connecting child nodes to a given parent
515      * @param n the parent node
516      * @return an iterator over the edges connecting child nodes to a given
517      * parent
518      */

519     public Iterator JavaDoc childEdges(Node n) {
520         return super.outEdges(n);
521     }
522     
523     /**
524      * Get an iterator over the child nodes of a parent node.
525      * @param n the parent node
526      * @return an iterator over the child nodes of a parent node
527      */

528     public Iterator JavaDoc children(Node n) {
529         return super.outNeighbors(n);
530     }
531     
532     // ------------------------------------------------------------------------
533
// Sanity Test
534

535     /**
536      * Check that the underlying graph structure forms a valid tree.
537      * @return true if this is a valid tree, false otherwise
538      */

539     public boolean isValidTree() {
540         // TODO: write a visitor interface and use that instead?
541
int nnodes = getNodeCount();
542         int nedges = getEdgeCount();
543         
544         // first make sure there are n nodes and n-1 edges
545
if ( nnodes != nedges+1 ) {
546             s_logger.warning("Node/edge counts incorrect.");
547             return false;
548         }
549         
550         // iterate through nodes, make sure each one has the right
551
// number of parents
552
int root = getRootRow();
553         IntIterator nodes = getNodeTable().rows();
554         while ( nodes.hasNext() ) {
555             int n = nodes.nextInt();
556             int id = getInDegree(n);
557             if ( n==root && id > 0 ) {
558                 s_logger.warning("Root node has a parent.");
559                 return false;
560             } else if ( id > 1 ) {
561                 s_logger.warning("Node "+n+" has multiple parents.");
562                 return false;
563             }
564         }
565         
566         // now do a traversal and make sure we visit everything
567
int[] counts = new int[] { 0, nedges };
568         isValidHelper(getRootRow(), counts);
569         if ( counts[0] > nedges ) {
570             s_logger.warning("The tree has non-tree edges in it.");
571             return false;
572         }
573         if ( counts[0] < nedges ) {
574             s_logger.warning("Not all of the tree was visited. " +
575                 "Only "+counts[0]+"/"+nedges+" edges encountered");
576             return false;
577         }
578         return true;
579     }
580     
581     /**
582      * isValidTree's recursive helper method.
583      */

584     private void isValidHelper(int node, int[] counts) {
585         IntIterator edges = childEdgeRows(node);
586         int ncount = 0;
587         while ( edges.hasNext() ) {
588             // get next edge, increment count
589
int edge = edges.nextInt();
590             ++ncount; ++counts[0];
591             // visit the next edge
592
int c = getAdjacentNode(edge, node);
593             isValidHelper(c, counts);
594             // check the counts
595
if ( counts[0] > counts[1] )
596                 return;
597         }
598     }
599
600     // ------------------------------------------------------------------------
601
// Spanning Tree Methods
602

603     /**
604      * Returns a spanning tree over this tree. If no spanning tree
605      * has been constructed at an alternative root, this method simply returns
606      * a pointer to this Tree instance. If a spanning tree rooted at an
607      * alternative node has been created, that tree is returned.
608      *
609      * @return a spanning tree over this tree
610      * @see #getSpanningTree(Node)
611      * @see Graph#clearSpanningTree()
612      */

613     public Tree getSpanningTree() {
614         return m_spanning==null ? this : m_spanning;
615     }
616     
617     /**
618      * Returns a spanning tree over this tree, rooted at the given root. If
619      * the given root is not the same as that of this Tree, a new spanning
620      * tree instance will be constructed, made the current spanning tree
621      * for this Tree instance, and returned.
622      *
623      * To clear out any generated spanning trees use the clearSpanningTree()
624      * method of the Graph class. After calling clearSpanningTree(), the
625      * getSpanningTree() method (with no arguments) will return a pointer
626      * to this Tree instance instead of any generated spanning trees.
627      *
628      * @param root the node at which to root the spanning tree.
629      * @return a spanning tree over this tree, rooted at the given root
630      * @see #getSpanningTree()
631      * @see Graph#clearSpanningTree()
632      */

633     public Tree getSpanningTree(Node root) {
634         nodeCheck(root, true);
635         if ( m_spanning == null ) {
636             if ( m_root == root.getRow() ) {
637                 return this;
638             } else {
639                 m_spanning = new SpanningTree(this, root);
640             }
641         } else if ( m_spanning.getRoot() != root ) {
642             m_spanning.buildSpanningTree(root);
643         }
644         return m_spanning;
645     }
646     
647     // ------------------------------------------------------------------------
648
// Tree Linkage Schema (appended to the Graph Linkage Schema)
649

650     /** Links table data field storing the index number of a child node */
651     protected static final String JavaDoc CHILDINDEX = "_childIndex";
652     /** Schema addition to be added onto {@link Graph#LINKS_SCHEMA}. */
653     protected static final Schema TREE_LINKS_SCHEMA = new Schema();
654     static {
655         TREE_LINKS_SCHEMA.addColumn(CHILDINDEX, int.class, new Integer JavaDoc(-1));
656         TREE_LINKS_SCHEMA.lockSchema();
657     }
658     
659 } // end of class Tree
660
Popular Tags