commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From d..@apache.org
Subject cvs commit: jakarta-commons-sandbox/graph2/src/test/org/apache/commons/graph/algorithm/util LabelTest.java
Date Wed, 08 May 2002 18:19:14 GMT
ddp         02/05/08 11:19:14

  Added:       graph2/src/test/org/apache/commons/graph/algorithm/path
                        AllPairsTest.java AllPathsTest.java
               graph2/src/test/org/apache/commons/graph/algorithm/spanning
                        MinimumSpanningForestTest.java
               graph2/src/test/org/apache/commons/graph/algorithm/util
                        LabelTest.java
  Log:
  Making tests which mirror package structure.
  
  Revision  Changes    Path
  1.1                  jakarta-commons-sandbox/graph2/src/test/org/apache/commons/graph/algorithm/path/AllPairsTest.java
  
  Index: AllPairsTest.java
  ===================================================================
  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));
          }
      }
  }
  
  
  
  1.1                  jakarta-commons-sandbox/graph2/src/test/org/apache/commons/graph/algorithm/path/AllPathsTest.java
  
  Index: AllPathsTest.java
  ===================================================================
  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() );
  
  
      }
  
  }
  
  
  
  
  
  
  
  
  
  1.1                  jakarta-commons-sandbox/graph2/src/test/org/apache/commons/graph/algorithm/spanning/MinimumSpanningForestTest.java
  
  Index: MinimumSpanningForestTest.java
  ===================================================================
  package org.apache.commons.graph.algorithm.spanning;
  
  import java.util.Set;
  
  import org.apache.commons.graph.*;
  import org.apache.commons.graph.exception.*;
  
  public class MinimumSpanningForestTest
    extends WeightedGraphTest
  {
    private String name = null;
  
    public MinimumSpanningForestTest( String name ) {
      super( name );
      this.name = name;
    }
  
    public void testNullGraph() throws Throwable {
      WeightedGraph graph = (WeightedGraph) makeNullGraph();
      MinimumSpanningForest msf = 
        new MinimumSpanningForest( graph );
      verifyGraph( msf, 0, 0 );
      verifyChords( msf, makeSet() );
    }
    
    public void testDirNullGraph() throws Throwable {
      WeightedGraph graph = (WeightedGraph) makeDirNullGraph();
      MinimumSpanningForest msf =
        new MinimumSpanningForest( graph );
      verifyGraph( msf, 0, 0 );
      verifyChords( msf, makeSet() );
    }
  
    public void testSingleVertex() throws Throwable {
      WeightedGraph graph = (WeightedGraph) makeSingleVertex();
      MinimumSpanningForest msf =
        new MinimumSpanningForest( graph );
      verifyGraph( msf, 1, 0 );
      verifyChords( msf, makeSet() );
    }
  
    public void testDirSingleVertex() throws Throwable {
      WeightedGraph graph = (WeightedGraph) makeDirSingleVertex();
      MinimumSpanningForest msf =
        new MinimumSpanningForest( graph );
      verifyGraph( msf, 1, 0 );
      verifyChords( msf, makeSet() );
    }
  
    public void testSelfLoop() throws Throwable {
      WeightedGraph graph = (WeightedGraph) makeSelfLoop();
      MinimumSpanningForest msf =
        new MinimumSpanningForest( graph );
      verifyGraph( msf, 1, 0 );
  
      verifyChords(msf, makeSet( V1_V1 ));
    }
  
    public void testDoubleVertex() throws Throwable {
      WeightedGraph graph = (WeightedGraph) makeDoubleVertex();
      MinimumSpanningForest msf = 
        new MinimumSpanningForest( graph );
      verifyGraph( msf, 2, 0 );
      verifyChords(msf, makeSet() );
    }
  
    public void testDirDoubleVertex() throws Throwable {
      WeightedGraph graph = (WeightedGraph) makeDirDoubleVertex();
      MinimumSpanningForest msf =
        new MinimumSpanningForest( graph );
      verifyGraph( msf, 2, 0 );
      verifyChords( msf, makeSet() );
    }
  
    public void testSingleEdge() throws Throwable {
      WeightedGraph graph = (WeightedGraph) makeSingleEdge();
      MinimumSpanningForest msf =
        new MinimumSpanningForest( graph );
      verifyGraph( msf, 2, 1 );
      verifyChords( msf, makeSet());
    }
  
    public void testDirectedEdge() throws Throwable {
      WeightedGraph graph = (WeightedGraph) makeDirectedEdge();
      MinimumSpanningForest msf =
        new MinimumSpanningForest( graph );
      verifyGraph( msf, 2, 1 );
      verifyChords( msf, makeSet());
    }
  
    public void testParallelEdges() throws Throwable {
      WeightedGraph graph = (WeightedGraph) makeParallelEdges();
      MinimumSpanningForest msf =
        new MinimumSpanningForest( graph );
      verifyGraph( msf, 2, 1 );
    }
  
    public void testDirParallelEdges() throws Throwable {
      WeightedGraph graph = (WeightedGraph) makeDirParallelEdges();
      MinimumSpanningForest msf =
        new MinimumSpanningForest( graph );
      verifyGraph( msf, 2, 1 );
    }
  
    public void testCycle() throws Throwable {
      WeightedGraph graph = (WeightedGraph) makeCycle();
      MinimumSpanningForest msf =
        new MinimumSpanningForest( graph );
      verifyGraph( msf, 3, 2 );
    }
  
    public void testTwoCycle() throws Throwable {
      WeightedGraph graph = (WeightedGraph) makeTwoCycle();
      MinimumSpanningForest msf =
        new MinimumSpanningForest( graph );
      verifyGraph( msf, 2, 1 );
    }
  
    public void testDirectedCycle() throws Throwable {
      WeightedGraph graph = (WeightedGraph) makeDirectedCycle();
      MinimumSpanningForest msf =
        new MinimumSpanningForest( graph );
      verifyGraph( msf, 3, 2 );
    }
  
    public void testNoCycle() throws Throwable {
      WeightedGraph graph = (WeightedGraph) makeNoCycle();
      MinimumSpanningForest msf =
        new MinimumSpanningForest( graph );
      verifyGraph( msf, 3, 2 );
    }
  
    public void testPipe() throws Throwable {
      WeightedGraph graph = (WeightedGraph) makePipe();
      MinimumSpanningForest msf =
        new MinimumSpanningForest( graph );
      verifyGraph( msf, 3, 2 );
    }
  
    public void testDiamond() throws Throwable {
      WeightedGraph graph = (WeightedGraph) makeDiamond();
      MinimumSpanningForest msf =
        new MinimumSpanningForest( graph );
      verifyGraph( msf, 4, 3 );
    }
  
    public void testPipelessCycle() throws Throwable {
      WeightedGraph graph = (WeightedGraph) makePipelessCycle();
      MinimumSpanningForest msf =
        new MinimumSpanningForest( graph );
      verifyGraph( msf, 4, 3 );
    }
  
    public void testHyperGraph() throws Throwable {
      WeightedGraph graph = (WeightedGraph) makeHyperGraph();
      try {
        MinimumSpanningForest msf =
  	new MinimumSpanningForest( graph );
        fail("HyperGraph Exception not thrown.");
      } catch (HyperGraphException hge) { }
    }
  
    public void testWDirectedEdge()
      throws Throwable
    {
      WeightedGraph graph = makeWDirectedEdge();
      
      MinimumSpanningForest msf = 
        new MinimumSpanningForest( graph );
      
      verifyGraph( msf, 2, 1 );
      verifyEdges( msf, makeSet( V1_V2 ) );
      assertEquals("Edge Weight not the same.",
  		 5.0, msf.getWeight(V1_V2), 0.00001 );
      verifyChords( msf, makeSet() );
    }
  
    public void testWSelfLoop()
      throws Throwable
    {
      MinimumSpanningForest IUT = 
        new MinimumSpanningForest( makeWSelfLoop() );
      verifyGraph(IUT, 1, 0);
      verifyEdges(IUT, makeSet() );
      verifyChords(IUT, makeSet( V1_V1 ));
    }
  
    public void testPositiveCycle() 
      throws Throwable
    {
      MinimumSpanningForest IUT =
        new MinimumSpanningForest( makePositiveCycle() );
      verifyGraph( IUT, 3, 2 );
      verifyEdges( IUT, makeSet( V3_V1, V1_V2 ));
      verifyChords( IUT, makeSet( V2_V3 ));
    }
  
    public void testPositivePartNegCycle()
      throws Throwable
    {
      MinimumSpanningForest IUT =
        new MinimumSpanningForest( makePositivePartNegCycle() );
      verifyGraph( IUT, 3, 2 );
      verifyEdges( IUT, makeSet( V3_V1, V1_V2 ) );
      verifyChords( IUT, makeSet( V2_V3 ));
    }
  
    public void testNegativeCycle()
      throws Throwable
    {
      MinimumSpanningForest IUT =
        new MinimumSpanningForest( makeNegativeCycle() );
      
      verifyGraph( IUT, 3, 2 );
      verifyEdges( IUT, makeSet( V2_V3, V1_V2 ));
      verifyChords( IUT, makeSet( V3_V1 ));
    }
  
    public void testNegativePartPosCycle()
      throws Throwable
    {
      MinimumSpanningForest IUT =
        new MinimumSpanningForest( makeNegativePartPosCycle() );
      
      verifyGraph( IUT, 3, 2 );
      verifyEdges( IUT, makeSet( V2_V3, V1_V2 ));
      verifyChords( IUT, makeSet( V3_V1 ));
    }
  
    public void testPositivePipe()
      throws Throwable
    {
      MinimumSpanningForest IUT =
        new MinimumSpanningForest( makePositivePipe() );
      
      verifyGraph( IUT, 3, 2 );
      verifyEdges( IUT, makeSet( V1_V2, V2_V3 ));
      verifyChords(IUT, makeSet());
    }
  
    public void testPositivePartNegPipe()
      throws Throwable
    {
      MinimumSpanningForest IUT =
        new MinimumSpanningForest( makePositivePartNegPipe() );
      
      verifyGraph( IUT, 3, 2 );
      verifyEdges( IUT, makeSet( V1_V2, V2_V3 ));
      verifyChords(IUT,  makeSet());
    }
  
    public void testNegativePipe()
      throws Throwable
    {
      MinimumSpanningForest IUT =
        new MinimumSpanningForest( makeNegativePipe() );
      
      verifyGraph( IUT, 3, 2 );
      verifyEdges( IUT, makeSet( V1_V2, V2_V3 ));
      verifyChords(IUT, makeSet());
    }
  
    public void testNegativePartPosPipe()
      throws Throwable
    {
      MinimumSpanningForest IUT =
        new MinimumSpanningForest( makeNegativePartPosPipe() );
      
      verifyGraph( IUT, 3, 2 );
      verifyEdges( IUT, makeSet( V1_V2, V2_V3 ));
      verifyChords(IUT, makeSet());
    }
  
    public void testMultiplePathL()
      throws Throwable
    {
      MinimumSpanningForest IUT =
        new MinimumSpanningForest( makeMultiplePathL() );
      
      verifyGraph( IUT, 4, 3 );
      verifyEdges( IUT, makeSet( V1_V2, V2_V4, V1_V3 ));
      verifyChords(IUT, makeSet( V3_V4 ));
    }
  
    public void testMultiplePathR()
      throws Throwable
    {
      MinimumSpanningForest IUT =
        new MinimumSpanningForest( makeMultiplePathR() );
      
      verifyGraph( IUT, 4, 3 );
      verifyEdges( IUT, makeSet( V1_V3, V3_V4, V2_V4 ));
      verifyChords(IUT, makeSet( V1_V2 ));
    }
  
    public void testMultiplePathEarlyLow()
      throws Throwable
    {
      MinimumSpanningForest IUT =
        new MinimumSpanningForest( makeMultiplePathEarlyLow() );
      
      verifyGraph( IUT, 4, 3 );
      verifyEdges( IUT, makeSet( V1_V2, V2_V4, V1_V3 ));
      verifyChords(IUT, makeSet( V3_V4 ));
    }
    public void testMaxMultiplePathEarlyLow()
      throws Throwable
    {
      MinimumSpanningForest IUT =
        new MinimumSpanningForest( false, 
  				 makeMultiplePathEarlyLow() );
      
      verifyGraph( IUT, 4, 3 );
      verifyEdges( IUT, makeSet( V1_V2, V2_V4, V3_V4 ));
      verifyChords(IUT, makeSet( V1_V3 ));
    }
  
    public void testMultiplePathEarlyHigh()
      throws Throwable
    {
      MinimumSpanningForest IUT =
        new MinimumSpanningForest( makeMultiplePathEarlyHigh() );
  
      verifyGraph( IUT, 4, 3 );
      verifyEdges( IUT, makeSet( V1_V2, V2_V4, V3_V4 ) );
      verifyChords(IUT, makeSet( V1_V3 ));
    }
  
    public void testMaxMultiplePathEarlyHigh()
      throws Throwable
    {
      MinimumSpanningForest IUT =
        new MinimumSpanningForest( false, 
  				 makeMultiplePathEarlyHigh());
      
      verifyGraph( IUT, 4, 3 );
      verifyEdges( IUT, makeSet( V1_V2, V2_V4, V1_V3 ));
      verifyChords(IUT, makeSet( V3_V4 ));
    }
  
    
    // Helpers. . .
      
    public void verifyEdges(Graph g, 
  			  Set edges) throws Throwable {
      Set gEdges = g.getEdges();
      assertTrue( "Graph has edges not in expected set.",
  		gEdges.containsAll( edges ));
      assertTrue( "Graph does not have expected edges.",
  		edges.containsAll( edges ));
    }
  
    public void verifyChords(MinimumSpanningForest msf, 
  			  Set chords) throws Throwable {
      Set gChords = msf.getChords();
      assertTrue( "Graph has chords not in expected set.",
  		gChords.containsAll( chords ));
      assertTrue( "Graph does not have expected edges.",
  		chords.containsAll( gChords ));
    }
  
  }
  
  
  
  
  
  
  
  
  1.1                  jakarta-commons-sandbox/graph2/src/test/org/apache/commons/graph/algorithm/util/LabelTest.java
  
  Index: LabelTest.java
  ===================================================================
  package org.apache.commons.graph.algorithm.util;
  
  import junit.framework.*;
  
  public class LabelTest
    extends TestCase
  {
    private String testName = null;
  
    public LabelTest( String testName ) {
      super( testName );
      this.testName = testName;
    }
  
    private Label L1;
    private Label L1_;
    private Label L1__;
    private Label L2;
    private Label L3;
    private Label L4;
    private Label L5;
    private Label L6;
  
    public void setUp() {
      L1 = new Label();
      L2 = new Label();
      L3 = new Label();
      L4 = new Label();
      L5 = new Label();
      L6 = new Label();
  
      L1_ = new Label( L1 );
  
      L1__ = new Label( L1_ );
    }
  
    public void testDefaultConfig()
      throws Throwable
    {
      assertEquals( L1.getRoot(), L1 );
      assertEquals( L1_.getRoot(), L1 );
      assertEquals( L1__.getRoot(), L1 );
    }
  
    public void testSetRoot1() 
      throws Throwable
    {
      assertEquals( L1.getRoot(), L1 );
      assertEquals( L2.getRoot(), L2 );
  
      L2.setRoot( L1 );
      assertEquals( L2.getRoot(), L1 );
    }
  
    public void testSetRoot2()
      throws Throwable
    {
      assertEquals( L1.getRoot(), L1 );
      assertEquals( L2.getRoot(), L2 );
      assertEquals( L3.getRoot(), L3 );
  
      L3.setRoot( L2 );
      L2.setRoot( L1 );
      
      assertEquals( L3.getRoot(), L1 );
      assertEquals( L2.getRoot(), L1 );
      assertEquals( L1.getRoot(), L1 );
    }
  
    public void testSetRoot3() 
      throws Throwable
    {
      assertEquals( L1.getRoot(), L1 );
      assertEquals( L2.getRoot(), L2 );
      assertEquals( L3.getRoot(), L3 );
  
      L2.setRoot( L1 );
      L3.setRoot( L2 );
  
      assertEquals( L3.getRoot(), L1 );
      assertEquals( L2.getRoot(), L1 );
      assertEquals( L1.getRoot(), L1 );
    }
  
    public void testSetRoot4()
      throws Throwable
    { 
      assertEquals( L1.getRoot(), L1 );
      assertEquals( L2.getRoot(), L2 );
      assertEquals( L3.getRoot(), L3 );
      assertEquals( L4.getRoot(), L4 );
  
      L4.setRoot( L3 );
      L2.setRoot( L1 );
      L3.setRoot( L1 );
  
      assertEquals( L4.getRoot(), L1 );
      assertEquals( L3.getRoot(), L1 );
      assertEquals( L2.getRoot(), L1 );
      assertEquals( L1.getRoot(), L1 );
    }
  
    public void testSetRootCycle() 
      throws Throwable
    {
      assertEquals( L1.getRoot(), L1 );
      assertEquals( L2.getRoot(), L2 );
  
      L1.setRoot( L2 );
      L2.setRoot( L1 );
  
      assertEquals( L2.getRoot(), L2 );
      assertEquals( L1.getRoot(), L2 );
    }
  
    public void setDiamond1() throws Throwable {
      assertEquals( L1.getRoot(), L1 );
      assertEquals( L2.getRoot(), L2 );
      assertEquals( L3.getRoot(), L3 );
      assertEquals( L4.getRoot(), L4 );
  
      L2.setRoot( L1 );
      L3.setRoot( L1 );
      L4.setRoot( L3 );
  
      assertEquals( L1.getRoot(), L1 );
      assertEquals( L2.getRoot(), L1 );
      assertEquals( L3.getRoot(), L1 );
      assertEquals( L4.getRoot(), L1 );
    }
  
    public void setDiamond2() throws Throwable {
      assertEquals( L1.getRoot(), L1 );
      assertEquals( L2.getRoot(), L2 );
      assertEquals( L3.getRoot(), L3 );
      assertEquals( L4.getRoot(), L4 );
  
      L4.setRoot( L3 );
      L2.setRoot( L1 );
      L3.setRoot( L1 );
  
      assertEquals( L1.getRoot(), L1 );
      assertEquals( L2.getRoot(), L1 );
      assertEquals( L3.getRoot(), L1 );
      assertEquals( L4.getRoot(), L1 );
    }
  }
  
  
  
  
  
  

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


Mime
View raw message