cziegeler 2004/04/02 00:29:28
Added:
fortress/container-api/src/java/org/apache/avalon/fortress/util/dag
Vertex.java CyclicDependencyException.java
DirectedAcyclicGraphVerifier.java
Removed: fortress/container-api/src/java/org/apache/avalon/fortress/util
CyclicDependencyException.java Vertex.java
DirectedAcyclicGraphVerifier.java
Log:
Correct package name
Revision Changes Path
1.1
avalon-excalibur/fortress/container-api/src/java/org/apache/avalon/fortress/util/dag/Vertex.java
Index: Vertex.java
===================================================================
/*
* Copyright 2003-2004 The Apache Software Foundation
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
* implied.
*
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.avalon.fortress.util.dag;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
* Vertex is used to track dependencies and each node in a graph. Typical
* uses would be to ensure components are started up and torn down in the
* proper order, or bundles were loaded and unloaded in the proper order, etc.
*
* @author <a href="mailto:dev@avalon.apache.org";>Avalon Development Team</a>
* @version CVS $ Revision: 1.1 $
*/
public final class Vertex implements Comparable
{
private final String m_name;
private final Object m_node;
private int m_order;
/** Flag used to keep track of whether or not a given vertex has been
* seen by the resolveOrder methods. */
private boolean m_seen;
/** List of all direct dependent Vertices. */
private final List m_dependencies;
/**
* A vertex wraps a node, which can be anything.
*
* @param node The wrapped node.
*/
public Vertex( final Object node )
{
this( node.toString(), node );
}
/**
* A vertex wraps a node, which can be anything.
*
* @param name A name for the node which will be used to produce useful
errors.
* @param node The wrapped node.
*/
public Vertex( final String name, final Object node )
{
m_name = name;
m_node = node;
m_dependencies = new ArrayList();
reset();
}
/**
* Reset the Vertex so that all the flags and runtime states are set back
* to the original values.
*/
public void reset()
{
m_order = 0;
m_seen = false;
}
/**
* Returns the name of the Vertex.
*
* @return The name of the Vertex.
*/
public String getName()
{
return m_name;
}
/**
* Get the wrapped node that this Vertex represents.
*
* @return the node
*/
public Object getNode()
{
return m_node;
}
/**
* Add a dependecy to this Vertex. The Vertex that this one depends on
will
* be marked as referenced and then added to the list of dependencies.
The
* list is checked before the dependency is added.
*
* @param v The vertex we depend on.
*/
public void addDependency( Vertex v )
{
if ( !m_dependencies.contains( v ) )
{
m_dependencies.add( v );
}
}
/**
* Recurse through the tree from this vertex assigning an order to each
* and at the same time checking for any cyclic dependencies.
*
* @throws CyclicDependencyException If a cyclic dependency is discovered.
*/
public void resolveOrder()
throws CyclicDependencyException
{
resolveOrder( getName() );
}
/**
* Recursively searches for cycles by travelling down the dependency lists
* of this vertex, looking for the start vertex.
*
* @param path The path to the Vertex. It is worth the load as it makes a
* descriptive error message possible.
*
* @return The highest order of any of the dependent vertices.
*
* @throws CyclicDependencyException If a cyclic dependency is discovered.
*/
private int resolveOrder( String path )
throws CyclicDependencyException
{
m_seen = true;
try
{
int highOrder = -1;
for ( Iterator iter = m_dependencies.iterator(); iter.hasNext(); )
{
Vertex dv = (Vertex)iter.next();
if ( dv.m_seen )
{
throw new CyclicDependencyException( path + " -> " +
dv.getName() );
}
else
{
highOrder = Math.max(
highOrder, dv.resolveOrder( path + " -> " +
dv.getName() ) );
}
}
// Set this order so it is one higher than the highest dependency.
m_order = highOrder + 1;
return m_order;
}
finally
{
m_seen = false;
}
}
/**
* Get the list of dependencies.
*
* @return The list of dependencies.
*/
public List getDependencies()
{
return m_dependencies;
}
/**
* Used in the sort algorithm to sort all the Vertices so that they
respect
* the ordinal they were given during the topological sort.
*
* @param o The other Vertex to compare with
* @return -1 if this < o, 0 if this == o, or 1 if this > o
*/
public int compareTo( final Object o )
{
final Vertex other = (Vertex) o;
int orderInd;
if ( m_order < other.m_order )
{
orderInd = -1;
}
else if ( m_order > other.m_order )
{
orderInd = 1;
}
else
{
orderInd = 0;
}
return orderInd;
}
/**
* Get the ordinal for this vertex.
*
* @return the order.
*/
public int getOrder()
{
return m_order;
}
}
1.1
avalon-excalibur/fortress/container-api/src/java/org/apache/avalon/fortress/util/dag/CyclicDependencyException.java
Index: CyclicDependencyException.java
===================================================================
/*
* Copyright 2003-2004 The Apache Software Foundation
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
* implied.
*
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.avalon.fortress.util.dag;
/**
* CyclicDependencyException is thrown any time the DAG verifier finds a
cycle.
*
* @author <a href="mailto:dev@avalon.apache.org";>Avalon Development Team</a>
* @version CVS $ Revision: 1.1 $
*/
public class CyclicDependencyException extends Exception
{
public CyclicDependencyException( String message )
{
super( message );
}
}
1.1
avalon-excalibur/fortress/container-api/src/java/org/apache/avalon/fortress/util/dag/DirectedAcyclicGraphVerifier.java
Index: DirectedAcyclicGraphVerifier.java
===================================================================
/*
* Copyright 2003-2004 The Apache Software Foundation
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
* implied.
*
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.avalon.fortress.util.dag;
import java.util.*;
/**
* 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.
*
* @author <a href="mailto:dev@avalon.apache.org";>Avalon Development Team</a>
* @version CVS $ Revision: 1.1 $
*/
public class DirectedAcyclicGraphVerifier
{
/**
* Verify that a vertex and its set of dependencies have no cycles.
*
* @param vertex The vertex we want to test.
*
* @throws CyclicDependencyException if there is a cycle.
*/
public static void verify( Vertex vertex )
throws CyclicDependencyException
{
// We need a list of vertices that contains the entire graph, so
build it.
List vertices = new ArrayList();
addDependencies( vertex, vertices );
verify( vertices );
}
/**
* Recursively add a vertex and all of its dependencies to a list of
* vertices
*
* @param vertex Vertex to be added.
* @param vertices Existing list of vertices.
*/
private static void addDependencies( final Vertex vertex, final List
vertices )
{
if ( !vertices.contains( vertex ) )
{
vertices.add( vertex );
for ( Iterator iter = vertex.getDependencies().iterator();
iter.hasNext(); )
{
addDependencies( (Vertex)iter.next(), vertices );
}
}
}
/**
* Verify a set of vertices and all their dependencies have no cycles.
All
* Vertices in the graph must exist in the list.
*
* @param vertices The list of vertices we want to test.
*
* @throws CyclicDependencyException if there is a cycle.
*/
public static void verify( List vertices )
throws CyclicDependencyException
{
// Reset the orders of all the vertices.
resetVertices( vertices );
// Assert that all vertices are in the vertices list and resolve each
of their orders.
Iterator it = vertices.iterator();
while ( it.hasNext() )
{
Vertex v = (Vertex) it.next();
// Make sure that any dependencies are also in the vertices list.
This adds
// a little bit to the load, but we don't test this and the test
would have
// failed, this would lead to some very hard to track down
problems elsewhere.
Iterator dit = v.getDependencies().iterator();
while( dit.hasNext() )
{
Vertex dv = (Vertex) dit.next();
if ( !vertices.contains( dv ) )
{
throw new IllegalStateException( "A dependent vertex (" +
dv.getName() + ") of "
+ "vertex (" + v.getName() + ") was not included in
the vertices list." );
}
}
v.resolveOrder();
}
}
/**
* 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".
*
* <p>
* <b>Implementation Detail:</b> 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|).
* </p>
*
* @param vertices
* @throws CyclicDependencyException
*/
public static void topologicalSort( final List vertices ) throws
CyclicDependencyException
{
// Verify the graph and set the vertex orders in the process.
verify( vertices );
// We now that there are no cycles and that each of the vertices has
an order
// that will allow them to be sorted.
Collections.sort( vertices );
}
/**
* Resets all the vertices so that the visitation flags and indegrees are
* reset to their start values.
*
* @param vertices
*/
public static void resetVertices( List vertices )
{
Iterator it = vertices.iterator();
while ( it.hasNext() )
{
( (Vertex) it.next() ).reset();
}
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
