|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectprefuse.data.tuple.AbstractTupleSet<T>
prefuse.data.tuple.CompositeTupleSet<T>
prefuse.data.Graph<T,N,E>
prefuse.data.Tree<T,N,E>
public class Tree<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<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.
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.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 |
---|
public static final java.lang.String DEFAULT_SOURCE_KEY
public static final java.lang.String DEFAULT_TARGET_KEY
protected int m_root
protected static final java.lang.String CHILDINDEX
protected static final Schema TREE_LINKS_SCHEMA
Graph.LINKS_SCHEMA
.
Constructor Detail |
---|
public Tree(Table<N> nodes, Table<E> edges)
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.public Tree(Table<N> nodes, Table<E> edges, java.lang.String sourceKey, java.lang.String targetKey)
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
tabletargetKey
- data field used to denote the target node in an edge
tablepublic Tree(Table<N> nodes, Table<E> edges, java.lang.String nodeKey, java.lang.String sourceKey, java.lang.String targetKey)
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 usedsourceKey
- data field used to denote the source node in an edge
tabletargetKey
- data field used to denote the target node in an edge
tableMethod Detail |
---|
public static Tree<TableTuple<?>,TableNode,TableEdge> createTree()
protected Table<TableTuple<?>> createLinkTable()
Graph
createLinkTable
in class Graph<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
Graph.createLinkTable()
protected void updateDegrees(int e, int s, int t, int incr)
Graph
updateDegrees
in class Graph<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
e
- the edge id for the updated links
- the source node id for the updated linkt
- the target node id for the updated linkincr
- the increment value, 1 for an added link,
-1 for a removed linkGraph.updateDegrees(int, int, int, int)
public int addRootRow()
public N addRoot()
public int addChild(int parent)
parent
- the parent node id (node table row number)
public N addChild(Node<?,?> parent)
parent
- the parent node
public int addChildEdge(int parent, int child)
parent
- the parent node id (node table row number)child
- the child node id (node table row number)
public E addChildEdge(Node<?,?> parent, Node<?,?> child)
parent
- the parent nodechild
- the child node
public boolean removeChildEdge(int edge)
edge
- the edge id (edge table row number) of the edge to remove
public boolean removeChildEdge(Edge<?,?> e)
e
- the edge to remove
public boolean removeChild(int node)
node
- the node id (node table row number) to remove
public boolean removeChild(Node<?,?> n)
n
- the node to remove
public int getRootRow()
public N getRoot()
getRoot
in interface DeclarativeTree<N extends Node<N,E>,E extends Edge<N,E>>
public int getChildRow(int node, int idx)
node
- the parent node id (node table row number)idx
- the child index
public int getChildIndex(int parent, int child)
parent
- the parent node id (node table row number)child
- the child node id (node table row number)
public int getFirstChildRow(int node)
node
- the parent node id (node table row number)
public int getLastChildRow(int node)
node
- the parent node id (node table row number)
public int getPreviousSiblingRow(int node)
node
- a node id (node table row number)
public N getPreviousSibling(N node)
getPreviousSibling
in interface DeclarativeTree<N extends Node<N,E>,E extends Edge<N,E>>
node
- a node
public java.util.List<java.lang.Integer> edgeRows(int node, int direction)
Graph
edgeRows
in class Graph<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
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).
public int getNextSiblingRow(int node)
node
- a node id (node table row number)
public N getNextSibling(N node)
getNextSibling
in interface DeclarativeTree<N extends Node<N,E>,E extends Edge<N,E>>
node
- a node
public int getDepth(N n)
getDepth
in interface DeclarativeTree<N extends Node<N,E>,E extends Edge<N,E>>
node
- a node
public int getDepth(int node)
node
- a node id (node table row number)
public int getChildCount(int node)
node
- a node id (node table row number)
public int getParentEdge(int node)
node
- the node id (node table row number)
public E getParentEdge(N n)
getParentEdge
in interface DeclarativeTree<N extends Node<N,E>,E extends Edge<N,E>>
n
- a Node instance
public int getParent(int node)
node
- the child node id (node table row number)
public N getParent(N n)
getParent
in interface DeclarativeTree<N extends Node<N,E>,E extends Edge<N,E>>
n
- the child node
public java.util.List<java.lang.Integer> childEdgeRows(int node)
node
- the parent node id (node table row number)
public java.util.List<E> childEdges(N n)
childEdges
in interface DeclarativeTree<N extends Node<N,E>,E extends Edge<N,E>>
n
- the parent node
public java.util.List<N> children(N n)
children
in interface DeclarativeTree<N extends Node<N,E>,E extends Edge<N,E>>
n
- the parent node
public boolean isValidTree()
public DeclarativeTree<N,E> getSpanningTree()
getSpanningTree
in class Graph<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
getSpanningTree(Node)
,
Graph.clearSpanningTree()
public DeclarativeTree<N,E> getSpanningTree(N root)
getSpanningTree
in class Graph<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
root
- the node at which to root the spanning tree.
getSpanningTree()
,
Graph.clearSpanningTree()
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |