graph.ordering

Class TopologicalOrdering

java.lang.Object

graph.ordering.TopologicalOrdering

public class TopologicalOrdering
extends java.lang.Object

A topological ordering T(G) is an assignment of integer values T(v) to each vertex v in V such that for every directed edge (u,v) in E T(u) < T(v)

Author:

Renata

Constructor Summary

Constructors

Constructor and Description
TopologicalOrdering()

Method Summary

Modifier and Type	Method and Description
static <V extends Vertex,E extends Edge<V>> java.util.Map<V,java.lang.Integer>	calculateOrdering(Graph<V,E> graph) Finds the topological ordering

Methods inherited from class java.lang.Object

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

Constructor Detail

TopologicalOrdering

public TopologicalOrdering()

Method Detail

calculateOrdering

public static <V extends Vertex,E extends Edge<V>> java.util.Map<V,java.lang.Integer> calculateOrdering(Graph<V,E> graph)
                                                                                                 throws CannotBeAppliedException

Finds the topological ordering

Type Parameters:

V - The vertex type

E - The edge type

Parameters:

graph - Graph

Returns:

A map of vertex to integer values - topological ordering of graph graph

Throws:

CannotBeAppliedException - if the graph doesn't have topological ordering