Coverage Report - net.sourceforge.combean.test.graph.alg.flow.AbstractTestMinCostFlowAlg
 
Classes in this File Line Coverage Branch Coverage Complexity
AbstractTestMinCostFlowAlg
100%
50/50
N/A
1
 
 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 30.08.2005
 20  
  *
 21  
  */
 22  
 package net.sourceforge.combean.test.graph.alg.flow;
 23  
 
 24  
 import junit.framework.TestCase;
 25  
 import net.sourceforge.combean.graph.containers.doubleval.EdgeMapAsDoubleEdgeMap;
 26  
 import net.sourceforge.combean.graph.containers.doubleval.NodeMapAsDoubleNodeMap;
 27  
 import net.sourceforge.combean.graph.prop.statics.ConstructableNumberedGraphBuilder;
 28  
 import net.sourceforge.combean.interfaces.graph.alg.flow.MinCostFlowAlg;
 29  
 import net.sourceforge.combean.interfaces.graph.containers.doubleval.DoubleEdgeMap;
 30  
 import net.sourceforge.combean.interfaces.graph.containers.doubleval.DoubleNodeMap;
 31  
 import net.sourceforge.combean.interfaces.graph.prop.ConstructableNumberedGraphProp;
 32  
 import net.sourceforge.combean.test.helpers.checks.CheckGraph;
 33  
 import net.sourceforge.combean.test.helpers.factories.GraphFixtureFactory;
 34  
 
 35  
 /**
 36  
  * @author schickin
 37  
  *
 38  
  */
 39  
 public abstract class AbstractTestMinCostFlowAlg extends TestCase {
 40  
     
 41  9
     private MinCostFlowAlg minCostAlg = null;
 42  
 
 43  9
     private ConstructableNumberedGraphProp constructG = null;
 44  
     
 45  3
     private static int[][] edges = {
 46  
             {0, 1},
 47  
             {0, 2},
 48  
             {2, 1},
 49  
             {1, 3},
 50  
             {2, 3}
 51  
     };
 52  
     
 53  3
     private static final double[] inflow = {10, 0, 0, -10};
 54  3
     private static final double[] edgeWeights = {0.0, 2.0, 5.0, 1.0, 10.0};
 55  3
     private static final double[] edgeCapacities =
 56  
     {2.0, 100.0, 200.0, 5.0, 50.0};
 57  3
     private static final double[] expectedFlow = {2.0, 8.0, 3.0, 5.0, 5.0};
 58  
     private static final double flowCost = 2*0 + 8*2 + 3*5 + 5*1 + 5*10;
 59  
     
 60  9
     private DoubleNodeMap inflowMap = null;
 61  9
     private DoubleEdgeMap capacityMap = null;
 62  9
     private DoubleEdgeMap weightMap = null;
 63  
 
 64  
     /*
 65  
      * @see TestCase#setUp()
 66  
      */
 67  
     protected void setUp() throws Exception {
 68  9
         super.setUp();
 69  
  
 70  9
         this.constructG = GraphFixtureFactory.createConstructableNumberedGraph();
 71  
         
 72  9
         ConstructableNumberedGraphBuilder builder =
 73  
             new ConstructableNumberedGraphBuilder(this.constructG);
 74  
         
 75  9
         builder.addNodes(inflow.length);
 76  9
         builder.addEdges(edges);
 77  
         
 78  9
         this.inflowMap = new NodeMapAsDoubleNodeMap();
 79  9
         builder.fillDoubleNodeMap(this.inflowMap, inflow);
 80  
         
 81  9
         this.capacityMap = new EdgeMapAsDoubleEdgeMap();
 82  9
         builder.fillDoubleEdgeMap(this.capacityMap, edgeCapacities);
 83  9
         this.weightMap = new EdgeMapAsDoubleEdgeMap();
 84  9
         builder.fillDoubleEdgeMap(this.weightMap, edgeWeights);
 85  
         
 86  9
         this.minCostAlg = createMinCostFlowAlg();
 87  
         
 88  9
         this.minCostAlg.setGraph(this.constructG);
 89  9
     }
 90  
 
 91  
     /*
 92  
      * @see TestCase#tearDown()
 93  
      */
 94  
     protected void tearDown() throws Exception {
 95  9
         super.tearDown();
 96  9
     }
 97  
 
 98  
     /**
 99  
      * Constructor for AbstractTestMinCostFlowAlg.
 100  
      * @param name
 101  
      */
 102  
     public AbstractTestMinCostFlowAlg(String name) {
 103  9
         super(name);
 104  9
     }
 105  
 
 106  
     protected abstract MinCostFlowAlg createMinCostFlowAlg();
 107  
     
 108  
     public void testInfeasibleFlowDueToMissingCapacities() {
 109  
         // restrict the capacitiy on the edge 2->3
 110  3
         this.capacityMap.putDouble(this.constructG.getEdge(4), 2.0);
 111  
         
 112  3
         this.minCostAlg.setInflowMap(this.inflowMap);
 113  3
         this.minCostAlg.setEdgeCapacityMap(this.capacityMap);
 114  3
         this.minCostAlg.setEdgeWeightsMap(this.weightMap);
 115  
         
 116  3
         this.minCostAlg.run();
 117  
         
 118  3
         assertFalse(this.minCostAlg.isFeasible());
 119  3
     }
 120  
 
 121  
     public final void testInfeasibleFlowDueToUnbalancedInflow() {
 122  3
         this.inflowMap.putDouble(this.constructG.getNode(0), 5.0);
 123  
         
 124  3
         this.minCostAlg.setInflowMap(this.inflowMap);
 125  3
         this.minCostAlg.setEdgeCapacityMap(this.capacityMap);
 126  3
         this.minCostAlg.setEdgeWeightsMap(this.weightMap);
 127  
         
 128  3
         this.minCostAlg.run();
 129  
         
 130  3
         assertFalse(this.minCostAlg.isFeasible());
 131  3
     }
 132  
 
 133  
     public final void testFeasibleFlow() {
 134  3
         this.minCostAlg.setInflowMap(this.inflowMap);
 135  3
         this.minCostAlg.setEdgeCapacityMap(this.capacityMap);
 136  3
         this.minCostAlg.setEdgeWeightsMap(this.weightMap);
 137  
         
 138  3
         this.minCostAlg.run();
 139  
         
 140  3
         assertTrue(this.minCostAlg.isFeasible());
 141  3
         assertEquals(flowCost, this.minCostAlg.getTotalCost(), 0.0);
 142  3
         CheckGraph.checkDoubleEdgeMap(this.constructG,
 143  
                 this.minCostAlg.getFlowMap(),
 144  
                 expectedFlow, 0.0 /* tolerance */);
 145  3
     }
 146  
 }