edu.uci.ics.jung.graph
Class DelegateTree<V,E>

java.lang.Object
  extended by edu.uci.ics.jung.graph.GraphDecorator<V,E>
      extended by edu.uci.ics.jung.graph.DelegateTree<V,E>
Type Parameters:
V - the vertex type
E - the edge type
All Implemented Interfaces:
DirectedGraph<V,E>, Forest<V,E>, Graph<V,E>, Hypergraph<V,E>, Tree<V,E>, Serializable

public class DelegateTree<V,E>
extends GraphDecorator<V,E>
implements Tree<V,E>, Serializable

An implementation of Tree that delegates to a specified instance of DirectedGraph.

Author:
Tom Nelson
See Also:
Serialized Form

Field Summary
protected  V root
           
protected  Map<V,Integer> vertex_depths
           
 
Fields inherited from class edu.uci.ics.jung.graph.GraphDecorator
delegate
 
Constructor Summary
DelegateTree()
          Creates an instance.
DelegateTree(DirectedGraph<V,E> graph)
          Creates a new DelegateTree which delegates to graph.
DelegateTree(org.apache.commons.collections15.Factory<DirectedGraph<V,E>> graphFactory)
          create an instance with passed values.
 
Method Summary
 boolean addChild(E edge, V parent, V child)
          add the passed child node as a child of parent.
 boolean addChild(E edge, V parent, V child, EdgeType edgeType)
          add the passed child node as a child of parent.
 boolean addEdge(E edge, Collection<? extends V> vertices)
          Adds edge to this graph.
 boolean addEdge(E e, V v1, V v2)
          Add an edge to the tree, connecting v1, the parent and v2, the child.
 boolean addEdge(E e, V v1, V v2, EdgeType edgeType)
          Add an edge to the tree, connecting v1, the parent and v2, the child.
 boolean addVertex(V vertex)
          Will set the root of the Tree, only if the Tree is empty and the root is currently unset.
 int getChildCount(V parent)
          get the number of children of the passed parent node
 Collection<E> getChildEdges(V vertex)
          Returns the edges connecting vertex to its children in this tree.
 Collection<V> getChildren(V parent)
          get the immediate children nodes of the passed parent
 int getDepth(V v)
          computes and returns the depth of the tree from the root to the passed vertex
static
<V,E> org.apache.commons.collections15.Factory<Tree<V,E>>
getFactory()
          Returns a Factory that creates an instance of this graph type.
 int getHeight()
          Computes and returns the height of the tree.
 int getIncidentCount(E edge)
          Returns the number of vertices that are incident to edge.
 V getParent(V child)
          get the single parent node of the passed child
 E getParentEdge(V vertex)
          Returns the edge connecting vertex to its parent in this tree.
 List<V> getPath(V vertex)
          returns an ordered list of the nodes beginning at the root and ending at the passed child node, including all intermediate nodes.
 V getRoot()
          getter for the root of the tree
 Collection<Tree<V,E>> getTrees()
          Returns a view of this graph as a collection of Tree instances.
 boolean isInternal(V v)
          Returns true if v is neither a leaf nor the root of this tree.
 boolean isLeaf(V v)
          Returns true if the passed node has no children.
 boolean isRoot(V v)
          computes whether the passed node is a root node (has no children)
 boolean removeChild(V orphan)
          removes a node from the tree, causing all descendants of the removed node also to be removed
 boolean removeVertex(V vertex)
          remove the passed node, and all nodes that are descendants of the passed node.
 void setRoot(V root)
          sets the root to the passed value, only if the root is previously unset
 String toString()
           
 
Methods inherited from class edu.uci.ics.jung.graph.GraphDecorator
addEdge, containsEdge, containsVertex, degree, findEdge, findEdgeSet, getDefaultEdgeType, getDest, getEdgeCount, getEdgeCount, getEdges, getEdges, getEdgeType, getEndpoints, getIncidentEdges, getIncidentVertices, getInEdges, getNeighborCount, getNeighbors, getOpposite, getOutEdges, getPredecessorCount, getPredecessors, getSource, getSuccessorCount, getSuccessors, getVertexCount, getVertices, inDegree, isDest, isIncident, isNeighbor, isPredecessor, isSource, isSuccessor, outDegree, removeEdge
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface edu.uci.ics.jung.graph.Graph
getDest, getEndpoints, getInEdges, getOpposite, getOutEdges, getPredecessorCount, getPredecessors, getSource, getSuccessorCount, getSuccessors, inDegree, isDest, isPredecessor, isSource, isSuccessor, outDegree
 
