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 typeE
- the edge type
- All Implemented Interfaces:
DirectedGraph<V,
,E> Forest<V,
,E> Graph<V,
,E> Hypergraph<V,
,E> Tree<V,
,E> Serializable
An implementation of
Tree
that delegates to
a specified instance of DirectedGraph
.- See Also:
-
Field Summary
FieldsFields inherited from class edu.uci.ics.jung.graph.GraphDecorator
delegate
-
Constructor Summary
ConstructorsConstructorDescriptionCreates an instance.DelegateTree
(com.google.common.base.Supplier<DirectedGraph<V, E>> graphFactory) create an instance with passed values.DelegateTree
(DirectedGraph<V, E> graph) Creates a newDelegateTree
which delegates tograph
. -
Method Summary
Modifier and TypeMethodDescriptionboolean
add the passed child node as a child of parent.boolean
add the passed child node as a child of parent.boolean
addEdge
(E edge, Collection<? extends V> vertices) Addsedge
to this graph.boolean
Add an edge to the tree, connecting v1, the parent and v2, the child.boolean
Add an edge to the tree, connecting v1, the parent and v2, the child.boolean
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 nodegetChildEdges
(V vertex) Returns the edges connectingvertex
to its children in this tree.getChildren
(V parent) get the immediate children nodes of the passed parentint
computes and returns the depth of the tree from the root to the passed vertexstatic final <V,
E> com.google.common.base.Supplier <Tree<V, E>> int
Computes and returns the height of the tree.int
getIncidentCount
(E edge) Returns the number of vertices that are incident toedge
.get the single parent node of the passed childgetParentEdge
(V vertex) Returns the edge connectingvertex
to its parent in this tree.Returns an ordered list of the nodes beginning at the root and ending atvertex
, including all intermediate nodes.getRoot()
getter for the root of the treeCollection
<Tree<V, E>> getTrees()
Returns a view of this graph as a collection ofTree
instances.boolean
isInternal
(V v) boolean
boolean
boolean
removeChild
(V orphan) removes a node from the tree, causing all descendants of the removed node also to be removedboolean
removeVertex
(V vertex) remove the passed node, and all nodes that are descendants of the passed node.void
sets the root to the passed value, only if the root is previously unsettoString()
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 Details
-
root
-
vertex_depths
-
-
Constructor Details
-
DelegateTree
public DelegateTree()Creates an instance. -
DelegateTree
create an instance with passed values.- Parameters:
graphFactory
- must create a DirectedGraph to use as a delegate
-
DelegateTree
Creates a newDelegateTree
which delegates tograph
. Assumes thatgraph
is already a tree; if it's not, future behavior of this instance is undefined.- Parameters:
graph
- the graph to which this instance will delegate operations.
-
-
Method Details
-
getFactory
- Type Parameters:
V
- the vertex type for the graph SupplierE
- the edge type for the graph Supplier- Returns:
- a
Supplier
that creates an instance of this graph type.
-
addEdge
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. -
addEdge
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. -
addVertex
Will set the root of the Tree, only if the Tree is empty and the root is currently unset.- Specified by:
addVertex
in interfaceHypergraph<V,
E> - Overrides:
addVertex
in classGraphDecorator<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:
-
removeVertex
remove the passed node, and all nodes that are descendants of the passed node.- Specified by:
removeVertex
in interfaceHypergraph<V,
E> - Overrides:
removeVertex
in classGraphDecorator<V,
E> - Parameters:
vertex
- the vertex to remove- Returns:
true
iff the tree was modified- See Also:
-
addChild
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 nodesparent
- the existing parent to attach the child tochild
- the new child to add to the tree as a child of parentedgeType
- must be EdgeType.DIRECTED or the underlying graph may throw an exception- Returns:
- whether this call mutates the underlying graph
-
addChild
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 nodesparent
- the existing parent to attach the child tochild
- the new child to add to the tree as a child of parent- Returns:
- whether this call mutates the underlying graph
-
getChildCount
get the number of children of the passed parent node- Specified by:
getChildCount
in interfaceForest<V,
E> - Parameters:
parent
- the vertex whose child edges are to be returned- Returns:
- the
Collection
of edges connectingvertex
to its children in this tree - See Also:
-
getChildren
get the immediate children nodes of the passed parent- Specified by:
getChildren
in interfaceForest<V,
E> - Parameters:
parent
- the vertex whose children are to be returned- Returns:
- the
Collection
of children ofvertex
in this tree - See Also:
-
getParent
get the single parent node of the passed child -
getPath
Returns an ordered list of the nodes beginning at the root and ending atvertex
, 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
getter for the root of the tree -
setRoot
sets the root to the passed value, only if the root is previously unset- Parameters:
root
- the initial tree root
-
removeChild
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
computes and returns the depth of the tree from the root to the passed vertex -
getHeight
public int getHeight()Computes and returns the height of the tree. -
isInternal
- Parameters:
v
- the vertex to test- Returns:
true
ifv
is neither a leaf nor the root of this tree
-
isLeaf
- Parameters:
v
- the vertex to test- Returns:
true
ifv
has no children
-
isRoot
- Parameters:
v
- the vertex to test- Returns:
true
ifv
has no parent
-
getIncidentCount
Description copied from interface:Hypergraph
Returns the number of vertices that are incident toedge
. 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 interfaceHypergraph<V,
E> - Overrides:
getIncidentCount
in classGraphDecorator<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:
-
addEdge
Description copied from interface:Hypergraph
Addsedge
to this graph. Fails under the following circumstances:edge
is already an element of the graph- either
edge
orvertices
isnull
vertices
has the wrong number of vertices for the graph typevertices
are already connected by another edge in this graph, and this graph does not accept parallel edges
- Specified by:
addEdge
in interfaceHypergraph<V,
E> - Overrides:
addEdge
in classGraphDecorator<V,
E> - Parameters:
edge
- the edge to addvertices
- the vertices to which the edge will be connected- Returns:
true
if the add is successful, andfalse
otherwise- See Also:
-
toString
-
getTrees
Description copied from interface:Forest
Returns a view of this graph as a collection ofTree
instances. -
getChildEdges
Description copied from interface:Forest
Returns the edges connectingvertex
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 forgetOutEdges(vertex)
.- Specified by:
getChildEdges
in interfaceForest<V,
E> - Parameters:
vertex
- the vertex whose child edges are to be returned- Returns:
- the
Collection
of edges connectingvertex
to its children in this tree - See Also:
-
getParentEdge
Description copied from interface:Forest
Returns the edge connectingvertex
to its parent in this tree. (Ifvertex
is the root, returnsnull
.) 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 toGraph.getInEdges(vertex).iterator().next()
, and also toGraph.findEdge(vertex, getParent(vertex))
.- Specified by:
getParentEdge
in interfaceForest<V,
E> - Parameters:
vertex
- the vertex whose incoming edge is to be returned- Returns:
- the edge connecting
vertex
to its parent, ornull
ifvertex
is the root - See Also:
-