Package edu.uci.ics.jung.graph
Class DelegateForest<V,E>
java.lang.Object
edu.uci.ics.jung.graph.GraphDecorator<V,E>
edu.uci.ics.jung.graph.DelegateForest<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> Serializable
An implementation of
Forest
that delegates to a specified DirectedGraph
instance.- See Also:
-
Field Summary
Fields inherited from class edu.uci.ics.jung.graph.GraphDecorator
delegate
-
Constructor Summary
ConstructorsConstructorDescriptionCreates an instance backed by a newDirectedSparseGraph
instance.DelegateForest
(DirectedGraph<V, E> delegate) Creates an instance backed by the inputDirectedGraph
. -
Method Summary
Modifier and TypeMethodDescriptionboolean
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.void
Addstree
to this graph as an element of this forest.boolean
Add vertex as a root of the treeint
getChildCount
(V vertex) Returns the number of children thatvertex
has in this tree.getChildEdges
(V vertex) Returns the edges connectingvertex
to its children in this tree.getChildren
(V v) Returns the children ofvertex
in this tree.int
computes and returns the depth of the tree from the root to the passed vertexint
computes and returns the height of the treeint
getIncidentCount
(E edge) Returns the number of vertices that are incident toedge
.Returns the parent ofvertex
in this tree.getParentEdge
(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 at the passed child node, including all intermediate nodes.getRoot()
getRoots()
Collection
<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
removeEdge
(E edge) Removesedge
from this tree, and the subtree rooted at the child vertex incident toedge
.boolean
removeEdge
(E edge, boolean remove_subtree) Removesedge
from this tree.boolean
removeVertex
(V vertex) Removesvertex
from this tree, and the subtree rooted atvertex
.boolean
removeVertex
(V vertex, boolean remove_subtrees) Removesvertex
from this tree.void
adds root as a root of the treeMethods inherited from class edu.uci.ics.jung.graph.GraphDecorator
addEdge, 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
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface edu.uci.ics.jung.graph.Graph
addEdge, 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
-
Constructor Details
-
DelegateForest
public DelegateForest()Creates an instance backed by a newDirectedSparseGraph
instance. -
DelegateForest
Creates an instance backed by the inputDirectedGraph
.- Parameters:
delegate
- the graph to which operations will be delegated
-
-
Method Details
-
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. -
addVertex
Add vertex as a root of the tree- Specified by:
addVertex
in interfaceHypergraph<V,
E> - Overrides:
addVertex
in classGraphDecorator<V,
E> - Parameters:
vertex
- the tree root to add- Returns:
- true if this call mutates the underlying graph
- See Also:
-
removeEdge
Removesedge
from this tree, and the subtree rooted at the child vertex incident toedge
. (The subtree is removed to ensure that the tree in which the edge was found is still a tree rather than a forest. To change this behavior so that the- Specified by:
removeEdge
in interfaceHypergraph<V,
E> - Overrides:
removeEdge
in classGraphDecorator<V,
E> - Parameters:
edge
- the edge to remove- Returns:
true
iff the tree was modified- See Also:
-
removeEdge
Removesedge
from this tree. Ifremove_subtree
istrue
, removes the subtree rooted at the child vertex incident toedge
. Otherwise, leaves the subtree intact as a new component tree of this forest.- Parameters:
edge
- the edge to removeremove_subtree
- iftrue
, remove the subtree- Returns:
true
iff the tree was modified
-
removeVertex
Removesvertex
from this tree, and the subtree rooted atvertex
.- 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:
-
removeVertex
Removesvertex
from this tree. Ifremove_subtrees
istrue
, removes the subtrees rooted at the children ofvertex
. Otherwise, leaves these subtrees intact as new component trees of this forest.- Parameters:
vertex
- the vertex to removeremove_subtrees
- iftrue
, remove the subtrees rooted atvertex
's children- Returns:
true
iff the tree was modified
-
getPath
returns an ordered list of the nodes beginning at the root and ending at the passed child node, including all intermediate nodes.- Parameters:
child
- the last node in the path from the root- Returns:
- an ordered list of the nodes from root to child
-
getParent
Description copied from interface:Forest
Returns the parent ofvertex
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.getPredecessors(vertex).iterator().next()
. -
getRoot
- Returns:
- the root of the tree, or null if the tree has > 1 roots
-
setRoot
adds root as a root of the tree- 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- 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- Returns:
- the height
-
isInternal
- Parameters:
v
- the vertex to test- Returns:
true
ifv
is neither a leaf nor a root
-
isLeaf
- Parameters:
v
- the vertex to test- Returns:
true
ifv
has no child nodes.
-
getChildren
Description copied from interface:Forest
Returns the children ofvertex
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 forgetSuccessors(vertex)
.- Specified by:
getChildren
in interfaceForest<V,
E> - Parameters:
v
- the vertex whose children are to be returned- Returns:
- the children of
v
. - See Also:
-
isRoot
- Parameters:
v
- the vertex to test- Returns:
true
ifv
has no parent node.
-
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:
-
getRoots
- Returns:
- the root of each tree of this forest as a
Collection
.
-
getTrees
Description copied from interface:Forest
Returns a view of this graph as a collection ofTree
instances. -
addTree
Addstree
to this graph as an element of this forest.- Parameters:
tree
- the tree to add to this forest as a component
-
getChildCount
Description copied from interface:Forest
Returns the number of children thatvertex
has 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 forgetSuccessorCount(vertex)
.- Specified by:
getChildCount
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:
-
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:
-