Package edu.uci.ics.jung.graph
Class OrderedKAryTree<V,E>
- java.lang.Object
-
- edu.uci.ics.jung.graph.AbstractGraph<V,E>
-
- edu.uci.ics.jung.graph.AbstractTypedGraph<V,E>
-
- edu.uci.ics.jung.graph.OrderedKAryTree<V,E>
-
- All Implemented Interfaces:
edu.uci.ics.jung.graph.DirectedGraph<V,E>
,edu.uci.ics.jung.graph.Forest<V,E>
,edu.uci.ics.jung.graph.Graph<V,E>
,edu.uci.ics.jung.graph.Hypergraph<V,E>
,edu.uci.ics.jung.graph.Tree<V,E>
,java.io.Serializable
public class OrderedKAryTree<V,E> extends AbstractTypedGraph<V,E> implements edu.uci.ics.jung.graph.Tree<V,E>
An implementation ofTree
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.- See Also:
- Serialized Form
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description protected class
OrderedKAryTree.VertexData
-
Field Summary
Fields Modifier and Type Field 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
-
Fields inherited from class edu.uci.ics.jung.graph.AbstractTypedGraph
edge_type
-
-
Constructor Summary
Constructors Constructor Description OrderedKAryTree(int order)
Creates a new instance with the specified order (maximum number of children).
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
addEdge(E edge, edu.uci.ics.jung.graph.util.Pair<? extends V> endpoints, edu.uci.ics.jung.graph.util.EdgeType edgeType)
Addsedge
to this graph with the specifiedendpoints
andEdgeType
.boolean
addEdge(E edge, java.util.Collection<? extends V> vertices, edu.uci.ics.jung.graph.util.EdgeType edge_type)
boolean
addEdge(E e, V parent, V child)
boolean
addEdge(E e, V parent, V child, int index)
Adds the specifiedchild
vertex and edgee
to the graph with the specified parent vertexparent
.boolean
addEdge(E e, V v1, V v2, edu.uci.ics.jung.graph.util.EdgeType edge_type)
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 ofvertex
at positionindex
in this tree, ornull
if it has no child at that position.int
getChildCount(V vertex)
Returns the number of children thatvertex
has.E
getChildEdge(V vertex, int index)
Returns the child edge of the vertex at indexindex
.java.util.Collection<E>
getChildEdges(V vertex)
java.util.Collection<V>
getChildren(V vertex)
Returns an ordered list ofvertex
'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 aFactory
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)
Returnstrue
ifvertex
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 iffv1
is the parent ofv2
.boolean
isRoot(V vertex)
Returnstrue
ifvertex
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)
-
Methods inherited from class edu.uci.ics.jung.graph.AbstractTypedGraph
getDefaultEdgeType, getEdgeCount, getEdges, getEdgeType, hasEqualEdgeType, validateEdgeType
-
Methods inherited from class edu.uci.ics.jung.graph.AbstractGraph
addEdge, addEdge, degree, getValidatedEndpoints, toString
-
-
-
-
Field Detail
-
vertex_data
protected java.util.Map<V,OrderedKAryTree.VertexData> vertex_data
-
height
protected int height
-
root
protected V root
-
order
protected int order
-
-
Method Detail
-
getFactory
public static <V,E> org.apache.commons.collections4.Factory<edu.uci.ics.jung.graph.DirectedGraph<V,E>> getFactory(int order)
Returns aFactory
that creates an instance of this graph type.- Type Parameters:
V
- the vertex type for the graph factoryE
- the edge type for the graph factory
-
getChildCount
public int getChildCount(V vertex)
Returns the number of children thatvertex
has.
-
getChildEdge
public E getChildEdge(V vertex, int index)
Returns the child edge of the vertex at indexindex
.- Parameters:
vertex
-index
-- Returns:
- the child edge of the vertex at index
index
-
getChildren
public java.util.Collection<V> getChildren(V vertex)
Returns an ordered list ofvertex
's child vertices. If there is no child in position i, then the list will containnull
in position i. Ifvertex
has no children then the empty set will be returned.
-
getDepth
public int getDepth(V vertex)
-
getHeight
public int getHeight()
Returns the height of the tree, or -1 if the tree is empty.
-
getRoot
public V getRoot()
-
addEdge
public boolean addEdge(E e, V parent, V child, int index)
Adds the specifiedchild
vertex and edgee
to the graph with the specified parent vertexparent
. Ifindex
is greater than or equal to 0, then the child is placed at positionindex
; 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.- See Also:
Graph.addEdge(java.lang.Object, java.lang.Object, java.lang.Object)
-
getOpposite
public V getOpposite(V vertex, E edge)
- Specified by:
getOpposite
in interfaceedu.uci.ics.jung.graph.Graph<V,E>
- Overrides:
getOpposite
in classAbstractGraph<V,E>
- See Also:
Graph.getOpposite(java.lang.Object, java.lang.Object)
-
getPredecessorCount
public int getPredecessorCount(V vertex)
- Specified by:
getPredecessorCount
in interfaceedu.uci.ics.jung.graph.Graph<V,E>
- Overrides:
getPredecessorCount
in classAbstractGraph<V,E>
- Returns:
- 0 if
vertex
is the root, -1 if the vertex is not an element of this tree, and 1 otherwise - See Also:
Graph.getPredecessorCount(java.lang.Object)
-
getSuccessorCount
public int getSuccessorCount(V vertex)
- Specified by:
getSuccessorCount
in interfaceedu.uci.ics.jung.graph.Graph<V,E>
- Overrides:
getSuccessorCount
in classAbstractGraph<V,E>
- See Also:
Graph.getSuccessorCount(java.lang.Object)
-
inDegree
public int inDegree(V vertex)
-
isLeaf
public boolean isLeaf(V vertex)
Returnstrue
ifvertex
is a leaf of this tree, i.e., if it has no children.- Parameters:
vertex
- the vertex to be queried- Returns:
true
ifoutDegree(vertex)==0
-
isPredecessor
public boolean isPredecessor(V v1, V v2)
Returns true iffv1
is the parent ofv2
. Note that ifv2
is the root andv1
isnull
, this method returnstrue
.- Specified by:
isPredecessor
in interfaceedu.uci.ics.jung.graph.Graph<V,E>
- Overrides:
isPredecessor
in classAbstractGraph<V,E>
- See Also:
Graph.isPredecessor(java.lang.Object, java.lang.Object)
-
isRoot
public boolean isRoot(V vertex)
Returnstrue
ifvertex
is a leaf of this tree, i.e., if it has no children.- Parameters:
vertex
- the vertex to be queried- Returns:
true
ifoutDegree(vertex)==0
-
isSuccessor
public boolean isSuccessor(V v1, V v2)
- Specified by:
isSuccessor
in interfaceedu.uci.ics.jung.graph.Graph<V,E>
- Overrides:
isSuccessor
in classAbstractGraph<V,E>
- See Also:
Graph.isSuccessor(java.lang.Object, java.lang.Object)
-
outDegree
public int outDegree(V vertex)
-
addEdge
public boolean addEdge(E edge, java.util.Collection<? extends V> vertices, edu.uci.ics.jung.graph.util.EdgeType edge_type)
-
addVertex
public boolean addVertex(V vertex)
-
isIncident
public boolean isIncident(V vertex, E edge)
- Specified by:
isIncident
in interfaceedu.uci.ics.jung.graph.Hypergraph<V,E>
- Overrides:
isIncident
in classAbstractGraph<V,E>
- See Also:
Hypergraph.isIncident(java.lang.Object, java.lang.Object)
-
isNeighbor
public boolean isNeighbor(V v1, V v2)
- Specified by:
isNeighbor
in interfaceedu.uci.ics.jung.graph.Hypergraph<V,E>
- Overrides:
isNeighbor
in classAbstractGraph<V,E>
- See Also:
Hypergraph.isNeighbor(java.lang.Object, java.lang.Object)
-
containsEdge
public boolean containsEdge(E edge)
-
containsVertex
public boolean containsVertex(V vertex)
-
findEdgeSet
public java.util.Collection<E> findEdgeSet(V v1, V v2)
- Specified by:
findEdgeSet
in interfaceedu.uci.ics.jung.graph.Hypergraph<V,E>
- Overrides:
findEdgeSet
in classAbstractGraph<V,E>
- See Also:
Hypergraph.findEdgeSet(java.lang.Object, java.lang.Object)
-
getChild
public V getChild(V vertex, int index)
Returns the child ofvertex
at positionindex
in this tree, ornull
if it has no child at that position.- Parameters:
vertex
- the vertex to query- Returns:
- the child of
vertex
at positionindex
in this tree, ornull
if it has no child at that position - Throws:
java.lang.ArrayIndexOutOfBoundsException
- ifindex
is not in the range[0, order-1]
-
getEdgeCount
public int getEdgeCount()
-
getEdges
public java.util.Collection<E> getEdges()
-
getIncidentCount
public int getIncidentCount(E edge)
- Specified by:
getIncidentCount
in interfaceedu.uci.ics.jung.graph.Hypergraph<V,E>
- Overrides:
getIncidentCount
in classAbstractGraph<V,E>
- See Also:
Hypergraph.getIncidentCount(java.lang.Object)
-
getIncidentVertices
public java.util.Collection<V> getIncidentVertices(E edge)
- Specified by:
getIncidentVertices
in interfaceedu.uci.ics.jung.graph.Hypergraph<V,E>
- Overrides:
getIncidentVertices
in classAbstractGraph<V,E>
- See Also:
Hypergraph.getIncidentVertices(java.lang.Object)
-
getNeighborCount
public int getNeighborCount(V vertex)
- Specified by:
getNeighborCount
in interfaceedu.uci.ics.jung.graph.Hypergraph<V,E>
- Overrides:
getNeighborCount
in classAbstractGraph<V,E>
- See Also:
Hypergraph.getNeighborCount(java.lang.Object)
-
getVertexCount
public int getVertexCount()
-
getVertices
public java.util.Collection<V> getVertices()
-
removeEdge
public boolean removeEdge(E edge)
-
removeVertex
public boolean removeVertex(V vertex)
-
addEdge
public boolean addEdge(E edge, edu.uci.ics.jung.graph.util.Pair<? extends V> endpoints, edu.uci.ics.jung.graph.util.EdgeType edgeType)
Description copied from class:AbstractGraph
Addsedge
to this graph with the specifiedendpoints
andEdgeType
.- Specified by:
addEdge
in classAbstractGraph<V,E>
- Returns:
- true iff the graph was modified as a result of this call
-
-