Package dev.nm.graph.algorithm.traversal
Class TraversalFromRoots<V>
- java.lang.Object
-
- dev.nm.graph.algorithm.traversal.TraversalFromRoots<V>
-
- Type Parameters:
V
- vertex type
- All Implemented Interfaces:
GraphTraversal<V>
public abstract class TraversalFromRoots<V> extends Object implements GraphTraversal<V>
A graph traversal is the problem of visiting all the nodes in a graph in a particular manner. For a directed graph, this implementation chooses as roots those vertices that have no incoming arcs.- See Also:
- Wikipedia: Graph traversal
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface dev.nm.graph.algorithm.traversal.GraphTraversal
GraphTraversal.Node<V>
-
-
Constructor Summary
Constructors Constructor Description TraversalFromRoots(Graph<? extends V,? extends Edge<V>> g)
Constructs a traversal order of a graph.
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description List<? extends GraphTraversal.Node<V>>
getOrderedNodes()
Gets the collection of visited nodes to build a spanning tree.abstract List<? extends GraphTraversal.Node<V>>
track(V root, int time)
Runs the traversal algorithm on a graph from a designated root.List<V>
traverse(V root, int time)
Runs the traversal algorithm on a graph from a designated root.
-
-
-
Method Detail
-
track
public abstract List<? extends GraphTraversal.Node<V>> track(V root, int time)
Runs the traversal algorithm on a graph from a designated root.- Parameters:
root
- a roottime
- the initial time- Returns:
- the nodes visited
-
traverse
public List<V> traverse(V root, int time)
Runs the traversal algorithm on a graph from a designated root.- Parameters:
root
- a roottime
- the initial time- Returns:
- the vertices visited
-
getOrderedNodes
public List<? extends GraphTraversal.Node<V>> getOrderedNodes()
Gets the collection of visited nodes to build a spanning tree.- Specified by:
getOrderedNodes
in interfaceGraphTraversal<V>
- Returns:
- the collection of visited nodes
-
-