org.graphstream.algorithm

Class TopologicalSortKahn

java.lang.Object

org.graphstream.algorithm.TopologicalSortKahn

All Implemented Interfaces:

Algorithm

public class TopologicalSortKahn
extends java.lang.Object
implements Algorithm

Implementation of Kahn's algorithm for a topological sorting of a directed acyclic graph (DAG). Every DAG has at least one topological ordering and this is a algorithm known for constructing a topological ordering in linear time without considering initial copying the graph and searching for source nodes.

Computational Complexity:

O(VxE) time, where V and E are the number of vertices and edges respectively.

Scientific Reference:

Kahn, Arthur B. (1962), "Topological sorting of large networks", Communications of the ACM, 5 (11): 558–562

Constructor Summary

Constructors

Constructor and Description
TopologicalSortKahn()

Method Summary

Modifier and Type	Method and Description
void	compute() Run the algorithm.
java.lang.String	defaultResult()
java.util.List<org.graphstream.graph.Node>	getSortedNodes() gets sorted list of the given graph
void	init(org.graphstream.graph.Graph theGraph) Initialization of the algorithm.

Methods inherited from class java.lang.Object

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

Constructor Detail

TopologicalSortKahn

public TopologicalSortKahn()

Method Detail

init

public void init(org.graphstream.graph.Graph theGraph)

Description copied from interface: Algorithm

Initialization of the algorithm. This method has to be called before the Algorithm.compute() method to initialize or reset the algorithm according to the new given graph.

Specified by:

init in interface Algorithm

Parameters:

theGraph - The graph this algorithm is using.

compute

public void compute()

Description copied from interface: Algorithm

Run the algorithm. The Algorithm.init(Graph) method has to be called before computing.

Specified by:

compute in interface Algorithm

See Also:

Algorithm.init(Graph)

getSortedNodes

public java.util.List<org.graphstream.graph.Node> getSortedNodes()

gets sorted list of the given graph

Returns:

topological sorted list of nodes

defaultResult

public java.lang.String defaultResult()