Methods inherited from interface edu.uci.ics.jung.graph.Hypergraph
addEdge, containsEdge, containsVertex, degree, findEdge, findEdgeSet, getDefaultEdgeType, getEdgeCount, getEdgeCount, getEdges, getEdges, getEdgeType, getIncidentEdges, getIncidentVertices, getNeighborCount, getNeighbors, getVertexCount, getVertices, isIncident, isNeighbor, removeEdge
 

Field Detail

root

protected V root

vertex_depths

protected Map<V,Integer> vertex_depths
Constructor Detail

DelegateTree

public DelegateTree()
Creates an instance.


DelegateTree

public DelegateTree(org.apache.commons.collections15.Factory<DirectedGraph<V,E>> graphFactory)
create an instance with passed values.

Parameters:
graphFactory - must create a DirectedGraph to use as a delegate

DelegateTree

public DelegateTree(DirectedGraph<V,E> graph)
Creates a new DelegateTree which delegates to graph. Assumes that graph is already a tree; if it's not, future behavior of this instance is undefined.

Method Detail

getFactory

public static final <V,E> org.apache.commons.collections15.Factory<Tree<V,E>> getFactory()
Returns a Factory that creates an instance of this graph type.

Type Parameters:
V - the vertex type for the graph factory
E - the edge type for the graph factory

addEdge

public boolean addEdge(E e,
                       V v1,
                       V v2,
                       EdgeType edgeType)
Add an edge to the tree, connecting v1, the parent and v2, the child. v1 must already exist in the tree, and v2 must not already exist the passed edge must be unique in the tree. Passing an edgeType other than EdgeType.DIRECTED may cause an illegal argument exception in the delegate graph.

Specified by:
addEdge in interface Graph<V,E>
Overrides:
addEdge in class GraphDecorator<V,E>
Parameters:
e - a unique edge to add
v1 - the parent node
v2 - the child node
edgeType - should be EdgeType.DIRECTED
Returns:
true if this call mutates the underlying graph
See Also:
Graph.addEdge(java.lang.Object, java.lang.Object, java.lang.Object, edu.uci.ics.jung.graph.util.EdgeType)

addEdge

public boolean addEdge(E e,
                       V v1,
                       V v2)
Add an edge to the tree, connecting v1, the parent and v2, the child. v1 must already exist in the tree, and v2 must not already exist the passed edge must be unique in the tree.

Specified by:
addEdge in interface Graph<V,E>
Overrides:
addEdge in class GraphDecorator<V,E>
Parameters:
e - a unique edge to add
v1 - the parent node
v2 - the child node
Returns:
true if this call mutates the underlying graph
See Also:
Graph.addEdge(java.lang.Object, java.lang.Object, java.lang.Object)

addVertex

public boolean addVertex(V vertex)
Will set the root of the Tree, only if the Tree is empty and the root is currently unset.

Specified by:
addVertex in interface Hypergraph<V,E>
Overrides:
addVertex in class GraphDecorator<V,E>
Parameters:
vertex - the tree root to set
Returns:
true if this call mutates the underlying graph
Throws:
UnsupportedOperationException - if the root was previously set
See Also:
Hypergraph.addVertex(java.lang.Object)

removeVertex

public boolean removeVertex(V vertex)
remove the passed node, and all nodes that are descendants of the passed node.

Specified by:
removeVertex in interface Hypergraph<V,E>
Overrides:
removeVertex in class GraphDecorator<V,E>
Parameters:
vertex -
Returns:
true iff the tree was modified
See Also:
Hypergraph.removeVertex(java.lang.Object)

addChild

public boolean addChild(E edge,
                        V parent,
                        V child,
                        EdgeType edgeType)
add the passed child node as a child of parent. parent must exist in the tree, and child must not already exist.

Parameters:
edge - the unique edge to connect the parent and child nodes
parent - the existing parent to attach the child to
child - the new child to add to the tree as a child of parent
edgeType - must be EdgeType.DIRECTED or the underlying graph may throw an exception
Returns:
whether this call mutates the underlying graph

addChild

public boolean addChild(E edge,
                        V parent,
                        V child)
add the passed child node as a child of parent. parent must exist in the tree, and child must not already exist

Parameters:
edge - the unique edge to connect the parent and child nodes
parent - the existing parent to attach the child to
child - the new child to add to the tree as a child of parent
Returns:
whether this call mutates the underlying graph

getChildCount

public int getChildCount(V parent)
get the number of children of the passed parent node

Specified by:
getChildCount in interface Forest<V,E>
Parameters:
parent - the vertex whose child edges are to be returned
Returns:
the Collection of edges connecting vertex to its children in this tree
See Also:
Forest.getChildEdges(Object), Forest.getChildren(Object), Graph.getSuccessorCount(Object)

getChildren

public Collection<V> getChildren(V parent)
get the immediate children nodes of the passed parent

