org.graphstream.algorithm

Class TopologicalSortDFS

java.lang.Object

org.graphstream.algorithm.TopologicalSortDFS

All Implemented Interfaces:

Algorithm

public class TopologicalSortDFS
extends java.lang.Object
implements Algorithm

Implementation of depth first search 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.

Computational Complexity:

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

Scientific Reference:

Tarjan, Robert E. (1976), "Edge-disjoint spanning trees and depth-first search", Acta Informatica, 6 (2): 171–185

Constructor Summary

Constructors

Constructor and Description
TopologicalSortDFS()

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

TopologicalSortDFS

public TopologicalSortDFS()

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()