Package com.jgalgo.alg.dag

Interface TopologicalOrderAlgo

All Known Implementing Classes:

TopologicalOrderAlgoAbstract, TopologicalOrderAlgoImpl

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
default <V, E> TopologicalOrderAlgo.Result<V,E>	computeTopologicalSorting(Graph<V,E> g)	Compute the topological order of the vertices in a DAG graph.
<V, E> Optional<TopologicalOrderAlgo.Result<V,E>>	computeTopologicalSortingIfExist(Graph<V,E> g)	Compute the topological order of the vertices, if the graph is DAG.
static TopologicalOrderAlgo	newInstance()	Create a new topological order algorithm object.

Method Details

computeTopologicalSorting

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

Compute the topological order of the vertices in a DAG graph.

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

computeTopologicalSortingIfExist

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

Compute the topological order of the vertices, if the graph is DAG.

If g is IntGraph, the returned optional will contain is TopologicalOrderAlgo.IResult.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a directed graph

Returns:

an optional of a result object containing the computed order, or an empty optional 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