Tree


1   package prefuse.data;
2   
3   import java.util.Iterator  ;
4   import java.util.logging.Logger  ;
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   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   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   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   sourceKey, String   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   nodeKey,
105             String   sourceKey, String   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  (
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   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   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   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  (-1));
656         TREE_LINKS_SCHEMA.lockSchema();
657     }
658     
659 } // end of class Tree
660
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags