prefuse.data
Class SpanningTree

java.lang.Object
  prefuse.data.tuple.AbstractTupleSet
      prefuse.data.tuple.CompositeTupleSet
          prefuse.data.Graph
              prefuse.data.Tree
                  prefuse.data.SpanningTree

All Implemented Interfaces:

TupleSet

public class SpanningTree
extends Tree

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

Graph.Listener

Field Summary

protected static Schema	EDGE_SCHEMA Edge table schema used by the spanning tree.
protected Graph	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 g, Node root)
Create a new SpanningTree.

Method Summary

int	addChild(int parent) Unsupported operation.
Node	addChild(Node parent) Unsupported operation.
int	addChildEdge(int parent, int child) Unsupported operation.
Edge	addChildEdge(Node parent, Node child) Unsupported operation.
int	addEdge(int s, int t) Unsupported operation.
Edge	addEdge(Node s, Node t) Unsupported operation.
Node	addNode() Unsupported operation.
int	addNodeRow() Unsupported operation.
Node	addRoot() Unsupported operation.
int	addRootRow() Unsupported operation.
void	buildSpanningTree(Node 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 edges) Unsupported operation.
void	setTupleManagers(TupleManager ntm, TupleManager etm) Unsupported operation.

Methods inherited from class prefuse.data.Tree

childEdgeRows, childEdges, children, createLinkTable, getChild, getChildCount, getChildIndex, getChildIndex, getChildRow, getDepth, getFirstChild, getFirstChildRow, getLastChild, 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, 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, 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

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 m_backing

A reference to the backing graph that this tree spans.

Constructor Detail

SpanningTree

public SpanningTree(Graph g,
                    Node 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(Node 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

Parameters:

parent - the parent node id (node table row number)

Returns:

the added child node id

See Also:

Tree.addChild(int)

addChild

public Node addChild(Node parent)

Unsupported operation. Spanning trees should not be edited.

Overrides:

addChild in class Tree

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

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 Edge addChildEdge(Node parent,
                         Node child)

Unsupported operation. Spanning trees should not be edited.

Overrides:

addChildEdge in class Tree

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 Node addRoot()

Unsupported operation. Spanning trees should not be edited.

Overrides:

addRoot in class Tree

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

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

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

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

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

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

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 Edge addEdge(Node s,
                    Node t)

Unsupported operation. Spanning trees should not be edited.

Overrides:

addEdge in class Graph

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 Node addNode()

Unsupported operation. Spanning trees should not be edited.

Overrides:

addNode in class Graph

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

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

Overrides:

clear in class Graph

See Also:

TupleSet.clear()

removeEdge

public boolean removeEdge(Edge e)

Unsupported operation. Spanning trees should not be edited.

Overrides:

removeEdge in class Graph

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

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

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

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

Overrides:

removeTuple in class Graph

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 edges)

Unsupported operation. Spanning trees should not be edited.

Overrides:

setEdgeTable in class Graph

Parameters:

edges - the new edge table.

See Also:

Graph.setEdgeTable(prefuse.data.Table)

setTupleManagers

public void setTupleManagers(TupleManager ntm,
                             TupleManager etm)

Unsupported operation. Spanning trees should not be edited.

Overrides:

setTupleManagers in class Graph

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)