public class OrderedKAryTree<V,E> extends AbstractTypedGraph<V,E> implements edu.uci.ics.jung.graph.Tree<V,E>
Tree
in which each vertex has
<= k children. The value of 'k' is specified by the constructor
parameter. A specific child (edge) can be retrieved directly by specifying the
index at which the child is located. By default, new (child) vertices
are added at the lowest index available, if no index is specified.Modifier and Type | Class and Description |
---|---|
protected class |
OrderedKAryTree.VertexData |
Modifier and Type | Field and Description |
---|---|
protected java.util.Map<E,edu.uci.ics.jung.graph.util.Pair<V>> |
edge_vpairs |
protected int |
height |
protected int |
order |
protected V |
root |
protected java.util.Map<V,OrderedKAryTree.VertexData> |
vertex_data |
edge_type
Constructor and Description |
---|
OrderedKAryTree(int order)
Creates a new instance with the specified order (maximum number of children).
|
Modifier and Type | Method and Description |
---|---|
boolean |
addEdge(E edge,
java.util.Collection<? extends V> vertices,
edu.uci.ics.jung.graph.util.EdgeType edge_type) |
boolean |
addEdge(E edge,
edu.uci.ics.jung.graph.util.Pair<? extends V> endpoints,
edu.uci.ics.jung.graph.util.EdgeType edgeType)
Adds
edge to this graph with the specified endpoints
and EdgeType . |
boolean |
addEdge(E e,
V parent,
V child) |
boolean |
addEdge(E e,
V v1,
V v2,
edu.uci.ics.jung.graph.util.EdgeType edge_type) |
boolean |
addEdge(E e,
V parent,
V child,
int index)
Adds the specified
child vertex and edge e to the graph
with the specified parent vertex parent . |
boolean |
addVertex(V vertex) |
boolean |
containsEdge(E edge) |
boolean |
containsVertex(V vertex) |
E |
findEdge(V v1,
V v2) |
java.util.Collection<E> |
findEdgeSet(V v1,
V v2) |
V |
getChild(V vertex,
int index)
Returns the child of
vertex at position index
in this tree, or null if it has no child at that position. |
int |
getChildCount(V vertex)
Returns the number of children that
vertex has. |
E |
getChildEdge(V vertex,
int index)
Returns the child edge of the vertex at index
index . |
java.util.Collection<E> |
getChildEdges(V vertex) |
java.util.Collection<V> |
getChildren(V vertex)
Returns an ordered list of
vertex 's child vertices. |
int |
getDepth(V vertex) |
V |
getDest(E directed_edge) |
int |
getEdgeCount() |
java.util.Collection<E> |
getEdges() |
edu.uci.ics.jung.graph.util.Pair<V> |
getEndpoints(E edge) |
static <V,E> org.apache.commons.collections4.Factory<edu.uci.ics.jung.graph.DirectedGraph<V,E>> |
getFactory(int order)
Returns a
Factory that creates an instance of this graph type. |
int |
getHeight()
Returns the height of the tree, or -1 if the tree is empty.
|
int |
getIncidentCount(E edge) |
java.util.Collection<E> |
getIncidentEdges(V vertex) |
java.util.Collection<V> |
getIncidentVertices(E edge) |
java.util.Collection<E> |
getInEdges(V vertex) |
int |
getNeighborCount(V vertex) |
java.util.Collection<V> |
getNeighbors(V vertex) |
V |
getOpposite(V vertex,
E edge) |
java.util.Collection<E> |
getOutEdges(V vertex) |
V |
getParent(V vertex) |
E |
getParentEdge(V vertex) |
int |
getPredecessorCount(V vertex) |
java.util.Collection<V> |
getPredecessors(V vertex) |
V |
getRoot() |
V |
getSource(E directed_edge) |
int |
getSuccessorCount(V vertex) |
java.util.Collection<V> |
getSuccessors(V vertex) |
java.util.Collection<edu.uci.ics.jung.graph.Tree<V,E>> |
getTrees() |
int |
getVertexCount() |
java.util.Collection<V> |
getVertices() |
int |
inDegree(V vertex) |
boolean |
isDest(V vertex,
E edge) |
boolean |
isIncident(V vertex,
E edge) |
boolean |
isLeaf(V vertex)
Returns
true if vertex is a leaf of this tree,
i.e., if it has no children. |
boolean |
isNeighbor(V v1,
V v2) |
boolean |
isPredecessor(V v1,
V v2)
Returns true iff
v1 is the parent of v2 . |
boolean |
isRoot(V vertex)
Returns
true if vertex is a leaf of this tree,
i.e., if it has no children. |
boolean |
isSource(V vertex,
E edge) |
boolean |
isSuccessor(V v1,
V v2) |
int |
outDegree(V vertex) |
boolean |
removeEdge(E edge) |
boolean |
removeVertex(V vertex) |
getDefaultEdgeType, getEdgeCount, getEdges, getEdgeType, hasEqualEdgeType, validateEdgeType
addEdge, addEdge, degree, getValidatedEndpoints, toString
protected java.util.Map<V,OrderedKAryTree.VertexData> vertex_data
protected int height
protected V root
protected int order
public OrderedKAryTree(int order)
public static <V,E> org.apache.commons.collections4.Factory<edu.uci.ics.jung.graph.DirectedGraph<V,E>> getFactory(int order)
Factory
that creates an instance of this graph type.V
- the vertex type for the graph factoryE
- the edge type for the graph factorypublic int getChildCount(V vertex)
vertex
has.public E getChildEdge(V vertex, int index)
index
.vertex
- index
- index
public java.util.Collection<V> getChildren(V vertex)
vertex
's child vertices.
If there is no child in position i, then the list will contain
null
in position i. If vertex
has no children
then the empty set will be returned.public int getDepth(V vertex)
public int getHeight()
public V getRoot()
public boolean addEdge(E e, V parent, V child, int index)
child
vertex and edge e
to the graph
with the specified parent vertex parent
. If index
is
greater than or equal to 0, then the child is placed at position
index
; if it is less than 0, the child is placed at the lowest
available position; if it is greater than or equal to the order of this
tree, an exception is thrown.Graph.addEdge(java.lang.Object, java.lang.Object, java.lang.Object)
public V getOpposite(V vertex, E edge)
getOpposite
in interface edu.uci.ics.jung.graph.Graph<V,E>
getOpposite
in class AbstractGraph<V,E>
Graph.getOpposite(java.lang.Object, java.lang.Object)
public int getPredecessorCount(V vertex)
getPredecessorCount
in interface edu.uci.ics.jung.graph.Graph<V,E>
getPredecessorCount
in class AbstractGraph<V,E>
vertex
is the root, -1 if the vertex is
not an element of this tree, and 1 otherwiseGraph.getPredecessorCount(java.lang.Object)
public int getSuccessorCount(V vertex)
getSuccessorCount
in interface edu.uci.ics.jung.graph.Graph<V,E>
getSuccessorCount
in class AbstractGraph<V,E>
Graph.getSuccessorCount(java.lang.Object)
public int inDegree(V vertex)
public boolean isLeaf(V vertex)
true
if vertex
is a leaf of this tree,
i.e., if it has no children.vertex
- the vertex to be queriedtrue
if outDegree(vertex)==0
public boolean isPredecessor(V v1, V v2)
v1
is the parent of v2
.
Note that if v2
is the root and v1
is null
,
this method returns true
.isPredecessor
in interface edu.uci.ics.jung.graph.Graph<V,E>
isPredecessor
in class AbstractGraph<V,E>
Graph.isPredecessor(java.lang.Object, java.lang.Object)
public boolean isRoot(V vertex)
true
if vertex
is a leaf of this tree,
i.e., if it has no children.vertex
- the vertex to be queriedtrue
if outDegree(vertex)==0
public boolean isSuccessor(V v1, V v2)
isSuccessor
in interface edu.uci.ics.jung.graph.Graph<V,E>
isSuccessor
in class AbstractGraph<V,E>
Graph.isSuccessor(java.lang.Object, java.lang.Object)
public int outDegree(V vertex)
public boolean addEdge(E edge, java.util.Collection<? extends V> vertices, edu.uci.ics.jung.graph.util.EdgeType edge_type)
public boolean addVertex(V vertex)
public boolean isIncident(V vertex, E edge)
isIncident
in interface edu.uci.ics.jung.graph.Hypergraph<V,E>
isIncident
in class AbstractGraph<V,E>
Hypergraph.isIncident(java.lang.Object, java.lang.Object)
public boolean isNeighbor(V v1, V v2)
isNeighbor
in interface edu.uci.ics.jung.graph.Hypergraph<V,E>
isNeighbor
in class AbstractGraph<V,E>
Hypergraph.isNeighbor(java.lang.Object, java.lang.Object)
public boolean containsEdge(E edge)
public boolean containsVertex(V vertex)
public java.util.Collection<E> findEdgeSet(V v1, V v2)
findEdgeSet
in interface edu.uci.ics.jung.graph.Hypergraph<V,E>
findEdgeSet
in class AbstractGraph<V,E>
Hypergraph.findEdgeSet(java.lang.Object, java.lang.Object)
public V getChild(V vertex, int index)
vertex
at position index
in this tree, or null
if it has no child at that position.vertex
- the vertex to queryvertex
at position index
in this tree, or null
if it has no child at that positionjava.lang.ArrayIndexOutOfBoundsException
- if index
is not in
the range [0, order-1]
public int getEdgeCount()
public java.util.Collection<E> getEdges()
public int getIncidentCount(E edge)
getIncidentCount
in interface edu.uci.ics.jung.graph.Hypergraph<V,E>
getIncidentCount
in class AbstractGraph<V,E>
Hypergraph.getIncidentCount(java.lang.Object)
public java.util.Collection<V> getIncidentVertices(E edge)
getIncidentVertices
in interface edu.uci.ics.jung.graph.Hypergraph<V,E>
getIncidentVertices
in class AbstractGraph<V,E>
Hypergraph.getIncidentVertices(java.lang.Object)
public int getNeighborCount(V vertex)
getNeighborCount
in interface edu.uci.ics.jung.graph.Hypergraph<V,E>
getNeighborCount
in class AbstractGraph<V,E>
Hypergraph.getNeighborCount(java.lang.Object)
public int getVertexCount()
public java.util.Collection<V> getVertices()
public boolean removeEdge(E edge)
public boolean removeVertex(V vertex)
public boolean addEdge(E edge, edu.uci.ics.jung.graph.util.Pair<? extends V> endpoints, edu.uci.ics.jung.graph.util.EdgeType edgeType)
AbstractGraph
edge
to this graph with the specified endpoints
and EdgeType
.addEdge
in class AbstractGraph<V,E>
true iff the graph was modified as a result of this call