avalon-cvs mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From cziege...@apache.org
Subject cvs commit: avalon-excalibur/fortress/container-api/src/java/org/apache/avalon/fortress/util CyclicDependencyException.java Vertex.java DirectedAcyclicGraphVerifier.java
Date Fri, 02 Apr 2004 08:29:28 GMT
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: cvs-unsubscribe@avalon.apache.org
For additional commands, e-mail: cvs-help@avalon.apache.org


Mime
View raw message