avalon-cvs mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From l...@apache.org
Subject cvs commit: avalon-excalibur/fortress/src/java/org/apache/avalon/fortress/util/dag Vertex.java
Date Wed, 28 May 2003 17:50:05 GMT
leif        2003/05/28 10:50:05

  Modified:    fortress/src/java/org/apache/avalon/fortress/util/dag
                        Vertex.java
  Log:
  Rework the way the Directed Graph is validated and sorted so it works correctly.
  This new method also maintains all of the information necessary to be able to
  display a useful description of any cyclic loops in the graph if they are detected.
  
  Revision  Changes    Path
  1.3       +97 -46    avalon-excalibur/fortress/src/java/org/apache/avalon/fortress/util/dag/Vertex.java
  
  Index: Vertex.java
  ===================================================================
  RCS file: /home/cvs/avalon-excalibur/fortress/src/java/org/apache/avalon/fortress/util/dag/Vertex.java,v
  retrieving revision 1.2
  retrieving revision 1.3
  diff -u -r1.2 -r1.3
  --- Vertex.java	23 May 2003 17:18:41 -0000	1.2
  +++ Vertex.java	28 May 2003 17:50:04 -0000	1.3
  @@ -50,6 +50,7 @@
   package org.apache.avalon.fortress.util.dag;
   
   import java.util.ArrayList;
  +import java.util.Iterator;
   import java.util.List;
   
   /**
  @@ -58,14 +59,20 @@
    * proper order, or bundles were loaded and unloaded in the proper order, etc.
    *
    * @author <a href="bloritsch.at.d-haven.org">Berin Loritsch</a>
  + * @author <a href="leif.at.apache.org">Leif Mortenson</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_indegrees;
  -    private int m_currentIndegrees;
       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;
   
       /**
  @@ -75,21 +82,21 @@
        */
       public Vertex( final Object node )
       {
  -        m_node = node;
  -        m_indegrees = 0;
  -        m_order = 0;
  -        m_dependencies = new ArrayList();
  -        reset();
  +        this( node.toString(), node );
       }
  -
  +    
       /**
  -     * Mark this vertex so that it knows it is referenced.  It is used to
  -     * determine the number of indegrees this vertex has.
  +     * 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.
        */
  -    private void isReferenced()
  +    public Vertex( final String name, final Object node )
       {
  -        m_indegrees++;
  -        m_currentIndegrees++;
  +        m_name = name;
  +        m_node = node;
  +        m_dependencies = new ArrayList();
  +        reset();
       }
   
       /**
  @@ -98,41 +105,20 @@
        */
       public void reset()
       {
  -        m_currentIndegrees = m_indegrees;
           m_order = 0;
  +        m_seen = false;
       }
  -
  +    
       /**
  -     * Provide an ordinal or order number for the vertex, used in properly
  -     * sorting the verteces.
  +     * Returns the name of the Vertex.
        *
  -     * @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.
  +     * @return The name of the Vertex.
        */
  -    public void accountForIndegree()
  +    public String getName()
       {
  -        m_currentIndegrees--;
  +        return m_name;
       }
  -
  +    
       /**
        * Get the wrapped node that this Vertex represents.
        *
  @@ -155,7 +141,62 @@
           if ( !m_dependencies.contains( v ) )
           {
               m_dependencies.add( v );
  -            v.isReferenced();
  +        }
  +    }
  +    
  +    
  +    /**
  +     * 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 start Vertex which will indicate a cylic graph.
  +     * @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;
           }
       }
   
  @@ -170,7 +211,7 @@
       }
   
       /**
  -     * Used in the sort algorithm to sort all the Verteces so that they respect
  +     * 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
  @@ -179,10 +220,20 @@
       public int compareTo( final Object o )
       {
           final Vertex other = (Vertex) o;
  -        int orderInd = 0;
  +        int orderInd;
   
  -        if ( m_order < other.m_order ) orderInd = -1;
  -        if ( m_order > other.m_order ) orderInd = 1;
  +        if ( m_order < other.m_order )
  +        {
  +            orderInd = -1;
  +        }
  +        else if ( m_order > other.m_order )
  +        {
  +            orderInd = 1;
  +        }
  +        else
  +        {
  +            orderInd = 0;
  +        }
   
           return orderInd;
       }
  
  
  

---------------------------------------------------------------------
To unsubscribe, e-mail: cvs-unsubscribe@avalon.apache.org
For additional commands, e-mail: cvs-help@avalon.apache.org


Mime
View raw message