Package dev.nm.graph.type
Class SparseTree<V>
- java.lang.Object
-
- dev.nm.graph.type.SparseTree<V>
-
-
Constructor Summary
Constructors Constructor Description SparseTree(V root)
Construct a tree with a root.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description SparseTree<V>
addEdge(Arc<V> e)
Add an edge to the tree, connecting v1, the parent and v2..., the children.SparseTree<V>
addVertex(V v)
Adds a vertex to this graph.Set<V>
children(V v)
Gets the set of all children of this vertex.int
depth(V v)
Gets the (unweighted) distance of a vertex from the root of the vertex.Set<Arc<V>>
edges()
Gets the set of all edges in this graph.Set<Arc<V>>
edges(V v)
Gets the set of all edges associated with a vertex in this graph.int
height()
Gets the maximum depth in this tree.Set<Arc<V>>
incomingArcs(V v)
Gets the set of all incoming arcs associated with a vertex in this graph.Set<Arc<V>>
outgoingArcs(V v)
Gets the set of all outgoing arcs associated with a vertex in this graph.V
parent(V v)
Gets the unique parent of a vertex.Set<V>
parents(V v)
Gets the set of all parents of this vertex.SparseTree<V>
removeEdge(Arc<V> e)
Removes an edge from this graph.SparseTree<V>
removeVertex(V v)
Removes a vertex from this graph.V
root()
Gets the root of this tree.RootedTree<V,Arc<V>>
rotate(V v)
This method re-pivots the tree with a new root vertex.RootedTree<V,Arc<V>>
subTree(V v)
Gets a sub-tree starting from a vertex.int
topologicalOrder(V v)
Get the topological order of a vertex.Set<V>
vertices()
Gets the set of all vertices in this graph.
-
-
-
Constructor Detail
-
SparseTree
public SparseTree(V root)
Construct a tree with a root.- Parameters:
root
- the tree root
-
-
Method Detail
-
root
public V 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<V,Arc<V>>
- Returns:
- the root of this tree
-
depth
public int depth(V v)
Description copied from interface:RootedTree
Gets the (unweighted) distance of a vertex from the root of the vertex.- Specified by:
depth
in interfaceRootedTree<V,Arc<V>>
- 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<V,Arc<V>>
- Returns:
- the maximum depth in this tree
-
vertices
public Set<V> vertices()
Description copied from interface:Graph
Gets the set of all vertices in this graph.
-
edges
public Set<Arc<V>> edges()
Description copied from interface:Graph
Gets the set of all edges in this graph.
-
edges
public Set<Arc<V>> edges(V v)
Description copied from interface:Graph
Gets the set of all edges associated with a vertex in this graph.
-
addVertex
public SparseTree<V> addVertex(V v)
Description copied from interface:Graph
Adds a vertex to this graph. Does nothing ifv
is already in the graph.
-
addEdge
public SparseTree<V> addEdge(Arc<V> e)
Add an edge to the tree, connecting v1, the parent and v2..., the children. v1 must already exist in the tree, and the children must not already exist.
-
removeVertex
public SparseTree<V> removeVertex(V 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<V,Arc<V>>
- Parameters:
v
- the vertex to be removed- Returns:
- this graph (for builder pattern)
-
removeEdge
public SparseTree<V> removeEdge(Arc<V> 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<V,Arc<V>>
- Parameters:
e
- the edge to be removed- Returns:
- this graph (for builder pattern)
-
parent
public V parent(V v)
Description copied from interface:Tree
Gets the unique parent of a vertex.
-
subTree
public RootedTree<V,Arc<V>> subTree(V v)
Description copied from interface:RootedTree
Gets a sub-tree starting from a vertex.- Specified by:
subTree
in interfaceRootedTree<V,Arc<V>>
- Parameters:
v
- the root of the sub-tree- Returns:
- the sub-tree
-
rotate
public RootedTree<V,Arc<V>> rotate(V v)
This method re-pivots the tree with a new root vertex.- Parameters:
v
- the new root- Returns:
- a re-pivoted tree
-
topologicalOrder
public int topologicalOrder(V v)
Description copied from interface:DAGraph
Get the topological order of a vertex.- Specified by:
topologicalOrder
in interfaceDAGraph<V,Arc<V>>
- Parameters:
v
- a vertex- Returns:
- the topological order of a vertex
-
outgoingArcs
public Set<Arc<V>> outgoingArcs(V 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<V,Arc<V>>
- Parameters:
v
- a vertex- Returns:
- all outgoing arcs associated with a vertex
-
incomingArcs
public Set<Arc<V>> incomingArcs(V 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<V,Arc<V>>
- Parameters:
v
- a vertex- Returns:
- all incoming arcs associated with a vertex
-
parents
public Set<V> parents(V v)
Description copied from interface:DiGraph
Gets the set of all parents of this vertex.
-
-