prefuse.data
Class SpanningTree<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>
                  extended by prefuse.data.SpanningTree<T,N,E>
All Implemented Interfaces:
DeclarativeTree<N,E>, TupleSet<T>

public class SpanningTree<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
extends Tree<T,N,E>

Special tree instance for storing a spanning tree over a graph instance. The spanning tree ensures that only Node and Edge instances from the backing Graph are returned, so requesting nodes, edges, or iterators over this spanning tree will return the desired Node or Edge tuples from the backing graph this tree spans.

Author:
jeffrey heer

Nested Class Summary
 
Nested classes/interfaces inherited from class prefuse.data.Tree
Tree.TreeIntArrayList
 
Nested classes/interfaces inherited from class prefuse.data.Graph
Graph.IntArrayList, Graph.Listener
 
Field Summary
protected static Schema EDGE_SCHEMA
          Edge table schema used by the spanning tree.
protected  Graph<T,N,E> m_backing
          A reference to the backing graph that this tree spans.
static java.lang.String SOURCE_EDGE
          Extra edge table data field recording the id of the source edge a tree edge represents.
 
Fields inherited from class prefuse.data.Tree
CHILDINDEX, DEFAULT_SOURCE_KEY, DEFAULT_TARGET_KEY, m_root, TREE_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
SpanningTree(Graph<T,N,E> g, N root)
          Create a new SpanningTree.
 
Method Summary
 int addChild(int parent)
          Unsupported operation.
 N addChild(Node<?,?> parent)
          Unsupported operation.
 int addChildEdge(int parent, int child)
          Unsupported operation.
 E addChildEdge(Node<?,?> parent, Node<?,?> child)
          Unsupported operation.
 int addEdge(int s, int t)
          Unsupported operation.
 E addEdge(Node<?,?> s, Node<?,?> t)
          Unsupported operation.
 N addNode()
          Unsupported operation.
 int addNodeRow()
          Unsupported operation.
 N addRoot()
          Unsupported operation.
 int addRootRow()
          Unsupported operation.
 void buildSpanningTree(N root)
          Build the spanning tree, starting at the given root.
 void clear()
          Unsupported operation.
 boolean removeChild(int node)
          Unsupported operation.
 boolean removeChild(Node<?,?> n)
          Unsupported operation.
 boolean removeChildEdge(Edge<?,?> e)
          Unsupported operation.
 boolean removeChildEdge(int edge)
          Unsupported operation.
 boolean removeEdge(Edge<?,?> e)
          Unsupported operation.
 boolean removeEdge(int edge)
          Unsupported operation.
 boolean removeNode(int node)
          Unsupported operation.
 boolean removeNode(Node<?,?> n)
          Unsupported operation.
 boolean removeTuple(Tuple<?> t)
          Unsupported operation.
 void setEdgeTable(Table<E> edges)
          Unsupported operation.
 void setTupleManagers(TupleManager<N> ntm, TupleManager<E> etm)
          Unsupported operation.
 
Methods inherited from class prefuse.data.Tree
childEdgeRows, childEdges, children, createLinkTable, createTree, edgeRows, getChildCount, getChildIndex, getChildRow, getDepth, getDepth, getFirstChildRow, getLastChildRow, getNextSibling, getNextSiblingRow, getParent, getParent, getParentEdge, getParentEdge, getPreviousSibling, getPreviousSiblingRow, getRoot, getRootRow, getSpanningTree, getSpanningTree, isValidTree, updateDegrees
 
Methods inherited from class prefuse.data.Graph
addGraphModelListener, addLink, 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, removeGraphModelListener, 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

SOURCE_EDGE

public static final java.lang.String SOURCE_EDGE
Extra edge table data field recording the id of the source edge a tree edge represents.

See Also:
Constant Field Values

EDGE_SCHEMA

protected static final Schema EDGE_SCHEMA
Edge table schema used by the spanning tree.


m_backing

protected Graph<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>> m_backing
A reference to the backing graph that this tree spans.

Constructor Detail

SpanningTree

public SpanningTree(Graph<T,N,E> g,
                    N root)
Create a new SpanningTree.

Parameters:
g - the backing Graph to span
root - the Node to use as the root of the spanning tree
Method Detail

buildSpanningTree

public void buildSpanningTree(N root)
Build the spanning tree, starting at the given root. Uses an unweighted breadth first traversal to build the spanning tree.

Parameters:
root - the root node of the spanning tree

addChild

public int addChild(int parent)
Unsupported operation. Spanning trees should not be edited.

Overrides:
addChild in class Tree<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
Parameters:
parent - the parent node id (node table row number)
Returns:
the added child node id
See Also:
Tree.addChild(int)

addChild

public N addChild(Node<?,?> parent)
Unsupported operation. Spanning trees should not be edited.

Overrides:
addChild in class Tree<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
Parameters:
parent - the parent node
Returns:
the added child node
See Also:
Tree.addChild(prefuse.data.Node)

addChildEdge

public int addChildEdge(int parent,
                        int child)
Unsupported operation. Spanning trees should not be edited.

Overrides:
addChildEdge in class Tree<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
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
See Also:
Tree.addChildEdge(int, int)

addChildEdge

public E addChildEdge(Node<?,?> parent,
                      Node<?,?> child)
Unsupported operation. Spanning trees should not be edited.

Overrides:
addChildEdge in class Tree<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
Parameters:
parent - the parent node
child - the child node
Returns:
the added child edge
See Also:
Tree.addChildEdge(prefuse.data.Node, prefuse.data.Node)

addRoot

