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 Details

TopologicalOrderAlgoImpl

public TopologicalOrderAlgoImpl()

Create a new topological order algorithm.

Please prefer using TopologicalOrderAlgo.newInstance() to get a default implementation for the TopologicalOrderAlgo interface.