prefuse.data
Class Tree

java.lang.Object
  prefuse.data.tuple.AbstractTupleSet
      prefuse.data.tuple.CompositeTupleSet
          prefuse.data.Graph
              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()