prefuse.data
Class Tree<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>

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

public class Tree<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
extends Graph<T,N,E>
implements DeclarativeTree<N,E>

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
protected  class Tree.TreeIntArrayList
           
 
Nested classes/interfaces inherited from class prefuse.data.Graph
Graph.IntArrayList, 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(Table<N> nodes, Table<E> edges)
          Create a new Tree.
Tree(Table<N> nodes, Table<E> edges, java.lang.String sourceKey, java.lang.String targetKey)
          Create a new Tree.
Tree(Table<N> nodes, Table<E> 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.
 N 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.
 E addChildEdge(Node<?,?> parent, Node<?,?> child)
          Add a child edge between the given nodes.
 N addRoot()
          Add a new root node to an empty Tree.
 int addRootRow()
          Add a new root node to an empty Tree.
 java.util.List<java.lang.Integer> childEdgeRows(int node)
          Get an iterator over the edge ids for edges connecting child nodes to a given parent
 java.util.List<E> childEdges(N n)
          Get an iterator over the edges connecting child nodes to a given parent
 java.util.List<N> children(N n)
          Get an iterator over the child nodes of a parent node.
protected  Table<TableTuple<?>> createLinkTable()
          Instantiate and return the link table.
static Tree<TableTuple<?>,TableNode,TableEdge> createTree()
          Create a new, empty Tree.
 java.util.List<java.lang.Integer> edgeRows(int node, int direction)
          Get an iterator edge ids for edges incident on the given node.
 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 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.
 int getDepth(N n)
          Get the depth of the given node in the tree.
 int getFirstChildRow(int node)
          Get the node id of the first child of the given parent node id.
 int getLastChildRow(int node)
          Get the node id of the last child of the given parent node id.
 N getNextSibling(N 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
 N getParent(N n)
          Get a node's parent node
 int getParentEdge(int node)
          Get the edge id of the edge to the given node's parent.
 E getParentEdge(N n)
          Get the edge to the given node's parent.
 N getPreviousSibling(N 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.
 N getRoot()
          Get the root node.
 int getRootRow()
          Get the root node id (node table row number).
 DeclarativeTree<N,E> getSpanningTree()
          Returns a spanning tree over this tree.
 DeclarativeTree<N,E> getSpanningTree(N 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, createGraph, createGraph, createGraph, createGraph, createGraph, dispose, edgeCheck, 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
 
Methods inherited from interface prefuse.data.tree.DeclarativeTree
getNodeCount
 

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(Table<N> nodes,
            Table<E> 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<N> nodes,
            Table<E> 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<N> nodes,
            Table<E> 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

createTree

public static Tree<TableTuple<?>,TableNode,TableEdge> createTree()
Create a new, empty Tree.


createLinkTable

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

Overrides:
createLinkTable in class Graph<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
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<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
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 N 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 N 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 E 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 N getRoot()
Get the root node.

Specified by:
getRoot in interface DeclarativeTree<N extends Node<N,E>,E extends Edge<N,E>>
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)

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 invalid.

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

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

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 N getPreviousSibling(N node)
Get the previous sibling of the given node.

Specified by:
getPreviousSibling in interface DeclarativeTree<N extends Node<N,E>,E extends Edge<N,E>>
Parameters:
node - a node
Returns:
the previous sibling, or null if there is no previous sibling

edgeRows

public java.util.List<java.lang.Integer> edgeRows(int node,
                                                  int direction)
Description copied from class: Graph
Get an iterator edge ids for edges incident on the given node.

Overrides:
edgeRows in class Graph<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
Parameters:
node - a node id (node table row number)
direction - the directionality of the edges to include. One of Graph.INEDGES (for in-linking edges), Graph.OUTEDGES (for out-linking edges), or Graph.UNDIRECTED (for all edges).
Returns:
an iterator over all edge ids for edges incident on the given node

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 N getNextSibling(N node)
Get the next sibling of the given node.

Specified by:
getNextSibling in interface DeclarativeTree<N extends Node<N,E>,E extends Edge<N,E>>
Parameters:
node - a node
Returns:
the next sibling, or null if there is no next sibling

getDepth

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

Specified by:
getDepth in interface DeclarativeTree<N extends Node<N,E>,E extends Edge<N,E>>
Parameters:
node - a node
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 is not in the tree.

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 E getParentEdge(N n)
Get the edge to the given node's parent.

Specified by:
getParentEdge in interface DeclarativeTree<N extends Node<N,E>,E extends Edge<N,E>>
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 N getParent(N n)
Get a node's parent node

Specified by:
getParent in interface DeclarativeTree<N extends Node<N,E>,E extends Edge<N,E>>
Parameters:
n - the child node
Returns:
the parent node, or null if there is no parent

childEdgeRows

public java.util.List<java.lang.Integer> 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.List<E> childEdges(N n)
Get an iterator over the edges connecting child nodes to a given parent

Specified by:
childEdges in interface DeclarativeTree<N extends Node<N,E>,E extends Edge<N,E>>
Parameters:
n - the parent node
Returns:
an iterator over the edges connecting child nodes to a given parent

children

public java.util.List<N> children(N n)
Get an iterator over the child nodes of a parent node.

Specified by:
children in interface DeclarativeTree<N extends Node<N,E>,E extends Edge<N,E>>
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 DeclarativeTree<N,E> 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<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
Returns:
a spanning tree over this tree
See Also:
getSpanningTree(Node), Graph.clearSpanningTree()

getSpanningTree

public DeclarativeTree<N,E> getSpanningTree(N 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<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
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 © 2008 Regents of the University of California