Package org.graph4j.ordering

Class TopologicalOrdering

java.lang.Object

org.graph4j.DirectedGraphAlgorithm

org.graph4j.ordering.TopologicalOrdering

public class TopologicalOrdering
extends DirectedGraphAlgorithm

Computes an ordering of a directed graph vertices such that for every directed edge (u,v) from vertex u to vertex v, u comes before v in the ordering. A graph is chordal if and only if it has a perfect elimination ordering. For a chordal graph, LexBFS and Maximum Cardinality Search algorithms produce reversed perfect elimination orderings.

Author:

Cristian Frăsinaru

Field Summary

Fields inherited from class org.graph4j.DirectedGraphAlgorithm

graph, stronglyConnected

Constructor Summary

Constructors

Constructor	Description
TopologicalOrdering(Digraph digraph)

Method Summary

Modifier and Type	Method	Description
int[]	findOrdering()
int[]	getLevels()
boolean	isUnique()	Checks if the topological sorting is unique.

Methods inherited from class org.graph4j.DirectedGraphAlgorithm

isStronglyConnected

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

TopologicalOrdering

public TopologicalOrdering(Digraph digraph)

Parameters:

digraph - the input directed graph.

Method Details

findOrdering

public int[] findOrdering()

Returns:

the topological order, or null if the digraph is not acyclic.

isUnique

public boolean isUnique()

Checks if the topological sorting is unique. If it is unique, the digraph contains a Hamiltonian path.

Returns:

true if the topological sorting exists and it is unique.

getLevels

public int[] getLevels()

Returns:

the levels of the DAG.