You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by di...@apache.org on 2003/01/01 03:14:39 UTC
cvs commit: jakarta-commons-sandbox/graph2/src/test/org/apache/commons/graph/decorator TransposeTest.java
dion 2002/12/31 18:14:39
Modified: graph2/src/test/org/apache/commons/graph/domain/dependency
DependencyTest.java
graph2/src/test/org/apache/commons/graph DirGraphTest.java
UndirGraphTest.java GraphTest.java
graph2/src/test/org/apache/commons/graph/algorithm/dataflow
DataFlowSolutionsTest.java
graph2/src/test/org/apache/commons/graph/algorithm/path
AllPairsTest.java AllPathsTest.java
graph2/src/test/org/apache/commons/graph/decorator
TransposeTest.java
Log:
Clean up code/fix compile errors
Revision Changes Path
1.2 +269 -269 jakarta-commons-sandbox/graph2/src/test/org/apache/commons/graph/domain/dependency/DependencyTest.java
Index: DependencyTest.java
===================================================================
RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/test/org/apache/commons/graph/domain/dependency/DependencyTest.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- DependencyTest.java 8 May 2002 18:15:21 -0000 1.1
+++ DependencyTest.java 1 Jan 2003 02:14:38 -0000 1.2
@@ -1,269 +1,269 @@
-package org.apache.commons.graph.domain.dependency;
-
-import java.util.Set;
-import java.util.List;
-import java.util.HashSet;
-
-import org.apache.commons.graph.*;
-import org.apache.commons.graph.dependency.exception.*;
-
-/**
- * Description of the Class
- */
-public class DependencyTest
- extends GraphTest
-{
- private DependencyGraph IUT = null;
-
- /**
- * Constructor for the DependencyTest object
- *
- * @param name
- */
- public DependencyTest(String name)
- {
- super(name);
- }
-
- /**
- * The JUnit setup method
- */
- public void setUp()
- {
- IUT = new DependencyGraph();
- }
-
- /**
- * Description of the Class
- */
- private class Task
- {
- private String name;
-
- /**
- * Constructor for the Task object
- *
- * @param name
- */
- public Task(String name)
- {
- this.name = name;
- }
-
- /**
- * Description of the Method
- */
- public String toString()
- {
- return name;
- }
- }
-
- /**
- * Description of the Field
- */
- public Task T1 = new Task("T1");
- /**
- * Description of the Field
- */
- public Task T2 = new Task("T2");
- /**
- * Description of the Field
- */
- public Task T3 = new Task("T3");
- /**
- * Description of the Field
- */
- public Task T4 = new Task("T4");
- /**
- * Description of the Field
- */
- public Task T5 = new Task("T5");
-
- /**
- * A unit test for JUnit
- */
- public void testNoDeps()
- throws Throwable
- {
- Set deps = new HashSet();
-
- IUT.addDependencies(T1, deps);
- }
-
- /**
- * A unit test for JUnit
- */
- public void testTwoTasksNoDeps()
- throws Throwable
- {
- Set deps = new HashSet();
- IUT.addDependencies(T1, deps);
- IUT.addDependencies(T2, deps);
- }
-
- /**
- * A unit test for JUnit
- */
- public void testSelfDep()
- throws Throwable
- {
- Set deps = new HashSet();
- deps.add(T1);
-
- try
- {
- IUT.addDependencies(T1, deps);
- fail("Self Dependency added without exception.");
- }
- catch (CircularDependencyException ex)
- {}
- }
-
- /**
- * A unit test for JUnit
- */
- public void testTwoCyclicDeps()
- throws Throwable
- {
- Set t1Deps = new HashSet();
- t1Deps.add(T2);
-
- Set t2Deps = new HashSet();
- t2Deps.add(T1);
-
- IUT.addDependencies(T1, t1Deps);
- try
- {
- IUT.addDependencies(T2, t2Deps);
- fail("No CircularDependencyException thrown.");
- }
- catch (CircularDependencyException ex)
- {}
- }
-
- /**
- * A unit test for JUnit
- */
- public void testThreeCyclicDeps()
- throws Throwable
- {
- Set t1Deps = new HashSet();
- t1Deps.add(T2);
-
- Set t2Deps = new HashSet();
- t2Deps.add(T3);
-
- Set t3Deps = new HashSet();
- t3Deps.add(T1);
-
- IUT.addDependencies(T1, t1Deps);
- IUT.addDependencies(T2, t2Deps);
-
- try
- {
- IUT.addDependencies(T3, t3Deps);
- fail("No CircularDependencyException Thrown.");
- }
- catch (CircularDependencyException ex)
- {}
- }
-
- /**
- * A unit test for JUnit
- */
- public void testSortedDepsEasy()
- throws Throwable
- {
- Set t1Deps = new HashSet();
- t1Deps.add(T2);
-
- Set t2Deps = new HashSet();
- t2Deps.add(T3);
-
- IUT.addDependencies(T1, t1Deps);
- IUT.addDependencies(T2, t2Deps);
- IUT.addDependencies(T3, new HashSet());
-
- // T3
- List t3SDeps =
- IUT.getSortedDependencies(T3);
- assertEquals("T3: Wrong number of Deps for T3",
- 1, t3SDeps.size());
-
- assertEquals("T3: Wrong thing at pos 0",
- T3, t3SDeps.get(0));
-
- // T2
- List t2SDeps =
- IUT.getSortedDependencies(T2);
- assertEquals("T2: Wrong number of Deps for T2",
- 2, t2SDeps.size());
-
- try
- {
- assertEquals("T2: Wrong thing at pos 0",
- T3, t2SDeps.get(0));
- assertEquals("T2: Wrong thing at pos 1",
- T2, t2SDeps.get(1));
- }
- catch (Throwable ex)
- {
- System.err.println(t2SDeps);
- throw ex;
- }
-
- // T1
- List t1SDeps =
- IUT.getSortedDependencies(T1);
- assertEquals("T1: Wrong number of Deps for T1",
- 3, t1SDeps.size());
-
- assertEquals("T1: Wrong thing at pos 0",
- T3, t1SDeps.get(0));
- assertEquals("T1: Wrong thing at pos 1",
- T2, t1SDeps.get(1));
- assertEquals("T1: Wrong thing at pos 2",
- T1, t1SDeps.get(2));
-
- }
-
- /**
- * A unit test for JUnit
- */
- public void testSortedDepsHard()
- {
- Set t1Deps = new HashSet();
- t1Deps.add(T2);
- t1Deps.add(T3);
- t1Deps.add(T5);
-
- Set t2Deps = new HashSet();
- t2Deps.add(T4);
- t2Deps.add(T5);
-
- IUT.addDependencies(T1, t1Deps);
- IUT.addDependencies(T2, t2Deps);
-
- List t1SDeps = IUT.getSortedDependencies(T1);
- assertEquals("T1: Wrong number of dependents.",
- 5, t1SDeps.size());
-
- List t2SDeps = IUT.getSortedDependencies(T2);
- assertEquals("T2: Wrong number of dependents.",
- 3, t2SDeps.size());
-
- List t3SDeps = IUT.getSortedDependencies(T3);
- assertEquals("T1: Wrong number of dependents.",
- 1, t3SDeps.size());
-
- List t4SDeps = IUT.getSortedDependencies(T4);
- assertEquals("T4: Wrong number of dependents.",
- 1, t4SDeps.size());
-
- List t5SDeps = IUT.getSortedDependencies(T5);
- assertEquals("T5: Wrong number of dependents.",
- 1, t5SDeps.size());
-
- }
-}
+package org.apache.commons.graph.domain.dependency;
+
+import java.util.Set;
+import java.util.List;
+import java.util.HashSet;
+
+import org.apache.commons.graph.*;
+import org.apache.commons.graph.domain.dependency.exception.*;
+
+/**
+ * Description of the Class
+ */
+public class DependencyTest
+ extends GraphTest
+{
+ private DependencyGraph IUT = null;
+
+ /**
+ * Constructor for the DependencyTest object
+ *
+ * @param name
+ */
+ public DependencyTest(String name)
+ {
+ super(name);
+ }
+
+ /**
+ * The JUnit setup method
+ */
+ public void setUp()
+ {
+ IUT = new DependencyGraph();
+ }
+
+ /**
+ * Description of the Class
+ */
+ private class Task
+ {
+ private String name;
+
+ /**
+ * Constructor for the Task object
+ *
+ * @param name
+ */
+ public Task(String name)
+ {
+ this.name = name;
+ }
+
+ /**
+ * Description of the Method
+ */
+ public String toString()
+ {
+ return name;
+ }
+ }
+
+ /**
+ * Description of the Field
+ */
+ public Task T1 = new Task("T1");
+ /**
+ * Description of the Field
+ */
+ public Task T2 = new Task("T2");
+ /**
+ * Description of the Field
+ */
+ public Task T3 = new Task("T3");
+ /**
+ * Description of the Field
+ */
+ public Task T4 = new Task("T4");
+ /**
+ * Description of the Field
+ */
+ public Task T5 = new Task("T5");
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testNoDeps()
+ throws Throwable
+ {
+ Set deps = new HashSet();
+
+ IUT.addDependencies(T1, deps);
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testTwoTasksNoDeps()
+ throws Throwable
+ {
+ Set deps = new HashSet();
+ IUT.addDependencies(T1, deps);
+ IUT.addDependencies(T2, deps);
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testSelfDep()
+ throws Throwable
+ {
+ Set deps = new HashSet();
+ deps.add(T1);
+
+ try
+ {
+ IUT.addDependencies(T1, deps);
+ fail("Self Dependency added without exception.");
+ }
+ catch (CircularDependencyException ex)
+ {}
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testTwoCyclicDeps()
+ throws Throwable
+ {
+ Set t1Deps = new HashSet();
+ t1Deps.add(T2);
+
+ Set t2Deps = new HashSet();
+ t2Deps.add(T1);
+
+ IUT.addDependencies(T1, t1Deps);
+ try
+ {
+ IUT.addDependencies(T2, t2Deps);
+ fail("No CircularDependencyException thrown.");
+ }
+ catch (CircularDependencyException ex)
+ {}
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testThreeCyclicDeps()
+ throws Throwable
+ {
+ Set t1Deps = new HashSet();
+ t1Deps.add(T2);
+
+ Set t2Deps = new HashSet();
+ t2Deps.add(T3);
+
+ Set t3Deps = new HashSet();
+ t3Deps.add(T1);
+
+ IUT.addDependencies(T1, t1Deps);
+ IUT.addDependencies(T2, t2Deps);
+
+ try
+ {
+ IUT.addDependencies(T3, t3Deps);
+ fail("No CircularDependencyException Thrown.");
+ }
+ catch (CircularDependencyException ex)
+ {}
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testSortedDepsEasy()
+ throws Throwable
+ {
+ Set t1Deps = new HashSet();
+ t1Deps.add(T2);
+
+ Set t2Deps = new HashSet();
+ t2Deps.add(T3);
+
+ IUT.addDependencies(T1, t1Deps);
+ IUT.addDependencies(T2, t2Deps);
+ IUT.addDependencies(T3, new HashSet());
+
+ // T3
+ List t3SDeps =
+ IUT.getSortedDependencies(T3);
+ assertEquals("T3: Wrong number of Deps for T3",
+ 1, t3SDeps.size());
+
+ assertEquals("T3: Wrong thing at pos 0",
+ T3, t3SDeps.get(0));
+
+ // T2
+ List t2SDeps =
+ IUT.getSortedDependencies(T2);
+ assertEquals("T2: Wrong number of Deps for T2",
+ 2, t2SDeps.size());
+
+ try
+ {
+ assertEquals("T2: Wrong thing at pos 0",
+ T3, t2SDeps.get(0));
+ assertEquals("T2: Wrong thing at pos 1",
+ T2, t2SDeps.get(1));
+ }
+ catch (Throwable ex)
+ {
+ System.err.println(t2SDeps);
+ throw ex;
+ }
+
+ // T1
+ List t1SDeps =
+ IUT.getSortedDependencies(T1);
+ assertEquals("T1: Wrong number of Deps for T1",
+ 3, t1SDeps.size());
+
+ assertEquals("T1: Wrong thing at pos 0",
+ T3, t1SDeps.get(0));
+ assertEquals("T1: Wrong thing at pos 1",
+ T2, t1SDeps.get(1));
+ assertEquals("T1: Wrong thing at pos 2",
+ T1, t1SDeps.get(2));
+
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testSortedDepsHard()
+ {
+ Set t1Deps = new HashSet();
+ t1Deps.add(T2);
+ t1Deps.add(T3);
+ t1Deps.add(T5);
+
+ Set t2Deps = new HashSet();
+ t2Deps.add(T4);
+ t2Deps.add(T5);
+
+ IUT.addDependencies(T1, t1Deps);
+ IUT.addDependencies(T2, t2Deps);
+
+ List t1SDeps = IUT.getSortedDependencies(T1);
+ assertEquals("T1: Wrong number of dependents.",
+ 5, t1SDeps.size());
+
+ List t2SDeps = IUT.getSortedDependencies(T2);
+ assertEquals("T2: Wrong number of dependents.",
+ 3, t2SDeps.size());
+
+ List t3SDeps = IUT.getSortedDependencies(T3);
+ assertEquals("T1: Wrong number of dependents.",
+ 1, t3SDeps.size());
+
+ List t4SDeps = IUT.getSortedDependencies(T4);
+ assertEquals("T4: Wrong number of dependents.",
+ 1, t4SDeps.size());
+
+ List t5SDeps = IUT.getSortedDependencies(T5);
+ assertEquals("T5: Wrong number of dependents.",
+ 1, t5SDeps.size());
+
+ }
+}
1.3 +474 -478 jakarta-commons-sandbox/graph2/src/test/org/apache/commons/graph/DirGraphTest.java
Index: DirGraphTest.java
===================================================================
RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/test/org/apache/commons/graph/DirGraphTest.java,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- DirGraphTest.java 8 May 2002 18:24:47 -0000 1.2
+++ DirGraphTest.java 1 Jan 2003 02:14:38 -0000 1.3
@@ -1,478 +1,474 @@
-package org.apache.commons.graph;
-
-/* ====================================================================
- * The Apache Software License, Version 1.1
- *
- * Copyright (c) 2001 The Apache Software Foundation. All rights
- * reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, 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 "Apache" and "Apache Software Foundation" and
- * "Commons" 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",
- * "Commons", 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 (INCLUDING, 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/>.
- */
-
-/**
- * DirGraphTest This test will ensure that we can represent a Directed Graph.
- */
-
-import java.util.Set;
-import java.util.HashSet;
-import java.util.Iterator;
-
-/**
- * Description of the Class
- */
-public class DirGraphTest
- extends GraphTest
-{
- private String testName = null;
-
- /**
- * Constructor for the DirGraphTest object
- *
- * @param name
- */
- public DirGraphTest(String name)
- {
- super(name);
- this.testName = name;
- }
-
- /**
- * A unit test for JUnit
- */
- public void testDirNull()
- throws Throwable
- {
- verifyGraph(makeDirNullGraph(), 0, 0);
- }
-
- /**
- * A unit test for JUnit
- */
- public void testSingleVertex()
- throws Throwable
- {
- verifyGraph(makeDirSingleVertex(), 1, 0);
- }
-
- /**
- * A unit test for JUnit
- */
- public void testDoubleVertex()
- throws Throwable
- {
- verifyGraph(makeDirDoubleVertex(), 2, 0);
- }
-
- /**
- * A unit test for JUnit
- */
- public void testSelfLoop()
- throws Throwable
- {
- DirectedGraph IUT = makeSelfLoop();
- try
- {
-
- verifyGraph(IUT, 1, 1);
-
- verifyAdjVertices(IUT, V1,
- makeSet(V1));
-
- verifyAdjVertices(IUT, V1,
- makeSet(V1),
- makeSet(V1));
- }
- catch (Throwable t)
- {
- printGraph(t, IUT);
- throw t;
- }
- }
-
- /**
- * A unit test for JUnit
- */
- public void testDirectedEdge()
- throws Throwable
- {
- DirectedGraph IUT = makeDirectedEdge();
- try
- {
-
- verifyGraph(IUT, 2, 1);
-
- verifyAdjVertices(IUT, V1,
- makeSet(V1, V2));
- verifyAdjVertices(IUT, V1,
- makeSet(V1, V2));
-
- verifyAdjVertices(IUT, V1,
- makeSet(),
- makeSet(V2));
- verifyAdjVertices(IUT, V2,
- makeSet(V1),
- makeSet());
- }
- catch (Throwable t)
- {
- printGraph(t, IUT);
- throw t;
- }
- }
-
- /**
- * A unit test for JUnit
- */
- public void testDirParallelEdges()
- throws Throwable
- {
- DirectedGraph IUT = makeDirParallelEdges();
- try
- {
-
- verifyGraph(IUT, 2, 2);
-
- verifyAdjVertices(IUT, V1,
- makeSet(V1, V2));
- verifyAdjVertices(IUT, V2,
- makeSet(V1, V2));
-
- verifyAdjVertices(IUT, V1,
- makeSet(),
- makeSet(V2));
- verifyAdjVertices(IUT, V2,
- makeSet(V1),
- makeSet());
-
- }
- catch (Throwable t)
- {
- printGraph(t, IUT);
- throw t;
- }
- }
-
- /**
- * A unit test for JUnit
- */
- public void testTwoCycle()
- throws Throwable
- {
- DirectedGraph IUT = makeTwoCycle();
- try
- {
-
- verifyGraph(IUT, 2, 2);
-
- verifyAdjVertices(IUT, V1,
- makeSet(V1, V2));
- verifyAdjVertices(IUT, V2,
- makeSet(V1, V2));
-
- verifyAdjVertices(IUT, V1,
- makeSet(V2),
- makeSet(V2));
- verifyAdjVertices(IUT, V2,
- makeSet(V1),
- makeSet(V1));
- }
- catch (Throwable t)
- {
- printGraph(t, IUT);
- throw t;
- }
- }
-
- /**
- * A unit test for JUnit
- */
- public void testDirectedCycle()
- throws Throwable
- {
- DirectedGraph IUT = makeDirectedCycle();
- try
- {
-
- verifyGraph(IUT, 3, 3);
-
- verifyAdjVertices(IUT, V1,
- makeSet(V1, V2, V3));
- verifyAdjVertices(IUT, V2,
- makeSet(V1, V2, V3));
- verifyAdjVertices(IUT, V3,
- makeSet(V1, V2, V3));
-
- verifyAdjVertices(IUT, V1,
- makeSet(V3),
- makeSet(V2));
- verifyAdjVertices(IUT, V2,
- makeSet(V1),
- makeSet(V3));
- verifyAdjVertices(IUT, V3,
- makeSet(V2),
- makeSet(V1));
- }
- catch (Throwable t)
- {
- printGraph(t, IUT);
- throw t;
- }
- }
-
-
- /**
- * A unit test for JUnit
- */
- public void testPipe()
- throws Throwable
- {
- DirectedGraph IUT = makePipe();
- try
- {
-
- verifyGraph(IUT, 3, 2);
-
- verifyAdjVertices(IUT, V1,
- makeSet(V1, V2));
- verifyAdjVertices(IUT, V2,
- makeSet(V1, V2, V3));
- verifyAdjVertices(IUT, V3,
- makeSet(V2, V3));
-
- verifyAdjVertices(IUT, V1,
- makeSet(),
- makeSet(V2));
- verifyAdjVertices(IUT, V2,
- makeSet(V1),
- makeSet(V3));
- verifyAdjVertices(IUT, V3,
- makeSet(V2),
- makeSet());
- }
- catch (Throwable t)
- {
- printGraph(t, IUT);
- throw t;
- }
- }
-
- /**
- * A unit test for JUnit
- */
- public void testDiamond()
- throws Throwable
- {
- DirectedGraph IUT = makeDiamond();
- try
- {
-
- verifyGraph(IUT, 4, 4);
-
- verifyAdjVertices(IUT, V1,
- makeSet(V1, V2, V3));
- verifyAdjVertices(IUT, V2,
- makeSet(V1, V2, V4));
- verifyAdjVertices(IUT, V3,
- makeSet(V1, V3, V4));
- verifyAdjVertices(IUT, V4,
- makeSet(V2, V3, V4));
-
- verifyAdjVertices(IUT, V1,
- makeSet(),
- makeSet(V2, V3));
- verifyAdjVertices(IUT, V2,
- makeSet(V1),
- makeSet(V4));
- verifyAdjVertices(IUT, V3,
- makeSet(V1),
- makeSet(V4));
- verifyAdjVertices(IUT, V4,
- makeSet(V2, V3),
- makeSet());
- }
- catch (Throwable t)
- {
- printGraph(t, IUT);
- throw t;
- }
- }
-
- /**
- * A unit test for JUnit
- */
- public void testPipelessCycle()
- throws Throwable
- {
- DirectedGraph IUT = makePipelessCycle();
- try
- {
-
- verifyGraph(IUT, 4, 4);
-
- verifyAdjVertices(IUT, V1,
- makeSet(V1, V2, V3));
- verifyAdjVertices(IUT, V2,
- makeSet(V1, V2, V4));
- verifyAdjVertices(IUT, V3,
- makeSet(V1, V3, V4));
- verifyAdjVertices(IUT, V4,
- makeSet(V2, V3, V4));
-
- verifyAdjVertices(IUT, V1,
- makeSet(),
- makeSet(V2, V3));
- verifyAdjVertices(IUT, V2,
- makeSet(V1, V4),
- makeSet());
- verifyAdjVertices(IUT, V3,
- makeSet(V1, V4),
- makeSet());
- verifyAdjVertices(IUT, V4,
- makeSet(),
- makeSet(V2, V3));
- }
- catch (Throwable t)
- {
- printGraph(t, IUT);
- throw t;
- }
- }
-
- /**
- * A unit test for JUnit
- */
- public void testParentTree()
- throws Throwable
- {
- DirectedGraph IUT = makeParentTree();
- try
- {
-
- verifyGraph(IUT, 5, 4);
-
- verifyAdjVertices(IUT, V1,
- makeSet(V1, V2, V3));
- verifyAdjVertices(IUT, V2,
- makeSet(V1, V2));
- verifyAdjVertices(IUT, V3,
- makeSet(V1, V3, V4, V5));
- verifyAdjVertices(IUT, V4,
- makeSet(V3, V4));
- verifyAdjVertices(IUT, V5,
- makeSet(V3, V5));
-
- verifyAdjVertices(IUT, V1,
- makeSet(V2, V3),
- makeSet());
- verifyAdjVertices(IUT, V2,
- makeSet(),
- makeSet(V1));
- verifyAdjVertices(IUT, V3,
- makeSet(V4, V5),
- makeSet(V1));
- verifyAdjVertices(IUT, V4,
- makeSet(),
- makeSet(V3));
- verifyAdjVertices(IUT, V5,
- makeSet(),
- makeSet(V3));
- }
- catch (Throwable t)
- {
- printGraph(t, IUT);
- throw t;
- }
- }
-
- /**
- * A unit test for JUnit
- */
- public void testChildTree()
- throws Throwable
- {
- DirectedGraph IUT = makeChildTree();
- try
- {
-
- verifyGraph(IUT, 5, 4);
-
- verifyAdjVertices(IUT, V1,
- makeSet(V1, V2, V3));
- verifyAdjVertices(IUT, V2,
- makeSet(V1, V2));
- verifyAdjVertices(IUT, V3,
- makeSet(V1, V3, V4, V5));
- verifyAdjVertices(IUT, V4,
- makeSet(V3, V4));
- verifyAdjVertices(IUT, V5,
- makeSet(V3, V5));
-
- verifyAdjVertices(IUT, V1,
- makeSet(),
- makeSet(V2, V3));
- verifyAdjVertices(IUT, V2,
- makeSet(V1),
- makeSet());
- verifyAdjVertices(IUT, V3,
- makeSet(V1),
- makeSet(V4, V5));
- verifyAdjVertices(IUT, V4,
- makeSet(V3),
- makeSet());
- verifyAdjVertices(IUT, V5,
- makeSet(V3),
- makeSet());
- }
- catch (Throwable t)
- {
- printGraph(t, IUT);
- throw t;
- }
- }
-
-}
+package org.apache.commons.graph;
+
+/* ====================================================================
+ * The Apache Software License, Version 1.1
+ *
+ * Copyright (c) 2001 The Apache Software Foundation. All rights
+ * reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, 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 "Apache" and "Apache Software Foundation" and
+ * "Commons" 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",
+ * "Commons", 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 (INCLUDING, 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/>.
+ */
+
+/**
+ * DirGraphTest This test will ensure that we can represent a Directed Graph.
+ */
+
+/**
+ * Description of the Class
+ */
+public class DirGraphTest
+ extends GraphTest
+{
+ private String testName = null;
+
+ /**
+ * Constructor for the DirGraphTest object
+ *
+ * @param name
+ */
+ public DirGraphTest(String name)
+ {
+ super(name);
+ this.testName = name;
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testDirNull()
+ throws Throwable
+ {
+ verifyGraph(makeDirNullGraph(), 0, 0);
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testSingleVertex()
+ throws Throwable
+ {
+ verifyGraph(makeDirSingleVertex(), 1, 0);
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testDoubleVertex()
+ throws Throwable
+ {
+ verifyGraph(makeDirDoubleVertex(), 2, 0);
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testSelfLoop()
+ throws Throwable
+ {
+ DirectedGraph IUT = makeSelfLoop();
+ try
+ {
+
+ verifyGraph(IUT, 1, 1);
+
+ verifyAdjVertices(IUT, V1,
+ makeSet(V1));
+
+ verifyAdjVertices(IUT, V1,
+ makeSet(V1),
+ makeSet(V1));
+ }
+ catch (Throwable t)
+ {
+ printGraph(t, IUT);
+ throw t;
+ }
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testDirectedEdge()
+ throws Throwable
+ {
+ DirectedGraph IUT = makeDirectedEdge();
+ try
+ {
+
+ verifyGraph(IUT, 2, 1);
+
+ verifyAdjVertices(IUT, V1,
+ makeSet(V1, V2));
+ verifyAdjVertices(IUT, V1,
+ makeSet(V1, V2));
+
+ verifyAdjVertices(IUT, V1,
+ makeSet(),
+ makeSet(V2));
+ verifyAdjVertices(IUT, V2,
+ makeSet(V1),
+ makeSet());
+ }
+ catch (Throwable t)
+ {
+ printGraph(t, IUT);
+ throw t;
+ }
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testDirParallelEdges()
+ throws Throwable
+ {
+ DirectedGraph IUT = makeDirParallelEdges();
+ try
+ {
+
+ verifyGraph(IUT, 2, 2);
+
+ verifyAdjVertices(IUT, V1,
+ makeSet(V1, V2));
+ verifyAdjVertices(IUT, V2,
+ makeSet(V1, V2));
+
+ verifyAdjVertices(IUT, V1,
+ makeSet(),
+ makeSet(V2));
+ verifyAdjVertices(IUT, V2,
+ makeSet(V1),
+ makeSet());
+
+ }
+ catch (Throwable t)
+ {
+ printGraph(t, IUT);
+ throw t;
+ }
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testTwoCycle()
+ throws Throwable
+ {
+ DirectedGraph IUT = makeTwoCycle();
+ try
+ {
+
+ verifyGraph(IUT, 2, 2);
+
+ verifyAdjVertices(IUT, V1,
+ makeSet(V1, V2));
+ verifyAdjVertices(IUT, V2,
+ makeSet(V1, V2));
+
+ verifyAdjVertices(IUT, V1,
+ makeSet(V2),
+ makeSet(V2));
+ verifyAdjVertices(IUT, V2,
+ makeSet(V1),
+ makeSet(V1));
+ }
+ catch (Throwable t)
+ {
+ printGraph(t, IUT);
+ throw t;
+ }
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testDirectedCycle()
+ throws Throwable
+ {
+ DirectedGraph IUT = makeDirectedCycle();
+ try
+ {
+
+ verifyGraph(IUT, 3, 3);
+
+ verifyAdjVertices(IUT, V1,
+ makeSet(V1, V2, V3));
+ verifyAdjVertices(IUT, V2,
+ makeSet(V1, V2, V3));
+ verifyAdjVertices(IUT, V3,
+ makeSet(V1, V2, V3));
+
+ verifyAdjVertices(IUT, V1,
+ makeSet(V3),
+ makeSet(V2));
+ verifyAdjVertices(IUT, V2,
+ makeSet(V1),
+ makeSet(V3));
+ verifyAdjVertices(IUT, V3,
+ makeSet(V2),
+ makeSet(V1));
+ }
+ catch (Throwable t)
+ {
+ printGraph(t, IUT);
+ throw t;
+ }
+ }
+
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testPipe()
+ throws Throwable
+ {
+ DirectedGraph IUT = makePipe();
+ try
+ {
+
+ verifyGraph(IUT, 3, 2);
+
+ verifyAdjVertices(IUT, V1,
+ makeSet(V1, V2));
+ verifyAdjVertices(IUT, V2,
+ makeSet(V1, V2, V3));
+ verifyAdjVertices(IUT, V3,
+ makeSet(V2, V3));
+
+ verifyAdjVertices(IUT, V1,
+ makeSet(),
+ makeSet(V2));
+ verifyAdjVertices(IUT, V2,
+ makeSet(V1),
+ makeSet(V3));
+ verifyAdjVertices(IUT, V3,
+ makeSet(V2),
+ makeSet());
+ }
+ catch (Throwable t)
+ {
+ printGraph(t, IUT);
+ throw t;
+ }
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testDiamond()
+ throws Throwable
+ {
+ DirectedGraph IUT = makeDiamond();
+ try
+ {
+
+ verifyGraph(IUT, 4, 4);
+
+ verifyAdjVertices(IUT, V1,
+ makeSet(V1, V2, V3));
+ verifyAdjVertices(IUT, V2,
+ makeSet(V1, V2, V4));
+ verifyAdjVertices(IUT, V3,
+ makeSet(V1, V3, V4));
+ verifyAdjVertices(IUT, V4,
+ makeSet(V2, V3, V4));
+
+ verifyAdjVertices(IUT, V1,
+ makeSet(),
+ makeSet(V2, V3));
+ verifyAdjVertices(IUT, V2,
+ makeSet(V1),
+ makeSet(V4));
+ verifyAdjVertices(IUT, V3,
+ makeSet(V1),
+ makeSet(V4));
+ verifyAdjVertices(IUT, V4,
+ makeSet(V2, V3),
+ makeSet());
+ }
+ catch (Throwable t)
+ {
+ printGraph(t, IUT);
+ throw t;
+ }
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testPipelessCycle()
+ throws Throwable
+ {
+ DirectedGraph IUT = makePipelessCycle();
+ try
+ {
+
+ verifyGraph(IUT, 4, 4);
+
+ verifyAdjVertices(IUT, V1,
+ makeSet(V1, V2, V3));
+ verifyAdjVertices(IUT, V2,
+ makeSet(V1, V2, V4));
+ verifyAdjVertices(IUT, V3,
+ makeSet(V1, V3, V4));
+ verifyAdjVertices(IUT, V4,
+ makeSet(V2, V3, V4));
+
+ verifyAdjVertices(IUT, V1,
+ makeSet(),
+ makeSet(V2, V3));
+ verifyAdjVertices(IUT, V2,
+ makeSet(V1, V4),
+ makeSet());
+ verifyAdjVertices(IUT, V3,
+ makeSet(V1, V4),
+ makeSet());
+ verifyAdjVertices(IUT, V4,
+ makeSet(),
+ makeSet(V2, V3));
+ }
+ catch (Throwable t)
+ {
+ printGraph(t, IUT);
+ throw t;
+ }
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testParentTree()
+ throws Throwable
+ {
+ DirectedGraph IUT = makeParentTree();
+ try
+ {
+
+ verifyGraph(IUT, 5, 4);
+
+ verifyAdjVertices(IUT, V1,
+ makeSet(V1, V2, V3));
+ verifyAdjVertices(IUT, V2,
+ makeSet(V1, V2));
+ verifyAdjVertices(IUT, V3,
+ makeSet(V1, V3, V4, V5));
+ verifyAdjVertices(IUT, V4,
+ makeSet(V3, V4));
+ verifyAdjVertices(IUT, V5,
+ makeSet(V3, V5));
+
+ verifyAdjVertices(IUT, V1,
+ makeSet(V2, V3),
+ makeSet());
+ verifyAdjVertices(IUT, V2,
+ makeSet(),
+ makeSet(V1));
+ verifyAdjVertices(IUT, V3,
+ makeSet(V4, V5),
+ makeSet(V1));
+ verifyAdjVertices(IUT, V4,
+ makeSet(),
+ makeSet(V3));
+ verifyAdjVertices(IUT, V5,
+ makeSet(),
+ makeSet(V3));
+ }
+ catch (Throwable t)
+ {
+ printGraph(t, IUT);
+ throw t;
+ }
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testChildTree()
+ throws Throwable
+ {
+ DirectedGraph IUT = makeChildTree();
+ try
+ {
+
+ verifyGraph(IUT, 5, 4);
+
+ verifyAdjVertices(IUT, V1,
+ makeSet(V1, V2, V3));
+ verifyAdjVertices(IUT, V2,
+ makeSet(V1, V2));
+ verifyAdjVertices(IUT, V3,
+ makeSet(V1, V3, V4, V5));
+ verifyAdjVertices(IUT, V4,
+ makeSet(V3, V4));
+ verifyAdjVertices(IUT, V5,
+ makeSet(V3, V5));
+
+ verifyAdjVertices(IUT, V1,
+ makeSet(),
+ makeSet(V2, V3));
+ verifyAdjVertices(IUT, V2,
+ makeSet(V1),
+ makeSet());
+ verifyAdjVertices(IUT, V3,
+ makeSet(V1),
+ makeSet(V4, V5));
+ verifyAdjVertices(IUT, V4,
+ makeSet(V3),
+ makeSet());
+ verifyAdjVertices(IUT, V5,
+ makeSet(V3),
+ makeSet());
+ }
+ catch (Throwable t)
+ {
+ printGraph(t, IUT);
+ throw t;
+ }
+ }
+
+}
1.3 +375 -379 jakarta-commons-sandbox/graph2/src/test/org/apache/commons/graph/UndirGraphTest.java
Index: UndirGraphTest.java
===================================================================
RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/test/org/apache/commons/graph/UndirGraphTest.java,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- UndirGraphTest.java 8 May 2002 18:24:47 -0000 1.2
+++ UndirGraphTest.java 1 Jan 2003 02:14:38 -0000 1.3
@@ -1,379 +1,375 @@
-package org.apache.commons.graph;
-
-/* ====================================================================
- * The Apache Software License, Version 1.1
- *
- * Copyright (c) 2001 The Apache Software Foundation. All rights
- * reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, 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 "Apache" and "Apache Software Foundation" and
- * "Commons" 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",
- * "Commons", 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 (INCLUDING, 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/>.
- */
-/**
- * GraphTest This test will ensure that we can indeed represent a graph. We will
- * implement the following graphs. () No Vertex, No Edges @ One Vertex, No Edges
- * @ @ Two Vertices, No Edges @-@ Two Vertices, One edge /-\ @ @ Two Vertices,
- * Two Edges (Parallel Edges) \-/ @ / \ Three Vertices, Three Edges (Cycle)
- * @---@ @--@--@ Three Vertices, Two Edges (No Cycle) @ / \ @ @ 5 Vertices, 4
- * Edges (Tree) / \ @ @ @-@ @-@ 4 Vertices, 2 Edges (Disconnected)
- */
-
-import java.util.Set;
-import java.util.Map;
-import java.util.HashSet;
-import java.util.HashMap;
-import java.util.Iterator;
-
-import junit.framework.*;
-
-/**
- * Description of the Class
- */
-public class UndirGraphTest extends GraphTest
-{
- /**
- * Constructor for the UndirGraphTest object
- *
- * @param name
- */
- public UndirGraphTest(String name)
- {
- super(name);
- }
-
- /**
- * Test the NULL Graph.
- */
- public void testNullGraph()
- throws Throwable
- {
- verifyGraph(makeNullGraph(), 0, 0);
- }
-
-
- /**
- * Test the Single Vertex.
- */
- public void testSingleVertex()
- throws Throwable
- {
- verifyGraph(makeSingleVertex(), 1, 0);
- }
-
- /**
- * Tests Double Vertex graph.
- */
- public void testDoubleVertex()
- throws Throwable
- {
- verifyGraph(makeDoubleVertex(), 2, 0);
- }
-
- /**
- * Test Single Edge Graph.
- */
- public void testSingleEdge()
- throws Throwable
- {
- Graph IUT = makeSingleEdge();
-
- verifyGraph(IUT, 2, 1);
-
- // Verify Edge from Vertex Count
- verifyVertexEdgeCount(IUT, V1, 1);
- verifyVertexEdgeCount(IUT, V2, 1);
-
- Set expectV1 = new HashSet();
- expectV1.add(V2);
-
- verifyAdjVertices(IUT, V1, expectV1);
-
- Set expectV2 = new HashSet();
- expectV2.add(V1);
-
- verifyAdjVertices(IUT, V2, expectV2);
- }
-
- /**
- * Test Parallel Edges, make sure the representation is right.
- */
- public void testParallelEdges()
- throws Throwable
- {
- Graph IUT = makeParallelEdges();
-
- verifyGraph(IUT, 2, 2);
-
- // Verify Edge from Vertex Count
- verifyVertexEdgeCount(IUT, V1, 2);
- verifyVertexEdgeCount(IUT, V2, 2);
-
- // Verify Adjacent Vertex
- Set expectV1 = new HashSet();
- Set expectV2 = new HashSet();
-
- expectV1.add(V2);
- expectV2.add(V1);
-
- verifyAdjVertices(IUT, V1, expectV1);
- verifyAdjVertices(IUT, V2, expectV2);
-
- }
-
- /**
- * Test the Cycle Graph.
- */
- public void testCycle()
- throws Throwable
- {
- Graph IUT = makeCycle();
-
- verifyGraph(IUT, 3, 3);
-
- // Verify Edge from Vertex Count
- verifyVertexEdgeCount(IUT, V1, 2);
- verifyVertexEdgeCount(IUT, V2, 2);
- verifyVertexEdgeCount(IUT, V3, 2);
-
- // Verify Adjacent Vertex
- Set expectV1 = new HashSet();
- Set expectV2 = new HashSet();
- Set expectV3 = new HashSet();
-
- expectV1.add(V2);
- expectV1.add(V3);
- expectV2.add(V1);
- expectV2.add(V3);
- expectV3.add(V1);
- expectV3.add(V2);
-
- verifyAdjVertices(IUT, V1, expectV1);
- verifyAdjVertices(IUT, V2, expectV2);
- verifyAdjVertices(IUT, V3, expectV3);
- }
-
- /**
- * Test the No Cycle Graph.
- */
- public void testNoCycle()
- throws Throwable
- {
- Graph IUT = makeNoCycle();
-
- verifyGraph(IUT, 3, 2);
-
- // Verify Edge from Vertex Count
- verifyVertexEdgeCount(IUT, V1, 1);
- verifyVertexEdgeCount(IUT, V2, 2);
- verifyVertexEdgeCount(IUT, V3, 1);
-
- // Verify Adjacent Vertex
- Set expectV1 = new HashSet();
- Set expectV2 = new HashSet();
- Set expectV3 = new HashSet();
-
- expectV1.add(V2);
- expectV2.add(V1);
- expectV2.add(V3);
- expectV3.add(V2);
-
- verifyAdjVertices(IUT, V1, expectV1);
- verifyAdjVertices(IUT, V2, expectV2);
- verifyAdjVertices(IUT, V3, expectV3);
- }
-
- /**
- * Test the Tree Graph.
- */
- public void testTree()
- throws Throwable
- {
- Graph IUT = makeTree();
-
- verifyGraph(IUT, 5, 4);
-
- // Verify Edge from Vertex Count
- verifyVertexEdgeCount(IUT, V1, 2);
- verifyVertexEdgeCount(IUT, V2, 1);
- verifyVertexEdgeCount(IUT, V3, 3);
- verifyVertexEdgeCount(IUT, V4, 1);
- verifyVertexEdgeCount(IUT, V5, 1);
-
- // Verify Adjacent Vertex
- Set expectV1 = new HashSet();
- Set expectV2 = new HashSet();
- Set expectV3 = new HashSet();
- Set expectV4 = new HashSet();
- Set expectV5 = new HashSet();
-
- expectV1.add(V2);
- expectV1.add(V3);
- expectV2.add(V1);
- expectV3.add(V1);
- expectV3.add(V4);
- expectV3.add(V5);
- expectV4.add(V3);
- expectV5.add(V3);
-
- verifyAdjVertices(IUT, V1, expectV1);
- verifyAdjVertices(IUT, V2, expectV2);
- verifyAdjVertices(IUT, V3, expectV3);
- verifyAdjVertices(IUT, V4, expectV4);
- verifyAdjVertices(IUT, V5, expectV5);
- }
-
- /**
- * Test the Disconnected Graph.
- */
- public void testDisconnected()
- throws Throwable
- {
- Graph IUT = makeDisconnected();
-
- verifyGraph(IUT, 4, 2);
-
- // Verify Edge from Vertex Count
- verifyVertexEdgeCount(IUT, V1, 1);
- verifyVertexEdgeCount(IUT, V2, 1);
- verifyVertexEdgeCount(IUT, V3, 1);
- verifyVertexEdgeCount(IUT, V4, 1);
-
- // Verify Adjacent Vertex
- Set expectV1 = new HashSet();
- Set expectV2 = new HashSet();
- Set expectV3 = new HashSet();
- Set expectV4 = new HashSet();
-
- expectV1.add(V2);
- expectV2.add(V1);
- expectV3.add(V4);
- expectV4.add(V3);
-
- verifyAdjVertices(IUT, V1, expectV1);
- verifyAdjVertices(IUT, V2, expectV2);
- verifyAdjVertices(IUT, V3, expectV3);
- verifyAdjVertices(IUT, V4, expectV4);
- }
-
-
- /**
- * Description of the Method
- */
- public void verifyVertexEdgeCount(Graph IUT,
- Vertex v,
- int numEdge)
- throws Throwable
- {
- assertEquals(v.toString() + " has wrong number of adjacent edges.",
- IUT.getEdges(v).size(), numEdge);
- }
-
- /**
- * Gets the adjVertices attribute of the UndirGraphTest object
- */
- private Set getAdjVertices(Graph IUT,
- Vertex v)
- {
- Set RC = new HashSet();
- Iterator edges = IUT.getEdges(v).iterator();
-
- while (edges.hasNext())
- {
- Edge e = (Edge) edges.next();
-
- Set verts = IUT.getVertices(e);
- verts.remove(v);
- RC.addAll(verts);
- }
-
- return RC;
- }
-
- /**
- * Description of the Method
- */
- public void verifyAdjVertices(Graph IUT,
- Vertex v,
- Set expected)
- throws Throwable
- {
- Set adjacent = getAdjVertices(IUT, v);
- Iterator adjV = adjacent.iterator();
-
- while (adjV.hasNext())
- {
- Vertex curr = (Vertex) adjV.next();
-
- assertTrue(curr.toString() + " is not supposed to be " +
- "next to " + v.toString(),
- expected.contains(curr));
- }
-
- Iterator expect = expected.iterator();
-
- while (expect.hasNext())
- {
- Vertex curr = (Vertex) expect.next();
-
- assertTrue(curr.toString() + " is supposed to be next to " +
- v.toString(),
- adjacent.contains(curr));
- }
- }
-
- /**
- * Description of the Method
- */
- public void verifyGraph(Graph g, int numVertex, int numEdge)
- throws Throwable
- {
- assertEquals("Incorrect Number of Vertices.",
- g.getVertices().size(), numVertex);
- assertEquals("Incorrect Number of Edges.",
- g.getEdges().size(), numEdge);
- }
-}
+package org.apache.commons.graph;
+
+/* ====================================================================
+ * The Apache Software License, Version 1.1
+ *
+ * Copyright (c) 2001 The Apache Software Foundation. All rights
+ * reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, 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 "Apache" and "Apache Software Foundation" and
+ * "Commons" 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",
+ * "Commons", 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 (INCLUDING, 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/>.
+ */
+/**
+ * GraphTest This test will ensure that we can indeed represent a graph. We will
+ * implement the following graphs. () No Vertex, No Edges @ One Vertex, No Edges
+ * @ @ Two Vertices, No Edges @-@ Two Vertices, One edge /-\ @ @ Two Vertices,
+ * Two Edges (Parallel Edges) \-/ @ / \ Three Vertices, Three Edges (Cycle)
+ * @---@ @--@--@ Three Vertices, Two Edges (No Cycle) @ / \ @ @ 5 Vertices, 4
+ * Edges (Tree) / \ @ @ @-@ @-@ 4 Vertices, 2 Edges (Disconnected)
+ */
+
+import java.util.Set;
+import java.util.HashSet;
+import java.util.Iterator;
+
+/**
+ * Description of the Class
+ */
+public class UndirGraphTest extends GraphTest
+{
+ /**
+ * Constructor for the UndirGraphTest object
+ *
+ * @param name
+ */
+ public UndirGraphTest(String name)
+ {
+ super(name);
+ }
+
+ /**
+ * Test the NULL Graph.
+ */
+ public void testNullGraph()
+ throws Throwable
+ {
+ verifyGraph(makeNullGraph(), 0, 0);
+ }
+
+
+ /**
+ * Test the Single Vertex.
+ */
+ public void testSingleVertex()
+ throws Throwable
+ {
+ verifyGraph(makeSingleVertex(), 1, 0);
+ }
+
+ /**
+ * Tests Double Vertex graph.
+ */
+ public void testDoubleVertex()
+ throws Throwable
+ {
+ verifyGraph(makeDoubleVertex(), 2, 0);
+ }
+
+ /**
+ * Test Single Edge Graph.
+ */
+ public void testSingleEdge()
+ throws Throwable
+ {
+ Graph IUT = makeSingleEdge();
+
+ verifyGraph(IUT, 2, 1);
+
+ // Verify Edge from Vertex Count
+ verifyVertexEdgeCount(IUT, V1, 1);
+ verifyVertexEdgeCount(IUT, V2, 1);
+
+ Set expectV1 = new HashSet();
+ expectV1.add(V2);
+
+ verifyAdjVertices(IUT, V1, expectV1);
+
+ Set expectV2 = new HashSet();
+ expectV2.add(V1);
+
+ verifyAdjVertices(IUT, V2, expectV2);
+ }
+
+ /**
+ * Test Parallel Edges, make sure the representation is right.
+ */
+ public void testParallelEdges()
+ throws Throwable
+ {
+ Graph IUT = makeParallelEdges();
+
+ verifyGraph(IUT, 2, 2);
+
+ // Verify Edge from Vertex Count
+ verifyVertexEdgeCount(IUT, V1, 2);
+ verifyVertexEdgeCount(IUT, V2, 2);
+
+ // Verify Adjacent Vertex
+ Set expectV1 = new HashSet();
+ Set expectV2 = new HashSet();
+
+ expectV1.add(V2);
+ expectV2.add(V1);
+
+ verifyAdjVertices(IUT, V1, expectV1);
+ verifyAdjVertices(IUT, V2, expectV2);
+
+ }
+
+ /**
+ * Test the Cycle Graph.
+ */
+ public void testCycle()
+ throws Throwable
+ {
+ Graph IUT = makeCycle();
+
+ verifyGraph(IUT, 3, 3);
+
+ // Verify Edge from Vertex Count
+ verifyVertexEdgeCount(IUT, V1, 2);
+ verifyVertexEdgeCount(IUT, V2, 2);
+ verifyVertexEdgeCount(IUT, V3, 2);
+
+ // Verify Adjacent Vertex
+ Set expectV1 = new HashSet();
+ Set expectV2 = new HashSet();
+ Set expectV3 = new HashSet();
+
+ expectV1.add(V2);
+ expectV1.add(V3);
+ expectV2.add(V1);
+ expectV2.add(V3);
+ expectV3.add(V1);
+ expectV3.add(V2);
+
+ verifyAdjVertices(IUT, V1, expectV1);
+ verifyAdjVertices(IUT, V2, expectV2);
+ verifyAdjVertices(IUT, V3, expectV3);
+ }
+
+ /**
+ * Test the No Cycle Graph.
+ */
+ public void testNoCycle()
+ throws Throwable
+ {
+ Graph IUT = makeNoCycle();
+
+ verifyGraph(IUT, 3, 2);
+
+ // Verify Edge from Vertex Count
+ verifyVertexEdgeCount(IUT, V1, 1);
+ verifyVertexEdgeCount(IUT, V2, 2);
+ verifyVertexEdgeCount(IUT, V3, 1);
+
+ // Verify Adjacent Vertex
+ Set expectV1 = new HashSet();
+ Set expectV2 = new HashSet();
+ Set expectV3 = new HashSet();
+
+ expectV1.add(V2);
+ expectV2.add(V1);
+ expectV2.add(V3);
+ expectV3.add(V2);
+
+ verifyAdjVertices(IUT, V1, expectV1);
+ verifyAdjVertices(IUT, V2, expectV2);
+ verifyAdjVertices(IUT, V3, expectV3);
+ }
+
+ /**
+ * Test the Tree Graph.
+ */
+ public void testTree()
+ throws Throwable
+ {
+ Graph IUT = makeTree();
+
+ verifyGraph(IUT, 5, 4);
+
+ // Verify Edge from Vertex Count
+ verifyVertexEdgeCount(IUT, V1, 2);
+ verifyVertexEdgeCount(IUT, V2, 1);
+ verifyVertexEdgeCount(IUT, V3, 3);
+ verifyVertexEdgeCount(IUT, V4, 1);
+ verifyVertexEdgeCount(IUT, V5, 1);
+
+ // Verify Adjacent Vertex
+ Set expectV1 = new HashSet();
+ Set expectV2 = new HashSet();
+ Set expectV3 = new HashSet();
+ Set expectV4 = new HashSet();
+ Set expectV5 = new HashSet();
+
+ expectV1.add(V2);
+ expectV1.add(V3);
+ expectV2.add(V1);
+ expectV3.add(V1);
+ expectV3.add(V4);
+ expectV3.add(V5);
+ expectV4.add(V3);
+ expectV5.add(V3);
+
+ verifyAdjVertices(IUT, V1, expectV1);
+ verifyAdjVertices(IUT, V2, expectV2);
+ verifyAdjVertices(IUT, V3, expectV3);
+ verifyAdjVertices(IUT, V4, expectV4);
+ verifyAdjVertices(IUT, V5, expectV5);
+ }
+
+ /**
+ * Test the Disconnected Graph.
+ */
+ public void testDisconnected()
+ throws Throwable
+ {
+ Graph IUT = makeDisconnected();
+
+ verifyGraph(IUT, 4, 2);
+
+ // Verify Edge from Vertex Count
+ verifyVertexEdgeCount(IUT, V1, 1);
+ verifyVertexEdgeCount(IUT, V2, 1);
+ verifyVertexEdgeCount(IUT, V3, 1);
+ verifyVertexEdgeCount(IUT, V4, 1);
+
+ // Verify Adjacent Vertex
+ Set expectV1 = new HashSet();
+ Set expectV2 = new HashSet();
+ Set expectV3 = new HashSet();
+ Set expectV4 = new HashSet();
+
+ expectV1.add(V2);
+ expectV2.add(V1);
+ expectV3.add(V4);
+ expectV4.add(V3);
+
+ verifyAdjVertices(IUT, V1, expectV1);
+ verifyAdjVertices(IUT, V2, expectV2);
+ verifyAdjVertices(IUT, V3, expectV3);
+ verifyAdjVertices(IUT, V4, expectV4);
+ }
+
+
+ /**
+ * Description of the Method
+ */
+ public void verifyVertexEdgeCount(Graph IUT,
+ Vertex v,
+ int numEdge)
+ throws Throwable
+ {
+ assertEquals(v.toString() + " has wrong number of adjacent edges.",
+ IUT.getEdges(v).size(), numEdge);
+ }
+
+ /**
+ * Gets the adjVertices attribute of the UndirGraphTest object
+ */
+ private Set getAdjVertices(Graph IUT,
+ Vertex v)
+ {
+ Set RC = new HashSet();
+ Iterator edges = IUT.getEdges(v).iterator();
+
+ while (edges.hasNext())
+ {
+ Edge e = (Edge) edges.next();
+
+ Set verts = IUT.getVertices(e);
+ verts.remove(v);
+ RC.addAll(verts);
+ }
+
+ return RC;
+ }
+
+ /**
+ * Description of the Method
+ */
+ public void verifyAdjVertices(Graph IUT,
+ Vertex v,
+ Set expected)
+ throws Throwable
+ {
+ Set adjacent = getAdjVertices(IUT, v);
+ Iterator adjV = adjacent.iterator();
+
+ while (adjV.hasNext())
+ {
+ Vertex curr = (Vertex) adjV.next();
+
+ assertTrue(curr.toString() + " is not supposed to be " +
+ "next to " + v.toString(),
+ expected.contains(curr));
+ }
+
+ Iterator expect = expected.iterator();
+
+ while (expect.hasNext())
+ {
+ Vertex curr = (Vertex) expect.next();
+
+ assertTrue(curr.toString() + " is supposed to be next to " +
+ v.toString(),
+ adjacent.contains(curr));
+ }
+ }
+
+ /**
+ * Description of the Method
+ */
+ public void verifyGraph(Graph g, int numVertex, int numEdge)
+ throws Throwable
+ {
+ assertEquals("Incorrect Number of Vertices.",
+ g.getVertices().size(), numVertex);
+ assertEquals("Incorrect Number of Edges.",
+ g.getEdges().size(), numEdge);
+ }
+}
1.3 +1024 -1026jakarta-commons-sandbox/graph2/src/test/org/apache/commons/graph/GraphTest.java
Index: GraphTest.java
===================================================================
RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/test/org/apache/commons/graph/GraphTest.java,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- GraphTest.java 8 May 2002 18:24:47 -0000 1.2
+++ GraphTest.java 1 Jan 2003 02:14:38 -0000 1.3
@@ -1,1026 +1,1024 @@
-package org.apache.commons.graph;
-
-/* ====================================================================
- * The Apache Software License, Version 1.1
- *
- * Copyright (c) 2001 The Apache Software Foundation. All rights
- * reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, 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 "Apache" and "Apache Software Foundation" and
- * "Commons" 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",
- * "Commons", 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 (INCLUDING, 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/>.
- */
-/**
- * GraphTest This is a superclass of other tests to provide some utilities in
- * verifying graphs. This test will provide Undirected and Directed Graphs as
- * well. We will implement the following graphs. Undirected Graphs
- * ------------------- () No Vertex, No Edges @ One Vertex, No Edges @ @ Two
- * Vertices, No Edges @-@ Two Vertices, One edge /-\ @ @ Two Vertices, Two Edges
- * (Parallel Edges) \-/ @ / \ Three Vertices, Three Edges (Cycle) @---@ @--@--@
- * Three Vertices, Two Edges (No Cycle) @ / \ @ @ 5 Vertices, 4 Edges (Tree) / \
- * @ @ @-@ @-@ 4 Vertices, 2 Edges (Disconnected)
- */
-
-import java.util.Set;
-import java.util.Map;
-import java.util.HashSet;
-import java.util.HashMap;
-import java.util.Iterator;
-
-import junit.framework.*;
-
-import org.apache.commons.graph.domain.basic.*;
-import org.apache.commons.graph.exception.*;
-
-/**
- * Description of the Class
- */
-public class GraphTest extends TestCase
-{
- /**
- * Description of the Class
- */
- public class VertexImpl
- implements Vertex
- {
- private String name = null;
-
- /**
- * Constructor for the VertexImpl object
- *
- * @param name
- */
- public VertexImpl(String name)
- {
- this.name = name;
- }
-
- /**
- * Description of the Method
- */
- public String toString()
- {
- return name;
- }
- }
-
- /**
- * Description of the Class
- */
- public class EdgeImpl
- implements Edge
- {
- private Vertex start;
- private Vertex end;
-
- /**
- * Constructor for the EdgeImpl object
- *
- * @param start
- * @param end
- */
- public EdgeImpl(Vertex start,
- Vertex end)
- {
- this.start = start;
- this.end = end;
- }
-
- /**
- * Gets the otherVertex attribute of the EdgeImpl object
- */
- public Vertex getOtherVertex(Vertex v)
- {
- if (v == start)
- {
- return end;
- }
- if (v == end)
- {
- return start;
- }
- return null;
- }
-
- /**
- * Gets the vertices attribute of the EdgeImpl object
- */
- public Set getVertices()
- {
- Set RC = new HashSet();
- RC.add(start);
- RC.add(end);
- return RC;
- }
-
- /**
- * Gets the source attribute of the EdgeImpl object
- */
- public Vertex getSource()
- {
- return start;
- }
-
- /**
- * Gets the target attribute of the EdgeImpl object
- */
- public Vertex getTarget()
- {
- return end;
- }
-
- /**
- * Description of the Method
- */
- public String toString()
- {
- return start.toString() + " <-> " + end.toString();
- }
- }
-
- /**
- * Description of the Field
- */
- public Vertex V1 = new VertexImpl("V1");
- /**
- * Description of the Field
- */
- public Vertex V2 = new VertexImpl("V2");
- /**
- * Description of the Field
- */
- public Vertex V3 = new VertexImpl("V3");
- /**
- * Description of the Field
- */
- public Vertex V4 = new VertexImpl("V4");
- /**
- * Description of the Field
- */
- public Vertex V5 = new VertexImpl("V5");
-
- /**
- * Description of the Field
- */
- public EdgeImpl V1_V1 = new EdgeImpl(V1, V1);// For Self-Loops.
- /**
- * Description of the Field
- */
- public EdgeImpl V1_V2 = new EdgeImpl(V1, V2);
- /**
- * Description of the Field
- */
- public EdgeImpl V1_V2_ = new EdgeImpl(V1, V2);// For Parallel
- /**
- * Description of the Field
- */
- public EdgeImpl V1_V2__ = new EdgeImpl(V1, V2);// For Parallel #2
-
- public EdgeImpl V1_V2_V3 = new EdgeImpl(V1, V2); // HyperEdge. . .
-
- /**
- * Description of the Field
- */
- public EdgeImpl V1_V3 = new EdgeImpl(V1, V3);
- /**
- * Description of the Field
- */
- public EdgeImpl V1_V4 = new EdgeImpl(V1, V4);
- /**
- * Description of the Field
- */
- public EdgeImpl V1_V5 = new EdgeImpl(V1, V5);
-
- /**
- * Description of the Field
- */
- public EdgeImpl V2_V1 = new EdgeImpl(V2, V1);
- /**
- * Description of the Field
- */
- public EdgeImpl V2_V3 = new EdgeImpl(V2, V3);
- /**
- * Description of the Field
- */
- public EdgeImpl V2_V4 = new EdgeImpl(V2, V4);
- /**
- * Description of the Field
- */
- public EdgeImpl V2_V5 = new EdgeImpl(V2, V5);
-
- /**
- * Description of the Field
- */
- public EdgeImpl V3_V1 = new EdgeImpl(V3, V1);
- /**
- * Description of the Field
- */
- public EdgeImpl V3_V2 = new EdgeImpl(V3, V2);
- /**
- * Description of the Field
- */
- public EdgeImpl V3_V4 = new EdgeImpl(V3, V4);
- /**
- * Description of the Field
- */
- public EdgeImpl V3_V5 = new EdgeImpl(V3, V5);
-
- /**
- * Description of the Field
- */
- public EdgeImpl V4_V1 = new EdgeImpl(V4, V1);
- /**
- * Description of the Field
- */
- public EdgeImpl V4_V2 = new EdgeImpl(V4, V2);
- /**
- * Description of the Field
- */
- public EdgeImpl V4_V3 = new EdgeImpl(V4, V3);
- /**
- * Description of the Field
- */
- public EdgeImpl V4_V5 = new EdgeImpl(V4, V5);
-
- /**
- * Description of the Field
- */
- public EdgeImpl V5_V1 = new EdgeImpl(V5, V1);
- /**
- * Description of the Field
- */
- public EdgeImpl V5_V2 = new EdgeImpl(V5, V2);
- /**
- * Description of the Field
- */
- public EdgeImpl V5_V3 = new EdgeImpl(V5, V3);
- /**
- * Description of the Field
- */
- public EdgeImpl V5_V4 = new EdgeImpl(V5, V4);
-
- /**
- * Constructor for the GraphTest object
- *
- * @param name
- */
- public GraphTest(String name)
- {
- super(name);
- this.testName = name;
- }
-
- private String testName = null;
-
- /**
- * Return this graph: ()
- */
- public UndirectedGraph makeNullGraph()
- throws GraphException
- {
- return new UndirectedGraphImpl();
- }
-
- /**
- * Description of the Method
- */
- public DirectedGraph makeDirNullGraph()
- throws GraphException
- {
- return new DirectedGraphImpl();
- }
-
- /**
- * Return this graph: v1
- */
- public UndirectedGraph makeSingleVertex()
- throws GraphException
- {
- UndirectedGraphImpl RC = new UndirectedGraphImpl();
- RC.addVertex(V1);
- return RC;
- }
-
- /**
- * Description of the Method
- */
- public DirectedGraph makeDirSingleVertex()
- throws GraphException
- {
- DirectedGraphImpl RC = new DirectedGraphImpl();
- RC.addVertex(V1);
- return RC;
- }
-
- /**
- * /--\ v1 | ^--/
- */
- public DirectedGraph makeSelfLoop()
- throws GraphException
- {
- DirectedGraphImpl RC = new DirectedGraphImpl();
- RC.addVertex(V1);
- RC.addEdge(V1_V1, V1, V1);
- return RC;
- }
-
- /**
- * v1 v2 Two Vertices, No Edges
- */
- public UndirectedGraph makeDoubleVertex()
- throws GraphException
- {
- UndirectedGraphImpl RC = new UndirectedGraphImpl();
- RC.addVertex(V1);
- RC.addVertex(V2);
- return RC;
- }
-
- /**
- * Description of the Method
- */
- public DirectedGraph makeDirDoubleVertex()
- throws GraphException
- {
- DirectedGraphImpl RC = new DirectedGraphImpl();
- RC.addVertex(V1);
- RC.addVertex(V2);
- return RC;
- }
-
- /**
- * v1-v2 Two Vertices, One edge
- */
- public UndirectedGraph makeSingleEdge()
- throws GraphException
- {
- UndirectedGraphImpl RC = new UndirectedGraphImpl();
-
- RC.addVertex(V1);
- RC.addVertex(V2);
-
- RC.addEdge(V1_V2, V1_V2.getVertices());
-
- return RC;
- }
-
- /**
- * v1 -> v2 Directed Edge
- */
- public DirectedGraph makeDirectedEdge()
- throws GraphException
- {
- DirectedGraphImpl RC = new DirectedGraphImpl();
-
- RC.addVertex(V1);
- RC.addVertex(V2);
-
- RC.addEdge(V1_V2,
- V1, V2);
-
- return RC;
- }
-
- /**
- * /-\ v1 v2 Two Vertices, Two Edges (Parallel Edges) \-/
- */
- public UndirectedGraph makeParallelEdges()
- throws GraphException
- {
- UndirectedGraphImpl RC = new UndirectedGraphImpl();
-
- RC.addVertex(V1);
- RC.addVertex(V2);
-
- RC.addEdge(V1_V2, V1_V2.getVertices());
- RC.addEdge(V1_V2_, V1_V2_.getVertices());
-
- return RC;
- }
-
- /**
- * /--->\ @ @ \--->/
- */
- public DirectedGraph makeDirParallelEdges()
- throws GraphException
- {
- DirectedGraphImpl RC = new DirectedGraphImpl();
-
- RC.addVertex(V1);
- RC.addVertex(V2);
-
- RC.addEdge(V1_V2, V1, V2);
- // Second edge must be distinct. . .
- RC.addEdge(V1_V2_, V1, V2);
-
- return RC;
- }
-
- /**
- * v1 / \ Three Vertices, Three Edges (Cycle) v2---v3
- */
- public UndirectedGraph makeCycle()
- throws GraphException
- {
- UndirectedGraphImpl RC = new UndirectedGraphImpl();
-
- RC.addVertex(V1);
- RC.addVertex(V2);
- RC.addVertex(V3);
-
- RC.addEdge(V1_V2, V1_V2.getVertices());
- RC.addEdge(V2_V3, V2_V3.getVertices());
- RC.addEdge(V3_V1, V3_V1.getVertices());
-
- return RC;
- }
-
- /**
- * /--->\ v1 v2 \<---/
- */
- public DirectedGraph makeTwoCycle()
- throws GraphException
- {
- DirectedGraphImpl RC = new DirectedGraphImpl();
-
- RC.addVertex(V1);
- RC.addVertex(V2);
-
- RC.addEdge(V1_V2, V1, V2);
- RC.addEdge(V2_V1, V2, V1);
-
- return RC;
- }
-
- /**
- * v1 / ^ v \ v2 ---> v3
- */
- public DirectedGraph makeDirectedCycle()
- throws GraphException
- {
- DirectedGraphImpl RC = new DirectedGraphImpl();
-
- RC.addVertex(V1);
- RC.addVertex(V2);
- RC.addVertex(V3);
-
- RC.addEdge(V1_V2, V1, V2);
- RC.addEdge(V2_V3, V2, V3);
- RC.addEdge(V3_V1, V3, V1);
-
- return RC;
- }
-
- /**
- * v1 / ^ v \ v2 ---> v3
- */
- public DirectedGraph makeDirected4Cycle()
- throws GraphException
- {
- DirectedGraphImpl RC = new DirectedGraphImpl();
-
- RC.addVertex(V1);
- RC.addVertex(V2);
- RC.addVertex(V3);
- RC.addVertex(V4);
-
- RC.addEdge(V1_V2, V1, V2);
- RC.addEdge(V2_V3, V2, V3);
- RC.addEdge(V3_V4, V3, V4);
- RC.addEdge(V4_V1, V4, V1);
-
- return RC;
- }
-
- /**
- * v1--v2--v3 Three Vertices, Two Edges (No Cycle)
- */
- public UndirectedGraph makeNoCycle()
- throws GraphException
- {
- UndirectedGraphImpl RC = new UndirectedGraphImpl();
-
- RC.addVertex(V1);
- RC.addVertex(V2);
- RC.addVertex(V3);
-
- RC.addEdge(V1_V2, V1_V2.getVertices());
- RC.addEdge(V2_V3, V2_V3.getVertices());
-
- return RC;
- }
-
- /**
- * v1 --> v2 --> v3
- */
- public DirectedGraph makePipe()
- throws GraphException
- {
- DirectedGraphImpl RC = new DirectedGraphImpl();
-
- RC.addVertex(V1);
- RC.addVertex(V2);
- RC.addVertex(V3);
-
- RC.addEdge(V1_V2, V1, V2);
- RC.addEdge(V2_V3, V2, V3);
-
- return RC;
- }
-
- /**
- * v1 / \ v v v2 v3 \ / v v v4
- */
- public DirectedGraph makeDiamond()
- throws GraphException
- {
- DirectedGraphImpl RC = new DirectedGraphImpl();
-
- RC.addVertex(V1);
- RC.addVertex(V2);
- RC.addVertex(V3);
- RC.addVertex(V4);
-
- RC.addEdge(V1_V2, V1, V2);
- RC.addEdge(V1_V3, V1, V3);
- RC.addEdge(V2_V4, V2, V4);
- RC.addEdge(V3_V4, V3, V4);
-
- return RC;
- }
-
- /**
- * v1 / \ v v v2 v3 ^ ^ \ / v4
- */
- public DirectedGraph makePipelessCycle()
- throws GraphException
- {
- DirectedGraphImpl RC = new DirectedGraphImpl();
-
- RC.addVertex(V1);
- RC.addVertex(V2);
- RC.addVertex(V3);
- RC.addVertex(V4);
-
- RC.addEdge(V1_V2, V1, V2);
- RC.addEdge(V1_V3, V1, V3);
- RC.addEdge(V4_V2, V4, V2);
- RC.addEdge(V4_V3, V4, V3);
-
- return RC;
- }
-
- /**
- * v1 / \ v2 v3 5 Vertices, 4 Edges (Tree) / \ v4 v5
- */
- public UndirectedGraph makeTree()
- throws GraphException
- {
- UndirectedGraphImpl RC = new UndirectedGraphImpl();
-
- RC.addVertex(V1);
- RC.addVertex(V2);
- RC.addVertex(V3);
- RC.addVertex(V4);
- RC.addVertex(V5);
-
- RC.addEdge(V1_V2, V1_V2.getVertices());
- RC.addEdge(V1_V3, V1_V3.getVertices());
- RC.addEdge(V3_V4, V3_V4.getVertices());
- RC.addEdge(V3_V5, V3_V5.getVertices());
-
- return RC;
- }
-
- /**
- * Description of the Method
- */
- public DirectedGraph makeParentTree()
- throws GraphException
- {
- DirectedGraphImpl RC = new DirectedGraphImpl();
-
- RC.addVertex(V1);
- RC.addVertex(V2);
- RC.addVertex(V3);
- RC.addVertex(V4);
- RC.addVertex(V5);
-
- RC.addEdge(V2_V1, V2, V1);
- RC.addEdge(V3_V1, V3, V1);
- RC.addEdge(V4_V3, V4, V3);
- RC.addEdge(V5_V3, V5, V3);
-
- return RC;
- }
-
- /**
- * Description of the Method
- */
- public DirectedGraph makeChildTree()
- throws GraphException
- {
- DirectedGraphImpl RC = new DirectedGraphImpl();
-
- RC.addVertex(V1);
- RC.addVertex(V2);
- RC.addVertex(V3);
- RC.addVertex(V4);
- RC.addVertex(V5);
-
- RC.addEdge(V1_V2, V1, V2);
- RC.addEdge(V1_V3, V1, V3);
- RC.addEdge(V3_V4, V3, V4);
- RC.addEdge(V3_V5, V3, V5);
-
- return RC;
- }
-
- /**
- * v1-v2 v3-v4 4 Vertices, 2 Edges (Disconnected)
- */
- public UndirectedGraph makeDisconnected()
- throws GraphException
- {
- UndirectedGraphImpl RC = new UndirectedGraphImpl();
-
- RC.addVertex(V1);
- RC.addVertex(V2);
- RC.addVertex(V3);
- RC.addVertex(V4);
-
- RC.addEdge(V1_V2, V1_V2.getVertices());
- RC.addEdge(V3_V4, V3_V4.getVertices());
-
- return RC;
- }
-
- /**
- * makeHyperEdgeGraph
- *
- * This makes a graph which has more than one Vertex on an Edge.
- *
- * V1
- * |
- * *
- * / \
- * V2 V3
- *
- */
- public Graph makeHyperGraph() {
- UndirectedGraphImpl RC = new UndirectedGraphImpl();
-
- RC.addVertex( V1 );
- RC.addVertex( V2 );
- RC.addVertex( V3 );
-
- RC.addEdge( V1_V2_V3 );
- RC.connect( V1_V2_V3, V1 );
- RC.connect( V1_V2_V3, V2 );
- RC.connect( V1_V2_V3, V3 );
-
- return RC;
- }
-
-
- /**
- *
- * V1 --> V2 --> V3 <--> V4
- */
- public DirectedGraph makeCycleNoReturn()
- throws GraphException
- {
- DirectedGraphImpl RC = new DirectedGraphImpl();
-
- RC.addVertex(V1);
- RC.addVertex(V2);
- RC.addVertex(V3);
- RC.addVertex(V4);
-
- RC.addEdge(V1_V2, V1, V2);
- RC.addEdge(V2_V3, V2, V3);
- RC.addEdge(V3_V4, V3, V4);
- RC.addEdge(V4_V3, V4, V3);
-
- return RC;
- }
-
- /**
- * A unit test for JUnit
- */
- public void testNothing()
- throws Throwable { }
-
- /**
- * Description of the Method
- */
- public void verifyVertexEdgeCount(Graph IUT,
- Vertex v,
- int numEdge)
- throws Throwable
- {
- assertEquals(v.toString() + " has wrong number of adjacent edges.",
- IUT.getEdges(v).size(), numEdge);
- }
-
- /**
- * Gets the outboundVertices attribute of the GraphTest object
- */
- private Set getOutboundVertices(DirectedGraph IUT,
- Vertex v)
- {
- Set RC = new HashSet();
- Iterator edges = IUT.getOutbound(v).iterator();
-
- while (edges.hasNext())
- {
- Edge e = (Edge) edges.next();
- RC.add(IUT.getTarget(e));
- }
-
- return RC;
- }
-
- /**
- * Gets the inboundVertices attribute of the GraphTest object
- */
- private Set getInboundVertices(DirectedGraph IUT,
- Vertex v)
- {
- Set RC = new HashSet();
- Iterator edges = IUT.getInbound(v).iterator();
-
- while (edges.hasNext())
- {
- Edge e = (Edge) edges.next();
- RC.add(IUT.getSource(e));
- }
-
- return RC;
- }
-
-
- /**
- * Gets the adjVertices attribute of the GraphTest object
- */
- private Set getAdjVertices(Graph IUT,
- Vertex v)
- {
- Set RC = new HashSet();
- Iterator edges = IUT.getEdges(v).iterator();
-
- while (edges.hasNext())
- {
- Edge e = (Edge) edges.next();
-
- Set verts = IUT.getVertices(e);
- RC.addAll(verts);
- }
-
- return RC;
- }
-
- /**
- * Description of the Method
- */
- public Set makeSet()
- {
- return new HashSet();
- }
-
-
- /**
- * Description of the Method
- */
- public Set makeSet(Object v)
- {
- Set RC = new HashSet();
- RC.add(v);
- return RC;
- }
-
- /**
- * Description of the Method
- */
- public Set makeSet(Object v1,
- Object v2)
- {
- Set RC = makeSet(v1);
- RC.add(v2);
- return RC;
- }
-
- /**
- * Description of the Method
- */
- public Set makeSet(Set s1,
- Set s2)
- {
- Set RC = new HashSet();
- RC.addAll(s1);
- RC.addAll(s2);
- return RC;
- }
-
- /**
- * Description of the Method
- */
- public Set makeSet(Object v1,
- Object v2,
- Object v3)
- {
- return makeSet(makeSet(v1, v2),
- makeSet(v3));
- }
-
- /**
- * Description of the Method
- */
- public Set makeSet(Object v1,
- Object v2,
- Object v3,
- Object v4)
- {
- return makeSet(makeSet(v1, v2),
- makeSet(v3, v4));
- }
-
- /**
- * Description of the Method
- */
- public void verifyAdjVertices(DirectedGraph IUT,
- Vertex v,
- Set inExpect,
- Set outExpect)
- {
- Set inbound = getInboundVertices(IUT, v);
- Set outbound = getOutboundVertices(IUT, v);
-
- Iterator verts;
-
- // inbound is a subset of inExpect
- verts = inbound.iterator();
-
- while (verts.hasNext())
- {
- Vertex curr = (Vertex) verts.next();
-
- assertTrue(curr.toString() + " is not supposed to be " +
- "next to " + v.toString(),
- inExpect.contains(curr));
- }
-
- // inExpect is a subset of inbound
- verts = inExpect.iterator();
-
- while (verts.hasNext())
- {
- Vertex curr = (Vertex) verts.next();
- assertTrue(curr.toString() + " is supposed to be next to " +
- v.toString(),
- inbound.contains(curr));
- }
-
- // outbound is a subset of outExpect
- verts = outbound.iterator();
-
- while (verts.hasNext())
- {
- Vertex curr = (Vertex) verts.next();
-
- assertTrue(curr.toString() + " is not supposed to be " +
- "next to " + v.toString(),
- outExpect.contains(curr));
- }
-
- // outExpect is a subset of outbound
- verts = outExpect.iterator();
-
- while (verts.hasNext())
- {
- Vertex curr = (Vertex) verts.next();
- assertTrue(curr.toString() + " is supposed to be next to " +
- v.toString(),
- outbound.contains(curr));
- }
-
- }
-
- /**
- * Description of the Method
- */
- public void verifyAdjVertices(Graph IUT,
- Vertex v,
- Set expected)
- throws Throwable
- {
- Set adjacent = getAdjVertices(IUT, v);
- Iterator adjV = adjacent.iterator();
-
- while (adjV.hasNext())
- {
- Vertex curr = (Vertex) adjV.next();
- assertTrue(curr.toString() + " is not supposed to be " +
- "next to " + v.toString(),
- expected.contains(curr));
- }
-
- Iterator expect = expected.iterator();
-
- while (expect.hasNext())
- {
- Vertex curr = (Vertex) expect.next();
- assertTrue(curr.toString() + " is supposed to be next to " +
- v.toString(),
- adjacent.contains(curr));
- }
- }
-
- /**
- * Description of the Method
- */
- public void verifyGraph(Graph g, int numVertex, int numEdge)
- throws Throwable
- {
- assertEquals("Incorrect Number of Vertices.",
- numVertex, g.getVertices().size());
- assertEquals("Incorrect Number of Edges.",
- numEdge, g.getEdges().size());
- }
-
- /**
- * Description of the Method
- */
- public void printGraph(Throwable t,
- DirectedGraph IUT)
- {
- System.err.println(testName + ": " + t.toString());
- System.err.println("VERTICES: " + IUT.getVertices());
- System.err.println("EDGES: " + IUT.getEdges());
-
- Iterator verts = IUT.getVertices().iterator();
- while (verts.hasNext())
- {
- Vertex vert = (Vertex) verts.next();
- System.err.println("[ " + vert + " ]");
-
- Iterator inbounds = IUT.getInbound(vert).iterator();
- while (inbounds.hasNext())
- {
- Edge inbound = (Edge) inbounds.next();
- System.err.println("\tI [" + inbound + "]");
- }
-
- Iterator outbounds = IUT.getOutbound(vert).iterator();
- while (outbounds.hasNext())
- {
- Edge outbound = (Edge) outbounds.next();
- System.err.println("\tO [" + outbound + "]");
- }
- }
- }
-
-}
+package org.apache.commons.graph;
+
+/* ====================================================================
+ * The Apache Software License, Version 1.1
+ *
+ * Copyright (c) 2001 The Apache Software Foundation. All rights
+ * reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, 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 "Apache" and "Apache Software Foundation" and
+ * "Commons" 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",
+ * "Commons", 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 (INCLUDING, 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/>.
+ */
+/**
+ * GraphTest This is a superclass of other tests to provide some utilities in
+ * verifying graphs. This test will provide Undirected and Directed Graphs as
+ * well. We will implement the following graphs. Undirected Graphs
+ * ------------------- () No Vertex, No Edges @ One Vertex, No Edges @ @ Two
+ * Vertices, No Edges @-@ Two Vertices, One edge /-\ @ @ Two Vertices, Two Edges
+ * (Parallel Edges) \-/ @ / \ Three Vertices, Three Edges (Cycle) @---@ @--@--@
+ * Three Vertices, Two Edges (No Cycle) @ / \ @ @ 5 Vertices, 4 Edges (Tree) / \
+ * @ @ @-@ @-@ 4 Vertices, 2 Edges (Disconnected)
+ */
+
+import java.util.Set;
+import java.util.HashSet;
+import java.util.Iterator;
+
+import junit.framework.*;
+
+import org.apache.commons.graph.domain.basic.*;
+import org.apache.commons.graph.exception.*;
+
+/**
+ * Description of the Class
+ */
+public class GraphTest extends TestCase
+{
+ /**
+ * Description of the Class
+ */
+ public class VertexImpl
+ implements Vertex
+ {
+ private String name = null;
+
+ /**
+ * Constructor for the VertexImpl object
+ *
+ * @param name
+ */
+ public VertexImpl(String name)
+ {
+ this.name = name;
+ }
+
+ /**
+ * Description of the Method
+ */
+ public String toString()
+ {
+ return name;
+ }
+ }
+
+ /**
+ * Description of the Class
+ */
+ public class EdgeImpl
+ implements Edge
+ {
+ private Vertex start;
+ private Vertex end;
+
+ /**
+ * Constructor for the EdgeImpl object
+ *
+ * @param start
+ * @param end
+ */
+ public EdgeImpl(Vertex start,
+ Vertex end)
+ {
+ this.start = start;
+ this.end = end;
+ }
+
+ /**
+ * Gets the otherVertex attribute of the EdgeImpl object
+ */
+ public Vertex getOtherVertex(Vertex v)
+ {
+ if (v == start)
+ {
+ return end;
+ }
+ if (v == end)
+ {
+ return start;
+ }
+ return null;
+ }
+
+ /**
+ * Gets the vertices attribute of the EdgeImpl object
+ */
+ public Set getVertices()
+ {
+ Set RC = new HashSet();
+ RC.add(start);
+ RC.add(end);
+ return RC;
+ }
+
+ /**
+ * Gets the source attribute of the EdgeImpl object
+ */
+ public Vertex getSource()
+ {
+ return start;
+ }
+
+ /**
+ * Gets the target attribute of the EdgeImpl object
+ */
+ public Vertex getTarget()
+ {
+ return end;
+ }
+
+ /**
+ * Description of the Method
+ */
+ public String toString()
+ {
+ return start.toString() + " <-> " + end.toString();
+ }
+ }
+
+ /**
+ * Description of the Field
+ */
+ public Vertex V1 = new VertexImpl("V1");
+ /**
+ * Description of the Field
+ */
+ public Vertex V2 = new VertexImpl("V2");
+ /**
+ * Description of the Field
+ */
+ public Vertex V3 = new VertexImpl("V3");
+ /**
+ * Description of the Field
+ */
+ public Vertex V4 = new VertexImpl("V4");
+ /**
+ * Description of the Field
+ */
+ public Vertex V5 = new VertexImpl("V5");
+
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V1_V1 = new EdgeImpl(V1, V1);// For Self-Loops.
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V1_V2 = new EdgeImpl(V1, V2);
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V1_V2_ = new EdgeImpl(V1, V2);// For Parallel
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V1_V2__ = new EdgeImpl(V1, V2);// For Parallel #2
+
+ public EdgeImpl V1_V2_V3 = new EdgeImpl(V1, V2); // HyperEdge. . .
+
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V1_V3 = new EdgeImpl(V1, V3);
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V1_V4 = new EdgeImpl(V1, V4);
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V1_V5 = new EdgeImpl(V1, V5);
+
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V2_V1 = new EdgeImpl(V2, V1);
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V2_V3 = new EdgeImpl(V2, V3);
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V2_V4 = new EdgeImpl(V2, V4);
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V2_V5 = new EdgeImpl(V2, V5);
+
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V3_V1 = new EdgeImpl(V3, V1);
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V3_V2 = new EdgeImpl(V3, V2);
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V3_V4 = new EdgeImpl(V3, V4);
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V3_V5 = new EdgeImpl(V3, V5);
+
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V4_V1 = new EdgeImpl(V4, V1);
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V4_V2 = new EdgeImpl(V4, V2);
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V4_V3 = new EdgeImpl(V4, V3);
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V4_V5 = new EdgeImpl(V4, V5);
+
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V5_V1 = new EdgeImpl(V5, V1);
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V5_V2 = new EdgeImpl(V5, V2);
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V5_V3 = new EdgeImpl(V5, V3);
+ /**
+ * Description of the Field
+ */
+ public EdgeImpl V5_V4 = new EdgeImpl(V5, V4);
+
+ /**
+ * Constructor for the GraphTest object
+ *
+ * @param name
+ */
+ public GraphTest(String name)
+ {
+ super(name);
+ this.testName = name;
+ }
+
+ private String testName = null;
+
+ /**
+ * Return this graph: ()
+ */
+ public UndirectedGraph makeNullGraph()
+ throws GraphException
+ {
+ return new UndirectedGraphImpl();
+ }
+
+ /**
+ * Description of the Method
+ */
+ public DirectedGraph makeDirNullGraph()
+ throws GraphException
+ {
+ return new DirectedGraphImpl();
+ }
+
+ /**
+ * Return this graph: v1
+ */
+ public UndirectedGraph makeSingleVertex()
+ throws GraphException
+ {
+ UndirectedGraphImpl RC = new UndirectedGraphImpl();
+ RC.addVertex(V1);
+ return RC;
+ }
+
+ /**
+ * Description of the Method
+ */
+ public DirectedGraph makeDirSingleVertex()
+ throws GraphException
+ {
+ DirectedGraphImpl RC = new DirectedGraphImpl();
+ RC.addVertex(V1);
+ return RC;
+ }
+
+ /**
+ * /--\ v1 | ^--/
+ */
+ public DirectedGraph makeSelfLoop()
+ throws GraphException
+ {
+ DirectedGraphImpl RC = new DirectedGraphImpl();
+ RC.addVertex(V1);
+ RC.addEdge(V1_V1, V1, V1);
+ return RC;
+ }
+
+ /**
+ * v1 v2 Two Vertices, No Edges
+ */
+ public UndirectedGraph makeDoubleVertex()
+ throws GraphException
+ {
+ UndirectedGraphImpl RC = new UndirectedGraphImpl();
+ RC.addVertex(V1);
+ RC.addVertex(V2);
+ return RC;
+ }
+
+ /**
+ * Description of the Method
+ */
+ public DirectedGraph makeDirDoubleVertex()
+ throws GraphException
+ {
+ DirectedGraphImpl RC = new DirectedGraphImpl();
+ RC.addVertex(V1);
+ RC.addVertex(V2);
+ return RC;
+ }
+
+ /**
+ * v1-v2 Two Vertices, One edge
+ */
+ public UndirectedGraph makeSingleEdge()
+ throws GraphException
+ {
+ UndirectedGraphImpl RC = new UndirectedGraphImpl();
+
+ RC.addVertex(V1);
+ RC.addVertex(V2);
+
+ RC.addEdge(V1_V2, V1_V2.getVertices());
+
+ return RC;
+ }
+
+ /**
+ * v1 -> v2 Directed Edge
+ */
+ public DirectedGraph makeDirectedEdge()
+ throws GraphException
+ {
+ DirectedGraphImpl RC = new DirectedGraphImpl();
+
+ RC.addVertex(V1);
+ RC.addVertex(V2);
+
+ RC.addEdge(V1_V2,
+ V1, V2);
+
+ return RC;
+ }
+
+ /**
+ * /-\ v1 v2 Two Vertices, Two Edges (Parallel Edges) \-/
+ */
+ public UndirectedGraph makeParallelEdges()
+ throws GraphException
+ {
+ UndirectedGraphImpl RC = new UndirectedGraphImpl();
+
+ RC.addVertex(V1);
+ RC.addVertex(V2);
+
+ RC.addEdge(V1_V2, V1_V2.getVertices());
+ RC.addEdge(V1_V2_, V1_V2_.getVertices());
+
+ return RC;
+ }
+
+ /**
+ * /--->\ @ @ \--->/
+ */
+ public DirectedGraph makeDirParallelEdges()
+ throws GraphException
+ {
+ DirectedGraphImpl RC = new DirectedGraphImpl();
+
+ RC.addVertex(V1);
+ RC.addVertex(V2);
+
+ RC.addEdge(V1_V2, V1, V2);
+ // Second edge must be distinct. . .
+ RC.addEdge(V1_V2_, V1, V2);
+
+ return RC;
+ }
+
+ /**
+ * v1 / \ Three Vertices, Three Edges (Cycle) v2---v3
+ */
+ public UndirectedGraph makeCycle()
+ throws GraphException
+ {
+ UndirectedGraphImpl RC = new UndirectedGraphImpl();
+
+ RC.addVertex(V1);
+ RC.addVertex(V2);
+ RC.addVertex(V3);
+
+ RC.addEdge(V1_V2, V1_V2.getVertices());
+ RC.addEdge(V2_V3, V2_V3.getVertices());
+ RC.addEdge(V3_V1, V3_V1.getVertices());
+
+ return RC;
+ }
+
+ /**
+ * /--->\ v1 v2 \<---/
+ */
+ public DirectedGraph makeTwoCycle()
+ throws GraphException
+ {
+ DirectedGraphImpl RC = new DirectedGraphImpl();
+
+ RC.addVertex(V1);
+ RC.addVertex(V2);
+
+ RC.addEdge(V1_V2, V1, V2);
+ RC.addEdge(V2_V1, V2, V1);
+
+ return RC;
+ }
+
+ /**
+ * v1 / ^ v \ v2 ---> v3
+ */
+ public DirectedGraph makeDirectedCycle()
+ throws GraphException
+ {
+ DirectedGraphImpl RC = new DirectedGraphImpl();
+
+ RC.addVertex(V1);
+ RC.addVertex(V2);
+ RC.addVertex(V3);
+
+ RC.addEdge(V1_V2, V1, V2);
+ RC.addEdge(V2_V3, V2, V3);
+ RC.addEdge(V3_V1, V3, V1);
+
+ return RC;
+ }
+
+ /**
+ * v1 / ^ v \ v2 ---> v3
+ */
+ public DirectedGraph makeDirected4Cycle()
+ throws GraphException
+ {
+ DirectedGraphImpl RC = new DirectedGraphImpl();
+
+ RC.addVertex(V1);
+ RC.addVertex(V2);
+ RC.addVertex(V3);
+ RC.addVertex(V4);
+
+ RC.addEdge(V1_V2, V1, V2);
+ RC.addEdge(V2_V3, V2, V3);
+ RC.addEdge(V3_V4, V3, V4);
+ RC.addEdge(V4_V1, V4, V1);
+
+ return RC;
+ }
+
+ /**
+ * v1--v2--v3 Three Vertices, Two Edges (No Cycle)
+ */
+ public UndirectedGraph makeNoCycle()
+ throws GraphException
+ {
+ UndirectedGraphImpl RC = new UndirectedGraphImpl();
+
+ RC.addVertex(V1);
+ RC.addVertex(V2);
+ RC.addVertex(V3);
+
+ RC.addEdge(V1_V2, V1_V2.getVertices());
+ RC.addEdge(V2_V3, V2_V3.getVertices());
+
+ return RC;
+ }
+
+ /**
+ * v1 --> v2 --> v3
+ */
+ public DirectedGraph makePipe()
+ throws GraphException
+ {
+ DirectedGraphImpl RC = new DirectedGraphImpl();
+
+ RC.addVertex(V1);
+ RC.addVertex(V2);
+ RC.addVertex(V3);
+
+ RC.addEdge(V1_V2, V1, V2);
+ RC.addEdge(V2_V3, V2, V3);
+
+ return RC;
+ }
+
+ /**
+ * v1 / \ v v v2 v3 \ / v v v4
+ */
+ public DirectedGraph makeDiamond()
+ throws GraphException
+ {
+ DirectedGraphImpl RC = new DirectedGraphImpl();
+
+ RC.addVertex(V1);
+ RC.addVertex(V2);
+ RC.addVertex(V3);
+ RC.addVertex(V4);
+
+ RC.addEdge(V1_V2, V1, V2);
+ RC.addEdge(V1_V3, V1, V3);
+ RC.addEdge(V2_V4, V2, V4);
+ RC.addEdge(V3_V4, V3, V4);
+
+ return RC;
+ }
+
+ /**
+ * v1 / \ v v v2 v3 ^ ^ \ / v4
+ */
+ public DirectedGraph makePipelessCycle()
+ throws GraphException
+ {
+ DirectedGraphImpl RC = new DirectedGraphImpl();
+
+ RC.addVertex(V1);
+ RC.addVertex(V2);
+ RC.addVertex(V3);
+ RC.addVertex(V4);
+
+ RC.addEdge(V1_V2, V1, V2);
+ RC.addEdge(V1_V3, V1, V3);
+ RC.addEdge(V4_V2, V4, V2);
+ RC.addEdge(V4_V3, V4, V3);
+
+ return RC;
+ }
+
+ /**
+ * v1 / \ v2 v3 5 Vertices, 4 Edges (Tree) / \ v4 v5
+ */
+ public UndirectedGraph makeTree()
+ throws GraphException
+ {
+ UndirectedGraphImpl RC = new UndirectedGraphImpl();
+
+ RC.addVertex(V1);
+ RC.addVertex(V2);
+ RC.addVertex(V3);
+ RC.addVertex(V4);
+ RC.addVertex(V5);
+
+ RC.addEdge(V1_V2, V1_V2.getVertices());
+ RC.addEdge(V1_V3, V1_V3.getVertices());
+ RC.addEdge(V3_V4, V3_V4.getVertices());
+ RC.addEdge(V3_V5, V3_V5.getVertices());
+
+ return RC;
+ }
+
+ /**
+ * Description of the Method
+ */
+ public DirectedGraph makeParentTree()
+ throws GraphException
+ {
+ DirectedGraphImpl RC = new DirectedGraphImpl();
+
+ RC.addVertex(V1);
+ RC.addVertex(V2);
+ RC.addVertex(V3);
+ RC.addVertex(V4);
+ RC.addVertex(V5);
+
+ RC.addEdge(V2_V1, V2, V1);
+ RC.addEdge(V3_V1, V3, V1);
+ RC.addEdge(V4_V3, V4, V3);
+ RC.addEdge(V5_V3, V5, V3);
+
+ return RC;
+ }
+
+ /**
+ * Description of the Method
+ */
+ public DirectedGraph makeChildTree()
+ throws GraphException
+ {
+ DirectedGraphImpl RC = new DirectedGraphImpl();
+
+ RC.addVertex(V1);
+ RC.addVertex(V2);
+ RC.addVertex(V3);
+ RC.addVertex(V4);
+ RC.addVertex(V5);
+
+ RC.addEdge(V1_V2, V1, V2);
+ RC.addEdge(V1_V3, V1, V3);
+ RC.addEdge(V3_V4, V3, V4);
+ RC.addEdge(V3_V5, V3, V5);
+
+ return RC;
+ }
+
+ /**
+ * v1-v2 v3-v4 4 Vertices, 2 Edges (Disconnected)
+ */
+ public UndirectedGraph makeDisconnected()
+ throws GraphException
+ {
+ UndirectedGraphImpl RC = new UndirectedGraphImpl();
+
+ RC.addVertex(V1);
+ RC.addVertex(V2);
+ RC.addVertex(V3);
+ RC.addVertex(V4);
+
+ RC.addEdge(V1_V2, V1_V2.getVertices());
+ RC.addEdge(V3_V4, V3_V4.getVertices());
+
+ return RC;
+ }
+
+ /**
+ * makeHyperEdgeGraph
+ *
+ * This makes a graph which has more than one Vertex on an Edge.
+ *
+ * V1
+ * |
+ * *
+ * / \
+ * V2 V3
+ *
+ */
+ public Graph makeHyperGraph() {
+ UndirectedGraphImpl RC = new UndirectedGraphImpl();
+
+ RC.addVertex( V1 );
+ RC.addVertex( V2 );
+ RC.addVertex( V3 );
+
+ RC.addEdge( V1_V2_V3 );
+ RC.connect( V1_V2_V3, V1 );
+ RC.connect( V1_V2_V3, V2 );
+ RC.connect( V1_V2_V3, V3 );
+
+ return RC;
+ }
+
+
+ /**
+ *
+ * V1 --> V2 --> V3 <--> V4
+ */
+ public DirectedGraph makeCycleNoReturn()
+ throws GraphException
+ {
+ DirectedGraphImpl RC = new DirectedGraphImpl();
+
+ RC.addVertex(V1);
+ RC.addVertex(V2);
+ RC.addVertex(V3);
+ RC.addVertex(V4);
+
+ RC.addEdge(V1_V2, V1, V2);
+ RC.addEdge(V2_V3, V2, V3);
+ RC.addEdge(V3_V4, V3, V4);
+ RC.addEdge(V4_V3, V4, V3);
+
+ return RC;
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testNothing()
+ throws Throwable { }
+
+ /**
+ * Description of the Method
+ */
+ public void verifyVertexEdgeCount(Graph IUT,
+ Vertex v,
+ int numEdge)
+ throws Throwable
+ {
+ assertEquals(v.toString() + " has wrong number of adjacent edges.",
+ IUT.getEdges(v).size(), numEdge);
+ }
+
+ /**
+ * Gets the outboundVertices attribute of the GraphTest object
+ */
+ private Set getOutboundVertices(DirectedGraph IUT,
+ Vertex v)
+ {
+ Set RC = new HashSet();
+ Iterator edges = IUT.getOutbound(v).iterator();
+
+ while (edges.hasNext())
+ {
+ Edge e = (Edge) edges.next();
+ RC.add(IUT.getTarget(e));
+ }
+
+ return RC;
+ }
+
+ /**
+ * Gets the inboundVertices attribute of the GraphTest object
+ */
+ private Set getInboundVertices(DirectedGraph IUT,
+ Vertex v)
+ {
+ Set RC = new HashSet();
+ Iterator edges = IUT.getInbound(v).iterator();
+
+ while (edges.hasNext())
+ {
+ Edge e = (Edge) edges.next();
+ RC.add(IUT.getSource(e));
+ }
+
+ return RC;
+ }
+
+
+ /**
+ * Gets the adjVertices attribute of the GraphTest object
+ */
+ private Set getAdjVertices(Graph IUT,
+ Vertex v)
+ {
+ Set RC = new HashSet();
+ Iterator edges = IUT.getEdges(v).iterator();
+
+ while (edges.hasNext())
+ {
+ Edge e = (Edge) edges.next();
+
+ Set verts = IUT.getVertices(e);
+ RC.addAll(verts);
+ }
+
+ return RC;
+ }
+
+ /**
+ * Description of the Method
+ */
+ public Set makeSet()
+ {
+ return new HashSet();
+ }
+
+
+ /**
+ * Description of the Method
+ */
+ public Set makeSet(Object v)
+ {
+ Set RC = new HashSet();
+ RC.add(v);
+ return RC;
+ }
+
+ /**
+ * Description of the Method
+ */
+ public Set makeSet(Object v1,
+ Object v2)
+ {
+ Set RC = makeSet(v1);
+ RC.add(v2);
+ return RC;
+ }
+
+ /**
+ * Description of the Method
+ */
+ public Set makeSet(Set s1,
+ Set s2)
+ {
+ Set RC = new HashSet();
+ RC.addAll(s1);
+ RC.addAll(s2);
+ return RC;
+ }
+
+ /**
+ * Description of the Method
+ */
+ public Set makeSet(Object v1,
+ Object v2,
+ Object v3)
+ {
+ return makeSet(makeSet(v1, v2),
+ makeSet(v3));
+ }
+
+ /**
+ * Description of the Method
+ */
+ public Set makeSet(Object v1,
+ Object v2,
+ Object v3,
+ Object v4)
+ {
+ return makeSet(makeSet(v1, v2),
+ makeSet(v3, v4));
+ }
+
+ /**
+ * Description of the Method
+ */
+ public void verifyAdjVertices(DirectedGraph IUT,
+ Vertex v,
+ Set inExpect,
+ Set outExpect)
+ {
+ Set inbound = getInboundVertices(IUT, v);
+ Set outbound = getOutboundVertices(IUT, v);
+
+ Iterator verts;
+
+ // inbound is a subset of inExpect
+ verts = inbound.iterator();
+
+ while (verts.hasNext())
+ {
+ Vertex curr = (Vertex) verts.next();
+
+ assertTrue(curr.toString() + " is not supposed to be " +
+ "next to " + v.toString(),
+ inExpect.contains(curr));
+ }
+
+ // inExpect is a subset of inbound
+ verts = inExpect.iterator();
+
+ while (verts.hasNext())
+ {
+ Vertex curr = (Vertex) verts.next();
+ assertTrue(curr.toString() + " is supposed to be next to " +
+ v.toString(),
+ inbound.contains(curr));
+ }
+
+ // outbound is a subset of outExpect
+ verts = outbound.iterator();
+
+ while (verts.hasNext())
+ {
+ Vertex curr = (Vertex) verts.next();
+
+ assertTrue(curr.toString() + " is not supposed to be " +
+ "next to " + v.toString(),
+ outExpect.contains(curr));
+ }
+
+ // outExpect is a subset of outbound
+ verts = outExpect.iterator();
+
+ while (verts.hasNext())
+ {
+ Vertex curr = (Vertex) verts.next();
+ assertTrue(curr.toString() + " is supposed to be next to " +
+ v.toString(),
+ outbound.contains(curr));
+ }
+
+ }
+
+ /**
+ * Description of the Method
+ */
+ public void verifyAdjVertices(Graph IUT,
+ Vertex v,
+ Set expected)
+ throws Throwable
+ {
+ Set adjacent = getAdjVertices(IUT, v);
+ Iterator adjV = adjacent.iterator();
+
+ while (adjV.hasNext())
+ {
+ Vertex curr = (Vertex) adjV.next();
+ assertTrue(curr.toString() + " is not supposed to be " +
+ "next to " + v.toString(),
+ expected.contains(curr));
+ }
+
+ Iterator expect = expected.iterator();
+
+ while (expect.hasNext())
+ {
+ Vertex curr = (Vertex) expect.next();
+ assertTrue(curr.toString() + " is supposed to be next to " +
+ v.toString(),
+ adjacent.contains(curr));
+ }
+ }
+
+ /**
+ * Description of the Method
+ */
+ public void verifyGraph(Graph g, int numVertex, int numEdge)
+ throws Throwable
+ {
+ assertEquals("Incorrect Number of Vertices.",
+ numVertex, g.getVertices().size());
+ assertEquals("Incorrect Number of Edges.",
+ numEdge, g.getEdges().size());
+ }
+
+ /**
+ * Description of the Method
+ */
+ public void printGraph(Throwable t,
+ DirectedGraph IUT)
+ {
+ System.err.println(testName + ": " + t.toString());
+ System.err.println("VERTICES: " + IUT.getVertices());
+ System.err.println("EDGES: " + IUT.getEdges());
+
+ Iterator verts = IUT.getVertices().iterator();
+ while (verts.hasNext())
+ {
+ Vertex vert = (Vertex) verts.next();
+ System.err.println("[ " + vert + " ]");
+
+ Iterator inbounds = IUT.getInbound(vert).iterator();
+ while (inbounds.hasNext())
+ {
+ Edge inbound = (Edge) inbounds.next();
+ System.err.println("\tI [" + inbound + "]");
+ }
+
+ Iterator outbounds = IUT.getOutbound(vert).iterator();
+ while (outbounds.hasNext())
+ {
+ Edge outbound = (Edge) outbounds.next();
+ System.err.println("\tO [" + outbound + "]");
+ }
+ }
+ }
+
+}
1.2 +0 -2 jakarta-commons-sandbox/graph2/src/test/org/apache/commons/graph/algorithm/dataflow/DataFlowSolutionsTest.java
Index: DataFlowSolutionsTest.java
===================================================================
RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/test/org/apache/commons/graph/algorithm/dataflow/DataFlowSolutionsTest.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- DataFlowSolutionsTest.java 26 Jul 2002 14:54:43 -0000 1.1
+++ DataFlowSolutionsTest.java 1 Jan 2003 02:14:38 -0000 1.2
@@ -58,8 +58,6 @@
import java.util.BitSet;
-import junit.framework.*;
-
public class DataFlowSolutionsTest extends GraphTest {
private static BitSet BS_000 = null;
private static BitSet BS_001 = null;
1.2 +564 -567 jakarta-commons-sandbox/graph2/src/test/org/apache/commons/graph/algorithm/path/AllPairsTest.java
Index: AllPairsTest.java
===================================================================
RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/test/org/apache/commons/graph/algorithm/path/AllPairsTest.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- AllPairsTest.java 8 May 2002 18:19:13 -0000 1.1
+++ AllPairsTest.java 1 Jan 2003 02:14:38 -0000 1.2
@@ -1,567 +1,564 @@
-package org.apache.commons.graph.algorithm.path;
-
-/* ====================================================================
- * The Apache Software License, Version 1.1
- *
- * Copyright (c) 2001 The Apache Software Foundation. All rights
- * reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, 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 "Apache" and "Apache Software Foundation" and
- * "Commons" 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",
- * "Commons", 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 (INCLUDING, 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/>.
- */
-
-/**
- * AllPairsTest This tests the All Pairs Shortest Path solution.
- */
-
-import org.apache.commons.graph.*;
-import org.apache.commons.graph.exception.*;
-
-import java.util.List;
-import java.util.Iterator;
-
-import junit.framework.*;
-
-/**
- * Description of the Class
- */
-public class AllPairsTest
- extends WeightedGraphTest
-{
- /**
- * Constructor for the AllPairsTest object
- *
- * @param name
- */
- public AllPairsTest(String name)
- {
- super(name);
- }
-
- /**
- * A unit test for JUnit
- */
- public void testAPWDirectedEdge()
- throws Throwable
- {
- DirectedGraph g = makeWDirectedEdge();
- AllPairsShortestPath IUT = new AllPairsShortestPath(g);
-
- verifyPath(g, IUT.getShortestPath(V1, V1),
- V1, V1, V1,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V2, V2),
- V2, V2, V2,
- 0.0, 1, 0);
-
- verifyPath(g, IUT.getShortestPath(V1, V2),
- V1, V2, V1, V1_V2,
- 5.0, 2, 1);
- try
- {
- IUT.getShortestPath(V2, V1);
- fail("NoPathException not thrown.");
- }
- catch (NoPathException ex)
- {}
- }
-
- /**
- * A unit test for JUnit
- */
- public void testAPPositiveCycle()
- throws Throwable
- {
- DirectedGraph g = makePositiveCycle();
- AllPairsShortestPath IUT = new AllPairsShortestPath(g);
-
- verifyPath(g, IUT.getShortestPath(V1, V1),
- V1, V1, V1,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V2, V2),
- V2, V2, V2,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V3, V3),
- V3, V3, V3,
- 0.0, 1, 0);
-
- verifyPath(g, IUT.getShortestPath(V1, V2),
- V1, V2, V1, V1_V2,
- 2.0, 2, 1);
- verifyPath(g, IUT.getShortestPath(V2, V3),
- V2, V3, V2, V2_V3,
- 4.0, 2, 1);
- verifyPath(g, IUT.getShortestPath(V3, V1),
- V3, V1, V3, V3_V1,
- 1.5, 2, 1);
-
- verifyPath(g, IUT.getShortestPath(V1, V3),
- V1, V3, V2, V1_V2,
- 6.0, 3, 2);
- verifyPath(g, IUT.getShortestPath(V2, V1),
- V2, V1, V3, V2_V3,
- 5.5, 3, 2);
- verifyPath(g, IUT.getShortestPath(V3, V2),
- V3, V2, V1, V1_V2,
- 3.5, 3, 2);
- }
-
- /**
- * A unit test for JUnit
- */
- public void testAPPositivePartNegCycle()
- throws Throwable
- {
- DirectedGraph g = makePositivePartNegCycle();
- AllPairsShortestPath IUT = new AllPairsShortestPath(g);
-
- verifyPath(g, IUT.getShortestPath(V1, V1),
- V1, V1, V1,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V2, V2),
- V2, V2, V2,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V3, V3),
- V3, V3, V3,
- 0.0, 1, 0);
-
- verifyPath(g, IUT.getShortestPath(V1, V2),
- V1, V2, V1, V1_V2,
- 2.0, 2, 1);
- verifyPath(g, IUT.getShortestPath(V2, V3),
- V2, V3, V2, V2_V3,
- 4.0, 2, 1);
- verifyPath(g, IUT.getShortestPath(V3, V1),
- V3, V1, V3, V3_V1,
- -1.5, 2, 1);
-
- verifyPath(g, IUT.getShortestPath(V1, V3),
- V1, V3, V2, V2_V3,
- 6.0, 3, 2);
- verifyPath(g, IUT.getShortestPath(V2, V1),
- V2, V1, V3, V2_V3,
- 2.5, 3, 2);
- verifyPath(g, IUT.getShortestPath(V3, V2),
- V3, V2, V1, V1_V2,
- 0.5, 3, 2);
- }
-
- /**
- * A unit test for JUnit
- */
- public void testAPNegativeCycle()
- throws Throwable
- {
- try
- {
- AllPairsShortestPath IUT = new AllPairsShortestPath(makeNegativeCycle());
- fail("NegativeCycleException not thrown.");
- }
- catch (NegativeCycleException ex)
- {}
- }
-
- /**
- * A unit test for JUnit
- */
- public void testAPNegativePartPosCycle()
- throws Throwable
- {
- try
- {
- AllPairsShortestPath IUT = new AllPairsShortestPath(makeNegativePartPosCycle());
- fail("NegativeCycleException not thrown.");
- }
- catch (NegativeCycleException ex)
- {}
- }
-
- /*
- * Test Pipes now. . .
- */
- /**
- * A unit test for JUnit
- */
- public void testAPPositivePipe()
- throws Throwable
- {
- DirectedGraph g = makePositivePipe();
- AllPairsShortestPath IUT = new AllPairsShortestPath(g);
-
- verifyPath(g, IUT.getShortestPath(V1, V1),
- V1, V1, V1,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V2, V2),
- V2, V2, V2,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V3, V3),
- V3, V3, V3,
- 0.0, 1, 0);
-
- verifyPath(g, IUT.getShortestPath(V1, V2),
- V1, V2, V1, V1_V2,
- 1.5, 2, 1);
- verifyPath(g, IUT.getShortestPath(V2, V3),
- V2, V3, V2, V2_V3,
- 3.5, 2, 1);
-
- verifyPath(g, IUT.getShortestPath(V1, V3),
- V1, V3, V2, V1_V2,
- 5.0, 3, 2);
-
- }
-
- /**
- * A unit test for JUnit
- */
- public void testAPPositivePartNegPipe()
- throws Throwable
- {
- DirectedGraph g = makePositivePartNegPipe();
- AllPairsShortestPath IUT = new AllPairsShortestPath(g);
-
- verifyPath(g, IUT.getShortestPath(V1, V1),
- V1, V1, V1,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V2, V2),
- V2, V2, V2,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V3, V3),
- V3, V3, V3,
- 0.0, 1, 0);
-
- verifyPath(g, IUT.getShortestPath(V1, V2),
- V1, V2, V1, V1_V2,
- -1.5, 2, 1);
- verifyPath(g, IUT.getShortestPath(V2, V3),
- V2, V3, V2, V2_V3,
- 3.5, 2, 1);
-
- verifyPath(g, IUT.getShortestPath(V1, V3),
- V1, V3, V2, V2_V3,
- 2.0, 3, 2);
-
- }
-
- /**
- * A unit test for JUnit
- */
- public void testAPNegativePipe()
- throws Throwable
- {
- DirectedGraph g = makeNegativePipe();
- AllPairsShortestPath IUT = new AllPairsShortestPath(g);
-
- verifyPath(g, IUT.getShortestPath(V1, V1),
- V1, V1, V1,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V2, V2),
- V2, V2, V2,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V3, V3),
- V3, V3, V3,
- 0.0, 1, 0);
-
- verifyPath(g, IUT.getShortestPath(V1, V2),
- V1, V2, V1, V1_V2,
- -1.5, 2, 1);
- verifyPath(g, IUT.getShortestPath(V2, V3),
- V2, V3, V2, V2_V3,
- -3.5, 2, 1);
-
- verifyPath(g, IUT.getShortestPath(V1, V3),
- V1, V3, V2, V1_V2,
- -5.0, 3, 2);
-
- }
-
- /**
- * A unit test for JUnit
- */
- public void testAPNegativePartPosPipe()
- throws Throwable
- {
- DirectedGraph g = makeNegativePartPosPipe();
- AllPairsShortestPath IUT = new AllPairsShortestPath(g);
-
- verifyPath(g, IUT.getShortestPath(V1, V1),
- V1, V1, V1,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V2, V2),
- V2, V2, V2,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V3, V3),
- V3, V3, V3,
- 0.0, 1, 0);
-
- verifyPath(g, IUT.getShortestPath(V1, V2),
- V1, V2, V1, V1_V2,
- 1.5, 2, 1);
- verifyPath(g, IUT.getShortestPath(V2, V3),
- V2, V3, V2, V2_V3,
- -3.5, 2, 1);
-
- verifyPath(g, IUT.getShortestPath(V1, V3),
- V1, V3, V2, V1_V2,
- -2.0, 3, 2);
-
- }
-
- /**
- * A unit test for JUnit
- */
- public void testMultiplePathL()
- throws Throwable
- {
- DirectedGraph g = makeMultiplePathL();
- AllPairsShortestPath IUT = new AllPairsShortestPath(g);
-
- verifyPath(g, IUT.getShortestPath(V1, V1),
- V1, V1, V1,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V2, V2),
- V2, V2, V2,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V3, V3),
- V3, V3, V3,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V4, V4),
- V4, V4, V4,
- 0.0, 1, 0);
-
- verifyPath(g, IUT.getShortestPath(V1, V2),
- V1, V2, V1, V1_V2,
- 1.5, 2, 1);
- verifyPath(g, IUT.getShortestPath(V1, V3),
- V1, V3, V1, V1_V3,
- 2.5, 2, 1);
- verifyPath(g, IUT.getShortestPath(V2, V4),
- V2, V4, V2, V2_V4,
- 1.5, 2, 1);
- verifyPath(g, IUT.getShortestPath(V3, V4),
- V3, V4, V3, V3_V4,
- 3.5, 2, 1);
-
- verifyPath(g, IUT.getShortestPath(V1, V4),
- V1, V4, V2, V1_V2,
- 3.0, 3, 2);
- }
-
- /**
- * A unit test for JUnit
- */
- public void testMultiplePathR()
- throws Throwable
- {
- DirectedGraph g = makeMultiplePathR();
- AllPairsShortestPath IUT = new AllPairsShortestPath(g);
-
- verifyPath(g, IUT.getShortestPath(V1, V1),
- V1, V1, V1,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V2, V2),
- V2, V2, V2,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V3, V3),
- V3, V3, V3,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V4, V4),
- V4, V4, V4,
- 0.0, 1, 0);
-
- verifyPath(g, IUT.getShortestPath(V1, V2),
- V1, V2, V1, V1_V2,
- 3.5, 2, 1);
- verifyPath(g, IUT.getShortestPath(V1, V3),
- V1, V3, V1, V1_V3,
- 1.5, 2, 1);
- verifyPath(g, IUT.getShortestPath(V2, V4),
- V2, V4, V2, V2_V4,
- 2.5, 2, 1);
- verifyPath(g, IUT.getShortestPath(V3, V4),
- V3, V4, V3, V3_V4,
- 1.5, 2, 1);
-
- verifyPath(g, IUT.getShortestPath(V1, V4),
- V1, V4, V3, V1_V3,
- 3.0, 3, 2);
- }
-
- /**
- * A unit test for JUnit
- */
- public void testMultiplePathEarlyLow()
- throws Throwable
- {
- DirectedGraph g = makeMultiplePathEarlyLow();
- AllPairsShortestPath IUT = new AllPairsShortestPath(g);
-
- verifyPath(g, IUT.getShortestPath(V1, V1),
- V1, V1, V1,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V2, V2),
- V2, V2, V2,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V3, V3),
- V3, V3, V3,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V4, V4),
- V4, V4, V4,
- 0.0, 1, 0);
-
- verifyPath(g, IUT.getShortestPath(V1, V2),
- V1, V2, V1, V1_V2,
- 10.0, 2, 1);
- verifyPath(g, IUT.getShortestPath(V1, V3),
- V1, V3, V1, V1_V3,
- 0.5, 2, 1);
- verifyPath(g, IUT.getShortestPath(V2, V4),
- V2, V4, V2, V2_V4,
- 10.0, 2, 1);
- verifyPath(g, IUT.getShortestPath(V3, V4),
- V3, V4, V3, V3_V4,
- 10.5, 2, 1);
-
- verifyPath(g, IUT.getShortestPath(V1, V4),
- V1, V4, V3, V3_V4,
- 11.0, 3, 2);
- }
-
- /**
- * A unit test for JUnit
- */
- public void testMultiplePathEarlyHigh()
- throws Throwable
- {
- DirectedGraph g = makeMultiplePathEarlyHigh();
- AllPairsShortestPath IUT = new AllPairsShortestPath(g);
-
- verifyPath(g, IUT.getShortestPath(V1, V1),
- V1, V1, V1,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V2, V2),
- V2, V2, V2,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V3, V3),
- V3, V3, V3,
- 0.0, 1, 0);
- verifyPath(g, IUT.getShortestPath(V4, V4),
- V4, V4, V4,
- 0.0, 1, 0);
-
- verifyPath(g, IUT.getShortestPath(V1, V2),
- V1, V2, V1, V1_V2,
- 10.0, 2, 1);
- verifyPath(g, IUT.getShortestPath(V1, V3),
- V1, V3, V1, V1_V3,
- 10.5, 2, 1);
- verifyPath(g, IUT.getShortestPath(V2, V4),
- V2, V4, V2, V2_V4,
- 10.0, 2, 1);
- verifyPath(g, IUT.getShortestPath(V3, V4),
- V3, V4, V3, V3_V4,
- 0.5, 2, 1);
-
- verifyPath(g, IUT.getShortestPath(V1, V4),
- V1, V4, V3, V1_V3,
- 11.0, 3, 2);
- }
-
- /**
- * Description of the Method
- */
- public void verifyPath(DirectedGraph g, WeightedPath wp,
- Vertex start, Vertex end, Vertex mid,
- double cost, int vertexCount, int edgeCount)
- throws Throwable
- {
- verifyPath(g, wp, start, end, mid,
- null, cost, vertexCount, edgeCount);
- }
-
- /**
- * Description of the Method
- */
- public void verifyPath(DirectedGraph g, WeightedPath wp,
- Vertex start, Vertex end, Vertex mid, Edge midE,
- double cost, int vertexCount, int edgeCount)
- throws Throwable
- {
- assertEquals("Wrong Start",
- start, wp.getStart());
- assertEquals("Wrong End",
- end, wp.getEnd());
- assertEquals("Wrong Cost of Path: " + start + "->" + end,
- cost, wp.getWeight(), 0.0001);
- assertEquals("Wrong number of Vertices in " + start + "->" + end,
- vertexCount, wp.getVertices().size());
- assertEquals("Wrong number of Edges in " + start + "->" + end,
- edgeCount, wp.getEdges().size());
- assertTrue("Path " + start + "->" + end + " doesn't contain: " + mid,
- wp.getVertices().contains(mid));
- if (midE != null)
- {
- assertTrue("Path " + start + "-> " + end + " doesn't contain edge: " + midE,
- wp.getEdges().contains(midE));
- }
-
- List edgeList = wp.getEdges();
- List vertList = wp.getVertices();
-
- for (int i = 0; i < edgeList.size(); i++)
- {
- assertEquals("Edge: " + edgeList.get(i) + " doesn't use " +
- vertList.get(i) + " as source.",
- g.getSource((Edge) edgeList.get(i)),
- (Vertex) vertList.get(i));
- assertEquals("Edge: " + edgeList.get(i) + " doesn't use " +
- vertList.get(i) + " as target.",
- g.getTarget((Edge) edgeList.get(i)),
- (Vertex) vertList.get(i + 1));
- }
- }
-}
+package org.apache.commons.graph.algorithm.path;
+
+/* ====================================================================
+ * The Apache Software License, Version 1.1
+ *
+ * Copyright (c) 2001 The Apache Software Foundation. All rights
+ * reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, 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 "Apache" and "Apache Software Foundation" and
+ * "Commons" 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",
+ * "Commons", 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 (INCLUDING, 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/>.
+ */
+
+/**
+ * AllPairsTest This tests the All Pairs Shortest Path solution.
+ */
+
+import org.apache.commons.graph.*;
+import org.apache.commons.graph.exception.*;
+
+import java.util.List;
+
+/**
+ * Description of the Class
+ */
+public class AllPairsTest
+ extends WeightedGraphTest
+{
+ /**
+ * Constructor for the AllPairsTest object
+ *
+ * @param name
+ */
+ public AllPairsTest(String name)
+ {
+ super(name);
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testAPWDirectedEdge()
+ throws Throwable
+ {
+ DirectedGraph g = makeWDirectedEdge();
+ AllPairsShortestPath IUT = new AllPairsShortestPath(g);
+
+ verifyPath(g, IUT.getShortestPath(V1, V1),
+ V1, V1, V1,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V2, V2),
+ V2, V2, V2,
+ 0.0, 1, 0);
+
+ verifyPath(g, IUT.getShortestPath(V1, V2),
+ V1, V2, V1, V1_V2,
+ 5.0, 2, 1);
+ try
+ {
+ IUT.getShortestPath(V2, V1);
+ fail("NoPathException not thrown.");
+ }
+ catch (NoPathException ex)
+ {}
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testAPPositiveCycle()
+ throws Throwable
+ {
+ DirectedGraph g = makePositiveCycle();
+ AllPairsShortestPath IUT = new AllPairsShortestPath(g);
+
+ verifyPath(g, IUT.getShortestPath(V1, V1),
+ V1, V1, V1,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V2, V2),
+ V2, V2, V2,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V3, V3),
+ V3, V3, V3,
+ 0.0, 1, 0);
+
+ verifyPath(g, IUT.getShortestPath(V1, V2),
+ V1, V2, V1, V1_V2,
+ 2.0, 2, 1);
+ verifyPath(g, IUT.getShortestPath(V2, V3),
+ V2, V3, V2, V2_V3,
+ 4.0, 2, 1);
+ verifyPath(g, IUT.getShortestPath(V3, V1),
+ V3, V1, V3, V3_V1,
+ 1.5, 2, 1);
+
+ verifyPath(g, IUT.getShortestPath(V1, V3),
+ V1, V3, V2, V1_V2,
+ 6.0, 3, 2);
+ verifyPath(g, IUT.getShortestPath(V2, V1),
+ V2, V1, V3, V2_V3,
+ 5.5, 3, 2);
+ verifyPath(g, IUT.getShortestPath(V3, V2),
+ V3, V2, V1, V1_V2,
+ 3.5, 3, 2);
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testAPPositivePartNegCycle()
+ throws Throwable
+ {
+ DirectedGraph g = makePositivePartNegCycle();
+ AllPairsShortestPath IUT = new AllPairsShortestPath(g);
+
+ verifyPath(g, IUT.getShortestPath(V1, V1),
+ V1, V1, V1,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V2, V2),
+ V2, V2, V2,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V3, V3),
+ V3, V3, V3,
+ 0.0, 1, 0);
+
+ verifyPath(g, IUT.getShortestPath(V1, V2),
+ V1, V2, V1, V1_V2,
+ 2.0, 2, 1);
+ verifyPath(g, IUT.getShortestPath(V2, V3),
+ V2, V3, V2, V2_V3,
+ 4.0, 2, 1);
+ verifyPath(g, IUT.getShortestPath(V3, V1),
+ V3, V1, V3, V3_V1,
+ -1.5, 2, 1);
+
+ verifyPath(g, IUT.getShortestPath(V1, V3),
+ V1, V3, V2, V2_V3,
+ 6.0, 3, 2);
+ verifyPath(g, IUT.getShortestPath(V2, V1),
+ V2, V1, V3, V2_V3,
+ 2.5, 3, 2);
+ verifyPath(g, IUT.getShortestPath(V3, V2),
+ V3, V2, V1, V1_V2,
+ 0.5, 3, 2);
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testAPNegativeCycle()
+ throws Throwable
+ {
+ try
+ {
+ AllPairsShortestPath IUT = new AllPairsShortestPath(makeNegativeCycle());
+ fail("NegativeCycleException not thrown.");
+ }
+ catch (NegativeCycleException ex)
+ {}
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testAPNegativePartPosCycle()
+ throws Throwable
+ {
+ try
+ {
+ AllPairsShortestPath IUT = new AllPairsShortestPath(makeNegativePartPosCycle());
+ fail("NegativeCycleException not thrown.");
+ }
+ catch (NegativeCycleException ex)
+ {}
+ }
+
+ /*
+ * Test Pipes now. . .
+ */
+ /**
+ * A unit test for JUnit
+ */
+ public void testAPPositivePipe()
+ throws Throwable
+ {
+ DirectedGraph g = makePositivePipe();
+ AllPairsShortestPath IUT = new AllPairsShortestPath(g);
+
+ verifyPath(g, IUT.getShortestPath(V1, V1),
+ V1, V1, V1,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V2, V2),
+ V2, V2, V2,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V3, V3),
+ V3, V3, V3,
+ 0.0, 1, 0);
+
+ verifyPath(g, IUT.getShortestPath(V1, V2),
+ V1, V2, V1, V1_V2,
+ 1.5, 2, 1);
+ verifyPath(g, IUT.getShortestPath(V2, V3),
+ V2, V3, V2, V2_V3,
+ 3.5, 2, 1);
+
+ verifyPath(g, IUT.getShortestPath(V1, V3),
+ V1, V3, V2, V1_V2,
+ 5.0, 3, 2);
+
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testAPPositivePartNegPipe()
+ throws Throwable
+ {
+ DirectedGraph g = makePositivePartNegPipe();
+ AllPairsShortestPath IUT = new AllPairsShortestPath(g);
+
+ verifyPath(g, IUT.getShortestPath(V1, V1),
+ V1, V1, V1,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V2, V2),
+ V2, V2, V2,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V3, V3),
+ V3, V3, V3,
+ 0.0, 1, 0);
+
+ verifyPath(g, IUT.getShortestPath(V1, V2),
+ V1, V2, V1, V1_V2,
+ -1.5, 2, 1);
+ verifyPath(g, IUT.getShortestPath(V2, V3),
+ V2, V3, V2, V2_V3,
+ 3.5, 2, 1);
+
+ verifyPath(g, IUT.getShortestPath(V1, V3),
+ V1, V3, V2, V2_V3,
+ 2.0, 3, 2);
+
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testAPNegativePipe()
+ throws Throwable
+ {
+ DirectedGraph g = makeNegativePipe();
+ AllPairsShortestPath IUT = new AllPairsShortestPath(g);
+
+ verifyPath(g, IUT.getShortestPath(V1, V1),
+ V1, V1, V1,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V2, V2),
+ V2, V2, V2,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V3, V3),
+ V3, V3, V3,
+ 0.0, 1, 0);
+
+ verifyPath(g, IUT.getShortestPath(V1, V2),
+ V1, V2, V1, V1_V2,
+ -1.5, 2, 1);
+ verifyPath(g, IUT.getShortestPath(V2, V3),
+ V2, V3, V2, V2_V3,
+ -3.5, 2, 1);
+
+ verifyPath(g, IUT.getShortestPath(V1, V3),
+ V1, V3, V2, V1_V2,
+ -5.0, 3, 2);
+
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testAPNegativePartPosPipe()
+ throws Throwable
+ {
+ DirectedGraph g = makeNegativePartPosPipe();
+ AllPairsShortestPath IUT = new AllPairsShortestPath(g);
+
+ verifyPath(g, IUT.getShortestPath(V1, V1),
+ V1, V1, V1,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V2, V2),
+ V2, V2, V2,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V3, V3),
+ V3, V3, V3,
+ 0.0, 1, 0);
+
+ verifyPath(g, IUT.getShortestPath(V1, V2),
+ V1, V2, V1, V1_V2,
+ 1.5, 2, 1);
+ verifyPath(g, IUT.getShortestPath(V2, V3),
+ V2, V3, V2, V2_V3,
+ -3.5, 2, 1);
+
+ verifyPath(g, IUT.getShortestPath(V1, V3),
+ V1, V3, V2, V1_V2,
+ -2.0, 3, 2);
+
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testMultiplePathL()
+ throws Throwable
+ {
+ DirectedGraph g = makeMultiplePathL();
+ AllPairsShortestPath IUT = new AllPairsShortestPath(g);
+
+ verifyPath(g, IUT.getShortestPath(V1, V1),
+ V1, V1, V1,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V2, V2),
+ V2, V2, V2,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V3, V3),
+ V3, V3, V3,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V4, V4),
+ V4, V4, V4,
+ 0.0, 1, 0);
+
+ verifyPath(g, IUT.getShortestPath(V1, V2),
+ V1, V2, V1, V1_V2,
+ 1.5, 2, 1);
+ verifyPath(g, IUT.getShortestPath(V1, V3),
+ V1, V3, V1, V1_V3,
+ 2.5, 2, 1);
+ verifyPath(g, IUT.getShortestPath(V2, V4),
+ V2, V4, V2, V2_V4,
+ 1.5, 2, 1);
+ verifyPath(g, IUT.getShortestPath(V3, V4),
+ V3, V4, V3, V3_V4,
+ 3.5, 2, 1);
+
+ verifyPath(g, IUT.getShortestPath(V1, V4),
+ V1, V4, V2, V1_V2,
+ 3.0, 3, 2);
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testMultiplePathR()
+ throws Throwable
+ {
+ DirectedGraph g = makeMultiplePathR();
+ AllPairsShortestPath IUT = new AllPairsShortestPath(g);
+
+ verifyPath(g, IUT.getShortestPath(V1, V1),
+ V1, V1, V1,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V2, V2),
+ V2, V2, V2,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V3, V3),
+ V3, V3, V3,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V4, V4),
+ V4, V4, V4,
+ 0.0, 1, 0);
+
+ verifyPath(g, IUT.getShortestPath(V1, V2),
+ V1, V2, V1, V1_V2,
+ 3.5, 2, 1);
+ verifyPath(g, IUT.getShortestPath(V1, V3),
+ V1, V3, V1, V1_V3,
+ 1.5, 2, 1);
+ verifyPath(g, IUT.getShortestPath(V2, V4),
+ V2, V4, V2, V2_V4,
+ 2.5, 2, 1);
+ verifyPath(g, IUT.getShortestPath(V3, V4),
+ V3, V4, V3, V3_V4,
+ 1.5, 2, 1);
+
+ verifyPath(g, IUT.getShortestPath(V1, V4),
+ V1, V4, V3, V1_V3,
+ 3.0, 3, 2);
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testMultiplePathEarlyLow()
+ throws Throwable
+ {
+ DirectedGraph g = makeMultiplePathEarlyLow();
+ AllPairsShortestPath IUT = new AllPairsShortestPath(g);
+
+ verifyPath(g, IUT.getShortestPath(V1, V1),
+ V1, V1, V1,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V2, V2),
+ V2, V2, V2,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V3, V3),
+ V3, V3, V3,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V4, V4),
+ V4, V4, V4,
+ 0.0, 1, 0);
+
+ verifyPath(g, IUT.getShortestPath(V1, V2),
+ V1, V2, V1, V1_V2,
+ 10.0, 2, 1);
+ verifyPath(g, IUT.getShortestPath(V1, V3),
+ V1, V3, V1, V1_V3,
+ 0.5, 2, 1);
+ verifyPath(g, IUT.getShortestPath(V2, V4),
+ V2, V4, V2, V2_V4,
+ 10.0, 2, 1);
+ verifyPath(g, IUT.getShortestPath(V3, V4),
+ V3, V4, V3, V3_V4,
+ 10.5, 2, 1);
+
+ verifyPath(g, IUT.getShortestPath(V1, V4),
+ V1, V4, V3, V3_V4,
+ 11.0, 3, 2);
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testMultiplePathEarlyHigh()
+ throws Throwable
+ {
+ DirectedGraph g = makeMultiplePathEarlyHigh();
+ AllPairsShortestPath IUT = new AllPairsShortestPath(g);
+
+ verifyPath(g, IUT.getShortestPath(V1, V1),
+ V1, V1, V1,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V2, V2),
+ V2, V2, V2,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V3, V3),
+ V3, V3, V3,
+ 0.0, 1, 0);
+ verifyPath(g, IUT.getShortestPath(V4, V4),
+ V4, V4, V4,
+ 0.0, 1, 0);
+
+ verifyPath(g, IUT.getShortestPath(V1, V2),
+ V1, V2, V1, V1_V2,
+ 10.0, 2, 1);
+ verifyPath(g, IUT.getShortestPath(V1, V3),
+ V1, V3, V1, V1_V3,
+ 10.5, 2, 1);
+ verifyPath(g, IUT.getShortestPath(V2, V4),
+ V2, V4, V2, V2_V4,
+ 10.0, 2, 1);
+ verifyPath(g, IUT.getShortestPath(V3, V4),
+ V3, V4, V3, V3_V4,
+ 0.5, 2, 1);
+
+ verifyPath(g, IUT.getShortestPath(V1, V4),
+ V1, V4, V3, V1_V3,
+ 11.0, 3, 2);
+ }
+
+ /**
+ * Description of the Method
+ */
+ public void verifyPath(DirectedGraph g, WeightedPath wp,
+ Vertex start, Vertex end, Vertex mid,
+ double cost, int vertexCount, int edgeCount)
+ throws Throwable
+ {
+ verifyPath(g, wp, start, end, mid,
+ null, cost, vertexCount, edgeCount);
+ }
+
+ /**
+ * Description of the Method
+ */
+ public void verifyPath(DirectedGraph g, WeightedPath wp,
+ Vertex start, Vertex end, Vertex mid, Edge midE,
+ double cost, int vertexCount, int edgeCount)
+ throws Throwable
+ {
+ assertEquals("Wrong Start",
+ start, wp.getStart());
+ assertEquals("Wrong End",
+ end, wp.getEnd());
+ assertEquals("Wrong Cost of Path: " + start + "->" + end,
+ cost, wp.getWeight(), 0.0001);
+ assertEquals("Wrong number of Vertices in " + start + "->" + end,
+ vertexCount, wp.getVertices().size());
+ assertEquals("Wrong number of Edges in " + start + "->" + end,
+ edgeCount, wp.getEdges().size());
+ assertTrue("Path " + start + "->" + end + " doesn't contain: " + mid,
+ wp.getVertices().contains(mid));
+ if (midE != null)
+ {
+ assertTrue("Path " + start + "-> " + end + " doesn't contain edge: " + midE,
+ wp.getEdges().contains(midE));
+ }
+
+ List edgeList = wp.getEdges();
+ List vertList = wp.getVertices();
+
+ for (int i = 0; i < edgeList.size(); i++)
+ {
+ assertEquals("Edge: " + edgeList.get(i) + " doesn't use " +
+ vertList.get(i) + " as source.",
+ g.getSource((Edge) edgeList.get(i)),
+ (Vertex) vertList.get(i));
+ assertEquals("Edge: " + edgeList.get(i) + " doesn't use " +
+ vertList.get(i) + " as target.",
+ g.getTarget((Edge) edgeList.get(i)),
+ (Vertex) vertList.get(i + 1));
+ }
+ }
+}
1.2 +488 -492 jakarta-commons-sandbox/graph2/src/test/org/apache/commons/graph/algorithm/path/AllPathsTest.java
Index: AllPathsTest.java
===================================================================
RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/test/org/apache/commons/graph/algorithm/path/AllPathsTest.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- AllPathsTest.java 8 May 2002 18:19:13 -0000 1.1
+++ AllPathsTest.java 1 Jan 2003 02:14:38 -0000 1.2
@@ -1,492 +1,488 @@
-package org.apache.commons.graph.algorithm.path;
-
-/* ====================================================================
- * The Apache Software License, Version 1.1
- *
- * Copyright (c) 2001 The Apache Software Foundation. All rights
- * reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, 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 "Apache" and "Apache Software Foundation" and
- * "Commons" 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",
- * "Commons", 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 (INCLUDING, 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/>.
- */
-
-/**
- * AllPathsTest This tests the All Pairs Shortest Path solution.
- */
-
-import org.apache.commons.graph.*;
-import org.apache.commons.graph.exception.*;
-
-import java.util.Set;
-import java.util.List;
-import java.util.Random;
-import java.util.HashSet;
-import java.util.Iterator;
-import java.util.AbstractSet;
-
-import junit.framework.*;
-
-/**
- * Description of the Class
- */
-public class AllPathsTest
- extends GraphTest
-{
- /**
- * PathCollector
- *
- * This is the thing that collects Callbacks.
- */
- public class PathCollector
- extends AbstractSet
- implements PathListener,
- Set
- {
- private Set paths = new HashSet();
-
- public PathCollector() { }
-
- public void notifyPath( Path path ) {
- paths.add( path );
- }
-
- public int size() {
- return paths.size();
- }
-
- public Iterator iterator() {
- return paths.iterator();
- }
- }
-
- private String name = null;
- private Random random = new Random();
-
- /**
- * Constructor for the AllPathsTest object
- *
- * @param name
- */
- public AllPathsTest(String name)
- {
- super(name);
- this.name = name;
- }
-
- public void testSelfLoop() throws Throwable {
- AllPaths IUT = new AllPaths( makeSelfLoop() );
- verifyPathCount( IUT, V1, V1, 1, 1 );
-
- // Make sure it works with 0. . .
- verifyPathCount( IUT, V1, V1, 0, 0 );
-
- for (int i = 0; i < 5; i++) {
- int r = random.nextInt( 50 );
- verifyPathCount( IUT, V1, V1, r, r );
-
- Iterator iter = IUT.findPaths( V1, V1 );
- for (int j = 0; j < r; j++) {
- Path path = (Path) iter.next();
-
- assertEquals( "Path wrong size.",
- j + 2, path.size() );
- }
- }
-
- }
-
- public void testDirDoubleVertex()
- throws Throwable {
- AllPaths IUT = new AllPaths( makeDirDoubleVertex() );
-
- verifyPathCount( IUT, V1, V1, 0, 2 );
- verifyPathCount( IUT, V2, V2, 0, 2 );
-
- verifyPathCount( IUT, V1, V2, 0, 2 );
- verifyPathCount( IUT, V2, V1, 0, 2 );
- }
-
- /**
- * A unit test for JUnit
- */
- public void testDirectedEdge()
- throws Throwable
- {
- DirectedGraph g = makeDirectedEdge();
- final AllPaths IUT = new AllPaths(g);
-
- verifyPathCount( IUT, V1, V1, 0, 2 );
- verifyPathCount( IUT, V2, V2, 0, 2 );
-
- verifyPathCount( IUT, V2, V1, 0, 2 );
- verifyPathCount( IUT, V1, V2, 1, 2 );
-
- verifyPathCount( IUT, V1, V2, 1, 1 );
-
- // Make sure that no matter how big it
- // is, it still only returns 1 path.
- for (int i = 0; i < 5; i++) {
- int r = random.nextInt( 50 );
-
- r += 5;
- verifyPathCount( IUT, V1, V2, 1, r );
-
- }
-
- verifyHasNextFalse( IUT, V1, V2 );
- }
-
- public void testDirParallelEdges() throws Throwable {
- AllPaths IUT = new AllPaths( makeDirParallelEdges() );
- verifyPathCount( IUT, V1, V1, 0, 2 );
- verifyPathCount( IUT, V2, V2, 0, 2 );
-
- verifyPathCount( IUT, V1, V2, 2, 2 );
- verifyPathCount( IUT, V2, V1, 0, 2 );
- }
-
- public void testTwoCycle() throws Throwable {
- AllPaths IUT = new AllPaths( makeTwoCycle() );
- verifyPathCount( IUT, V1, V1, 1, 2 );
- verifyPathCount( IUT, V2, V2, 1, 2 );
-
-
- verifyPathCount( IUT, V1, V2, 1, 2 );
- verifyPathCount( IUT, V2, V1, 1, 2 );
- }
-
- public void testDirectedCycle() throws Throwable {
- AllPaths IUT = new AllPaths( makeDirectedCycle() );
-
- verifyPathCount( IUT, V1, V1, 1, 3 );
- verifyPathCount( IUT, V2, V2, 1, 3 );
- verifyPathCount( IUT, V3, V3, 1, 3 );
-
-
- verifyPathCount( IUT, V1, V2, 1, 3 );
- verifyPathCount( IUT, V1, V3, 1, 3 );
-
- verifyPathCount( IUT, V2, V3, 1, 3 );
- verifyPathCount( IUT, V2, V1, 1, 3 );
-
- verifyPathCount( IUT, V3, V1, 1, 3 );
- verifyPathCount( IUT, V3, V2, 1, 3 );
-
- for (int i = 0; i < 5; i++) {
- int r = random.nextInt( 50 );
- verifyPathCount( IUT, V1, V1, r, 3 * r );
- }
-
- verifyHasNextTrue( IUT, V1, V1 );
-
- }
-
- public void testDirected4Cycle() throws Throwable {
- AllPaths IUT = new AllPaths( makeDirected4Cycle() );
-
- verifyPathCount( IUT, V1, V1, 1, 4 );
- verifyPathCount( IUT, V2, V2, 1, 4 );
- verifyPathCount( IUT, V3, V3, 1, 4 );
- verifyPathCount( IUT, V4, V4, 1, 4 );
-
-
- verifyPathCount( IUT, V1, V2, 1, 4 );
- verifyPathCount( IUT, V1, V3, 1, 4 );
- verifyPathCount( IUT, V1, V4, 1, 4 );
-
- verifyPathCount( IUT, V2, V1, 1, 4 );
- verifyPathCount( IUT, V2, V3, 1, 4 );
- verifyPathCount( IUT, V2, V4, 1, 4 );
-
- verifyPathCount( IUT, V3, V1, 1, 4 );
- verifyPathCount( IUT, V3, V2, 1, 4 );
- verifyPathCount( IUT, V3, V4, 1, 4 );
-
- verifyPathCount( IUT, V4, V1, 1, 4 );
- verifyPathCount( IUT, V4, V2, 1, 4 );
- verifyPathCount( IUT, V4, V3, 1, 4 );
-
- verifyHasNextTrue( IUT, V1, V1 );
- }
-
- public void testCycleNoReturn() throws Throwable {
- AllPaths IUT = new AllPaths( makeCycleNoReturn() );
-
- verifyHasNextFalse( IUT, V1, V1 );
- }
- public void testPipe() throws Throwable {
- AllPaths IUT = new AllPaths( makePipe() );
- verifyPathCount( IUT, V1, V1, 0, 3 );
- verifyPathCount( IUT, V2, V2, 0, 3 );
- verifyPathCount( IUT, V3, V3, 0, 3 );
-
- verifyPathCount( IUT, V1, V2, 1, 3 );
- verifyPathCount( IUT, V1, V3, 1, 3 );
-
- verifyPathCount( IUT, V2, V3, 1, 3 );
- verifyPathCount( IUT, V2, V1, 0, 3 );
-
- verifyPathCount( IUT, V3, V1, 0, 3 );
- verifyPathCount( IUT, V3, V2, 0, 3 );
- }
-
- public void testDiamond() throws Throwable {
- AllPaths IUT = new AllPaths( makeDiamond() );
-
- verifyPathCount( IUT, V1, V1, 0, 4 );
- verifyPathCount( IUT, V2, V2, 0, 4 );
- verifyPathCount( IUT, V3, V3, 0, 4 );
- verifyPathCount( IUT, V4, V4, 0, 4 );
-
- verifyPathCount( IUT, V1, V2, 1, 4 );
- verifyPathCount( IUT, V1, V3, 1, 4 );
- verifyPathCount( IUT, V1, V4, 2, 4 );
-
- verifyPathCount( IUT, V2, V1, 0, 4 );
- verifyPathCount( IUT, V2, V3, 0, 4 );
- verifyPathCount( IUT, V2, V4, 1, 4 );
-
- verifyPathCount( IUT, V3, V1, 0, 4 );
- verifyPathCount( IUT, V3, V2, 0, 4 );
- verifyPathCount( IUT, V3, V4, 1, 4 );
-
- verifyPathCount( IUT, V4, V1, 0, 4 );
- verifyPathCount( IUT, V4, V2, 0, 4 );
- verifyPathCount( IUT, V4, V3, 0, 4 );
- }
-
- public void testPipelessCycle() throws Throwable {
- AllPaths IUT = new AllPaths( makePipelessCycle() );
-
- verifyPathCount( IUT, V1, V1, 0, 4 );
- verifyPathCount( IUT, V2, V2, 0, 4 );
- verifyPathCount( IUT, V3, V3, 0, 4 );
- verifyPathCount( IUT, V4, V4, 0, 4 );
-
- verifyPathCount( IUT, V1, V2, 1, 4 );
- verifyPathCount( IUT, V1, V3, 1, 4 );
- verifyPathCount( IUT, V1, V4, 0, 4 );
-
- verifyPathCount( IUT, V2, V3, 0, 4 );
- verifyPathCount( IUT, V2, V4, 0, 4 );
- verifyPathCount( IUT, V2, V1, 0, 4 );
-
- verifyPathCount( IUT, V3, V4, 0, 4 );
- verifyPathCount( IUT, V3, V1, 0, 4 );
- verifyPathCount( IUT, V3, V2, 0, 4 );
-
- verifyPathCount( IUT, V4, V1, 0, 4 );
- verifyPathCount( IUT, V4, V2, 1, 4 );
- verifyPathCount( IUT, V4, V3, 1, 4 );
- }
-
- public void testParentTree() throws Throwable {
- AllPaths IUT = new AllPaths( makeParentTree() );
-
- verifyPathCount( IUT, V1, V1, 0, 5 );
- verifyPathCount( IUT, V2, V2, 0, 5 );
- verifyPathCount( IUT, V3, V3, 0, 5 );
- verifyPathCount( IUT, V4, V4, 0, 5 );
- verifyPathCount( IUT, V5, V5, 0, 5 );
-
-
- verifyPathCount( IUT, V1, V2, 0, 5 );
- verifyPathCount( IUT, V1, V3, 0, 5 );
- verifyPathCount( IUT, V1, V4, 0, 5 );
- verifyPathCount( IUT, V1, V5, 0, 5 );
-
- verifyPathCount( IUT, V2, V1, 1, 5 );
- verifyPathCount( IUT, V2, V3, 0, 5 );
- verifyPathCount( IUT, V2, V4, 0, 5 );
- verifyPathCount( IUT, V2, V5, 0, 5 );
-
- verifyPathCount( IUT, V3, V1, 1, 5 );
- verifyPathCount( IUT, V3, V2, 0, 5 );
- verifyPathCount( IUT, V3, V4, 0, 5 );
- verifyPathCount( IUT, V3, V5, 0, 5 );
-
- verifyPathCount( IUT, V4, V1, 1, 5 );
- verifyPathCount( IUT, V4, V2, 0, 5 );
- verifyPathCount( IUT, V4, V3, 1, 5 );
- verifyPathCount( IUT, V4, V5, 0, 5 );
-
- verifyPathCount( IUT, V5, V1, 1, 5 );
- verifyPathCount( IUT, V5, V2, 0, 5 );
- verifyPathCount( IUT, V5, V3, 1, 5 );
- verifyPathCount( IUT, V5, V4, 0, 5 );
- }
-
- public void testChildTree() throws Throwable {
- AllPaths IUT = new AllPaths( makeChildTree() );
-
- verifyPathCount( IUT, V1, V1, 0, 5 );
- verifyPathCount( IUT, V2, V2, 0, 5 );
- verifyPathCount( IUT, V3, V3, 0, 5 );
- verifyPathCount( IUT, V4, V4, 0, 5 );
- verifyPathCount( IUT, V5, V5, 0, 5 );
-
- verifyPathCount( IUT, V1, V2, 1, 5 );
- verifyPathCount( IUT, V1, V3, 1, 5 );
- verifyPathCount( IUT, V1, V4, 1, 5 );
- verifyPathCount( IUT, V1, V5, 1, 5 );
-
- verifyPathCount( IUT, V2, V1, 0, 5 );
- verifyPathCount( IUT, V2, V3, 0, 5 );
- verifyPathCount( IUT, V2, V4, 0, 5 );
- verifyPathCount( IUT, V2, V5, 0, 5 );
-
- verifyPathCount( IUT, V3, V1, 0, 5 );
- verifyPathCount( IUT, V3, V2, 0, 5 );
- verifyPathCount( IUT, V3, V4, 1, 5 );
- verifyPathCount( IUT, V3, V5, 1, 5 );
-
- verifyPathCount( IUT, V4, V1, 0, 5 );
- verifyPathCount( IUT, V4, V2, 0, 5 );
- verifyPathCount( IUT, V4, V3, 0, 5 );
- verifyPathCount( IUT, V4, V5, 0, 5 );
-
- verifyPathCount( IUT, V5, V1, 0, 5 );
- verifyPathCount( IUT, V5, V2, 0, 5 );
- verifyPathCount( IUT, V5, V3, 0, 5 );
- verifyPathCount( IUT, V5, V4, 0, 5 );
- }
-
- public void verifyHasNextFalse( final AllPaths IUT,
- final Vertex start,
- final Vertex end )
- throws Throwable {
-
- for (int i = 0; i < 5; i++) {
- // This is run many times, because there
- // may be a race condition in it.
- Thread t = new Thread( new Runnable() {
- public void run() {
- Iterator iter = IUT.findPaths( start, end );
- if (iter.hasNext()) iter.next();
- boolean val = iter.hasNext();
- }
- });
-
- t.start();
- t.join( 1000 );
-
- assertTrue("Iterator didn't return from hasNext in one second.",
- !t.isAlive());
- }
-
-
- Iterator iter = IUT.findPaths( start, end );
- if (iter.hasNext()) iter.next();
-
- assertTrue("Iterator has too many elements.",
- !iter.hasNext());
-
- }
-
- public void verifyHasNextTrue( final AllPaths IUT,
- final Vertex start,
- final Vertex end )
- throws Throwable {
-
- final Iterator iter = IUT.findPaths( start, end );
-
- for (int i = 0; i < 5; i++) {
-
- // This is run many times, because there
- // may be a race condition in it.
- Thread t = new Thread( new Runnable() {
- public void run() {
- if (iter.hasNext()) { iter.next(); }
- }
- });
-
- t.start();
- t.join( 1000 );
-
- assertTrue("Iterator didn't return from hasNext in one second.",
- !t.isAlive());
- }
-
-
- assertTrue("Iterator terminated.",
- iter.hasNext());
-
- }
-
- public void verifyPathCount( AllPaths IUT,
- Vertex start,
- Vertex end,
- int expected,
- int depth ) throws Throwable {
- PathCollector paths = new PathCollector();
-
- IUT.findPaths( paths, start, end, depth );
-
- Iterator pathsIter = paths.iterator();
- while (pathsIter.hasNext()) {
- Path path = (Path) pathsIter.next();
- assertEquals("Path: " + path + " has wrong start.",
- start, path.getStart() );
- assertEquals("Path: " + path + " has wrong end.",
- end, path.getEnd() );
- assertTrue("Path: " + path + " is too long.",
- path.size() <= depth+1 );
- }
-
- assertEquals("Wrong number of paths returned for: " + start + "->" + end,
- expected, paths.size() );
-
-
- }
-
-}
-
-
-
-
-
-
+package org.apache.commons.graph.algorithm.path;
+
+/* ====================================================================
+ * The Apache Software License, Version 1.1
+ *
+ * Copyright (c) 2001 The Apache Software Foundation. All rights
+ * reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, 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 "Apache" and "Apache Software Foundation" and
+ * "Commons" 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",
+ * "Commons", 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 (INCLUDING, 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/>.
+ */
+
+/**
+ * AllPathsTest This tests the All Pairs Shortest Path solution.
+ */
+
+import org.apache.commons.graph.*;
+
+import java.util.Set;
+import java.util.Random;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.AbstractSet;
+
+/**
+ * Description of the Class
+ */
+public class AllPathsTest
+ extends GraphTest
+{
+ /**
+ * PathCollector
+ *
+ * This is the thing that collects Callbacks.
+ */
+ public class PathCollector
+ extends AbstractSet
+ implements PathListener,
+ Set
+ {
+ private Set paths = new HashSet();
+
+ public PathCollector() { }
+
+ public void notifyPath( Path path ) {
+ paths.add( path );
+ }
+
+ public int size() {
+ return paths.size();
+ }
+
+ public Iterator iterator() {
+ return paths.iterator();
+ }
+ }
+
+ private String name = null;
+ private Random random = new Random();
+
+ /**
+ * Constructor for the AllPathsTest object
+ *
+ * @param name
+ */
+ public AllPathsTest(String name)
+ {
+ super(name);
+ this.name = name;
+ }
+
+ public void testSelfLoop() throws Throwable {
+ AllPaths IUT = new AllPaths( makeSelfLoop() );
+ verifyPathCount( IUT, V1, V1, 1, 1 );
+
+ // Make sure it works with 0. . .
+ verifyPathCount( IUT, V1, V1, 0, 0 );
+
+ for (int i = 0; i < 5; i++) {
+ int r = random.nextInt( 50 );
+ verifyPathCount( IUT, V1, V1, r, r );
+
+ Iterator iter = IUT.findPaths( V1, V1 );
+ for (int j = 0; j < r; j++) {
+ Path path = (Path) iter.next();
+
+ assertEquals( "Path wrong size.",
+ j + 2, path.size() );
+ }
+ }
+
+ }
+
+ public void testDirDoubleVertex()
+ throws Throwable {
+ AllPaths IUT = new AllPaths( makeDirDoubleVertex() );
+
+ verifyPathCount( IUT, V1, V1, 0, 2 );
+ verifyPathCount( IUT, V2, V2, 0, 2 );
+
+ verifyPathCount( IUT, V1, V2, 0, 2 );
+ verifyPathCount( IUT, V2, V1, 0, 2 );
+ }
+
+ /**
+ * A unit test for JUnit
+ */
+ public void testDirectedEdge()
+ throws Throwable
+ {
+ DirectedGraph g = makeDirectedEdge();
+ final AllPaths IUT = new AllPaths(g);
+
+ verifyPathCount( IUT, V1, V1, 0, 2 );
+ verifyPathCount( IUT, V2, V2, 0, 2 );
+
+ verifyPathCount( IUT, V2, V1, 0, 2 );
+ verifyPathCount( IUT, V1, V2, 1, 2 );
+
+ verifyPathCount( IUT, V1, V2, 1, 1 );
+
+ // Make sure that no matter how big it
+ // is, it still only returns 1 path.
+ for (int i = 0; i < 5; i++) {
+ int r = random.nextInt( 50 );
+
+ r += 5;
+ verifyPathCount( IUT, V1, V2, 1, r );
+
+ }
+
+ verifyHasNextFalse( IUT, V1, V2 );
+ }
+
+ public void testDirParallelEdges() throws Throwable {
+ AllPaths IUT = new AllPaths( makeDirParallelEdges() );
+ verifyPathCount( IUT, V1, V1, 0, 2 );
+ verifyPathCount( IUT, V2, V2, 0, 2 );
+
+ verifyPathCount( IUT, V1, V2, 2, 2 );
+ verifyPathCount( IUT, V2, V1, 0, 2 );
+ }
+
+ public void testTwoCycle() throws Throwable {
+ AllPaths IUT = new AllPaths( makeTwoCycle() );
+ verifyPathCount( IUT, V1, V1, 1, 2 );
+ verifyPathCount( IUT, V2, V2, 1, 2 );
+
+
+ verifyPathCount( IUT, V1, V2, 1, 2 );
+ verifyPathCount( IUT, V2, V1, 1, 2 );
+ }
+
+ public void testDirectedCycle() throws Throwable {
+ AllPaths IUT = new AllPaths( makeDirectedCycle() );
+
+ verifyPathCount( IUT, V1, V1, 1, 3 );
+ verifyPathCount( IUT, V2, V2, 1, 3 );
+ verifyPathCount( IUT, V3, V3, 1, 3 );
+
+
+ verifyPathCount( IUT, V1, V2, 1, 3 );
+ verifyPathCount( IUT, V1, V3, 1, 3 );
+
+ verifyPathCount( IUT, V2, V3, 1, 3 );
+ verifyPathCount( IUT, V2, V1, 1, 3 );
+
+ verifyPathCount( IUT, V3, V1, 1, 3 );
+ verifyPathCount( IUT, V3, V2, 1, 3 );
+
+ for (int i = 0; i < 5; i++) {
+ int r = random.nextInt( 50 );
+ verifyPathCount( IUT, V1, V1, r, 3 * r );
+ }
+
+ verifyHasNextTrue( IUT, V1, V1 );
+
+ }
+
+ public void testDirected4Cycle() throws Throwable {
+ AllPaths IUT = new AllPaths( makeDirected4Cycle() );
+
+ verifyPathCount( IUT, V1, V1, 1, 4 );
+ verifyPathCount( IUT, V2, V2, 1, 4 );
+ verifyPathCount( IUT, V3, V3, 1, 4 );
+ verifyPathCount( IUT, V4, V4, 1, 4 );
+
+
+ verifyPathCount( IUT, V1, V2, 1, 4 );
+ verifyPathCount( IUT, V1, V3, 1, 4 );
+ verifyPathCount( IUT, V1, V4, 1, 4 );
+
+ verifyPathCount( IUT, V2, V1, 1, 4 );
+ verifyPathCount( IUT, V2, V3, 1, 4 );
+ verifyPathCount( IUT, V2, V4, 1, 4 );
+
+ verifyPathCount( IUT, V3, V1, 1, 4 );
+ verifyPathCount( IUT, V3, V2, 1, 4 );
+ verifyPathCount( IUT, V3, V4, 1, 4 );
+
+ verifyPathCount( IUT, V4, V1, 1, 4 );
+ verifyPathCount( IUT, V4, V2, 1, 4 );
+ verifyPathCount( IUT, V4, V3, 1, 4 );
+
+ verifyHasNextTrue( IUT, V1, V1 );
+ }
+
+ public void testCycleNoReturn() throws Throwable {
+ AllPaths IUT = new AllPaths( makeCycleNoReturn() );
+
+ verifyHasNextFalse( IUT, V1, V1 );
+ }
+ public void testPipe() throws Throwable {
+ AllPaths IUT = new AllPaths( makePipe() );
+ verifyPathCount( IUT, V1, V1, 0, 3 );
+ verifyPathCount( IUT, V2, V2, 0, 3 );
+ verifyPathCount( IUT, V3, V3, 0, 3 );
+
+ verifyPathCount( IUT, V1, V2, 1, 3 );
+ verifyPathCount( IUT, V1, V3, 1, 3 );
+
+ verifyPathCount( IUT, V2, V3, 1, 3 );
+ verifyPathCount( IUT, V2, V1, 0, 3 );
+
+ verifyPathCount( IUT, V3, V1, 0, 3 );
+ verifyPathCount( IUT, V3, V2, 0, 3 );
+ }
+
+ public void testDiamond() throws Throwable {
+ AllPaths IUT = new AllPaths( makeDiamond() );
+
+ verifyPathCount( IUT, V1, V1, 0, 4 );
+ verifyPathCount( IUT, V2, V2, 0, 4 );
+ verifyPathCount( IUT, V3, V3, 0, 4 );
+ verifyPathCount( IUT, V4, V4, 0, 4 );
+
+ verifyPathCount( IUT, V1, V2, 1, 4 );
+ verifyPathCount( IUT, V1, V3, 1, 4 );
+ verifyPathCount( IUT, V1, V4, 2, 4 );
+
+ verifyPathCount( IUT, V2, V1, 0, 4 );
+ verifyPathCount( IUT, V2, V3, 0, 4 );
+ verifyPathCount( IUT, V2, V4, 1, 4 );
+
+ verifyPathCount( IUT, V3, V1, 0, 4 );
+ verifyPathCount( IUT, V3, V2, 0, 4 );
+ verifyPathCount( IUT, V3, V4, 1, 4 );
+
+ verifyPathCount( IUT, V4, V1, 0, 4 );
+ verifyPathCount( IUT, V4, V2, 0, 4 );
+ verifyPathCount( IUT, V4, V3, 0, 4 );
+ }
+
+ public void testPipelessCycle() throws Throwable {
+ AllPaths IUT = new AllPaths( makePipelessCycle() );
+
+ verifyPathCount( IUT, V1, V1, 0, 4 );
+ verifyPathCount( IUT, V2, V2, 0, 4 );
+ verifyPathCount( IUT, V3, V3, 0, 4 );
+ verifyPathCount( IUT, V4, V4, 0, 4 );
+
+ verifyPathCount( IUT, V1, V2, 1, 4 );
+ verifyPathCount( IUT, V1, V3, 1, 4 );
+ verifyPathCount( IUT, V1, V4, 0, 4 );
+
+ verifyPathCount( IUT, V2, V3, 0, 4 );
+ verifyPathCount( IUT, V2, V4, 0, 4 );
+ verifyPathCount( IUT, V2, V1, 0, 4 );
+
+ verifyPathCount( IUT, V3, V4, 0, 4 );
+ verifyPathCount( IUT, V3, V1, 0, 4 );
+ verifyPathCount( IUT, V3, V2, 0, 4 );
+
+ verifyPathCount( IUT, V4, V1, 0, 4 );
+ verifyPathCount( IUT, V4, V2, 1, 4 );
+ verifyPathCount( IUT, V4, V3, 1, 4 );
+ }
+
+ public void testParentTree() throws Throwable {
+ AllPaths IUT = new AllPaths( makeParentTree() );
+
+ verifyPathCount( IUT, V1, V1, 0, 5 );
+ verifyPathCount( IUT, V2, V2, 0, 5 );
+ verifyPathCount( IUT, V3, V3, 0, 5 );
+ verifyPathCount( IUT, V4, V4, 0, 5 );
+ verifyPathCount( IUT, V5, V5, 0, 5 );
+
+
+ verifyPathCount( IUT, V1, V2, 0, 5 );
+ verifyPathCount( IUT, V1, V3, 0, 5 );
+ verifyPathCount( IUT, V1, V4, 0, 5 );
+ verifyPathCount( IUT, V1, V5, 0, 5 );
+
+ verifyPathCount( IUT, V2, V1, 1, 5 );
+ verifyPathCount( IUT, V2, V3, 0, 5 );
+ verifyPathCount( IUT, V2, V4, 0, 5 );
+ verifyPathCount( IUT, V2, V5, 0, 5 );
+
+ verifyPathCount( IUT, V3, V1, 1, 5 );
+ verifyPathCount( IUT, V3, V2, 0, 5 );
+ verifyPathCount( IUT, V3, V4, 0, 5 );
+ verifyPathCount( IUT, V3, V5, 0, 5 );
+
+ verifyPathCount( IUT, V4, V1, 1, 5 );
+ verifyPathCount( IUT, V4, V2, 0, 5 );
+ verifyPathCount( IUT, V4, V3, 1, 5 );
+ verifyPathCount( IUT, V4, V5, 0, 5 );
+
+ verifyPathCount( IUT, V5, V1, 1, 5 );
+ verifyPathCount( IUT, V5, V2, 0, 5 );
+ verifyPathCount( IUT, V5, V3, 1, 5 );
+ verifyPathCount( IUT, V5, V4, 0, 5 );
+ }
+
+ public void testChildTree() throws Throwable {
+ AllPaths IUT = new AllPaths( makeChildTree() );
+
+ verifyPathCount( IUT, V1, V1, 0, 5 );
+ verifyPathCount( IUT, V2, V2, 0, 5 );
+ verifyPathCount( IUT, V3, V3, 0, 5 );
+ verifyPathCount( IUT, V4, V4, 0, 5 );
+ verifyPathCount( IUT, V5, V5, 0, 5 );
+
+ verifyPathCount( IUT, V1, V2, 1, 5 );
+ verifyPathCount( IUT, V1, V3, 1, 5 );
+ verifyPathCount( IUT, V1, V4, 1, 5 );
+ verifyPathCount( IUT, V1, V5, 1, 5 );
+
+ verifyPathCount( IUT, V2, V1, 0, 5 );
+ verifyPathCount( IUT, V2, V3, 0, 5 );
+ verifyPathCount( IUT, V2, V4, 0, 5 );
+ verifyPathCount( IUT, V2, V5, 0, 5 );
+
+ verifyPathCount( IUT, V3, V1, 0, 5 );
+ verifyPathCount( IUT, V3, V2, 0, 5 );
+ verifyPathCount( IUT, V3, V4, 1, 5 );
+ verifyPathCount( IUT, V3, V5, 1, 5 );
+
+ verifyPathCount( IUT, V4, V1, 0, 5 );
+ verifyPathCount( IUT, V4, V2, 0, 5 );
+ verifyPathCount( IUT, V4, V3, 0, 5 );
+ verifyPathCount( IUT, V4, V5, 0, 5 );
+
+ verifyPathCount( IUT, V5, V1, 0, 5 );
+ verifyPathCount( IUT, V5, V2, 0, 5 );
+ verifyPathCount( IUT, V5, V3, 0, 5 );
+ verifyPathCount( IUT, V5, V4, 0, 5 );
+ }
+
+ public void verifyHasNextFalse( final AllPaths IUT,
+ final Vertex start,
+ final Vertex end )
+ throws Throwable {
+
+ for (int i = 0; i < 5; i++) {
+ // This is run many times, because there
+ // may be a race condition in it.
+ Thread t = new Thread( new Runnable() {
+ public void run() {
+ Iterator iter = IUT.findPaths( start, end );
+ if (iter.hasNext()) iter.next();
+ boolean val = iter.hasNext();
+ }
+ });
+
+ t.start();
+ t.join( 1000 );
+
+ assertTrue("Iterator didn't return from hasNext in one second.",
+ !t.isAlive());
+ }
+
+
+ Iterator iter = IUT.findPaths( start, end );
+ if (iter.hasNext()) iter.next();
+
+ assertTrue("Iterator has too many elements.",
+ !iter.hasNext());
+
+ }
+
+ public void verifyHasNextTrue( final AllPaths IUT,
+ final Vertex start,
+ final Vertex end )
+ throws Throwable {
+
+ final Iterator iter = IUT.findPaths( start, end );
+
+ for (int i = 0; i < 5; i++) {
+
+ // This is run many times, because there
+ // may be a race condition in it.
+ Thread t = new Thread( new Runnable() {
+ public void run() {
+ if (iter.hasNext()) { iter.next(); }
+ }
+ });
+
+ t.start();
+ t.join( 1000 );
+
+ assertTrue("Iterator didn't return from hasNext in one second.",
+ !t.isAlive());
+ }
+
+
+ assertTrue("Iterator terminated.",
+ iter.hasNext());
+
+ }
+
+ public void verifyPathCount( AllPaths IUT,
+ Vertex start,
+ Vertex end,
+ int expected,
+ int depth ) throws Throwable {
+ PathCollector paths = new PathCollector();
+
+ IUT.findPaths( paths, start, end, depth );
+
+ Iterator pathsIter = paths.iterator();
+ while (pathsIter.hasNext()) {
+ Path path = (Path) pathsIter.next();
+ assertEquals("Path: " + path + " has wrong start.",
+ start, path.getStart() );
+ assertEquals("Path: " + path + " has wrong end.",
+ end, path.getEnd() );
+ assertTrue("Path: " + path + " is too long.",
+ path.size() <= depth+1 );
+ }
+
+ assertEquals("Wrong number of paths returned for: " + start + "->" + end,
+ expected, paths.size() );
+
+
+ }
+
+}
+
+
+
+
+
+
1.2 +0 -6 jakarta-commons-sandbox/graph2/src/test/org/apache/commons/graph/decorator/TransposeTest.java
Index: TransposeTest.java
===================================================================
RCS file: /home/cvs/jakarta-commons-sandbox/graph2/src/test/org/apache/commons/graph/decorator/TransposeTest.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- TransposeTest.java 17 Mar 2002 16:28:19 -0000 1.1
+++ TransposeTest.java 1 Jan 2003 02:14:39 -0000 1.2
@@ -54,12 +54,6 @@
* <http://www.apache.org/>.
*/
-import java.util.Set;
-import java.util.Map;
-import java.util.HashSet;
-import java.util.HashMap;
-import java.util.Iterator;
-
import org.apache.commons.graph.*;
/**
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>