Coverage Report - net.sourceforge.combean.graph.alg.flow.MinCostFlowByLPAlg
 
Classes in this File Line Coverage Branch Coverage Complexity
MinCostFlowByLPAlg
86%
43/50
57%
8/14
1,9
 
 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.graph.alg.flow;
 23  
 
 24  
 import org.apache.commons.logging.Log;
 25  
 import org.apache.commons.logging.LogFactory;
 26  
 
 27  
 import net.sourceforge.combean.graph.alg.AbstractGraphAlg;
 28  
 import net.sourceforge.combean.graph.alg.lp.EdgesAsLPVariableSequence;
 29  
 import net.sourceforge.combean.graph.alg.lp.GraphAsLPModelColumns;
 30  
 import net.sourceforge.combean.graph.alg.lp.LPModelSolverAsFixedDoubleEdgeMap;
 31  
 import net.sourceforge.combean.graph.alg.lp.NodesAsLPConstraintSequence;
 32  
 import net.sourceforge.combean.graph.containers.doubleval.ScalingDoubleNodeMapDecorator;
 33  
 import net.sourceforge.combean.interfaces.graph.alg.flow.MinCostFlowAlg;
 34  
 import net.sourceforge.combean.interfaces.graph.containers.doubleval.FixedDoubleEdgeMap;
 35  
 import net.sourceforge.combean.interfaces.graph.containers.doubleval.FixedDoubleNodeMap;
 36  
 import net.sourceforge.combean.interfaces.graph.prop.GlobalNumberedGraphProp;
 37  
 import net.sourceforge.combean.interfaces.graph.prop.NeighborhoodGraphProp;
 38  
 import net.sourceforge.combean.interfaces.mathprog.lp.LPConstraint;
 39  
 import net.sourceforge.combean.interfaces.mathprog.lp.LPSolver;
 40  
 import net.sourceforge.combean.interfaces.mathprog.lp.model.LPModelSolver;
 41  
 import net.sourceforge.combean.mathprog.lp.model.ConstructableLPModel;
 42  
 import net.sourceforge.combean.mathprog.lp.model.LPModelSolverWithSequentialLoading;
 43  
 import net.sourceforge.combean.util.except.IllegalParameterException;
 44  
 
 45  
 /**
 46  
  * An implementation of a min-cost flow algorithm using an LP solver.
 47  
  * 
 48  
  * @author schickin
 49  
  *
 50  
  */
 51  
 public class MinCostFlowByLPAlg extends AbstractGraphAlg implements
 52  
         MinCostFlowAlg {
 53  
     
 54  3
     private static Log log = LogFactory.getLog(MinCostFlowByLPAlg.class);
 55  
     
 56  9
     private NeighborhoodGraphProp neigh = null;
 57  9
     private GlobalNumberedGraphProp numberedGraph = null;
 58  
     
 59  9
     private LPSolver lpSolver = null;
 60  9
     private LPModelSolver lpModelSolver = null;
 61  
     
 62  9
     private FixedDoubleNodeMap inflow = null;
 63  
     
 64  9
     private FixedDoubleEdgeMap edgeWeights = null;
 65  9
     private FixedDoubleEdgeMap edgeCapacities = null;
 66  
 
 67  
     /**
 68  
      * constructor
 69  
      */
 70  
     public MinCostFlowByLPAlg() {
 71  9
         super();
 72  9
     }
 73  
 
 74  
     /**
 75  
      * @param lpModelLoader
 76  
      */
 77  
     public final void setLpModelLoader(LPModelSolver lpModelLoader) {
 78  0
         this.lpModelSolver = lpModelLoader;
 79  0
     }
 80  
 
 81  
     /**
 82  
      * @param lpSolver The lpSolver to set.
 83  
      */
 84  
     public final void setLpSolver(LPSolver lpSolver) {
 85  9
         this.lpSolver = lpSolver;
 86  9
     }
 87  
 
 88  
     /* (non-Javadoc)
 89  
      * @see net.sourceforge.combean.interfaces.graph.alg.flow.MinCostFlowAlg#setEdgeWeightsMap(net.sourceforge.combean.interfaces.graph.containers.doubleval.FixedDoubleEdgeMap)
 90  
      */
 91  
     public void setEdgeWeightsMap(FixedDoubleEdgeMap edgeWeights) {
 92  9
         this.edgeWeights = edgeWeights;
 93  9
     }
 94  
 
 95  
     /* (non-Javadoc)
 96  
      * @see net.sourceforge.combean.interfaces.graph.alg.flow.FeasibleFlowAlg#setInflowMap(net.sourceforge.combean.interfaces.graph.containers.doubleval.FixedDoubleNodeMap)
 97  
      */
 98  
     public void setInflowMap(FixedDoubleNodeMap inflowMap) {
 99  9
         this.inflow = inflowMap;
 100  9
     }
 101  
 
 102  
     /* (non-Javadoc)
 103  
      * @see net.sourceforge.combean.interfaces.graph.alg.flow.AbstractFlowAlg#setEdgeCapacityMap(net.sourceforge.combean.interfaces.graph.containers.doubleval.FixedDoubleEdgeMap)
 104  
      */
 105  
     public void setEdgeCapacityMap(FixedDoubleEdgeMap edgeCapacities) {
 106  9
         this.edgeCapacities = edgeCapacities;
 107  9
     }
 108  
 
 109  
     /* (non-Javadoc)
 110  
      * @see net.sourceforge.combean.interfaces.graph.alg.GraphAlgorithm#run()
 111  
      */
 112  
     public void run() {
 113  9
         if (this.lpModelSolver == null) {
 114  9
             this.lpModelSolver = new LPModelSolverWithSequentialLoading();
 115  
         }
 116  9
         if (this.lpSolver == null) {
 117  0
             throw new IllegalParameterException("LP-solver must be set.");
 118  
         }
 119  9
         this.lpModelSolver.setLPSolver(this.lpSolver);
 120  
 
 121  9
         GraphAsLPModelColumns networkLPComponent =
 122  
             new GraphAsLPModelColumns("flow", "bal", this.neigh);
 123  
 
 124  9
         NodesAsLPConstraintSequence nodeFlowBalanceConstraints =
 125  
             new NodesAsLPConstraintSequence("bal", this.numberedGraph);
 126  9
         nodeFlowBalanceConstraints.setNodeRhs(
 127  
                 new ScalingDoubleNodeMapDecorator(this.inflow, -1.0));
 128  9
         nodeFlowBalanceConstraints.setRelation(LPConstraint.REL_EQUAL);
 129  
 
 130  9
         EdgesAsLPVariableSequence edgeFlowVariables =
 131  
             new EdgesAsLPVariableSequence("flow", this.numberedGraph);
 132  9
         edgeFlowVariables.setEdgeCost(this.edgeWeights);
 133  9
         edgeFlowVariables.setEdgeUpperBound(this.edgeCapacities);
 134  
         
 135  9
         ConstructableLPModel lpModel = new ConstructableLPModel();
 136  9
         lpModel.addConstraintSequence(nodeFlowBalanceConstraints);
 137  9
         lpModel.addVariableSequence(edgeFlowVariables);
 138  9
         lpModel.appendModelComponent(networkLPComponent);
 139  
         
 140  9
         this.lpModelSolver.loadModel(lpModel);
 141  
 
 142  9
         if (log.isInfoEnabled()) {
 143  0
             log.info("Starting LP-solver " + this.lpModelSolver.getLPSolver());
 144  
         }
 145  
 
 146  9
         this.lpModelSolver.solve();
 147  
         
 148  9
         if (log.isInfoEnabled()) {
 149  0
             log.info("LP-solver terminated with state " +
 150  
                     this.lpSolver.getSolutionStatus());
 151  
         }
 152  
 
 153  9
         if (this.lpSolver.getSolutionStatus() == LPSolver.LPSTAT_FAILURE) {
 154  0
             throw new IllegalParameterException("LP-solver failed");
 155  
         }
 156  9
         if (this.lpSolver.getSolutionStatus() == LPSolver.LPSTAT_UNBOUNDED) {
 157  0
             throw new IllegalParameterException("LP-solver returns unbounded flow");
 158  
         }
 159  9
     }
 160  
 
 161  
     /* (non-Javadoc)
 162  
      * @see net.sourceforge.combean.interfaces.graph.alg.flow.FeasibleFlowAlg#isFeasible()
 163  
      */
 164  
     public boolean isFeasible() {
 165  9
          return this.lpSolver.getSolutionStatus() == LPSolver.LPSTAT_SOLVED;
 166  
     }
 167  
 
 168  
     /* (non-Javadoc)
 169  
      * @see net.sourceforge.combean.interfaces.graph.alg.flow.MinCostFlowAlg#getTotalCost()
 170  
      */
 171  
     public double getTotalCost() {
 172  3
          return this.lpSolver.getSolutionValue();
 173  
     }
 174  
 
 175  
     /* (non-Javadoc)
 176  
      * @see net.sourceforge.combean.interfaces.graph.alg.flow.AbstractFlowAlg#getFlowMap()
 177  
      */
 178  
     public FixedDoubleEdgeMap getFlowMap() {
 179  3
          return new LPModelSolverAsFixedDoubleEdgeMap(this.lpModelSolver,
 180  
                  this.numberedGraph, "flow");
 181  
     }
 182  
 }