V
- the vertex type.E
- the edge type.public class Tree<V extends Vertex,E extends Edge<V>> extends Object implements Graph<V,E>, Serializable
Modifier and Type | Field and Description |
---|---|
private Collection<EdgeAttribute> |
edgeAttributes |
private HashMap<String,E> |
edgemaps |
private edu.uci.ics.jung.graph.DelegateTree<V,E> |
tree |
private Collection<VertexAttribute> |
vertexAttributes |
private HashMap<String,V> |
vertexmaps |
Constructor and Description |
---|
Tree()
Creates an instance of the tree.
|
Modifier and Type | Method and Description |
---|---|
boolean |
addEdge(E e,
V v1,
V v2)
Adds edge
e to this graph such that it connects vertex
v1 to
v2 . |
boolean |
addEdge(E e,
V v1,
V v2,
EdgeType edgeType)
Adds edge
e to this graph such that it connects vertex
v1 to
v2 . |
void |
addEdgeAttribute(String name,
Class type,
String defaultValue)
Add a new node attribute to the network.
|
void |
addSubtree(Tree<V,E> subtree,
V node,
E connectingEdge)
Add a [sub]tree to the current tree.
|
boolean |
addVertex(V vertex)
Adds a vertex to the graph.
|
void |
addVertexAttribute(String name,
Class type,
String defaultValue)
Add a new node attribute to the network.
|
protected void |
finalize() |
int |
getDepth(V vertex)
Returns the (unweighted) distance of vertex from the root of this tree.
|
V |
getDest(E directedEdge)
If
directed_edge is a directed edge in this graph, returns the destination; otherwise returns
null . |
E |
getEdge(String id)
Returns a view the edges in this graph with the given id.
|
Collection<E> |
getEdges()
Returns a view of all edges in this graph.
|
EdgeType |
getEdgeType()
Get the type of edge (directed/undirected employed in the graph.
|
Pair<V,V> |
getEndpoints(E edge)
Returns the endpoints of
edge as a
Pair . |
int |
getHeight()
Returns the maximum depth in this tree.
|
Collection<E> |
getInEdges(V vertex)
Returns a
Collection view of the incoming edges incident to
vertex in this graph. |
V |
getOpposite(V vertex,
E edge)
Returns the vertex at the other end of
edge from
vertex . |
Collection<E> |
getOutEdges(V vertex)
Returns a
Collection view of the outgoing edges incident to
vertex in this graph. |
V |
getPredecessor(V vertex)
Get the
vertex in this graph that is the source of the (single) edge that is incident on this
vertex. |
int |
getPredecessorCount(V vertex)
Returns the number of predecessors that
vertex has in this graph. |
Collection<V> |
getPredecessors(V vertex)
Returns a
Collection view of the predecessors of
vertex in this graph. |
V |
getRoot()
Returns the root of this tree.
|
V |
getSource(E directedEdge)
If
directed_edge is a directed edge in this graph, returns the source; otherwise returns
null . |
Tree<V,E> |
getSubTree(V vertex)
Obtain the sub-tree with
vertex as it's root. |
int |
getSuccessorCount(V vertex)
Returns the number of successors that
vertex has in this graph. |
Collection<V> |
getSuccessors(V vertex)
Returns a
Collection view of the successors of
vertex in this graph. |
V |
getVertex(String id)
Returns a view the vertex in this graph with a given id.Returns null if the edge does not exist.
|
int |
getVertexCount()
Returns the number of vertices in this graph.
|
Collection<V> |
getVertices()
Returns a view of all vertices in this graph.
|
int |
inDegree(V vertex)
Returns the number of incoming edges incident to
vertex . |
boolean |
isDest(V vertex,
E edge)
Returns
true if
vertex is the destination of
edge . |
boolean |
isPredecessor(V v1,
V v2)
Returns
true if
v1 is a predecessor of
v2 in this graph. |
boolean |
isSource(V vertex,
E edge)
Returns
true if
vertex is the source of
edge . |
boolean |
isSuccessor(V v1,
V v2)
Returns
true if
v1 is a successor of
v2 in this graph. |
int |
outDegree(V vertex)
Returns the number of outgoing edges incident to
vertex . |
boolean |
removeEdge(E edge)
Removes
edge from this graph. |
boolean |
removeVertex(V vertex)
Remove the passed node, and, in the case of a tree, all nodes that are descendants of the passed node.
|
clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
getEdgeAttributes, getVertexAttributes
private final Collection<VertexAttribute> vertexAttributes
private final Collection<EdgeAttribute> edgeAttributes
public final V getRoot()
public final int getHeight()
public final int getDepth(V vertex)
vertex
- the vertex whose depth is to be returned.public final boolean addVertex(V vertex)
Graph
public final Tree<V,E> getSubTree(V vertex)
vertex
as it's root.vertex
- the root node of the subtree.public final Collection<E> getInEdges(V vertex)
Graph
Collection
view of the incoming edges incident to
vertex
in this graph.public final Collection<E> getOutEdges(V vertex)
Graph
Collection
view of the outgoing edges incident to
vertex
in this graph.public final Collection<V> getPredecessors(V vertex)
Graph
Collection
view of the predecessors of
vertex
in this graph. A predecessor of
vertex
is defined as a vertex
v
which is connected to
vertex
by an edge
e
, where
e
is an outgoing edge of
v
and an incoming edge of
vertex
.public final Collection<V> getSuccessors(V vertex)
Graph
Collection
view of the successors of
vertex
in this graph. A successor of
vertex
is defined as a vertex
v
which is connected to
vertex
by an edge
e
, where
e
is an incoming edge of
v
and an outgoing edge of
vertex
.public final int inDegree(V vertex)
Graph
vertex
. Equivalent to
getInEdges(vertex).size()
.public final int outDegree(V vertex)
Graph
vertex
. Equivalent to
getOutEdges(vertex).size()
.public final boolean isPredecessor(V v1, V v2)
Graph
true
if
v1
is a predecessor of
v2
in this graph. Equivalent to
v1.getPredecessors().contains(v2)
.public final boolean isSuccessor(V v1, V v2)
Graph
true
if
v1
is a successor of
v2
in this graph. Equivalent to
v1.getSuccessors().contains(v2)
.public final int getPredecessorCount(V vertex)
Graph
vertex
has in this graph. Equivalent to
vertex.getPredecessors().size()
.public final int getSuccessorCount(V vertex)
Graph
vertex
has in this graph. Equivalent to
vertex.getSuccessors().size()
.public final V getSource(E directedEdge)
Graph
directed_edge
is a directed edge in this graph, returns the source; otherwise returns
null
. The source of a directed edge
d
is defined to be the vertex for which
d
is an outgoing edge.
directed_edge
is guaranteed to be a directed edge if its
EdgeType
is
DIRECTED
.public final V getDest(E directedEdge)
Graph
directed_edge
is a directed edge in this graph, returns the destination; otherwise returns
null
. The destination of a directed edge
d
is defined to be the vertex incident to
d
for which
d
is an incoming edge.
directed_edge
is guaranteed to be a directed edge if its
EdgeType
is
DIRECTED
.public final boolean isSource(V vertex, E edge)
Graph
true
if
vertex
is the source of
edge
. Equivalent to
getSource(edge).equals(vertex)
.public final boolean isDest(V vertex, E edge)
Graph
true
if
vertex
is the destination of
edge
. Equivalent to
getDest(edge).equals(vertex)
.public final boolean addEdge(E e, V v1, V v2)
Graph
e
to this graph such that it connects vertex
v1
to
v2
. Equivalent to
addEdge(e, new Pair(v1, v2))
. If this graph does not contain
v1
,
v2
, or both, implementations may choose to either silently add the vertices to the graph or throw an
IllegalArgumentException
. If this graph assigns edge types to its edges, the edge type of
e
will be the default for this graph. See
Hypergraph.addEdge()
for a listing of possible reasons for failure.addEdge
in interface Graph<V extends Vertex,E extends Edge<V>>
e
- the edge to be addedv1
- the first vertex to be connectedv2
- the second vertex to be connectedtrue
if the add is successful, false
otherwiseHypergraph#addEdge(Object, Collection)
,
#addEdge(Object, Object, Object, EdgeType)
public final boolean addEdge(E e, V v1, V v2, EdgeType edgeType)
Graph
e
to this graph such that it connects vertex
v1
to
v2
. Equivalent to
addEdge(e, new Pair(v1, v2))
. If this graph does not contain
v1
,
v2
, or both, implementations may choose to either silently add the vertices to the graph or throw an
IllegalArgumentException
. If
edgeType
is not legal for this graph, this method will throw
IllegalArgumentException
. See
Hypergraph.addEdge()
for a listing of possible reasons for failure.addEdge
in interface Graph<V extends Vertex,E extends Edge<V>>
e
- the edge to be addedv1
- the first vertex to be connectedv2
- the second vertex to be connectededgeType
- the type to be assigned to the edgetrue
if the add is successful, false
otherwiseHypergraph#addEdge(Object, Collection)
,
#addEdge(Object, Object, Object)
public final Pair<V,V> getEndpoints(E edge)
Graph
edge
as a
Pair
.public final V getOpposite(V vertex, E edge)
Graph
edge
from
vertex
. (That is, returns the vertex incident to
edge
which is not
vertex
.)public final int getVertexCount()
Graph
public final V getVertex(String id)
Graph
public final Collection<V> getVertices()
Graph
Collection
contract, and therefore makes no guarantees about the ordering of the vertices within the
set.public final E getEdge(String id)
Graph
public final Collection<E> getEdges()
Graph
Collection
contract, and therefore makes no guarantees about the ordering of the edges within the
set.public final V getPredecessor(V vertex)
vertex
in this graph that is the source of the (single) edge that is incident on this
vertex. A vertex on a tree has only one incident edge but several.vertex
- the vertex whose predecessor is to be returnedCollection
view of the predecessors of vertex
in this graphpublic final boolean removeVertex(V vertex)
Graph
public final boolean removeEdge(E edge)
Graph
edge
from this graph.
Fails if edge
is null, or is otherwise not an element of this graph.public final void addSubtree(Tree<V,E> subtree, V node, E connectingEdge)
subtree
- the tree to be added.node
- the node at which the tree is to be added.connectingEdge
- the edge that will be used to connect node
to the root of the subtree.public final EdgeType getEdgeType()
Graph
public final void addVertexAttribute(String name, Class type, String defaultValue)
Graph
public final void addEdgeAttribute(String name, Class type, String defaultValue)
Graph
Copyright © 2015 University of Glasgow. All rights reserved.