prefuse.data
Class Tree

java.lang.Object
  extended by prefuse.data.tuple.AbstractTupleSet
      extended by prefuse.data.tuple.CompositeTupleSet
          extended by prefuse.data.Graph
              extended by prefuse.data.Tree
All Implemented Interfaces:
TupleSet
Direct Known Subclasses:
SpanningTree, VisualTree

public class Tree
extends Graph

Graph subclass that models a tree structure of hierarchical parent-child relationships. For each edge, the source node is considered the parent, and the target node is considered the child. For the tree structure to be valid, each node can have at most one parent, and hence only one edge for which that node is the target. In addition to the methods of the Graph class, the tree also supports methods for navigating the tree structure, such as accessing parent or children nodes and next or previous sibling nodes (siblings are children nodes with a shared parent). Unlike the graph class, the default source and target key field names are renamed to DEFAULT_SOURCE_KEY and DEFAULT_TARGET_KEY. Like the Graph class, Trees are backed by node and edge tables, and use Node and Edge instances to provide object-oriented access to nodes and edges.

The Tree class does not currently enforce that the graph structure remain a valid tree. This is to allow a chain of editing operations that may break the tree structure at some point before repairing it. Use the isValidTree() method to test the validity of a tree.

By default, the getSpanningTree() method simply returns a reference to this Tree instance. However, if a spanning tree is created at a new root u sing the getSpanningTree(Node) method, a new SpanningTree instance is generated.

Author:
jeffrey heer

Nested Class Summary
 
Nested classes/interfaces inherited from class prefuse.data.Graph
Graph.Listener
 
Field Summary
protected static java.lang.String CHILDINDEX
          Links table data field storing the index number of a child node
static java.lang.String DEFAULT_SOURCE_KEY
          Default data field used to denote the source node in an edge table
static java.lang.String DEFAULT_TARGET_KEY
          Default data field used to denote the target node in an edge table
protected  int m_root
          The node table row number for the root node of the tree.
protected static Schema TREE_LINKS_SCHEMA
          Schema addition to be added onto Graph.LINKS_SCHEMA.
 
Fields inherited from class prefuse.data.Graph
DEFAULT_NODE_KEY, EDGES, INDEGREE, INEDGES, INLINKS, LINKS_SCHEMA, m_directed, m_edgeTuples, m_links, m_longKey, m_nidx, m_nkey, m_nodeTuples, m_skey, m_spanning, m_tkey, NODES, OUTDEGREE, OUTEDGES, OUTLINKS, UNDIRECTED
 
Fields inherited from interface prefuse.data.tuple.TupleSet
EMPTY_ARRAY
 
Constructor Summary
Tree()
          Create a new, empty Tree.
Tree(Table nodes, Table edges)
          Create a new Tree.
Tree(Table nodes, Table edges, java.lang.String sourceKey, java.lang.String targetKey)
          Create a new Tree.
Tree(Table nodes, Table edges, java.lang.String nodeKey, java.lang.String sourceKey, java.lang.String targetKey)
          Create a new Tree.
 
Method Summary
 int addChild(int parent)
          Add a child node to the given parent node.
 Node addChild(Node parent)
          Add a child node to the given parent node.
 int addChildEdge(int parent, int child)
          Add a child edge between the given nodes.
 Edge addChildEdge(Node parent, Node child)
          Add a child edge between the given nodes.
 Node addRoot()
          Add a new root node to an empty Tree.
 int addRootRow()
          Add a new root node to an empty Tree.
 IntIterator childEdgeRows(int node)
          Get an iterator over the edge ids for edges connecting child nodes to a given parent
 java.util.Iterator childEdges(Node n)
          Get an iterator over the edges connecting child nodes to a given parent
 java.util.Iterator children(Node n)
          Get an iterator over the child nodes of a parent node.
