jvanzyl 01/12/02 11:23:40
Modified: graph/src/java/org/apache/commons/graph Graph.java
graph/src/java/org/apache/commons/graph/util
DependencyResolver.java
graph/src/java/org/apache/commons/graph/visitor
DependencyVisitor.java
graph/src/test/org/apache/commons/graph/util
TestDependencyResolver.java
Log:
- the resolver now works but some additions have to be made to tell
the resolver to stop when all the neighbours of the starting
vertex have been visited as opposed to going through the whole
graph.
Revision Changes Path
1.4 +2 -2 jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/Graph.java
Index: Graph.java
===================================================================
RCS file: /home/cvs/jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/Graph.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- Graph.java 2001/12/02 18:07:18 1.3
+++ Graph.java 2001/12/02 19:23:40 1.4
@@ -65,7 +65,7 @@
/**
* Describes a generic graph G = (V, E), i.e. a set of vertices and edges.
*
- * @version $Id: Graph.java,v 1.3 2001/12/02 18:07:18 jvanzyl Exp $
+ * @version $Id: Graph.java,v 1.4 2001/12/02 19:23:40 jvanzyl Exp $
* @author <A HREF="http://www.inf.fu-berlin.de/~dahm">M. Dahm</A>
*/
public class Graph implements Cloneable, Serializable {
@@ -73,7 +73,7 @@
/**
* Debugging flag
*/
- private boolean debug = true;
+ private boolean debug = false;
private boolean directed = true;
1.2 +51 -10 jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/util/DependencyResolver.java
Index: DependencyResolver.java
===================================================================
RCS file: /home/cvs/jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/util/DependencyResolver.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- DependencyResolver.java 2001/12/02 18:07:18 1.1
+++ DependencyResolver.java 2001/12/02 19:23:40 1.2
@@ -75,7 +75,8 @@
*/
public List getSortedDependencies(String g)
{
- List l = getSortedDependencies(new LabeledVertex(g));
+ LabeledVertex start = (LabeledVertex) vertices.get(g);
+ List l = getSortedDependencies(start);
ArrayList sl = new ArrayList();
for (Iterator i = l.iterator(); i.hasNext();)
@@ -122,9 +123,8 @@
*/
public void addGraphable(String g, List dependencies)
{
- LabeledVertex startingVertex = null;
-
- if (vertices.get(g) == null)
+ LabeledVertex startingVertex = (LabeledVertex) vertices.get(g);
+ if (startingVertex == null)
{
// Create a labeled vertex with our starting vertex g.
startingVertex = new LabeledVertex(g);
@@ -141,16 +141,57 @@
// the graph and only add it if it isn't. We need to
// add some code to the graph object to deal with this
// automatically.
- if (vertices.get(dependencyName) == null)
+ LabeledVertex dependency = (LabeledVertex)vertices.get(dependencyName);
+ if (dependency == null)
{
- LabeledVertex dependency = new LabeledVertex(dependencyName);
+ dependency = new LabeledVertex(dependencyName);
vertices.put(dependencyName, dependency);
graph.addVertex(dependency);
-
- // Create an edge between the starting vertex and
- // the dependency.
- graph.addEdge(startingVertex, dependency);
}
+
+ // Create an edge between the starting vertex and
+ // the dependency.
+ graph.addEdge(startingVertex, dependency);
+ }
+ }
+
+ public static void main(String[] args)
+ {
+ Graph graph = new Graph(true);
+
+ LabeledVertex a = new LabeledVertex("A");
+ LabeledVertex b = new LabeledVertex("B");
+ LabeledVertex c = new LabeledVertex("C");
+ LabeledVertex d = new LabeledVertex("D");
+ LabeledVertex e = new LabeledVertex("E");
+ LabeledVertex f = new LabeledVertex("F");
+
+ graph.addVertex(a);
+ graph.addVertex(b);
+ graph.addVertex(c);
+ graph.addVertex(d);
+ graph.addVertex(e);
+ graph.addVertex(f);
+
+ graph.addEdge(c,f);
+
+ graph.addEdge(d,a);
+ graph.addEdge(d,b);
+
+ graph.addEdge(e,b);
+ graph.addEdge(e,c);
+ graph.addEdge(e,d);
+
+ graph.addEdge(f,d);
+
+ DependencyVisitor visitor = new DependencyVisitor();
+ DFS dfs = new DFS(visitor);
+ dfs.start(graph,(Vertex)f);
+ List l = visitor.getSortedDependencies();
+
+ for (Iterator i = l.iterator(); i.hasNext();)
+ {
+ System.out.println(i.next());
}
}
}
1.2 +5 -5 jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/visitor/DependencyVisitor.java
Index: DependencyVisitor.java
===================================================================
RCS file: /home/cvs/jakarta-commons-sandbox/graph/src/java/org/apache/commons/graph/visitor/DependencyVisitor.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- DependencyVisitor.java 2001/12/02 18:07:18 1.1
+++ DependencyVisitor.java 2001/12/02 19:23:40 1.2
@@ -54,7 +54,7 @@
* <http://www.apache.org/>.
*/
-import java.util.ArrayList;
+import java.util.LinkedList;
import java.util.List;
import org.apache.commons.graph.Vertex;
@@ -65,7 +65,7 @@
* this class (and of course its descendants) may be passed to a DFS
* object.
*
- * @version $Id: DependencyVisitor.java,v 1.1 2001/12/02 18:07:18 jvanzyl Exp $
+ * @version $Id: DependencyVisitor.java,v 1.2 2001/12/02 19:23:40 jvanzyl Exp $
* @author <A HREF="http://www.inf.fu-berlin.de/~dahm">M. Dahm</A>
* @see DFS
*/
@@ -78,20 +78,20 @@
* they must be processed by the mechanism using
* the dependency list.
*/
- List sortedDependencies;
+ LinkedList sortedDependencies;
/**
* Default constructor.
*/
public DependencyVisitor()
{
- sortedDependencies = new ArrayList();
+ sortedDependencies = new LinkedList();
}
public void finishVertex(Vertex v)
{
super.finishVertex(v);
- sortedDependencies.add(v);
+ sortedDependencies.addLast(v);
}
public List getSortedDependencies()
1.2 +2 -3 jakarta-commons-sandbox/graph/src/test/org/apache/commons/graph/util/TestDependencyResolver.java
Index: TestDependencyResolver.java
===================================================================
RCS file: /home/cvs/jakarta-commons-sandbox/graph/src/test/org/apache/commons/graph/util/TestDependencyResolver.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- TestDependencyResolver.java 2001/12/02 18:07:19 1.1
+++ TestDependencyResolver.java 2001/12/02 19:23:40 1.2
@@ -10,7 +10,7 @@
/**
* @author <a href="mailto:jvanzyl@apache.org">Jason van Zyl</a>
- * @version $Id: TestDependencyResolver.java,v 1.1 2001/12/02 18:07:19 jvanzyl Exp $
+ * @version $Id: TestDependencyResolver.java,v 1.2 2001/12/02 19:23:40 jvanzyl Exp $
*/
public class TestDependencyResolver
extends TestCase
@@ -90,8 +90,6 @@
d.addGraphable("E", deps("B,C,D"));
d.addGraphable("F", deps("D"));
- System.out.println(">>> " + d.getVerticesString());
-
// Get the dependencies where we exclude the
// specified target.
assertEquals(compare,getList(d.getSortedDependencies("F")));
@@ -99,6 +97,7 @@
}
catch( Exception e )
{
+ e.printStackTrace();
fail();
}
}
--
To unsubscribe, e-mail: <mailto:commons-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:commons-dev-help@jakarta.apache.org>
|