V
- the vertex typeE
- the edge typepublic class DelegateTree<V,E> extends GraphDecorator<V,E> implements Tree<V,E>
Tree
that delegates to
a specified instance of DirectedGraph
.Modifier and Type | Field and Description |
---|---|
protected V |
root |
protected Map<V,Integer> |
vertex_depths |
delegate
Constructor and Description |
---|
DelegateTree()
Creates an instance.
|
DelegateTree(DirectedGraph<V,E> graph)
Creates a new
DelegateTree which delegates to graph . |
DelegateTree(com.google.common.base.Supplier<DirectedGraph<V,E>> graphFactory)
create an instance with passed values.
|
Modifier and Type | Method and 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,
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> com.google.common.base.Supplier<Tree<V,E>> |
getFactory() |
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
vertex , 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) |
boolean |
isLeaf(V v) |
boolean |
isRoot(V v) |
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() |
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
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
getDest, getEndpoints, getInEdges, getOpposite, getOutEdges, getPredecessorCount, getPredecessors, getSource, getSuccessorCount, getSuccessors, inDegree, isDest, isPredecessor, isSource, isSuccessor, outDegree
addEdge, containsEdge, containsVertex, degree, findEdge, findEdgeSet, getDefaultEdgeType, getEdgeCount, getEdgeCount, getEdges, getEdges, getEdgeType, getIncidentEdges, getIncidentVertices, getNeighborCount, getNeighbors, getVertexCount, getVertices, isIncident, isNeighbor, removeEdge
public DelegateTree()
public DelegateTree(com.google.common.base.Supplier<DirectedGraph<V,E>> graphFactory)
graphFactory
- must create a DirectedGraph to use as a delegatepublic DelegateTree(DirectedGraph<V,E> graph)
DelegateTree
which delegates to graph
.
Assumes that graph
is already a tree; if it's not, future behavior
of this instance is undefined.graph
- the graph to which this instance will delegate operations.public static final <V,E> com.google.common.base.Supplier<Tree<V,E>> getFactory()
V
- the vertex type for the graph SupplierE
- the edge type for the graph SupplierSupplier
that creates an instance of this graph type.public boolean addEdge(E e, V v1, V v2, EdgeType edgeType)
addEdge
in interface Graph<V,E>
addEdge
in class GraphDecorator<V,E>
e
- a unique edge to addv1
- the parent nodev2
- the child nodeedgeType
- should be EdgeType.DIRECTEDGraph.addEdge(java.lang.Object, java.lang.Object, java.lang.Object, edu.uci.ics.jung.graph.util.EdgeType)
public boolean addEdge(E e, V v1, V v2)
addEdge
in interface Graph<V,E>
addEdge
in class GraphDecorator<V,E>
e
- a unique edge to addv1
- the parent nodev2
- the child nodeGraph.addEdge(java.lang.Object, java.lang.Object, java.lang.Object)
public boolean addVertex(V vertex)
addVertex
in interface Hypergraph<V,E>
addVertex
in class GraphDecorator<V,E>
vertex
- the tree root to setUnsupportedOperationException
- if the root was previously setHypergraph.addVertex(java.lang.Object)
public boolean removeVertex(V vertex)
removeVertex
in interface Hypergraph<V,E>
removeVertex
in class GraphDecorator<V,E>
vertex
- the vertex to removetrue
iff the tree was modifiedHypergraph.removeVertex(java.lang.Object)
public boolean addChild(E edge, V parent, V child, EdgeType edgeType)
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 exceptionpublic boolean addChild(E edge, V parent, V child)
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 parentpublic int getChildCount(V parent)
getChildCount
in interface Forest<V,E>
parent
- the vertex whose child edges are to be returnedCollection
of edges connecting
vertex
to its children in this treeForest.getChildEdges(Object)
,
Forest.getChildren(Object)
,
Graph.getSuccessorCount(Object)
public Collection<V> getChildren(V parent)
getChildren
in interface Forest<V,E>
parent
- the vertex whose children are to be returnedCollection
of children of vertex
in this treeGraph.getSuccessors(Object)
,
Forest.getChildEdges(Object)
public V getParent(V child)
getParent
in interface Forest<V,E>
child
- the vertex whose parent is to be returnedvertex
in this treeGraph.getPredecessors(Object)
,
Forest.getParentEdge(Object)
public List<V> getPath(V vertex)
vertex
, including all intermediate
nodes.vertex
- the last node in the path from the rootpublic V getRoot()
public void setRoot(V root)
root
- the initial tree rootpublic boolean removeChild(V orphan)
orphan
- the node to removepublic int getDepth(V v)
getDepth
in interface Tree<V,E>
v
- the node who's depth is computedTree.getHeight()
public int getHeight()
getHeight
in interface Tree<V,E>
Tree.getDepth(Object)
public boolean isInternal(V v)
v
- the vertex to testtrue
if v
is neither
a leaf nor the root of this treepublic boolean isLeaf(V v)
v
- the vertex to testtrue
if v
has no childrenpublic boolean isRoot(V v)
v
- the vertex to testtrue
if v
has no parentpublic int getIncidentCount(E edge)
Hypergraph
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()
.
getIncidentCount
in interface Hypergraph<V,E>
getIncidentCount
in class GraphDecorator<V,E>
edge
- the edge whose incident vertex count is to be returnededge
.Hypergraph.getIncidentCount(java.lang.Object)
public boolean addEdge(E edge, Collection<? extends V> vertices)
Hypergraph
edge
to this graph.
Fails under the following circumstances:
edge
is already an element of the graph
edge
or vertices
is null
vertices
has the wrong number of vertices for the graph type
vertices
are already connected by another edge in this graph,
and this graph does not accept parallel edges
addEdge
in interface Hypergraph<V,E>
addEdge
in class GraphDecorator<V,E>
edge
- the edge to addvertices
- the vertices to which the edge will be connectedtrue
if the add is successful, and false
otherwiseHypergraph.addEdge(java.lang.Object, java.util.Collection)
public Collection<Tree<V,E>> getTrees()
Forest
Tree
instances.public Collection<E> getChildEdges(V vertex)
Forest
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)
.getChildEdges
in interface Forest<V,E>
vertex
- the vertex whose child edges are to be returnedCollection
of edges connecting
vertex
to its children in this treeGraph.getOutEdges(Object)
,
Forest.getChildren(Object)
public E getParentEdge(V vertex)
Forest
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))
.getParentEdge
in interface Forest<V,E>
vertex
- the vertex whose incoming edge is to be returnedvertex
to its parent, or
null
if vertex
is the rootGraph.getInEdges(Object)
,
Forest.getParent(Object)
Copyright © 2015. All rights reserved.