protected  Table createLinkTable()
          Instantiate and return the link table.
 Node getChild(Node node, int idx)
          Get the child node at the given index.
 int getChildCount(int node)
          Get the number of children of the given node id.
 int getChildIndex(int parent, int child)
          Get the child index (order number of the child) for the given parent node id and child node id.
 int getChildIndex(Node p, Node c)
          Get the child index (order number of the child) for the given parent and child nodes.
 int getChildRow(int node, int idx)
          Get the child node id at the given index.
 int getDepth(int node)
          Get the depth of the given node id in the tree.
 Node getFirstChild(Node node)
          Get the first child node of the given parent node.
 int getFirstChildRow(int node)
          Get the node id of the first child of the given parent node id.
 Node getLastChild(Node node)
          Get the last child node of the given parent node.
 int getLastChildRow(int node)
          Get the node id of the last child of the given parent node id.
 Node getNextSibling(Node node)
          Get the next sibling of the given node.
 int getNextSiblingRow(int node)
          Get the node id of the next sibling of the given node id.
 int getParent(int node)
          Get a node's parent node id
 Node getParent(Node n)
          Get a node's parent node
 int getParentEdge(int node)
          Get the edge id of the edge to the given node's parent.
 Edge getParentEdge(Node n)
          Get the edge to the given node's parent.
 Node getPreviousSibling(Node node)
          Get the previous sibling of the given node.
 int getPreviousSiblingRow(int node)
          Get the node id of the previous sibling of the given node id.
 Node getRoot()
          Get the root node.
 int getRootRow()
          Get the root node id (node table row number).
 Tree getSpanningTree()
          Returns a spanning tree over this tree.
 Tree getSpanningTree(Node root)
          Returns a spanning tree over this tree, rooted at the given root.
 boolean isValidTree()
          Check that the underlying graph structure forms a valid tree.
 boolean removeChild(int node)
          Remove a node and its entire subtree rooted at the node from the tree.
 boolean removeChild(Node n)
          Remove a node and its entire subtree rooted at the node from the tree.
 boolean removeChildEdge(Edge e)
          Remove a child edge from the Tree.
 boolean removeChildEdge(int edge)
          Remove a child edge from the Tree.
protected  void updateDegrees(int e, int s, int t, int incr)
          Internal method for updating the linkage of this graph.
 
Methods inherited from class prefuse.data.Graph
addEdge, addEdge, addGraphModelListener, addLink, addNode, addNodeRow, clear, clearEdges, clearSpanningTree, dispose, edgeCheck, edgeRows, edgeRows, edgeRows, edges, edges, fireGraphEvent, getAdjacentNode, getAdjacentNode, getDegree, getDegree, getEdge, getEdge, getEdge, getEdgeCount, getEdges, getEdgeSourceField, getEdgeTable, getEdgeTargetField, getInDegree, getInDegree, getKey, getNode, getNodeCount, getNodeFromKey, getNodeIndex, getNodeKeyField, getNodes, getNodeTable, getOutDegree, getOutDegree, getSourceNode, getSourceNode, getTargetNode, getTargetNode, inEdgeRows, inEdges, init, initLinkTable, inNeighbors, isDirected, neighbors, nodeCheck, nodeRows, nodes, outEdgeRows, outEdges, outNeighbors, remLink, removeAllGraphModelListeners, removeEdge, removeEdge, removeGraphModelListener, removeNode, removeNode, removeTuple, setEdgeTable, setTupleManagers, tuples, tuples, updateDegrees, updateNodeData
 
Methods inherited from class prefuse.data.tuple.CompositeTupleSet
addColumn, addColumn, addColumn, addColumn, addSet, addTuple, containsSet, containsTuple, getSet, getTupleCount, hasSet, isAddColumnSupported, removeAllSets, removeSet, setNames, sets, setTuple
 
Methods inherited from class prefuse.data.tuple.AbstractTupleSet
addColumns, addPropertyChangeListener, addPropertyChangeListener, addTupleSetListener, fireTupleEvent, fireTupleEvent, fireTupleEvent, getClientProperty, putClientProperty, removePropertyChangeListener, removePropertyChangeListener, removeTupleSetListener, tuples
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

DEFAULT_SOURCE_KEY

public static final java.lang.String DEFAULT_SOURCE_KEY
Default data field used to denote the source node in an edge table


DEFAULT_TARGET_KEY

public static final java.lang.String DEFAULT_TARGET_KEY
Default data field used to denote the target node in an edge table


m_root

protected int m_root
The node table row number for the root node of the tree.


CHILDINDEX

protected static final java.lang.String CHILDINDEX
Links table data field storing the index number of a child node

See Also:
Constant Field Values

TREE_LINKS_SCHEMA

protected static final Schema TREE_LINKS_SCHEMA
Schema addition to be added onto Graph.LINKS_SCHEMA.

Constructor Detail

Tree

public Tree()
Create a new, empty Tree.


Tree

public Tree(Table nodes,
            Table edges)
Create a new Tree.

Parameters:
nodes - the backing table to use for node data. Node instances of this graph will get their data from this table.
edges - the backing table to use for edge data. Edge instances of this graph will get their data from this table.

Tree

public Tree(Table nodes,
            Table edges,
            java.lang.String sourceKey,
            java.lang.String targetKey)
Create a new Tree.

