com.codemelon.graph.algorithm.search

Class TopologicalSort<T extends ColoredVertex>

java.lang.Object

com.codemelon.graph.algorithm.search.TopologicalSort<T>

public class TopologicalSort<T extends ColoredVertex>
extends java.lang.Object

Assuming that there is no cycle in the graph, this algorithm creates a linked list representing an ordering that respects the edges in the graph. That is, for any 2 distinct vertices u and v, if the graph contains the edge (u, v), then u < v in the given ordering. If the graph contains a cycle, then no such ordering exists. Cf. CLRS, pp. 612ff. In order to allow the application of this algorithm to both DirectedEdgeDataGraph and DirectedSimpleGraph, the algorithm is implemented for AbstractGraph. This means that it can also in principle be run on undirected graphs, although in such cases the algorithm produces no useful results, since all such graphs contain a cycle if they contain any edges at all.

Constructor Summary

Constructors

Constructor and Description
TopologicalSort(AbstractGraph<T> graph) This constructor modifies the colors of the vertices in the graph.

Method Summary

Methods

Modifier and Type	Method and Description
java.util.LinkedList<ColoredVertex>	getSortedVertices() Returns a linked list of vertices in topologically sorted order.
boolean	precedes(ColoredVertex earlier, ColoredVertex later) Returns true if earlier precedes later in the topologically sorted list.

Methods inherited from class java.lang.Object

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

Constructor Detail

TopologicalSort

public TopologicalSort(AbstractGraph<T> graph)

This constructor modifies the colors of the vertices in the graph.

Parameters:

graph - graph whose vertices are to be topologically sorted

Method Detail

getSortedVertices

public java.util.LinkedList<ColoredVertex> getSortedVertices()

Returns a linked list of vertices in topologically sorted order. That is, for any 2 distinct vertices u and v, if the graph contains the edge (u, v) and if the graph doesn't contain a cycle, then u precedes v in the list. If the graph contains a cycle, the list will be meaningless.

Returns:

a linked list of vertices in topologically sorted order

precedes

public boolean precedes(ColoredVertex earlier,
               ColoredVertex later)

Returns true if earlier precedes later in the topologically sorted list. Returns false for equal vertices and for all other cases where earlier does not precede later in the list.

Parameters:

earlier - vertex tested for being earlier

later - vertex tested for being later

Returns:

true if earlier precedes later