commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From d..@apache.org
Subject cvs commit: jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/domain/dependency DependencyGraph.java DependencyVisitor.java
Date Fri, 26 Jul 2002 12:36:05 GMT
ddp         2002/07/26 05:36:05

  Modified:    graph2   build.xml project.xml
               graph2/src/java/org/apache/commons/graph/algorithm/search
                        DFS.java
               graph2/src/java/org/apache/commons/graph/domain/basic
                        DirectedGraphImpl.java
               graph2/src/java/org/apache/commons/graph/domain/dependency
                        DependencyGraph.java DependencyVisitor.java
  Log:
  Adding SortedDependencies
  
  Revision  Changes    Path
  1.2       +165 -39   jakarta-commons-sandbox/graph2/build.xml
  
  Index: build.xml
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/graph2/build.xml,v
  retrieving revision 1.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- build.xml	17 Mar 2002 16:28:13 -0000	1.1
  +++ build.xml	26 Jul 2002 12:36:04 -0000	1.2
  @@ -12,68 +12,194 @@
     <!-- Set default values for the build -->
     <property file="project.properties" />
   
  +
     <!-- maven:start -->
     
     <!-- ================================================================== -->
     <!-- D E L E G A T O R S                                                -->
     <!-- ================================================================== -->
           
  +
       <target name="maven:site">
  -      <ant antfile="${maven.home}/build-docs.xml" target="site"/>
  +      <ant antfile="${maven.home}/plugins/docs/build.xml" target="site"/>
       </target>
  -        
  -    <target name="maven:jar">
  -      <ant antfile="${maven.home}/build-maven.xml" target="jar"/>
  -    </target>
  -        
  -    <target name="maven:install-jar">
  -      <ant antfile="${maven.home}/build-maven.xml" target="install-jar"/>
  +
  +
  +    <target name="maven:dist">
  +      <ant antfile="${maven.home}/plugins/core/build.xml" target="dist"/>
       </target>
  -        
  +
  +
       <target name="maven:env">
  -      <ant antfile="${maven.home}/build-maven.xml" target="env"/>
  +      <ant antfile="${maven.home}/plugins/core/build.xml" target="env"/>
       </target>
  -        
  -    <target name="maven:docs">
  -      <ant antfile="${maven.home}/build-docs.xml" target="docs"/>
  -    </target>
  -        
  +
  +
       <target name="maven:test">
  -      <ant antfile="${maven.home}/build-test.xml" target="test"/>
  +      <ant antfile="${maven.home}/plugins/test/build.xml" target="test"/>
       </target>
  -        
  -    <target name="maven:clean">
  -      <ant antfile="${maven.home}/build-maven.xml" target="clean"/>
  +
  +
  +    <target name="maven:announce">
  +      <ant antfile="${maven.home}/plugins/core/build.xml" target="announce"/>
  +    </target>
  +
  +
  +    <target name="maven:activity-log">
  +      <ant antfile="${maven.home}/plugins/docs/build.xml" target="activity-log"/>
       </target>
  -        
  -    <target name="maven:metrics">
  -      <ant antfile="${maven.home}/build-metrics.xml" target="metrics"/>
  +
  +
  +    <target name="maven:compile">
  +      <ant antfile="${maven.home}/plugins/core/build.xml" target="compile"/>
       </target>
  -        
  -    <target name="maven:dist">
  -      <ant antfile="${maven.home}/build-maven.xml" target="dist"/>
  +
  +
  +    <target name="maven:validate-war">
  +      <ant antfile="${maven.home}/plugins/j2ee/build.xml" target="validate-war"/>
  +    </target>
  +
  +
  +    <target name="maven:pdf">
  +      <ant antfile="${maven.home}/plugins/docs/build.xml" target="pdf"/>
  +    </target>
  +
  +
  +    <target name="maven:iutest">
  +      <ant antfile="${maven.home}/plugins/iutest/build.xml" target="iutest"/>
       </target>
  -        
  +
  +
       <target name="maven:deploy-site">
  -      <ant antfile="${maven.home}/build-docs.xml" target="deploy-site"/>
  +      <ant antfile="${maven.home}/plugins/docs/build.xml" target="deploy-site"/>
       </target>
  -        
  -    <target name="maven:gump-descriptor">
  -      <ant antfile="${maven.home}/build-maven.xml" target="gump-descriptor"/>
  +
  +
  +    <target name="maven:deploy-dist">
  +      <ant antfile="${maven.home}/plugins/core/build.xml" target="deploy-dist"/>
  +    </target>
  +
  +
  +    <target name="maven:war">
  +      <ant antfile="${maven.home}/plugins/j2ee/build.xml" target="war"/>
  +    </target>
  +
  +
  +    <target name="maven:verify-project">
  +      <ant antfile="${maven.home}/plugins/core/build.xml" target="verify-project"/>
  +    </target>
  +
  +
  +    <target name="maven:cvs-change-log">
  +      <ant antfile="${maven.home}/plugins/docs/build.xml" target="cvs-change-log"/>
  +    </target>
  +
  +
  +    <target name="maven:ear">
  +      <ant antfile="${maven.home}/plugins/j2ee/build.xml" target="ear"/>
  +    </target>
  +
  +
  +    <target name="maven:cross-ref">
  +      <ant antfile="${maven.home}/plugins/docs/build.xml" target="cross-ref"/>
       </target>
  -        
  +
  +
  +    <target name="maven:update-jars">
  +      <ant antfile="${maven.home}/plugins/core/build.xml" target="update-jars"/>
  +    </target>
  +
  +
  +    <target name="maven:validate-pom">
  +      <ant antfile="${maven.home}/plugins/core/build.xml" target="validate-pom"/>
  +    </target>
  +
  +
  +    <target name="maven:install-jar">
  +      <ant antfile="${maven.home}/plugins/core/build.xml" target="install-jar"/>
  +    </target>
  +
  +
  +    <target name="maven:fo">
  +      <ant antfile="${maven.home}/plugins/docs/build.xml" target="fo"/>
  +    </target>
  +
  +
       <target name="maven:javadocs">
  -      <ant antfile="${maven.home}/build-docs.xml" target="javadocs"/>
  +      <ant antfile="${maven.home}/plugins/docs/build.xml" target="javadocs"/>
       </target>
  -        
  -    <target name="maven:compile">
  -      <ant antfile="${maven.home}/build-maven.xml" target="compile"/>
  +
  +
  +    <target name="maven:validate-struts-war">
  +      <ant antfile="${maven.home}/plugins/struts/build.xml" target="validate-struts-war"/>
  +    </target>
  +
  +
  +    <target name="maven:task-list">
  +      <ant antfile="${maven.home}/plugins/docs/build.xml" target="task-list"/>
  +    </target>
  +
  +
  +    <target name="maven:ejb">
  +      <ant antfile="${maven.home}/plugins/j2ee/build.xml" target="ejb"/>
       </target>
  -        
  -    <target name="maven:update-jars">
  -      <ant antfile="${maven.home}/build-maven.xml" target="update-jars"/>
  +
  +
  +    <target name="maven:docs">
  +      <ant antfile="${maven.home}/plugins/docs/build.xml" target="docs"/>
  +    </target>
  +
  +
  +    <target name="maven:clean">
  +      <ant antfile="${maven.home}/plugins/core/build.xml" target="clean"/>
  +    </target>
  +
  +
  +    <target name="maven:dist-build">
  +      <ant antfile="${maven.home}/plugins/core/build.xml" target="dist-build"/>
  +    </target>
  +
  +
  +    <target name="maven:metrics">
  +      <ant antfile="${maven.home}/plugins/metrics/build.xml" target="metrics"/>
  +    </target>
  +
  +
  +    <target name="maven:docs-quick">
  +      <ant antfile="${maven.home}/plugins/docs/build.xml" target="docs-quick"/>
  +    </target>
  +
  +
  +    <target name="maven:run-singletest">
  +      <ant antfile="${maven.home}/plugins/test/build.xml" target="run-singletest"/>
  +    </target>
  +
  +
  +    <target name="maven:check-source">
  +      <ant antfile="${maven.home}/plugins/core/build.xml" target="check-source"/>
  +    </target>
  +
  +
  +    <target name="maven:generate-reactor">
  +      <ant antfile="${maven.home}/plugins/reactor/build.xml" target="generate-reactor"/>
  +    </target>
  +
  +
  +    <target name="maven:jar">
  +      <ant antfile="${maven.home}/plugins/core/build.xml" target="jar"/>
  +    </target>
  +
  +
  +    <target name="maven:maven-update">
  +      <ant antfile="${maven.home}/plugins/core/build.xml" target="maven-update"/>
  +    </target>
  +
  +
  +    <target name="maven:gump-descriptor">
  +      <ant antfile="${maven.home}/plugins/core/build.xml" target="gump-descriptor"/>
       </target>
  -    
  +
  +
     <!-- maven:end -->
   
   </project>
  
  
  
  1.11      +2 -1      jakarta-commons-sandbox/graph2/project.xml
  
  Index: project.xml
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/graph2/project.xml,v
  retrieving revision 1.10
  retrieving revision 1.11
  diff -u -r1.10 -r1.11
  --- project.xml	26 Jul 2002 12:29:39 -0000	1.10
  +++ project.xml	26 Jul 2002 12:36:04 -0000	1.11
  @@ -89,12 +89,13 @@
         <id>commons-collections</id>
         <version>1.0</version>
       </dependency>
  -
  +<!--
       <dependency>
         <id>xerces</id>
         <version>1.2.3</version>
         <url>http://xml.apache.org/xerces/</url>
       </dependency>
  +-->
   
       <dependency>
         <id>junit</id>
  
  
  
  1.2       +22 -0     jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/search/DFS.java
  
  Index: DFS.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/search/DFS.java,v
  retrieving revision 1.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- DFS.java	8 May 2002 17:34:09 -0000	1.1
  +++ DFS.java	26 Jul 2002 12:36:05 -0000	1.2
  @@ -164,5 +164,27 @@
           visitor.finishGraph(graph);
       }
   
  +    /**
  +     * visit - Visits all nodes in the graph.
  +     */
  +    public void visit( DirectedGraph graph, Visitor visitor ) {
  +	Iterator vertices = graph.getVertices().iterator();
  +	while (vertices.hasNext()) {
  +	    colors.put( vertices.next(), WHITE );
  +	}
  +
  +	visitor.discoverGraph( graph );
  +	
  +	vertices = graph.getVertices().iterator();
  +	while (vertices.hasNext()) {
  +	    Vertex v = (Vertex) vertices.next();
  +
  +	    if (colors.get( v ) == WHITE) {
  +		visitVertex( graph, v, visitor );
  +	    }
  +	}
  +
  +	visitor.finishGraph( graph );
  +    }
   }
   
  
  
  
  1.2       +7 -3      jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/domain/basic/DirectedGraphImpl.java
  
  Index: DirectedGraphImpl.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/domain/basic/DirectedGraphImpl.java,v
  retrieving revision 1.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- DirectedGraphImpl.java	8 May 2002 17:43:20 -0000	1.1
  +++ DirectedGraphImpl.java	26 Jul 2002 12:36:05 -0000	1.2
  @@ -72,10 +72,12 @@
    */
   public class DirectedGraphImpl
        implements DirectedGraph,
  -    WeightedGraph,
  -    MutableDirectedGraph,
  -    InvocationHandler
  +		WeightedGraph,
  +		MutableDirectedGraph,
  +		InvocationHandler
   {
  +    private Vertex root = null;
  +
       private Set vertices = new HashSet();
       private Set edges = new HashSet();
       private List contracts = new ArrayList();
  @@ -264,6 +266,8 @@
       private void addVertexI(Vertex v)
           throws GraphException
       {
  +	if (root == null) root = v;
  +
           vertices.add(v);
       }
   
  
  
  
  1.3       +133 -214  jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/domain/dependency/DependencyGraph.java
  
  Index: DependencyGraph.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/domain/dependency/DependencyGraph.java,v
  retrieving revision 1.2
  retrieving revision 1.3
  diff -u -r1.2 -r1.3
  --- DependencyGraph.java	26 Jul 2002 12:29:39 -0000	1.2
  +++ DependencyGraph.java	26 Jul 2002 12:36:05 -0000	1.3
  @@ -1,214 +1,133 @@
  -package org.apache.commons.graph.domain.dependency;
  -
  -import org.apache.commons.graph.*;
  -import org.apache.commons.graph.contract.*;
  -import org.apache.commons.graph.exception.*;
  -import org.apache.commons.graph.domain.basic.*;
  -import org.apache.commons.graph.factory.GraphFactory;
  -import org.apache.commons.graph.decorator.DDirectedGraph;
  -import org.apache.commons.graph.dependency.exception.*;
  -
  -import java.util.ArrayList;
  -import java.util.Collection;
  -import java.util.HashMap;
  -import java.util.HashSet;
  -import java.util.Iterator;
  -import java.util.List;
  -import java.util.Map;
  -import java.util.Set;
  -
  -/**
  - * Description of the Class
  - */
  -public class DependencyGraph
  -     extends DDirectedGraph
  -  implements Acyclic
  -{
  -    private GraphFactory factory = new GraphFactory();
  -    private AcyclicContract acyclic = new AcyclicContract();
  -    private DependencyVisitor visitor = new DependencyVisitor();
  -
  -    private Map vertices = new HashMap();
  -
  -    private MutableDirectedGraph DAG = null;
  -
  -    /**
  -     * Constructor for the DependencyGraph object
  -     */
  -    public DependencyGraph()
  -    {
  -        super();
  -        Contract[] dagContracts = new Contract[1];
  -        dagContracts[0] = acyclic;
  -        DAG = factory.makeMutableDirectedGraph(dagContracts,
  -					       false,
  -					       null);
  -        setDirGraph(DAG);
  -    }
  -
  -    /**
  -     * Description of the Method
  -     */
  -    private void init()
  -    {
  -    }
  -    
  -    /**
  -     * Adds a feature to the Dependencies attribute of the DependencyGraph
  -     * object
  -     */
  -    public void addDependencies(Object head,
  -                                Collection deps)
  -        throws GraphException,
  -        CircularDependencyException
  -    {
  -        DependencyVertex vHead = findVertex(head);
  -
  -        if (!getVertices().contains(vHead))
  -        {
  -            DAG.addVertex(vHead);
  -        }
  -
  -        try
  -        {
  -            Iterator v = deps.iterator();
  -
  -            while (v.hasNext())
  -            {
  -                DependencyVertex vDep = findVertex(v.next());
  -
  -                if (!getVertices().contains(vDep))
  -                {
  -                    DAG.addVertex(vDep);
  -                }
  -
  -                DAG.addEdge(new Dependency(vHead.getValue(),
  -					   vDep.getValue()),
  -			    vHead, vDep);
  -            }
  -        }
  -        catch (CycleException ex)
  -	  {
  -            throw new CircularDependencyException(ex);
  -	  }
  -    }
  -
  -    /**
  -     * Description of the Method
  -     */
  -    public DependencyVertex findVertex(Object o)
  -    {
  -        if (vertices.containsKey(o))
  -        {
  -            return (DependencyVertex) vertices.get(o);
  -        }
  -        else
  -        {
  -            DependencyVertex RC = new DependencyVertex(o);
  -            vertices.put(o, RC);
  -            return RC;
  -        }
  -    }
  -
  -    /**
  -     * Gets the sortedDependencies attribute of the DependencyGraph object
  -     */
  -    public List getSortedDependencies(Object head)
  -    {
  -        return visitor.getSortedDependencies(this, findVertex(head));
  -    }
  -
  -    /** Retrieve the vertices in a flattened, sorted, valid order.
  -     *
  -     *  @return The list of vertices in a valid order.
  -     */
  -    public List getSortedVertices()
  -    {
  -        Set  vertices   = new HashSet( getVertices() );
  -        List sortedDeps = new ArrayList( vertices.size() );
  -
  -        Vertex vertex = null;
  -        List   deps   = null;
  -
  -        DependencyVisitor visitor = new DependencyVisitor();
  -        
  -        // While we still have unaccounted-for vertices
  -
  -        while ( ! vertices.isEmpty() )
  -        {
  -            // System.err.println( "--------------------------" );
  -
  -            // System.err.println( "## vertices = " + dumpVertices( vertices ) );
  -            // pick a vertex
  -            vertex = (Vertex) vertices.iterator().next();
  -            
  -            // System.err.println( "## vertex = " + ((Project)((DependencyVertex)vertex).getValue()).getId()
);
  -
  -            // finds its sorted dependencies (including itself)
  -            deps = visitor.getSortedDependencies( this, vertex );
  -
  -            // System.err.println( "## deps = " + dumpVertices( deps ) );
  -
  -            DependencyVertex eachVertex = null;
  -
  -            // for each dependency...
  -            for (Iterator i = deps.iterator(); i.hasNext();)
  -            {
  -                eachVertex = findVertex( i.next() );
  -                
  -                // if we haven't accounted for the dependency
  -                if ( vertices.contains( eachVertex ) )
  -                {
  -                    // account for it.
  -                    vertices.remove( eachVertex );
  -
  -                    // tag it to the tail end of the sorted list.
  -                    sortedDeps.add( eachVertex.getValue() );
  -                }
  -            }
  -        }
  -
  -        return sortedDeps;
  -    }
  -    
  -    /*
  -    protected String dumpVertices(Collection vertices)
  -    {
  -        StringBuffer buf = new StringBuffer();
  -
  -        buf.append( "{" );
  -
  -        Iterator vertIter = vertices.iterator();
  -
  -        Object eachVertex = null;
  -        DependencyVertex vertex = null;
  -
  -        while ( vertIter.hasNext() )
  -        {
  -            eachVertex = (Object) vertIter.next();
  -
  -            if ( eachVertex instanceof DependencyVertex)
  -            {
  -                vertex = (DependencyVertex) eachVertex;
  -            }
  -            else
  -            {
  -                vertex = findVertex( eachVertex );
  -            }
  -
  -            buf.append( ((Project)vertex.getValue()).getId() );
  -
  -            if ( vertIter.hasNext() )
  -            {
  -                buf.append( ", " );
  -            }
  -        }
  -
  -        buf.append( "}" );
  -
  -        return buf.toString();
  -    }
  -    */
  -}
  -
  -
  +package org.apache.commons.graph.domain.dependency;
  +
  +import org.apache.commons.graph.*;
  +import org.apache.commons.graph.contract.*;
  +import org.apache.commons.graph.exception.*;
  +import org.apache.commons.graph.domain.basic.*;
  +import org.apache.commons.graph.factory.GraphFactory;
  +import org.apache.commons.graph.decorator.DDirectedGraph;
  +import org.apache.commons.graph.dependency.exception.*;
  +
  +import java.util.ArrayList;
  +import java.util.Collection;
  +import java.util.HashMap;
  +import java.util.HashSet;
  +import java.util.Iterator;
  +import java.util.List;
  +import java.util.Map;
  +import java.util.Set;
  +
  +/**
  + * Description of the Class
  + */
  +public class DependencyGraph
  +     extends DDirectedGraph
  +  implements Acyclic
  +{
  +    private GraphFactory factory = new GraphFactory();
  +    private AcyclicContract acyclic = new AcyclicContract();
  +    private DependencyVisitor visitor = new DependencyVisitor();
  +
  +    private Map vertices = new HashMap();
  +
  +    private MutableDirectedGraph DAG = null;
  +
  +    /**
  +     * Constructor for the DependencyGraph object
  +     */
  +    public DependencyGraph()
  +    {
  +        super();
  +        Contract[] dagContracts = new Contract[1];
  +        dagContracts[0] = acyclic;
  +        DAG = factory.makeMutableDirectedGraph(dagContracts,
  +					       false,
  +					       null);
  +        setDirGraph(DAG);
  +    }
  +
  +    /**
  +     * Description of the Method
  +     */
  +    private void init()
  +    {
  +    }
  +    
  +    /**
  +     * Adds a feature to the Dependencies attribute of the DependencyGraph
  +     * object
  +     */
  +    public void addDependencies(Object head,
  +                                Collection deps)
  +        throws GraphException,
  +        CircularDependencyException
  +    {
  +        DependencyVertex vHead = findVertex(head);
  +
  +        if (!getVertices().contains(vHead))
  +        {
  +            DAG.addVertex(vHead);
  +        }
  +
  +        try
  +        {
  +            Iterator v = deps.iterator();
  +
  +            while (v.hasNext())
  +            {
  +                DependencyVertex vDep = findVertex(v.next());
  +
  +                if (!getVertices().contains(vDep))
  +                {
  +                    DAG.addVertex(vDep);
  +                }
  +
  +                DAG.addEdge(new Dependency(vHead.getValue(),
  +					   vDep.getValue()),
  +			    vHead, vDep);
  +            }
  +        }
  +        catch (CycleException ex)
  +	  {
  +            throw new CircularDependencyException(ex);
  +	  }
  +    }
  +
  +    /**
  +     * Description of the Method
  +     */
  +    public DependencyVertex findVertex(Object o)
  +    {
  +        if (vertices.containsKey(o))
  +        {
  +            return (DependencyVertex) vertices.get(o);
  +        }
  +        else
  +        {
  +            DependencyVertex RC = new DependencyVertex(o);
  +            vertices.put(o, RC);
  +            return RC;
  +        }
  +    }
  +
  +    /**
  +     * Gets the sortedDependencies attribute of the DependencyGraph object
  +     */
  +    public List getSortedDependencies(Object head)
  +    {
  +        return visitor.getSortedDependencies(this, findVertex(head));
  +    }
  +
  +    /** 
  +     * Retrieve the vertices in a flattened, sorted, valid order.
  +     *
  +     *  @return The list of vertices in a valid order.
  +     */
  +    public List getSortedDependencies()
  +    {
  +	return visitor.getSortedDependencies( this );
  +    }
  +}
  +
  +
  +
  
  
  
  1.2       +8 -0      jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/domain/dependency/DependencyVisitor.java
  
  Index: DependencyVisitor.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/domain/dependency/DependencyVisitor.java,v
  retrieving revision 1.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- DependencyVisitor.java	8 May 2002 17:43:20 -0000	1.1
  +++ DependencyVisitor.java	26 Jul 2002 12:36:05 -0000	1.2
  @@ -72,5 +72,13 @@
           dfs.visit(dg, root, this);
           return deps;
       }
  +
  +    public synchronized List
  +	getSortedDependencies(DependencyGraph dg )
  +    {
  +	deps = new LinkedList();
  +	dfs.visit( dg, this );
  +	return deps;
  +    }
   }
   
  
  
  

--
To unsubscribe, e-mail:   <mailto:commons-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:commons-dev-help@jakarta.apache.org>


Mime
View raw message