Package com.jgalgo.alg.dag
Class TopologicalOrderAlgoImpl
- java.lang.Object
-
- com.jgalgo.alg.dag.TopologicalOrderAlgoAbstract
-
- com.jgalgo.alg.dag.TopologicalOrderAlgoImpl
-
- All Implemented Interfaces:
TopologicalOrderAlgo
public class TopologicalOrderAlgoImpl extends TopologicalOrderAlgoAbstract
A simple algorithm that compute a topological order in a DAG graph.The algorithm perform iterations while maintaining the in-degree of each vertex. At each iteration, a vertex \(u\) with in-degree zero is added as the next vertex in the result topological order, and the vertex is 'removed' from the graph conceptually, practically the algorithm decrease the in-degree of each vertex reachable by one of \(u\)'s out going edges. If there is no vertex with zero in-degree before all vertices were added to the topological sort, there is a cycle and no topological order exists.
The algorithm is linear in both space and running time.
- Author:
- Barak Ugav
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface com.jgalgo.alg.dag.TopologicalOrderAlgo
TopologicalOrderAlgo.IResult, TopologicalOrderAlgo.Result<V,E>
-
-
Constructor Summary
Constructors Constructor Description TopologicalOrderAlgoImpl()Create a new topological order algorithm.
-
Method Summary
-
Methods inherited from class com.jgalgo.alg.dag.TopologicalOrderAlgoAbstract
computeTopologicalSortingIfExist
-
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Methods inherited from interface com.jgalgo.alg.dag.TopologicalOrderAlgo
computeTopologicalSorting
-
-
-
-
Constructor Detail
-
TopologicalOrderAlgoImpl
public TopologicalOrderAlgoImpl()
Create a new topological order algorithm.Please prefer using
TopologicalOrderAlgo.newInstance()to get a default implementation for theTopologicalOrderAlgointerface.
-
-