Parameters:
nodes - the backing table to use for node data. Node instances of this graph will get their data from this table.
edges - the backing table to use for edge data. Edge instances of this graph will get their data from this table.
sourceKey - data field used to denote the source node in an edge table
targetKey - data field used to denote the target node in an edge table

Tree

public Tree(Table nodes,
            Table edges,
            java.lang.String nodeKey,
            java.lang.String sourceKey,
            java.lang.String targetKey)
Create a new Tree.

Parameters:
nodes - the backing table to use for node data. Node instances of this graph will get their data from this table.
edges - the backing table to use for edge data. Edge instances of this graph will get their data from this table.
nodeKey - data field used to uniquely identify a node. If this field is null, the node table row numbers will be used
sourceKey - data field used to denote the source node in an edge table
targetKey - data field used to denote the target node in an edge table
Method Detail

createLinkTable

protected Table createLinkTable()
Description copied from class: Graph
Instantiate and return the link table.

Overrides:
createLinkTable in class Graph
Returns:
the created link table
See Also:
Graph.createLinkTable()

updateDegrees

protected void updateDegrees(int e,
                             int s,
                             int t,
                             int incr)
Description copied from class: Graph
Internal method for updating the linkage of this graph.

Overrides:
updateDegrees in class Graph
Parameters:
e - the edge id for the updated link
s - the source node id for the updated link
t - the target node id for the updated link
incr - the increment value, 1 for an added link, -1 for a removed link
See Also:
Graph.updateDegrees(int, int, int, int)

addRootRow

public int addRootRow()
Add a new root node to an empty Tree.

Returns:
the node id (node table row number) of the new root node.

addRoot

public Node addRoot()
Add a new root node to an empty Tree.

Returns:
the newly added root Node

addChild

public int addChild(int parent)
Add a child node to the given parent node. An edge between the two will also be created.

Parameters:
parent - the parent node id (node table row number)
Returns:
the added child node id

addChild

public Node addChild(Node parent)
Add a child node to the given parent node. An edge between the two will also be created.

Parameters:
parent - the parent node
Returns:
the added child node

addChildEdge

public int addChildEdge(int parent,
                        int child)
Add a child edge between the given nodes.

Parameters:
parent - the parent node id (node table row number)
child - the child node id (node table row number)
Returns:
the added child edge id

addChildEdge

public Edge addChildEdge(Node parent,
                         Node child)
Add a child edge between the given nodes.

Parameters:
parent - the parent node
child - the child node
Returns:
the added child edge

removeChildEdge

public boolean removeChildEdge(int edge)
Remove a child edge from the Tree. The child node and its subtree will also be removed from the Tree.

Parameters:
edge - the edge id (edge table row number) of the edge to remove
Returns:
true if the edge and attached subtree is successfully removed, false otherwise

removeChildEdge

public boolean removeChildEdge(Edge e)
Remove a child edge from the Tree. The child node and its subtree will also be removed from the Tree.

Parameters:
e - the edge to remove
Returns:
true if the edge and attached subtree is successfully removed, false otherwise

removeChild

public boolean removeChild(int node)
Remove a node and its entire subtree rooted at the node from the tree.

Parameters:
node - the node id (node table row number) to remove
Returns:
true if the node and its subtree is successfully removed, false otherwise

removeChild

public boolean removeChild(Node n)
Remove a node and its entire subtree rooted at the node from the tree.

Parameters:
n - the node to remove
Returns:
true if the node and its subtree is successfully removed, false otherwise

getRootRow

public int getRootRow()
Get the root node id (node table row number).

Returns:
the root node id

getRoot

public Node getRoot()
Get the root node.

Returns:
the root Node

getChildRow

public int getChildRow(int node,
                       int idx)
Get the child node id at the given index.

Parameters:
node - the parent node id (node table row number)
idx - the child index
Returns:
the child node id (node table row number)

getChild

public Node getChild(Node node,
                     int idx)
Get the child node at the given index.

Parameters:
node - the parent Node
idx - the child index
Returns:
the child Node

getChildIndex

public int getChildIndex(int parent,
                         int child)
Get the child index (order number of the child) for the given parent node id and child node id.

Parameters:
parent - the parent node id (node table row number)
child - the child node id (node table row number)
Returns:
the index of the child, or -1 if the given child node is not actually a child of the given parent node, or either node is invalud.

getChildIndex

public int getChildIndex(Node p,
                         Node c)
Get the child index (order number of the child) for the given parent and child nodes.

Parameters:
p - the parent Node
c - the child Node
Returns:
the index of the child, or -1 if the given child node is not actually a child of the given parent node, or either node is invalud.

