Package dev.nm.graph.type
Class VertexTree<T>
- java.lang.Object
-
- dev.nm.graph.type.VertexTree<T>
-
- Type Parameters:
T
- the data type of this vertex
- All Implemented Interfaces:
DAGraph<VertexTree<T>,Arc<VertexTree<T>>>
,DiGraph<VertexTree<T>,Arc<VertexTree<T>>>
,Graph<VertexTree<T>,Arc<VertexTree<T>>>
,RootedTree<VertexTree<T>,Arc<VertexTree<T>>>
,Tree<VertexTree<T>,Arc<VertexTree<T>>>
public class VertexTree<T> extends Object implements RootedTree<VertexTree<T>,Arc<VertexTree<T>>>
AVertexTree
is both a tree and a vertex/node.This implementation builds a tree incrementally and recursively (combining trees).
-
-
Constructor Summary
Constructors Constructor Description VertexTree(T t)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description VertexTree<T>
addEdge(Arc<VertexTree<T>> e)
Adds an edge to this graph.VertexTree<T>
addVertex(VertexTree<T> v)
Adds a vertex to this graph.Set<VertexTree<T>>
children(VertexTree<T> v)
Gets the set of all children of this vertex.T
data()
int
depth(VertexTree<T> v)
Gets the (unweighted) distance of a vertex from the root of the vertex.Set<Arc<VertexTree<T>>>
edges()
Gets the set of all edges in this graph.Set<Arc<VertexTree<T>>>
edges(VertexTree<T> v)
Gets the set of all edges associated with a vertex in this graph.static <T> List<Integer>
findPosition(VertexTree<T> node)
Finds the position of a node from its tree root recursively.int
height()
Gets the maximum depth in this tree.Set<Arc<VertexTree<T>>>
incomingArcs(VertexTree<T> v)
Gets the set of all incoming arcs associated with a vertex in this graph.Set<Arc<VertexTree<T>>>
outgoingArcs(VertexTree<T> v)
Gets the set of all outgoing arcs associated with a vertex in this graph.VertexTree<T>
parent(VertexTree<T> v)
Gets the unique parent of a vertex.Set<VertexTree<T>>
parents(VertexTree<T> v)
Gets the set of all parents of this vertex.VertexTree<T>
removeEdge(Arc<VertexTree<T>> e)
Removes an edge from this graph.VertexTree<T>
removeVertex(VertexTree<T> v)
Removes a vertex from this graph.VertexTree<T>
root()
Gets the root of this tree.RootedTree<VertexTree<T>,Arc<VertexTree<T>>>
subTree(VertexTree<T> v)
Gets a sub-tree starting from a vertex.int
topologicalOrder(VertexTree<T> v)
Get the topological order of a vertex.String
toString()
Set<VertexTree<T>>
vertices()
Gets the set of all vertices in this graph.
-
-
-
Constructor Detail
-
VertexTree
public VertexTree(T t)
-
-
Method Detail
-
findPosition
public static <T> List<Integer> findPosition(VertexTree<T> node)
Finds the position of a node from its tree root recursively.- Parameters:
node
-- Returns:
- the section numbers
-
data
public T data()
-
parents
public Set<VertexTree<T>> parents(VertexTree<T> v)
Description copied from interface:DiGraph
Gets the set of all parents of this vertex.- Specified by:
parents
in interfaceDiGraph<VertexTree<T>,Arc<VertexTree<T>>>
- Parameters:
v
- a vertex- Returns:
- the set of all parents
-
children
public Set<VertexTree<T>> children(VertexTree<T> v)
Description copied from interface:DiGraph
Gets the set of all children of this vertex.- Specified by:
children
in interfaceDiGraph<VertexTree<T>,Arc<VertexTree<T>>>
- Parameters:
v
- a vertex- Returns:
- the set of all children
-
root
public VertexTree<T> root()
Description copied from interface:RootedTree
Gets the root of this tree. The root is defined to be the vertex with respect to which vertex depth is measured.- Specified by:
root
in interfaceRootedTree<VertexTree<T>,Arc<VertexTree<T>>>
- Returns:
- the root of this tree
-
depth
public int depth(VertexTree<T> v)
Description copied from interface:RootedTree
Gets the (unweighted) distance of a vertex from the root of the vertex.- Specified by:
depth
in interfaceRootedTree<VertexTree<T>,Arc<VertexTree<T>>>
- Parameters:
v
- the vertex whose depth is to be computed- Returns:
- the length of the shortest unweighted path from its root to the vertex
-
height
public int height()
Description copied from interface:RootedTree
Gets the maximum depth in this tree.- Specified by:
height
in interfaceRootedTree<VertexTree<T>,Arc<VertexTree<T>>>
- Returns:
- the maximum depth in this tree
-
subTree
public RootedTree<VertexTree<T>,Arc<VertexTree<T>>> subTree(VertexTree<T> v)
Description copied from interface:RootedTree
Gets a sub-tree starting from a vertex.- Specified by:
subTree
in interfaceRootedTree<VertexTree<T>,Arc<VertexTree<T>>>
- Parameters:
v
- the root of the sub-tree- Returns:
- the sub-tree
-
parent
public VertexTree<T> parent(VertexTree<T> v)
Description copied from interface:Tree
Gets the unique parent of a vertex.- Specified by:
parent
in interfaceTree<VertexTree<T>,Arc<VertexTree<T>>>
- Parameters:
v
- a vertex- Returns:
- the parent of
v
-
vertices
public Set<VertexTree<T>> vertices()
Description copied from interface:Graph
Gets the set of all vertices in this graph.- Specified by:
vertices
in interfaceGraph<VertexTree<T>,Arc<VertexTree<T>>>
- Returns:
- all vertices in this graph
-
edges
public Set<Arc<VertexTree<T>>> edges()
Description copied from interface:Graph
Gets the set of all edges in this graph.- Specified by:
edges
in interfaceGraph<VertexTree<T>,Arc<VertexTree<T>>>
- Returns:
- all edges in this graph
-
edges
public Set<Arc<VertexTree<T>>> edges(VertexTree<T> v)
Description copied from interface:Graph
Gets the set of all edges associated with a vertex in this graph.- Specified by:
edges
in interfaceGraph<VertexTree<T>,Arc<VertexTree<T>>>
- Parameters:
v
- a vertex- Returns:
- all edges associated with a vertex
-
addVertex
public VertexTree<T> addVertex(VertexTree<T> v)
Description copied from interface:Graph
Adds a vertex to this graph. Does nothing ifv
is already in the graph.- Specified by:
addVertex
in interfaceGraph<VertexTree<T>,Arc<VertexTree<T>>>
- Parameters:
v
- the vertex to add- Returns:
- this graph (for builder pattern)
-
addEdge
public VertexTree<T> addEdge(Arc<VertexTree<T>> e)
Description copied from interface:Graph
Adds an edge to this graph. Does nothing ife
is already in the graph. If the edge contains new vertices, those will be added to the graph.- Specified by:
addEdge
in interfaceGraph<VertexTree<T>,Arc<VertexTree<T>>>
- Parameters:
e
- the edge to add- Returns:
- this graph (for builder pattern)
-
removeVertex
public VertexTree<T> removeVertex(VertexTree<T> v)
Description copied from interface:Graph
Removes a vertex from this graph. Does nothing ifv
is not in the graph. The edges associated with this vertex are also removed.- Specified by:
removeVertex
in interfaceGraph<VertexTree<T>,Arc<VertexTree<T>>>
- Parameters:
v
- the vertex to be removed- Returns:
- this graph (for builder pattern)
-
removeEdge
public VertexTree<T> removeEdge(Arc<VertexTree<T>> e)
Description copied from interface:Graph
Removes an edge from this graph. Does nothing ife
is not in the graph. The vertices associated with the edge is not removed.- Specified by:
removeEdge
in interfaceGraph<VertexTree<T>,Arc<VertexTree<T>>>
- Parameters:
e
- the edge to be removed- Returns:
- this graph (for builder pattern)
-
topologicalOrder
public int topologicalOrder(VertexTree<T> v)
Description copied from interface:DAGraph
Get the topological order of a vertex.- Specified by:
topologicalOrder
in interfaceDAGraph<VertexTree<T>,Arc<VertexTree<T>>>
- Parameters:
v
- a vertex- Returns:
- the topological order of a vertex
-
outgoingArcs
public Set<Arc<VertexTree<T>>> outgoingArcs(VertexTree<T> v)
Description copied from interface:DiGraph
Gets the set of all outgoing arcs associated with a vertex in this graph.- Specified by:
outgoingArcs
in interfaceDiGraph<VertexTree<T>,Arc<VertexTree<T>>>
- Parameters:
v
- a vertex- Returns:
- all outgoing arcs associated with a vertex
-
incomingArcs
public Set<Arc<VertexTree<T>>> incomingArcs(VertexTree<T> v)
Description copied from interface:DiGraph
Gets the set of all incoming arcs associated with a vertex in this graph.- Specified by:
incomingArcs
in interfaceDiGraph<VertexTree<T>,Arc<VertexTree<T>>>
- Parameters:
v
- a vertex- Returns:
- all incoming arcs associated with a vertex
-
-