public N addRoot()
Unsupported operation. Spanning trees should not be edited.

Overrides:
addRoot in class Tree<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
Returns:
the newly added root Node
See Also:
Tree.addRoot()

addRootRow

public int addRootRow()
Unsupported operation. Spanning trees should not be edited.

Overrides:
addRootRow in class Tree<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
Returns:
the node id (node table row number) of the new root node.
See Also:
Tree.addRootRow()

removeChild

public boolean removeChild(int node)
Unsupported operation. Spanning trees should not be edited.

Overrides:
removeChild in class Tree<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
Parameters:
node - the node id (node table row number) to remove
Returns:
true if the node and its subtree is successfully removed, false otherwise
See Also:
Tree.removeChild(int)

removeChild

public boolean removeChild(Node<?,?> n)
Unsupported operation. Spanning trees should not be edited.

Overrides:
removeChild in class Tree<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
Parameters:
n - the node to remove
Returns:
true if the node and its subtree is successfully removed, false otherwise
See Also:
Tree.removeChild(prefuse.data.Node)

removeChildEdge

public boolean removeChildEdge(Edge<?,?> e)
Unsupported operation. Spanning trees should not be edited.

Overrides:
removeChildEdge in class Tree<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
Parameters:
e - the edge to remove
Returns:
true if the edge and attached subtree is successfully removed, false otherwise
See Also:
Tree.removeChildEdge(prefuse.data.Edge)

removeChildEdge

public boolean removeChildEdge(int edge)
Unsupported operation. Spanning trees should not be edited.

Overrides:
removeChildEdge in class Tree<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
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
See Also:
Tree.removeChildEdge(int)

addEdge

public int addEdge(int s,
                   int t)
Unsupported operation. Spanning trees should not be edited.

Overrides:
addEdge in class Graph<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
Parameters:
s - the source node id
t - the target node id
Returns:
the edge id (edge table row number) of the added edge
See Also:
Graph.addEdge(int, int)

addEdge

public E addEdge(Node<?,?> s,
                 Node<?,?> t)
Unsupported operation. Spanning trees should not be edited.

Overrides:
addEdge in class Graph<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
Parameters:
s - the source Node
t - the target Node
Returns:
the new Edge instance
See Also:
Graph.addEdge(prefuse.data.Node, prefuse.data.Node)

addNode

public N addNode()
Unsupported operation. Spanning trees should not be edited.

Overrides:
addNode in class Graph<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
Returns:
the new Node instance
See Also:
Graph.addNode()

addNodeRow

public int addNodeRow()
Unsupported operation. Spanning trees should not be edited.

Overrides:
addNodeRow in class Graph<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
Returns:
the node id (node table row number) of the added node
See Also:
Graph.addNodeRow()

clear

public void clear()
Unsupported operation. Spanning trees should not be edited.

Specified by:
clear in interface TupleSet<T extends Tuple<?>>
Overrides:
clear in class Graph<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
See Also:
TupleSet.clear()

removeEdge

public boolean removeEdge(Edge<?,?> e)
Unsupported operation. Spanning trees should not be edited.

Overrides:
removeEdge in class Graph<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
Parameters:
e - the Edge to remove from the graph
Returns:
true if the edge was successfully removed, false if the edge was not found in this graph
See Also:
Graph.removeEdge(prefuse.data.Edge)

removeEdge

public boolean removeEdge(int edge)
Unsupported operation. Spanning trees should not be edited.

Overrides:
removeEdge in class Graph<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
Parameters:
edge - the edge id (edge table row number) of the edge to remove
Returns:
true if the edge was successfully removed, false if the edge was not found or was not valid
See Also:
Graph.removeEdge(int)

removeNode

public boolean removeNode(int node)
Unsupported operation. Spanning trees should not be edited.

Overrides:
removeNode in class Graph<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
Parameters:
node - the node id (node table row number) of the node to remove
Returns:
true if the node was successfully removed, false if the node id was not found or was not valid
See Also:
Graph.removeNode(int)

removeNode

public boolean removeNode(Node<?,?> n)
Unsupported operation. Spanning trees should not be edited.

Overrides:
removeNode in class Graph<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
Parameters:
n - the Node to remove from the graph
Returns:
true if the node was successfully removed, false if the node was not found in this graph
See Also:
Graph.removeNode(prefuse.data.Node)

removeTuple

public boolean removeTuple(Tuple<?> t)
Unsupported operation. Spanning trees should not be edited.

Specified by:
removeTuple in interface TupleSet<T extends Tuple<?>>
Overrides:
removeTuple in class Graph<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
Parameters:
t - the Tuple to remove
Returns:
true if the Tuple was found and removed, false otherwise
See Also:
TupleSet.removeTuple(prefuse.data.Tuple)

setEdgeTable

public void setEdgeTable(Table<E> edges)
Unsupported operation. Spanning trees should not be edited.

Overrides:
setEdgeTable in class Graph<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
Parameters:
edges - the new edge table.
See Also:
Graph.setEdgeTable(prefuse.data.Table)

setTupleManagers

public void setTupleManagers(TupleManager<N> ntm,
                             TupleManager<E> etm)
Unsupported operation. Spanning trees should not be edited.

Overrides:
setTupleManagers in class Graph<T extends Tuple<?>,N extends Node<N,E>,E extends Edge<N,E>>
Parameters:
ntm - the TupleManager to use for nodes
etm - the TupleManager to use for edges
See Also:
Graph.setTupleManagers(prefuse.data.tuple.TupleManager, prefuse.data.tuple.TupleManager)


Copyright © 2008 Regents of the University of California