getFirstChildRow

public int getFirstChildRow(int node)
Get the node id of the first child of the given parent node id.

Parameters:
node - the parent node id (node table row number)
Returns:
the node id of the first child

getFirstChild

public Node getFirstChild(Node node)
Get the first child node of the given parent node.

Parameters:
node - the parent Node
Returns:
the first child Node

getLastChildRow

public int getLastChildRow(int node)
Get the node id of the last child of the given parent node id.

Parameters:
node - the parent node id (node table row number)
Returns:
the node id of the last child

getLastChild

public Node getLastChild(Node node)
Get the last child node of the given parent node.

Parameters:
node - the parent Node
Returns:
the last child Node

getPreviousSiblingRow

public int getPreviousSiblingRow(int node)
Get the node id of the previous sibling of the given node id.

Parameters:
node - a node id (node table row number)
Returns:
the node id of the previous sibling, or -1 if there is no previous sibling.

getPreviousSibling

public Node getPreviousSibling(Node node)
Get the previous sibling of the given node.

Parameters:
node - a node
Returns:
the previous sibling, or null if there is no previous sibling

getNextSiblingRow

public int getNextSiblingRow(int node)
Get the node id of the next sibling of the given node id.

Parameters:
node - a node id (node table row number)
Returns:
the node id of the next sibling, or -1 if there is no next sibling.

getNextSibling

public Node getNextSibling(Node node)
Get the next sibling of the given node.

Parameters:
node - a node
Returns:
the next sibling, or null if there is no next sibling

getDepth

public int getDepth(int node)
Get the depth of the given node id in the tree.

Parameters:
node - a node id (node table row number)
Returns:
the depth of the node in tree. The root node is at a depth level of 0, with each child at a greater depth level. -1 is returned if the input node id is not in the tree.

getChildCount

public int getChildCount(int node)
Get the number of children of the given node id.

Parameters:
node - a node id (node table row number)
Returns:
the number of child nodes for the given node

getParentEdge

public int getParentEdge(int node)
Get the edge id of the edge to the given node's parent.

Parameters:
node - the node id (node table row number)
Returns:
the edge id (edge table row number) of the parent edge

getParentEdge

public Edge getParentEdge(Node n)
Get the edge to the given node's parent.

Parameters:
n - a Node instance
Returns:
the parent Edge connecting the given node to its parent

getParent

public int getParent(int node)
Get a node's parent node id

Parameters:
node - the child node id (node table row number)
Returns:
the parent node id, or -1 if there is no parent

getParent

public Node getParent(Node n)
Get a node's parent node

Parameters:
n - the child node
Returns:
the parent node, or null if there is no parent

childEdgeRows

public IntIterator childEdgeRows(int node)
Get an iterator over the edge ids for edges connecting child nodes to a given parent

Parameters:
node - the parent node id (node table row number)
Returns:
an iterator over the edge ids for edges conencting child nodes to a given parent

childEdges

public java.util.Iterator childEdges(Node n)
Get an iterator over the edges connecting child nodes to a given parent

Parameters:
n - the parent node
Returns:
an iterator over the edges connecting child nodes to a given parent

children

public java.util.Iterator children(Node n)
Get an iterator over the child nodes of a parent node.

Parameters:
n - the parent node
Returns:
an iterator over the child nodes of a parent node

isValidTree

public boolean isValidTree()
Check that the underlying graph structure forms a valid tree.

Returns:
true if this is a valid tree, false otherwise

getSpanningTree

public Tree getSpanningTree()
Returns a spanning tree over this tree. If no spanning tree has been constructed at an alternative root, this method simply returns a pointer to this Tree instance. If a spanning tree rooted at an alternative node has been created, that tree is returned.

Overrides:
getSpanningTree in class Graph
Returns:
a spanning tree over this tree
See Also:
getSpanningTree(Node), Graph.clearSpanningTree()

getSpanningTree

public Tree getSpanningTree(Node root)
Returns a spanning tree over this tree, rooted at the given root. If the given root is not the same as that of this Tree, a new spanning tree instance will be constructed, made the current spanning tree for this Tree instance, and returned. To clear out any generated spanning trees use the clearSpanningTree() method of the Graph class. After calling clearSpanningTree(), the getSpanningTree() method (with no arguments) will return a pointer to this Tree instance instead of any generated spanning trees.

Overrides:
getSpanningTree in class Graph
Parameters:
root - the node at which to root the spanning tree.
Returns:
a spanning tree over this tree, rooted at the given root
See Also:
getSpanningTree(), Graph.clearSpanningTree()


Copyright 2007 Regents of the University of California