

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object org.apache.avalon.fortress.util.dag.DirectedAcyclicGraphVerifier
DirectedAcyclicGraphVerifier provides methods to verify that any set of vertices has no cycles. A Directed Acyclic Graph is a "graph" or set of vertices where all connections between each vertex goes in a particular direction and there are no cycles or loops. It is used to track dependencies and ansure that dependencies can be loaded and unloaded in the proper order.
Constructor Summary  
DirectedAcyclicGraphVerifier()

Method Summary  
static void 
resetVertices(java.util.List vertices)
Resets all the vertices so that the visitation flags and indegrees are reset to their start values. 
static void 
topologicalSort(java.util.List vertices)
Sort a set of vertices so that no dependency is before its vertex. 
static void 
verify(java.util.List vertices)
Verify a set of vertices and all their dependencies have no cycles. 
static void 
verify(Vertex vertex)
Verify that a vertex and its set of dependencies have no cycles. 
Methods inherited from class java.lang.Object 
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
Constructor Detail 
public DirectedAcyclicGraphVerifier()
Method Detail 
public static void verify(Vertex vertex) throws CyclicDependencyException
vertex
 The vertex we want to test.
CyclicDependencyException
 if there is a cycle.public static void verify(java.util.List vertices) throws CyclicDependencyException
vertices
 The list of vertices we want to test.
CyclicDependencyException
 if there is a cycle.public static void topologicalSort(java.util.List vertices) throws CyclicDependencyException
Implementation Detail: This particular algorithm is a more efficient variation of the typical Topological Sort algorithm. It uses a Queue (Linked List) to ensure that each edge (connection between two vertices) or vertex is checked only once. The efficiency is O = (V + E).
vertices

CyclicDependencyException
public static void resetVertices(java.util.List vertices)
vertices



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