001: package prefuse.data;
002:
003: import java.util.Iterator;
004: import java.util.logging.Logger;
005:
006: import prefuse.util.PrefuseConfig;
007: import prefuse.util.collections.IntIterator;
008:
009: /**
010: * <p>Graph subclass that models a tree structure of hierarchical
011: * parent-child relationships. For each edge, the source node is considered
012: * the parent, and the target node is considered the child. For the tree
013: * structure to be valid, each node can have at most one parent, and hence
014: * only one edge for which that node is the target. In addition to the methods
015: * of the Graph class, the tree also supports methods for navigating the tree
016: * structure, such as accessing parent or children nodes and next or previous
017: * sibling nodes (siblings are children nodes with a shared parent). Unlike the
018: * graph class, the default source and target key field names are renamed to
019: * {@link #DEFAULT_SOURCE_KEY} and {@link #DEFAULT_TARGET_KEY}.
020: * Like the {@link Graph} class, Trees are backed by node and edge
021: * tables, and use {@link prefuse.data.Node} and
022: * {@link prefuse.data.Edge} instances to provide object-oriented access
023: * to nodes and edges.</p>
024: *
025: * <p>The Tree class does not currently enforce that the graph structure remain
026: * a valid tree. This is to allow a chain of editing operations that may break
027: * the tree structure at some point before repairing it. Use the
028: * {@link #isValidTree()} method to test the validity of a tree.</p>
029: *
030: * <p>By default, the {@link #getSpanningTree()} method simply returns a
031: * reference to this Tree instance. However, if a spanning tree is created at a
032: * new root u sing the {@link #getSpanningTree(Node)} method, a new
033: * {@link SpanningTree} instance is generated.</p>
034: *
035: * @author <a href="http://jheer.org">jeffrey heer</a>
036: */
037: public class Tree extends Graph {
038:
039: private static final Logger s_logger = Logger.getLogger(Tree.class
040: .getName());
041:
042: /** Default data field used to denote the source node in an edge table */
043: public static final String DEFAULT_SOURCE_KEY = PrefuseConfig
044: .get("data.tree.sourceKey");
045: /** Default data field used to denote the target node in an edge table */
046: public static final String DEFAULT_TARGET_KEY = PrefuseConfig
047: .get("data.tree.targetKey");
048:
049: // implement as graph with limitations on edge settings
050: // catch external modification events and throw exceptions as necessary
051:
052: /** The node table row number for the root node of the tree. */
053: protected int m_root = -1;
054:
055: // ------------------------------------------------------------------------
056: // Constructors
057:
058: /**
059: * Create a new, empty Tree.
060: */
061: public Tree() {
062: super (new Table(), false);
063: }
064:
065: /**
066: * Create a new Tree.
067: * @param nodes the backing table to use for node data.
068: * Node instances of this graph will get their data from this table.
069: * @param edges the backing table to use for edge data.
070: * Edge instances of this graph will get their data from this table.
071: */
072: public Tree(Table nodes, Table edges) {
073: this (nodes, edges, DEFAULT_SOURCE_KEY, DEFAULT_TARGET_KEY);
074: }
075:
076: /**
077: * Create a new Tree.
078: * @param nodes the backing table to use for node data.
079: * Node instances of this graph will get their data from this table.
080: * @param edges the backing table to use for edge data.
081: * Edge instances of this graph will get their data from this table.
082: * @param sourceKey data field used to denote the source node in an edge
083: * table
084: * @param targetKey data field used to denote the target node in an edge
085: * table
086: */
087: public Tree(Table nodes, Table edges, String sourceKey,
088: String targetKey) {
089: this (nodes, edges, DEFAULT_NODE_KEY, sourceKey, targetKey);
090: }
091:
092: /**
093: * Create a new Tree.
094: * @param nodes the backing table to use for node data.
095: * Node instances of this graph will get their data from this table.
096: * @param edges the backing table to use for edge data.
097: * Edge instances of this graph will get their data from this table.
098: * @param nodeKey data field used to uniquely identify a node. If this
099: * field is null, the node table row numbers will be used
100: * @param sourceKey data field used to denote the source node in an edge
101: * table
102: * @param targetKey data field used to denote the target node in an edge
103: * table
104: */
105: public Tree(Table nodes, Table edges, String nodeKey,
106: String sourceKey, String targetKey) {
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)
298: return -1;
299: int[] links = (int[]) m_links.get(node, OUTLINKS);
300: return getTargetNode(links[idx]);
301: }
302:
303: /**
304: * Get the child node at the given index.
305: * @param node the parent Node
306: * @param idx the child index
307: * @return the child Node
308: */
309: public Node getChild(Node node, int idx) {
310: int c = getChildRow(node.getRow(), idx);
311: return (c < 0 ? null : getNode(c));
312: }
313:
314: /**
315: * Get the child index (order number of the child) for the given parent
316: * node id and child node id.
317: * @param parent the parent node id (node table row number)
318: * @param child the child node id (node table row number)
319: * @return the index of the child, or -1 if the given child node is not
320: * actually a child of the given parent node, or either node is
321: * invalud.
322: */
323: public int getChildIndex(int parent, int child) {
324: if (getParent(child) != parent)
325: return -1;
326: return m_links.getInt(child, CHILDINDEX);
327: }
328:
329: /**
330: * Get the child index (order number of the child) for the given parent
331: * and child nodes.
332: * @param p the parent Node
333: * @param c the child Node
334: * @return the index of the child, or -1 if the given child node is not
335: * actually a child of the given parent node, or either node is
336: * invalud.
337: */
338: public int getChildIndex(Node p, Node c) {
339: return getChildIndex(p.getRow(), c.getRow());
340: }
341:
342: /**
343: * Get the node id of the first child of the given parent node id.
344: * @param node the parent node id (node table row number)
345: * @return the node id of the first child
346: */
347: public int getFirstChildRow(int node) {
348: return getChildRow(node, 0);
349: }
350:
351: /**
352: * Get the first child node of the given parent node.
353: * @param node the parent Node
354: * @return the first child Node
355: */
356: public Node getFirstChild(Node node) {
357: return getChild(node, 0);
358: }
359:
360: /**
361: * Get the node id of the last child of the given parent node id.
362: * @param node the parent node id (node table row number)
363: * @return the node id of the last child
364: */
365: public int getLastChildRow(int node) {
366: return getChildRow(node, getChildCount(node) - 1);
367: }
368:
369: /**
370: * Get the last child node of the given parent node.
371: * @param node the parent Node
372: * @return the last child Node
373: */
374: public Node getLastChild(Node node) {
375: return getChild(node, node.getChildCount() - 1);
376: }
377:
378: /**
379: * Get the node id of the previous sibling of the given node id.
380: * @param node a node id (node table row number)
381: * @return the node id of the previous sibling, or -1 if there
382: * is no previous sibling.
383: */
384: public int getPreviousSiblingRow(int node) {
385: int p = getParent(node);
386: if (p < 0)
387: return -1;
388: int[] links = (int[]) m_links.get(p, OUTLINKS);
389: int idx = m_links.getInt(node, CHILDINDEX);
390: return (idx <= 0 ? -1 : getTargetNode(links[idx - 1]));
391: }
392:
393: /**
394: * Get the previous sibling of the given node.
395: * @param node a node
396: * @return the previous sibling, or null if there is no previous sibling
397: */
398: public Node getPreviousSibling(Node node) {
399: int n = getPreviousSiblingRow(node.getRow());
400: return (n < 0 ? null : getNode(n));
401: }
402:
403: /**
404: * Get the node id of the next sibling of the given node id.
405: * @param node a node id (node table row number)
406: * @return the node id of the next sibling, or -1 if there
407: * is no next sibling.
408: */
409: public int getNextSiblingRow(int node) {
410: int p = getParent(node);
411: if (p < 0)
412: return -1;
413: int[] links = (int[]) m_links.get(p, OUTLINKS);
414: int idx = m_links.getInt(node, CHILDINDEX);
415: int max = getChildCount(p) - 1;
416: return (idx < 0 || idx >= max ? -1
417: : getTargetNode(links[idx + 1]));
418: }
419:
420: /**
421: * Get the next sibling of the given node.
422: * @param node a node
423: * @return the next sibling, or null if there is no next sibling
424: */
425: public Node getNextSibling(Node node) {
426: int n = getNextSiblingRow(node.getRow());
427: return (n < 0 ? null : getNode(n));
428: }
429:
430: /**
431: * Get the depth of the given node id in the tree.
432: * @param node a node id (node table row number)
433: * @return the depth of the node in tree. The root node
434: * is at a depth level of 0, with each child at a greater
435: * depth level. -1 is returned if the input node id is not
436: * in the tree.
437: */
438: public int getDepth(int node) {
439: if (!getNodeTable().isValidRow(node))
440: return -1;
441:
442: int depth = 0;
443: if (node != m_root && getParent(node) < 0)
444: return -1;
445: for (int i = node; i != m_root && i >= 0; ++depth, i = getParent(i))
446: ;
447: return depth;
448: }
449:
450: /**
451: * Get the number of children of the given node id.
452: * @param node a node id (node table row number)
453: * @return the number of child nodes for the given node
454: */
455: public int getChildCount(int node) {
456: return getOutDegree(node);
457: }
458:
459: /**
460: * Get the edge id of the edge to the given node's parent.
461: * @param node the node id (node table row number)
462: * @return the edge id (edge table row number) of the parent edge
463: */
464: public int getParentEdge(int node) {
465: if (getInDegree(node) > 0) {
466: int[] inlinks = (int[]) m_links.get(node, INLINKS);
467: return inlinks[0];
468: } else {
469: return -1;
470: }
471: }
472:
473: /**
474: * Get the edge to the given node's parent.
475: * @param n a Node instance
476: * @return the parent Edge connecting the given node to its parent
477: */
478: public Edge getParentEdge(Node n) {
479: nodeCheck(n, true);
480: int pe = getParentEdge(n.getRow());
481: return (pe < 0 ? null : getEdge(pe));
482: }
483:
484: /**
485: * Get a node's parent node id
486: * @param node the child node id (node table row number)
487: * @return the parent node id, or -1 if there is no parent
488: */
489: public int getParent(int node) {
490: int pe = getParentEdge(node);
491: return (pe < 0 ? -1 : getSourceNode(pe));
492: }
493:
494: /**
495: * Get a node's parent node
496: * @param n the child node
497: * @return the parent node, or null if there is no parent
498: */
499: public Node getParent(Node n) {
500: int p = getParent(n.getRow());
501: return (p < 0 ? null : getNode(p));
502: }
503:
504: // ------------------------------------------------------------------------
505: // Iterators
506:
507: /**
508: * Get an iterator over the edge ids for edges connecting child nodes to
509: * a given parent
510: * @param node the parent node id (node table row number)
511: * @return an iterator over the edge ids for edges conencting child nodes
512: * to a given parent
513: */
514: public IntIterator childEdgeRows(int node) {
515: return super .outEdgeRows(node);
516: }
517:
518: /**
519: * Get an iterator over the edges connecting child nodes to a given parent
520: * @param n the parent node
521: * @return an iterator over the edges connecting child nodes to a given
522: * parent
523: */
524: public Iterator childEdges(Node n) {
525: return super .outEdges(n);
526: }
527:
528: /**
529: * Get an iterator over the child nodes of a parent node.
530: * @param n the parent node
531: * @return an iterator over the child nodes of a parent node
532: */
533: public Iterator children(Node n) {
534: return super .outNeighbors(n);
535: }
536:
537: // ------------------------------------------------------------------------
538: // Sanity Test
539:
540: /**
541: * Check that the underlying graph structure forms a valid tree.
542: * @return true if this is a valid tree, false otherwise
543: */
544: public boolean isValidTree() {
545: // TODO: write a visitor interface and use that instead?
546: int nnodes = getNodeCount();
547: int nedges = getEdgeCount();
548:
549: // first make sure there are n nodes and n-1 edges
550: if (nnodes != nedges + 1) {
551: s_logger.warning("Node/edge counts incorrect.");
552: return false;
553: }
554:
555: // iterate through nodes, make sure each one has the right
556: // number of parents
557: int root = getRootRow();
558: IntIterator nodes = getNodeTable().rows();
559: while (nodes.hasNext()) {
560: int n = nodes.nextInt();
561: int id = getInDegree(n);
562: if (n == root && id > 0) {
563: s_logger.warning("Root node has a parent.");
564: return false;
565: } else if (id > 1) {
566: s_logger
567: .warning("Node " + n + " has multiple parents.");
568: return false;
569: }
570: }
571:
572: // now do a traversal and make sure we visit everything
573: int[] counts = new int[] { 0, nedges };
574: isValidHelper(getRootRow(), counts);
575: if (counts[0] > nedges) {
576: s_logger.warning("The tree has non-tree edges in it.");
577: return false;
578: }
579: if (counts[0] < nedges) {
580: s_logger.warning("Not all of the tree was visited. "
581: + "Only " + counts[0] + "/" + nedges
582: + " edges encountered");
583: return false;
584: }
585: return true;
586: }
587:
588: /**
589: * isValidTree's recursive helper method.
590: */
591: private void isValidHelper(int node, int[] counts) {
592: IntIterator edges = childEdgeRows(node);
593: int ncount = 0;
594: while (edges.hasNext()) {
595: // get next edge, increment count
596: int edge = edges.nextInt();
597: ++ncount;
598: ++counts[0];
599: // visit the next edge
600: int c = getAdjacentNode(edge, node);
601: isValidHelper(c, counts);
602: // check the counts
603: if (counts[0] > counts[1])
604: return;
605: }
606: }
607:
608: // ------------------------------------------------------------------------
609: // Spanning Tree Methods
610:
611: /**
612: * Returns a spanning tree over this tree. If no spanning tree
613: * has been constructed at an alternative root, this method simply returns
614: * a pointer to this Tree instance. If a spanning tree rooted at an
615: * alternative node has been created, that tree is returned.
616: *
617: * @return a spanning tree over this tree
618: * @see #getSpanningTree(Node)
619: * @see Graph#clearSpanningTree()
620: */
621: public Tree getSpanningTree() {
622: return m_spanning == null ? this : m_spanning;
623: }
624:
625: /**
626: * Returns a spanning tree over this tree, rooted at the given root. If
627: * the given root is not the same as that of this Tree, a new spanning
628: * tree instance will be constructed, made the current spanning tree
629: * for this Tree instance, and returned.
630: *
631: * To clear out any generated spanning trees use the clearSpanningTree()
632: * method of the Graph class. After calling clearSpanningTree(), the
633: * getSpanningTree() method (with no arguments) will return a pointer
634: * to this Tree instance instead of any generated spanning trees.
635: *
636: * @param root the node at which to root the spanning tree.
637: * @return a spanning tree over this tree, rooted at the given root
638: * @see #getSpanningTree()
639: * @see Graph#clearSpanningTree()
640: */
641: public Tree getSpanningTree(Node root) {
642: nodeCheck(root, true);
643: if (m_spanning == null) {
644: if (m_root == root.getRow()) {
645: return this ;
646: } else {
647: m_spanning = new SpanningTree(this , root);
648: }
649: } else if (m_spanning.getRoot() != root) {
650: m_spanning.buildSpanningTree(root);
651: }
652: return m_spanning;
653: }
654:
655: // ------------------------------------------------------------------------
656: // Tree Linkage Schema (appended to the Graph Linkage Schema)
657:
658: /** Links table data field storing the index number of a child node */
659: protected static final String CHILDINDEX = "_childIndex";
660: /** Schema addition to be added onto {@link Graph#LINKS_SCHEMA}. */
661: protected static final Schema TREE_LINKS_SCHEMA = new Schema();
662: static {
663: TREE_LINKS_SCHEMA.addColumn(CHILDINDEX, int.class, new Integer(
664: -1));
665: TREE_LINKS_SCHEMA.lockSchema();
666: }
667:
668: } // end of class Tree
|