Package com.jgalgo.alg

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.

Use newInstance() to get a default implementation of this interface.

Author:

Barak Ugav

See Also:

Wikipedia

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	TopologicalOrderAlgo.IResult	A result object of a TopologicalOrderAlgo algorithm for IntGraph.
static interface	TopologicalOrderAlgo.Result<V,E>	A result object of a TopologicalOrderAlgo algorithm.

Method Summary

Modifier and Type	Method	Description
<V,E> TopologicalOrderAlgo.Result<V,E>	computeTopologicalSorting(Graph<V,E> g)	Compute the topological order of a DAG vertices.
static TopologicalOrderAlgo	newInstance()	Create a new topological order algorithm object.

Method Detail

computeTopologicalSorting

<V,E> TopologicalOrderAlgo.Result<V,E> computeTopologicalSorting(Graph<V,E> g)

Compute the topological order of a DAG vertices.

If g is IntGraph, the returned object is TopologicalOrderAlgo.IResult.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a directed acyclic graph (DAG).

Returns:

a result object containing the computed order

Throws:

IllegalArgumentException - if the graph is not DAG

newInstance

static TopologicalOrderAlgo newInstance()

Create a new topological order algorithm object.

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

Returns:

a default implementation of TopologicalOrderAlgo