Specified by:
getChildren in interface Forest<V,E>
Parameters:
parent - the vertex whose children are to be returned
Returns:
the Collection of children of vertex in this tree
See Also:
Graph.getSuccessors(Object), Forest.getChildEdges(Object)

getParent

public V getParent(V child)
get the single parent node of the passed child

Specified by:
getParent in interface Forest<V,E>
Returns:
the parent of vertex in this tree
See Also:
Graph.getPredecessors(Object), Forest.getParentEdge(Object)

getPath

public List<V> getPath(V vertex)
returns an ordered list of the nodes beginning at the root and ending at the passed child node, including all intermediate nodes.

Parameters:
vertex - the last node in the path from the root
Returns:
an ordered list of the nodes from root to child

getRoot

public V getRoot()
getter for the root of the tree

Specified by:
getRoot in interface Tree<V,E>
Returns:
the root

setRoot

public void setRoot(V root)
sets the root to the passed value, only if the root is previously unset

Parameters:
root - the initial tree root

removeChild

public boolean removeChild(V orphan)
removes a node from the tree, causing all descendants of the removed node also to be removed

Parameters:
orphan - the node to remove
Returns:
whether this call mutates the underlying graph

getDepth

public int getDepth(V v)
computes and returns the depth of the tree from the root to the passed vertex

Specified by:
getDepth in interface Tree<V,E>
Parameters:
v - the node who's depth is computed
Returns:
the depth to the passed node.
See Also:
Tree.getHeight()

getHeight

public int getHeight()
Computes and returns the height of the tree.

Specified by:
getHeight in interface Tree<V,E>
Returns:
the height
See Also:
Tree.getDepth(Object)

isInternal

public boolean isInternal(V v)
Returns true if v is neither a leaf nor the root of this tree.

Returns:
true if v is neither a leaf nor the root of this tree

isLeaf

public boolean isLeaf(V v)
Returns true if the passed node has no children.

Returns:
true if the passed node has no children

isRoot

public boolean isRoot(V v)
computes whether the passed node is a root node (has no children)


getIncidentCount

public int getIncidentCount(E edge)
Description copied from interface: Hypergraph
Returns the number of vertices that are incident to edge. For hyperedges, this can be any nonnegative integer; for edges this must be 2 (or 1 if self-loops are permitted).

Equivalent to getIncidentVertices(edge).size().

Specified by:
getIncidentCount in interface Hypergraph<V,E>
Overrides:
getIncidentCount in class GraphDecorator<V,E>
Parameters:
edge - the edge whose incident vertex count is to be returned
Returns:
the number of vertices that are incident to edge.
See Also:
Hypergraph.getIncidentCount(java.lang.Object)

addEdge

public boolean addEdge(E edge,
                       Collection<? extends V> vertices)
Description copied from interface: Hypergraph
Adds edge to this graph. Fails under the following circumstances:

Specified by:
addEdge in interface Hypergraph<V,E>
Overrides:
addEdge in class GraphDecorator<V,E>
Returns:
true if the add is successful, and false otherwise
See Also:
Hypergraph.addEdge(java.lang.Object, java.util.Collection)

toString

public String toString()
Overrides:
toString in class Object

getTrees

public Collection<Tree<V,E>> getTrees()
Description copied from interface: Forest
Returns a view of this graph as a collection of Tree instances.

Specified by:
getTrees in interface Forest<V,E>
Returns:
a view of this graph as a collection of Trees

getChildEdges

public Collection<E> getChildEdges(V vertex)
Description copied from interface: Forest
Returns the edges connecting vertex to its children in this tree. The children of a vertex are defined as being the successors of that vertex on the respective (unique) shortest paths from the root to those vertices. This is syntactic (maple) sugar for getOutEdges(vertex).

Specified by:
getChildEdges in interface Forest<V,E>
Parameters:
vertex - the vertex whose child edges are to be returned
Returns:
the Collection of edges connecting vertex to its children in this tree
See Also:
Graph.getOutEdges(Object), Forest.getChildren(Object)

getParentEdge

public E getParentEdge(V vertex)
Description copied from interface: Forest
Returns the edge connecting vertex to its parent in this tree. (If vertex is the root, returns null.) The parent of a vertex is defined as being its predecessor in the (unique) shortest path from the root to this vertex. This is a convenience method which is equivalent to Graph.getInEdges(vertex).iterator().next(), and also to Graph.findEdge(vertex, getParent(vertex)).

Specified by:
getParentEdge in interface Forest<V,E>
Returns:
the edge connecting vertex to its parent, or null if vertex is the root
See Also:
Graph.getInEdges(Object), Forest.getParent(Object)


Copyright © 2009. All Rights Reserved.