alma.acs.algorithms

Class TopologicalSort

java.lang.Object

alma.acs.algorithms.TopologicalSort

public class TopologicalSort
extends java.lang.Object

Topological sort algorithm, following Cormen et al, "Introduction to Algorithms".

To be used to sort a list of interdependent nodes, or to find out that this is impossible because the dependencies are cyclic. Applications need to wrap each of their nodes with a Vertex object, set up the directed dependencies between any two such vertex objects (see addAdjacentVertex), run the sort algorithm, and then extract the original nodes from the sorted vertices.

Expected use is to detangle component dependencies etc.

Constructor Summary

Constructors

Constructor and Description
TopologicalSort(java.util.Collection<Vertex> vertices) Constructor that takes the nodes, which we hope form a directed acyclic graph

Method Summary

Modifier and Type	Method and Description
java.util.Map	getCyclicVertices() Returns the vertices (graph nodes) that form a back edge in the graph.
boolean	hasCycles() States whether the graph contains cyclic dependencies, which implies that it could not be sorted.
java.util.List	sort() Tries to sort the vertices and to return them in a list.

Methods inherited from class java.lang.Object

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

Constructor Detail

TopologicalSort

public TopologicalSort(java.util.Collection<Vertex> vertices)

Constructor that takes the nodes, which we hope form a directed acyclic graph

Parameters:

vertices -

Method Detail

sort

public java.util.List sort()

Tries to sort the vertices and to return them in a list. The list will be incomplete if the graph could not be sorted, see hasCycles().

hasCycles

public boolean hasCycles()

States whether the graph contains cyclic dependencies, which implies that it could not be sorted. To be called after sort() was called.

Returns:

true if cycles were found

getCyclicVertices

public java.util.Map getCyclicVertices()

Returns the vertices (graph nodes) that form a back edge in the graph.

Returns:

Map [key = Vertex, Value = List of adjacent Vertex objects that form the cycle]