Package edu.uci.ics.jung.graph

Class DelegateTree<V,E>

java.lang.Object

edu.uci.ics.jung.graph.GraphDecorator<V,E>

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

Type Parameters:

V - the vertex type

E - the edge type

All Implemented Interfaces:

edu.uci.ics.jung.graph.DirectedGraph<V,E>, edu.uci.ics.jung.graph.Forest<V,E>, edu.uci.ics.jung.graph.Graph<V,E>, edu.uci.ics.jung.graph.Hypergraph<V,E>, edu.uci.ics.jung.graph.Tree<V,E>, java.io.Serializable

public class DelegateTree<V,E>
extends edu.uci.ics.jung.graph.GraphDecorator<V,E>
implements edu.uci.ics.jung.graph.Tree<V,E>

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

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field	Description
protected V	root
protected java.util.Map<V,java.lang.Integer>	vertex_depths

Fields inherited from class edu.uci.ics.jung.graph.GraphDecorator

delegate

Constructor Summary

Constructors

Constructor	Description
DelegateTree()	Creates an instance.
DelegateTree(edu.uci.ics.jung.graph.DirectedGraph<V,E> graph)	Creates a new DelegateTree which delegates to graph.
DelegateTree(org.apache.commons.collections4.Factory<edu.uci.ics.jung.graph.DirectedGraph<V,E>> graphFactory)	create an instance with passed values.

Method Summary

Modifier and Type	Method	Description
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, edu.uci.ics.jung.graph.util.EdgeType edgeType)	add the passed child node as a child of parent.
boolean	addEdge(E edge, java.util.Collection<? extends V> vertices)
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, edu.uci.ics.jung.graph.util.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
java.util.Collection<E>	getChildEdges(V vertex)
java.util.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.collections4.Factory<edu.uci.ics.jung.graph.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)
V	getParent(V child)	get the single parent node of the passed child
E	getParentEdge(V vertex)
java.util.List<V>	getPath(V vertex)	Returns an ordered list of the nodes beginning at the root and ending at vertex, including all intermediate nodes.
V	getRoot()	getter for the root of the tree
java.util.Collection<edu.uci.ics.jung.graph.Tree<V,E>>	getTrees()
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
java.lang.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 java.util.Map<V,java.lang.Integer> vertex_depths

Constructor Detail

DelegateTree

public DelegateTree()

Creates an instance.

DelegateTree

public DelegateTree(org.apache.commons.collections4.Factory<edu.uci.ics.jung.graph.DirectedGraph<V,E>> graphFactory)

create an instance with passed values.

Parameters:

graphFactory - must create a DirectedGraph to use as a delegate

DelegateTree

public DelegateTree(edu.uci.ics.jung.graph.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.collections4.Factory<edu.uci.ics.jung.graph.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,
                       edu.uci.ics.jung.graph.util.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 edu.uci.ics.jung.graph.Graph<V,E>

Overrides:

addEdge in class edu.uci.ics.jung.graph.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 edu.uci.ics.jung.graph.Graph<V,E>

Overrides:

addEdge in class edu.uci.ics.jung.graph.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 edu.uci.ics.jung.graph.Hypergraph<V,E>

Overrides:

addVertex in class edu.uci.ics.jung.graph.GraphDecorator<V,E>

Parameters:

vertex - the tree root to set

Returns:

true if this call mutates the underlying graph

Throws:

java.lang.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 edu.uci.ics.jung.graph.Hypergraph<V,E>

Overrides:

removeVertex in class edu.uci.ics.jung.graph.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,
                        edu.uci.ics.jung.graph.util.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 edu.uci.ics.jung.graph.Forest<V,E>

getChildren

public java.util.Collection<V> getChildren(V parent)

get the immediate children nodes of the passed parent

Specified by:

getChildren in interface edu.uci.ics.jung.graph.Forest<V,E>

getParent

public V getParent(V child)

get the single parent node of the passed child

Specified by:

getParent in interface edu.uci.ics.jung.graph.Forest<V,E>

getPath

public java.util.List<V> getPath(V vertex)

Returns an ordered list of the nodes beginning at the root and ending at vertex, 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 edu.uci.ics.jung.graph.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 edu.uci.ics.jung.graph.Tree<V,E>

Parameters:

v - the node who's depth is computed

Returns:

the depth to the passed node.

getHeight

public int getHeight()

Computes and returns the height of the tree.

Specified by:

getHeight in interface edu.uci.ics.jung.graph.Tree<V,E>

Returns:

the height

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)

Specified by:

getIncidentCount in interface edu.uci.ics.jung.graph.Hypergraph<V,E>

Overrides:

getIncidentCount in class edu.uci.ics.jung.graph.GraphDecorator<V,E>

addEdge

public boolean addEdge(E edge,
                       java.util.Collection<? extends V> vertices)

Specified by:

addEdge in interface edu.uci.ics.jung.graph.Hypergraph<V,E>

Overrides:

addEdge in class edu.uci.ics.jung.graph.GraphDecorator<V,E>

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

getTrees

public java.util.Collection<edu.uci.ics.jung.graph.Tree<V,E>> getTrees()

Specified by:

getTrees in interface edu.uci.ics.jung.graph.Forest<V,E>

getChildEdges

public java.util.Collection<E> getChildEdges(V vertex)

Specified by:

getChildEdges in interface edu.uci.ics.jung.graph.Forest<V,E>

getParentEdge

public E getParentEdge(V vertex)

Specified by:

getParentEdge in interface edu.uci.ics.jung.graph.Forest<V,E>