org.apache.avalon.fortress.util.dag

Class DirectedAcyclicGraphVerifier

java.lang.Object

org.apache.avalon.fortress.util.dag.DirectedAcyclicGraphVerifier

public class DirectedAcyclicGraphVerifier
extends java.lang.Object

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.

Version:

CVS $ Revision: 1.1 $

Author:

Avalon Development Team

Constructor Summary

Constructors

Constructor and Description
DirectedAcyclicGraphVerifier()

Method Summary

Methods

Modifier and Type	Method and Description
private static void	addDependencies(Vertex vertex, java.util.List vertices) Recursively add a vertex and all of its dependencies to a list of vertices
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

DirectedAcyclicGraphVerifier

public DirectedAcyclicGraphVerifier()

Method Detail

verify

public static void verify(Vertex vertex)
                   throws CyclicDependencyException

Verify that a vertex and its set of dependencies have no cycles.

Parameters:

vertex - The vertex we want to test.

Throws:

CyclicDependencyException - if there is a cycle.

addDependencies

private static void addDependencies(Vertex vertex,
                   java.util.List vertices)

Recursively add a vertex and all of its dependencies to a list of vertices

Parameters:

vertex - Vertex to be added.

vertices - Existing list of vertices.

verify

public static void verify(java.util.List vertices)
                   throws CyclicDependencyException

Verify a set of vertices and all their dependencies have no cycles. All Vertices in the graph must exist in the list.

Parameters:

vertices - The list of vertices we want to test.

Throws:

CyclicDependencyException - if there is a cycle.

topologicalSort

public static void topologicalSort(java.util.List vertices)
                            throws CyclicDependencyException

Sort a set of vertices so that no dependency is before its vertex. If we have a vertex named "Parent" and one named "Child" that is listed as a dependency of "Parent", we want to ensure that "Child" always comes after "Parent". As long as there are no cycles in the list, we can sort any number of vertices that may or may not be related. Both "Parent" and "Child" must exist in the vertices list, but "Child" will also be referenced as a dependency of "Parent".

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|).

Parameters:

vertices -

Throws:

CyclicDependencyException

resetVertices

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

Resets all the vertices so that the visitation flags and indegrees are reset to their start values.

Parameters:

vertices -