com.tensegrity.graph.algorithm
Class TopologicalSort

java.lang.Object
  com.tensegrity.graph.algorithm.TopologicalSort

public class TopologicalSort

extends java.lang.Object

This class implements the topological-sort algorithm. This algorithm also checks whether a graph has cycles or not. A sort may not be possible if there are cycles in a graph.

Version:

$Id: TopologicalSort.java,v 1.21 2005/05/24 14:17:20 KevinCVS Exp $

Author:

Stepan Rutz

Constructor Summary

TopologicalSort()
Constructs a new stateless instance of the TopologicalSort algorithm.

Method Summary

boolean	apply(Graph graph, Node[] order) Returns true if there is one or more cycles in the graph.
boolean	apply(Subgraph subgraph, Node[] order) Returns true if there is one or more cycles in the subgraph.

Methods inherited from class java.lang.Object

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

Constructor Detail

TopologicalSort

public TopologicalSort()

Constructs a new stateless instance of the TopologicalSort algorithm.

Method Detail

apply

public boolean apply(Graph graph,
                     Node[] order)
              throws GraphException

Returns true if there is one or more cycles in the graph. The array order[] is filled with the topological sorting.

Parameters:

graph - the Graph to examine, may not be null.

order - array that is filled with the order that is given by the topological sorting, may be null, in this the information is considered to be unwanted.

Returns:

true if there are cycles, otherwise the graph has no cycle and false is returned.

Throws:

GraphException - thrown if the is not directed.

apply

public boolean apply(Subgraph subgraph,
                     Node[] order)
              throws GraphException

Returns true if there is one or more cycles in the subgraph. The array order[] is filled with the topological sorting numbers.

Parameters:

subgraph - the Subgraph to examine, may not be null.

order - array that is filled with the order that is given by the topological sorting, may not be null.

Returns:

true if there are cycles, otherwise the subgraph has no cycle and false is returned.

Throws:

GraphException - thrown if the is not directed.