avalon-cvs mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From blorit...@apache.org
Subject cvs commit: avalon-excalibur/fortress/src/test/org/apache/avalon/fortress/util/dag/test DirectedAcyclicGraphVerifierTest.java VertexTest.java
Date Thu, 15 May 2003 17:10:29 GMT
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


Mime
View raw message