Package com.jgalgo

Interface TopologicalOrderAlgo

public interface TopologicalOrderAlgo

Algorithm that calculate a topological order of graph vertices.

A topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge $(u,v)$, $u$ comes before $v$ in the ordering. A topological ordering exist if and only if the graph is directed and acyclic (DAG).

This algorithm compute the topological ordering of a given DAG graph in linear time and space.

Author:

Barak Ugav

See Also:

Wikipedia

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	TopologicalOrderAlgo.Builder	A builder for TopologicalOrderAlgo objects.
static interface	TopologicalOrderAlgo.Result	A result object of a TopologicalOrderAlgo algorithm.

Method Summary

Modifier and Type	Method	Description
TopologicalOrderAlgo.Result	computeTopologicalSorting(Graph g)	Compute the topological order of a DAG vertices.
static TopologicalOrderAlgo.Builder	newBuilder()	Create a new topological order algorithm builder.

Method Detail

computeTopologicalSorting

TopologicalOrderAlgo.Result computeTopologicalSorting(Graph g)

Compute the topological order of a DAG vertices.

Parameters:

g - a directed acyclic graph (DAG).

Returns:

a result object containing the computed order

Throws:

IllegalArgumentException - if the graph is not DAG

newBuilder

static TopologicalOrderAlgo.Builder newBuilder()

Create a new topological order algorithm builder.

This is the recommended way to instantiate a new TopologicalOrderAlgo object.

Returns:

a new builder that can build TopologicalOrderAlgo objects