You are viewing a plain text version of this content. The canonical link for it is here.
Posted to cvs@avalon.apache.org by bl...@apache.org on 2003/05/15 19:10:29 UTC
cvs commit: avalon-excalibur/fortress/src/test/org/apache/avalon/fortress/util/dag/test DirectedAcyclicGraphVerifierTest.java VertexTest.java
bloritsch 2003/05/15 10:10:29
Added: fortress/src/java/org/apache/avalon/fortress/util/dag
CyclicDependencyException.java
DirectedAcyclicGraphVerifier.java Vertex.java
fortress/src/test/org/apache/avalon/fortress/util/dag/test
DirectedAcyclicGraphVerifierTest.java
VertexTest.java
Log:
add DAG testing and testcases
Revision Changes Path
1.1 avalon-excalibur/fortress/src/java/org/apache/avalon/fortress/util/dag/CyclicDependencyException.java
Index: CyclicDependencyException.java
===================================================================
/*
============================================================================
The Apache Software License, Version 1.1
============================================================================
Copyright (C) 1999-2003 The Apache Software Foundation. All rights reserved.
Redistribution and use in source and binary forms, with or without modifica-
tion, are permitted provided that the following conditions are met:
1. Redistributions of source code must retain the above copyright notice,
this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.
3. The end-user documentation included with the redistribution, if any, must
include the following acknowledgment: "This product includes software
developed by the Apache Software Foundation (http://www.apache.org/)."
Alternately, this acknowledgment may appear in the software itself, if
and wherever such third-party acknowledgments normally appear.
4. The names "Jakarta", "Avalon", "Excalibur" and "Apache Software Foundation"
must not be used to endorse or promote products derived from this software
without prior written permission. For written permission, please contact
apache@apache.org.
5. Products derived from this software may not be called "Apache", nor may
"Apache" appear in their name, without prior written permission of the
Apache Software Foundation.
THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
APACHE SOFTWARE FOUNDATION OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLU-
DING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
This software consists of voluntary contributions made by many individuals
on behalf of the Apache Software Foundation. For more information on the
Apache Software Foundation, please see <http://www.apache.org/>.
*/
package org.apache.avalon.fortress.util.dag;
/**
* CyclicDependencyException is thrown any time the DAG verifier finds a cycle.
*
* @author <a href="bloritsch.at.apache.org">Berin Loritsch</a>
* @version CVS $ Revision: 1.1 $
*/
public class CyclicDependencyException extends Exception
{
public CyclicDependencyException()
{
}
}
1.1 avalon-excalibur/fortress/src/java/org/apache/avalon/fortress/util/dag/DirectedAcyclicGraphVerifier.java
Index: DirectedAcyclicGraphVerifier.java
===================================================================
/*
============================================================================
The Apache Software License, Version 1.1
============================================================================
Copyright (C) 1999-2003 The Apache Software Foundation. All rights reserved.
Redistribution and use in source and binary forms, with or without modifica-
tion, are permitted provided that the following conditions are met:
1. Redistributions of source code must retain the above copyright notice,
this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.
3. The end-user documentation included with the redistribution, if any, must
include the following acknowledgment: "This product includes software
developed by the Apache Software Foundation (http://www.apache.org/)."
Alternately, this acknowledgment may appear in the software itself, if
and wherever such third-party acknowledgments normally appear.
4. The names "Jakarta", "Avalon", "Excalibur" and "Apache Software Foundation"
must not be used to endorse or promote products derived from this software
without prior written permission. For written permission, please contact
apache@apache.org.
5. Products derived from this software may not be called "Apache", nor may
"Apache" appear in their name, without prior written permission of the
Apache Software Foundation.
THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
APACHE SOFTWARE FOUNDATION OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLU-
DING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
This software consists of voluntary contributions made by many individuals
on behalf of the Apache Software Foundation. For more information on the
Apache Software Foundation, please see <http://www.apache.org/>.
*/
package org.apache.avalon.fortress.util.dag;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
/**
* DirectedAcyclicGraphVerifier provides methods to verify that any set of
* verteces has no cycles. A Directed Acyclic Graph is a "graph" or set of
* verteces 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="bloritsch.at.d-haven.org">Berin Loritsch</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
{
vertex.visit();
verify( vertex.getDependencies() );
}
/**
* Verify a set of verteces and all their dependencies have no cycles.
*
* @param verteces The list of verteces we want to test.
* @throws CyclicDependencyException if there is a cycle.
*/
public static void verify( List verteces ) throws CyclicDependencyException
{
Iterator it = verteces.iterator();
while ( it.hasNext() )
{
Vertex v = (Vertex) it.next();
if ( v.hasBeenVisited() )
{
throw new CyclicDependencyException();
}
v.visit();
verify( v.getDependencies() );
}
}
/**
* Sort a set of verteces 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 verteces that may or may not be related.
*
* <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 verteces) or vertex is checked only once. The efficiency is
* O = (|V| + |E|).
* </p>
*
* @param verteces
* @throws CyclicDependencyException
*/
public static void topologicalSort( final List verteces ) throws CyclicDependencyException
{
resetVerteces( verteces );
int counter = 0;
final LinkedList queue = new LinkedList();
Iterator it = verteces.iterator();
while ( it.hasNext() )
{
Vertex v = (Vertex) it.next();
if ( v.getIndegrees() == 0 )
{
queue.addFirst( v );
}
}
while ( !queue.isEmpty() )
{
Vertex v = (Vertex) queue.removeLast();
v.setOrder( counter );
counter++;
Iterator deps = v.getDependencies().iterator();
while ( deps.hasNext() )
{
Vertex w = (Vertex) deps.next();
w.accountForIndegree();
if ( w.getIndegrees() == 0 )
{
queue.addFirst( w );
}
}
}
if ( counter != verteces.size() ) throw new CyclicDependencyException();
Collections.sort( verteces );
}
/**
* Resets all the verteces so that the visitation flags and indegrees are
* reset to their start values.
*
* @param vertices
*/
public static void resetVerteces( List vertices )
{
Iterator it = vertices.iterator();
while ( it.hasNext() )
{
( (Vertex) it.next() ).reset();
}
}
}
1.1 avalon-excalibur/fortress/src/java/org/apache/avalon/fortress/util/dag/Vertex.java
Index: Vertex.java
===================================================================
/*
============================================================================
The Apache Software License, Version 1.1
============================================================================
Copyright (C) 1999-2003 The Apache Software Foundation. All rights reserved.
Redistribution and use in source and binary forms, with or without modifica-
tion, are permitted provided that the following conditions are met:
1. Redistributions of source code must retain the above copyright notice,
this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.
3. The end-user documentation included with the redistribution, if any, must
include the following acknowledgment: "This product includes software
developed by the Apache Software Foundation (http://www.apache.org/)."
Alternately, this acknowledgment may appear in the software itself, if
and wherever such third-party acknowledgments normally appear.
4. The names "Jakarta", "Avalon", "Excalibur" and "Apache Software Foundation"
must not be used to endorse or promote products derived from this software
without prior written permission. For written permission, please contact
apache@apache.org.
5. Products derived from this software may not be called "Apache", nor may
"Apache" appear in their name, without prior written permission of the
Apache Software Foundation.
THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
APACHE SOFTWARE FOUNDATION OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLU-
DING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
This software consists of voluntary contributions made by many individuals
on behalf of the Apache Software Foundation. For more information on the
Apache Software Foundation, please see <http://www.apache.org/>.
*/
package org.apache.avalon.fortress.util.dag;
import java.util.ArrayList;
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="bloritsch.at.d-haven.org">Berin Loritsch</a>
* @version CVS $ Revision: 1.1 $
*/
public final class Vertex implements Comparable
{
private boolean m_visited = false;
private final Object m_node;
private int m_indegrees;
private int m_currentIndegrees;
private int m_order;
private final List m_dependencies;
/**
* A vertex wraps a node, which can be anything.
*
* @param node The wrapped node.
*/
public Vertex( final Object node )
{
m_node = node;
m_indegrees = 0;
m_order = 0;
m_dependencies = new ArrayList();
reset();
}
/**
* Determine wether this vertex has been visited or not. It is used in the
* </code>DirectedAcyclicGraphVerifier.verify</code> method.
*
* @return <code>true</code> if this vertex has been visited.
*/
public boolean hasBeenVisited()
{
return m_visited;
}
/**
* Mark this vertex as visited.
*/
public void visit()
{
m_visited = true;
}
/**
* Mark this vertex so that it knows it is referenced. It is used to
* determine the number of indegrees this vertex has.
*/
private void isReferenced()
{
m_indegrees++;
m_currentIndegrees++;
}
/**
* Reset the Vertex so that all the flags and runtime states are set back
* to the original values.
*/
public void reset()
{
m_visited = false;
m_currentIndegrees = m_indegrees;
m_order = 0;
}
/**
* Provide an ordinal or order number for the vertex, used in properly
* sorting the verteces.
*
* @param orderNum The ordinal for this vertex.
*/
public void setOrder( int orderNum )
{
m_order = orderNum;
}
/**
* Get the number of indegrees for this Vertex. An indegree is an incomming
* edge, or a Vertex that depends on this one.
*
* @return The current number of tracked indegrees
*/
public int getIndegrees()
{
return m_currentIndegrees;
}
/**
* Account for one of the indegrees. This decrements the current number of
* tracked indegrees, and is used in the topological sort algorithm.
*/
public void accountForIndegree()
{
m_currentIndegrees--;
}
/**
* 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 );
v.isReferenced();
}
}
/**
* 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 Verteces 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 = 0;
if ( m_order < other.m_order ) orderInd = -1;
if ( m_order > other.m_order ) orderInd = 1;
return orderInd;
}
/**
* Get the ordinal for this vertex.
*
* @return the order.
*/
public int getOrder()
{
return m_order;
}
}
1.1 avalon-excalibur/fortress/src/test/org/apache/avalon/fortress/util/dag/test/DirectedAcyclicGraphVerifierTest.java
Index: DirectedAcyclicGraphVerifierTest.java
===================================================================
/*
============================================================================
The Apache Software License, Version 1.1
============================================================================
Copyright (C) 1999-2003 The Apache Software Foundation. All rights reserved.
Redistribution and use in source and binary forms, with or without modifica-
tion, are permitted provided that the following conditions are met:
1. Redistributions of source code must retain the above copyright notice,
this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.
3. The end-user documentation included with the redistribution, if any, must
include the following acknowledgment: "This product includes software
developed by the Apache Software Foundation (http://www.apache.org/)."
Alternately, this acknowledgment may appear in the software itself, if
and wherever such third-party acknowledgments normally appear.
4. The names "Jakarta", "Avalon", "Excalibur" and "Apache Software Foundation"
must not be used to endorse or promote products derived from this software
without prior written permission. For written permission, please contact
apache@apache.org.
5. Products derived from this software may not be called "Apache", nor may
"Apache" appear in their name, without prior written permission of the
Apache Software Foundation.
THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
APACHE SOFTWARE FOUNDATION OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLU-
DING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
This software consists of voluntary contributions made by many individuals
on behalf of the Apache Software Foundation. For more information on the
Apache Software Foundation, please see <http://www.apache.org/>.
*/
package org.apache.avalon.fortress.util.dag.test;
import junit.framework.TestCase;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import org.apache.avalon.fortress.util.dag.*;
/**
* DirectedAcyclicGraphVerifierTest.java does XYZ
*
* @author <a href="bloritsch.at.d-haven.org">Berin Loritsch</a>
* @version CVS $ Revision: 1.1 $
*/
public class DirectedAcyclicGraphVerifierTest extends TestCase
{
public DirectedAcyclicGraphVerifierTest( String name )
{
super( name );
}
public void setUp()
{
}
public void tearDown()
{
}
public void testIsDAG()
{
try
{
Vertex root = new Vertex( "Root" );
root.addDependency( new Vertex( "Child1" ) );
root.addDependency( new Vertex( "Child2" ) );
DirectedAcyclicGraphVerifier.verify( root );
}
catch ( CyclicDependencyException cde )
{
fail( "Incorrectly found a Cycle" );
}
try
{
Vertex root = new Vertex( "Root" );
root.addDependency( new Vertex( "Child1" ) );
root.addDependency( new Vertex( "Child2" ) );
Vertex child3 = new Vertex( "Child3" );
child3.addDependency( root );
root.addDependency( child3 );
DirectedAcyclicGraphVerifier.verify( root );
fail( "Incorrectly missed the Cycle" );
}
catch ( CyclicDependencyException cde )
{
// Success!
}
}
public void testSortDAG() throws Exception
{
Vertex component1 = new Vertex( "Component1" );
Vertex component2 = new Vertex( "Component2" );
Vertex component3 = new Vertex( "Component3" );
Vertex component4 = new Vertex( "Component4" );
Vertex component5 = new Vertex( "Component5" );
component1.addDependency( component2 );
component1.addDependency( component3 );
component3.addDependency( component4 );
component5.addDependency( component2 );
component5.addDependency( component4 );
List vertices = new ArrayList( 5 );
vertices.add( component1 );
vertices.add( component2 );
vertices.add( component3 );
vertices.add( component4 );
vertices.add( component5 );
DirectedAcyclicGraphVerifier.topologicalSort( vertices );
List verifyList = generateVerifyList( component1, component5, component2, component3, component4 );
verifyTopSort( vertices, verifyList );
Collections.shuffle( vertices );
DirectedAcyclicGraphVerifier.topologicalSort( vertices );
verifyList = generateVerifyList( component1, component5, component2, component3, component4 );
verifyTopSort( vertices, verifyList );
component4.addDependency( component1 );
Collections.shuffle( vertices );
try
{
DirectedAcyclicGraphVerifier.topologicalSort( vertices );
fail( "Did not detect the expected cyclic dependency" );
}
catch ( CyclicDependencyException cde )
{
//Success!
}
}
private List generateVerifyList( Vertex component1, Vertex component5, Vertex component2, Vertex component3, Vertex component4 )
{
List verifyList = new ArrayList( 3 );
List level1 = new ArrayList( 2 );
level1.add( component1 );
level1.add( component5 );
verifyList.add( level1 );
List level2 = new ArrayList( 2 );
level2.add( component2 );
level2.add( component3 );
verifyList.add( level2 );
List level3 = new ArrayList( 1 );
level3.add( component4 );
verifyList.add( level3 );
return verifyList;
}
private void verifyTopSort( List vertices, List verifyList )
{
List currList = null;
Iterator it = vertices.iterator();
while ( it.hasNext() )
{
if ( null == currList || currList.isEmpty() )
{
currList = (List) verifyList.remove( 0 );
}
Vertex v = (Vertex) it.next();
assertTrue( currList.remove( v ) );
}
}
}
1.1 avalon-excalibur/fortress/src/test/org/apache/avalon/fortress/util/dag/test/VertexTest.java
Index: VertexTest.java
===================================================================
/*
============================================================================
The Apache Software License, Version 1.1
============================================================================
Copyright (C) 1999-2003 The Apache Software Foundation. All rights reserved.
Redistribution and use in source and binary forms, with or without modifica-
tion, are permitted provided that the following conditions are met:
1. Redistributions of source code must retain the above copyright notice,
this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.
3. The end-user documentation included with the redistribution, if any, must
include the following acknowledgment: "This product includes software
developed by the Apache Software Foundation (http://www.apache.org/)."
Alternately, this acknowledgment may appear in the software itself, if
and wherever such third-party acknowledgments normally appear.
4. The names "Jakarta", "Avalon", "Excalibur" and "Apache Software Foundation"
must not be used to endorse or promote products derived from this software
without prior written permission. For written permission, please contact
apache@apache.org.
5. Products derived from this software may not be called "Apache", nor may
"Apache" appear in their name, without prior written permission of the
Apache Software Foundation.
THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
APACHE SOFTWARE FOUNDATION OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLU-
DING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
This software consists of voluntary contributions made by many individuals
on behalf of the Apache Software Foundation. For more information on the
Apache Software Foundation, please see <http://www.apache.org/>.
*/
package org.apache.avalon.fortress.util.dag.test;
import junit.framework.TestCase;
import org.apache.avalon.fortress.util.dag.Vertex;
import java.util.List;
/**
* VertexTest does XYZ
*
* @author <a href="bloritsch.at.d-haven.org">Berin Loritsch</a>
* @version CVS $ Revision: 1.1 $
*/
public class VertexTest extends TestCase
{
public VertexTest( String name )
{
super( name );
}
public void setUp()
{
}
public void tearDown()
{
}
public void testVisit()
{
Vertex v = new Vertex( "Test" );
assertTrue( !v.hasBeenVisited() );
v.visit();
assertTrue( v.hasBeenVisited() );
v.reset();
assertTrue( !v.hasBeenVisited() );
}
public void testSortMethods()
{
Vertex v = new Vertex( "Root" );
List deps = v.getDependencies();
assertNotNull( deps );
assertEquals( 0, deps.size() );
assertEquals( 0, v.getIndegrees() );
assertEquals( "Root", v.getNode() );
assertEquals( 0, v.getOrder() );
v.setOrder( 4 );
assertEquals( 4, v.getOrder() );
Vertex w = new Vertex( "Child" );
v.addDependency( w );
deps = v.getDependencies();
assertNotNull( deps );
assertEquals( 1, deps.size() );
v.reset();
w.reset();
assertEquals( 1, w.getIndegrees() );
w.accountForIndegree();
assertEquals( 0, w.getIndegrees() );
w.reset();
assertEquals( 1, w.getIndegrees() );
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: cvs-unsubscribe@avalon.apache.org
For additional commands, e-mail: cvs-help@avalon.apache.org
Re: cvs commit: DirectedAcyclicGraph.java
Posted by Berin Loritsch <bl...@apache.org>.
Leo Simons wrote:
> we now have a DAG in phoenix, merlin, fortress. Does it make sense to
> factor out a common base or do we just keep the duplicity given that
> this stuff is "write once, never modify"?
Question is where to keep it.
With a Bundle API, if all containers supported it, then that would be
a natural location.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@avalon.apache.org
For additional commands, e-mail: dev-help@avalon.apache.org
Re: cvs commit: DirectedAcyclicGraph.java
Posted by Peter Royal <pr...@apache.org>.
On Tuesday, May 20, 2003, at 11:25 AM, Leo Simons wrote:
> we now have a DAG in phoenix, merlin, fortress. Does it make sense to
> factor out a common base or do we just keep the duplicity given that
> this stuff is "write once, never modify"?
I say keep the duplicity, unless someone wants to start a Jakarta
Commons project for it, as it really is utility code at that kinda
reusable level..
-pete
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@avalon.apache.org
For additional commands, e-mail: dev-help@avalon.apache.org
Re: cvs commit: DirectedAcyclicGraph.java
Posted by Leo Simons <le...@apache.org>.
we now have a DAG in phoenix, merlin, fortress. Does it make sense to
factor out a common base or do we just keep the duplicity given that
this stuff is "write once, never modify"?
- LSD
bloritsch@apache.org wrote:
> add DAG testing
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@avalon.apache.org
For additional commands, e-mail: dev-help@avalon.apache.org