

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: INNER  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object  +jdsl.graph.algo.AbstractTopologicalSort
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 levelnumbering 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.
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 ordernumber 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 
protected InspectableGraph graph_
protected boolean is_cyclic_
public java.lang.Object NUMBER_KEY_
protected Sequence queue_
Constructor Detail 
public AbstractTopologicalSort()
Method Detail 
public void execute(InspectableGraph g) throws InvalidEdgeException
InspectableGraph
 g the graph upon which the algo is executedInvalidEdgeException
 if an undirected edge is found in gprotected void init(InspectableGraph g) throws InvalidEdgeException
InspectableGraph
 g the Graph upon which the algo is executedInvalidEdgeException
 if an undirected Edge is foundprotected abstract void sort()
TopologicalSort
,
UnitWeightedTopologicalNumbering
public int number(Vertex v) throws InvalidQueryException, InvalidVertexException
Vertex
 vInvalidQueryException
 if the Graph has cyclespublic boolean isCyclic() throws InvalidQueryException
public void cleanup()


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: INNER  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 