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.intdepth(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.intheight()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.Vparent(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.Vroot()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.inttopologicalOrder(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:RootedTreeGets the root of this tree. The root is defined to be the vertex with respect to which vertex depth is measured.- Specified by:
rootin interfaceRootedTree<V,Arc<V>>- Returns:
- the root of this tree
-
depth
public int depth(V v)
Description copied from interface:RootedTreeGets the (unweighted) distance of a vertex from the root of the vertex.- Specified by:
depthin 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:RootedTreeGets the maximum depth in this tree.- Specified by:
heightin interfaceRootedTree<V,Arc<V>>- Returns:
- the maximum depth in this tree
-
vertices
public Set<V> vertices()
Description copied from interface:GraphGets the set of all vertices in this graph.
-
edges
public Set<Arc<V>> edges()
Description copied from interface:GraphGets the set of all edges in this graph.
-
edges
public Set<Arc<V>> edges(V v)
Description copied from interface:GraphGets the set of all edges associated with a vertex in this graph.
-
addVertex
public SparseTree<V> addVertex(V v)
Description copied from interface:GraphAdds a vertex to this graph. Does nothing ifvis 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:GraphRemoves a vertex from this graph. Does nothing ifvis not in the graph. The edges associated with this vertex are also removed.- Specified by:
removeVertexin 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:GraphRemoves an edge from this graph. Does nothing ifeis not in the graph. The vertices associated with the edge is not removed.- Specified by:
removeEdgein 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:TreeGets the unique parent of a vertex.
-
subTree
public RootedTree<V,Arc<V>> subTree(V v)
Description copied from interface:RootedTreeGets a sub-tree starting from a vertex.- Specified by:
subTreein 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:DAGraphGet the topological order of a vertex.- Specified by:
topologicalOrderin 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:DiGraphGets the set of all outgoing arcs associated with a vertex in this graph.- Specified by:
outgoingArcsin 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:DiGraphGets the set of all incoming arcs associated with a vertex in this graph.- Specified by:
incomingArcsin 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:DiGraphGets the set of all parents of this vertex.
-
-