nz.ac.waikato.jdsl.graph.algo
Class AbstractTopologicalSort

java.lang.Object
  nz.ac.waikato.jdsl.graph.algo.AbstractTopologicalSort

Direct Known Subclasses:

TopologicalSort, UnitWeightedTopologicalNumbering

public abstract class AbstractTopologicalSort
extends java.lang.Object

This abstract class is the foundation for both types of topological sorts, that is, the standard variety where each vertex is given a unique number, and the level-numbering variety in which numbers attached to vertices are not unique. The algorithm can be constructed once, and used multiple times. The algorithm object is executed by calling the execute(InspectableGraph) method. After execution, the client can query the algorithm object for the numbers of particular vertices. The client should then call the cleanup() method, to ensure that all decorations are removed from the graph. The cleanup() method should be called after each execution of the algorithm. The topological sorts yield useful results only on a directed acyclic graph (DAG). Before querying for results, the client can use the public isCyclic() method to verify whether the graph was acyclic or not. If a graph with undirected edges is passed in to execute(.), an InvalidEdgeException is thrown immediately. If the graph is found to have cycles, the calls to number(Vertex) will result in an InvalidQueryException. Note that this algorithm will give valid results on disconnected as well as connected graphs.

Version:

JDSL 2.1.1

Author:

Lucy Perry (lep)

See Also:

TopologicalSort, UnitWeightedTopologicalNumbering

Field Summary

protected InspectableGraph	graph_ The Graph that the algorithm executes upon.
protected boolean	is_cyclic_ Whether the graph has cycles or not.
java.lang.Object	NUMBER_KEY_ This Object is the key for the numbering Decoration.
protected Sequence	queue_ Sequence used as a queue by the sort() method.

Constructor Summary

AbstractTopologicalSort()
Constructor.

Method Summary

void	cleanup() Cleans up all decorations that this algorithm was storing in the provided graph.
void	execute(InspectableGraph g) The client calls this method to execute the algorithm.
protected void	init(InspectableGraph g) This helper method is called by the execute(.) method.
boolean	isCyclic() Query method for asking whether the Graph is cyclic, (and therefore inappropriate for a topological ordering).
int	number(Vertex v) Used for retrieving the topological order-number associated with the given Vertex.
protected abstract void	sort() This abstract method is overridden in the subclasses.

Methods inherited from class java.lang.Object

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

Field Detail

graph_

protected InspectableGraph graph_

The Graph that the algorithm executes upon. It is passed in via the constructor.

is_cyclic_

protected boolean is_cyclic_

Whether the graph has cycles or not. Boolean to be calculated during the execute() method.

NUMBER_KEY_

public java.lang.Object NUMBER_KEY_

This Object is the key for the numbering Decoration. It is used to retrieve the topological order-number for a given Vertex. This key can be used by the client as a an equivalent alternative to the public accessor method number(Vertex). Note that attempting to access a topological number using this key may result in an InvalidAttributeException or an invalid number - if the graph was found to have cycles, or if execute(.) has not yet been called, or if cleanup() was not called after a previous execution.

queue_

protected Sequence queue_

Sequence used as a queue by the sort() method.

Constructor Detail

AbstractTopologicalSort

public AbstractTopologicalSort()

Constructor.

Method Detail

execute

public void execute(InspectableGraph g)
             throws InvalidEdgeException

The client calls this method to execute the algorithm. Note that if a null InspectableGraph g is passed in to this method, a NullPointerException will result from init(InspectableGraph). After an execution of the algorithm, the cleanup() method should be called before execute() gets called again.

Parameters:

g - the graph upon which the algo is executed

Throws:

InvalidEdgeException - if an undirected edge is found in g

init

protected void init(InspectableGraph g)
             throws InvalidEdgeException

This helper method is called by the execute(.) method. It performs all setup work, and ensures that all Edges are directed. Takes O(E) time, where E = number of Edges in the Graph.

Parameters:

g - the graph upon which the algo is executed

Throws:

InvalidEdgeException - if an undirected Edge is found

sort

protected abstract void sort()

This abstract method is overridden in the subclasses. It is called from within execute(.).

See Also:

TopologicalSort, UnitWeightedTopologicalNumbering

number

public int number(Vertex v)
           throws InvalidQueryException,
                  InvalidVertexException

Used for retrieving the topological order-number associated with the given Vertex. Takes O(1) time. Note that this method does not check against a null or invalid Vertex v. If a null or invalid Vertex is passed in, the result will be a NullPointerException, or an InvalidAttributeException This should not be called until execute(.) has already been called. Doing so will result in an InvalidAttributeException.

Parameters:

v - a vertex

Returns:

the topological order-number associated with v

Throws:

InvalidQueryException - if the Graph has cycles

InvalidVertexException

isCyclic

public boolean isCyclic()
                 throws InvalidQueryException

Query method for asking whether the Graph is cyclic, (and therefore inappropriate for a topological ordering). Takes O(1) time, since this boolean was already computed during algorithm execution. This method should not be called until execute(.) has already been called. Doing so will yield a boolean answer, but a meaningless one.

Returns:

boolean

Throws:

InvalidQueryException

cleanup

public void cleanup()

Cleans up all decorations that this algorithm was storing in the provided graph. This should be called after the user has completely finished everything resulting from a single DFS execution. Note that calling this method before calling execute(.), while incorrect, will simply do nothing.