Coverage Report - net.sourceforge.combean.test.graph.alg.spath.GraphWithNegativeCycleFixture
 
Classes in this File Line Coverage Branch Coverage Complexity
GraphWithNegativeCycleFixture
100%
23/23
75%
6/8
0
 
 1  
 /*
 2  
     This file is part of Combean.
 3  
 
 4  
     Combean is free software; you can redistribute it and/or modify
 5  
     it under the terms of the GNU General Public License as published by
 6  
     the Free Software Foundation; either version 2 of the License, or
 7  
     (at your option) any later version.
 8  
 
 9  
     Combean is distributed in the hope that it will be useful,
 10  
     but WITHOUT ANY WARRANTY; without even the implied warranty of
 11  
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 12  
     GNU General Public License for more details.
 13  
 
 14  
     You should have received a copy of the GNU General Public License
 15  
     along with Combean; if not, write to the Free Software
 16  
     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 17  
 */
 18  
 /*
 19  
  * Created on 10.04.2005
 20  
  *
 21  
  */
 22  
 package net.sourceforge.combean.test.graph.alg.spath;
 23  
 
 24  
 import net.sourceforge.combean.interfaces.graph.NodeIterator;
 25  
 import net.sourceforge.combean.interfaces.graph.alg.spath.SingleSourceShortestPathWithNegCycleDetectionAlg;
 26  
 import net.sourceforge.combean.interfaces.graph.containers.FixedPath;
 27  
 
 28  
 /**
 29  
  * @author schickin
 30  
  *
 31  
  */
 32  
 public class GraphWithNegativeCycleFixture
 33  
 extends AbstractGraphWithEdgeWeightsFixture {
 34  
 
 35  
     // graph taken from "Network Flows", Ahuja/Magnanti/Orlin, p. 110
 36  
     //
 37  
     //              2
 38  
     //    ----> 2 -----> 4 -----
 39  
     //    |     ^*       |     |
 40  
     //  4 |     | \      |     | 3
 41  
     //    |     |  \   1 |     *
 42  
     //    0   2 |   \    |     5
 43  
     //    |     | -4 \   |     ^
 44  
     //  6 |     |     \  |     |
 45  
     //    |     |      \ *     | 7
 46  
     //    ----> 1 -----> 3 -----
 47  
     //              2
 48  
     //
 49  
     // The shortest path from 1 to 3 is: (1, 3, 5, 6) with length 4+2+3=9
 50  
     //
 51  3
     private static int[][] edgesWithWeights = {
 52  
             {0, 2, 4},
 53  
             {0, 1, 6},
 54  
             {1, 2, 2},
 55  
             {1, 3, 2},
 56  
             {3, 2,-4},
 57  
             {2, 4, 2},
 58  
             {3, 5, 7},
 59  
             {4, 3, 1},
 60  
             {4, 5, 3}
 61  
     };
 62  
 
 63  3
     private static int[] cycleNodes = {2,4,3,2,4,3};
 64  
     
 65  
     /**
 66  
      * constructor
 67  
      */
 68  
     public GraphWithNegativeCycleFixture() throws Exception {
 69  21
         super(6, edgesWithWeights);
 70  21
     }
 71  
     
 72  
     public final void checkNegativeCycleDetection(
 73  
             SingleSourceShortestPathWithNegCycleDetectionAlg<Double> alg) {
 74  3
         runShortestPathAlg(alg);
 75  
         
 76  3
         boolean negCycleFound = alg.hasNegativeCycle();
 77  3
         assertTrue(negCycleFound);
 78  
         
 79  3
         FixedPath cycle = alg.getNegativeCycle();
 80  3
         assertNotNull(cycle);
 81  
         
 82  3
         int idxOfFirstNodeInCycle =
 83  
             this.constructG.getNodeNumber(cycle.getFirstNode());
 84  3
         int startNodeIdx = -1;
 85  6
         for (int i = 0; i < 3; i++) {
 86  6
             if (cycleNodes[i] == idxOfFirstNodeInCycle) {
 87  3
                 startNodeIdx = i;
 88  3
                 break;
 89  
             }
 90  
         }
 91  3
         assertTrue("first node of cycle with number " + idxOfFirstNodeInCycle +
 92  
                 " must belong to cyclenodes array",
 93  
                 -1 != startNodeIdx);
 94  
         
 95  3
         NodeIterator itCycle = cycle.getNodeIterator();
 96  15
         for (int i = 0; i < 4; i++) {
 97  12
             assertTrue("cycle may not end prematurely", itCycle.hasNext());
 98  12
             int currNodeNum = this.constructG.getNodeNumber(itCycle.next());
 99  12
             assertEquals(cycleNodes[startNodeIdx + i], currNodeNum);
 100  
         }
 101  3
         assertFalse("cycle may not have additional nodes", itCycle.hasNext());
 102  3
     }
 103  
 }