demo/lp_maxflow_demo.cc
author hegyi
Thu, 12 Jan 2006 15:24:24 +0000
changeset 1893 4a35c7847c77
parent 1641 77f6ab7ad66f
child 1956 a055123339d5
permissions -rw-r--r--
Documenatation of MapWin.
     1 /* -*- C++ -*-
     2  * demo/lp_maxflow_demo.cc - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 ///\ingroup demos
    18 ///\file
    19 ///\brief Max flow problem solved with an LP solver (demo).
    20 ///
    21 /// This demo program shows how to solve a maximum (or maximal) flow
    22 /// problem using the LEMON LP solver interface. We would like to lay
    23 /// the emphasis on the simplicity of the way one can formulate LP
    24 /// constraints that arise in graph theory in our library LEMON .
    25 ///
    26 /// \include lp_maxflow_demo.cc
    27 
    28 #include<lemon/graph_reader.h>
    29 #include<lemon/list_graph.h>
    30 #include <lemon/lp.h>
    31 
    32 #include <fstream>
    33 #include <iostream>
    34 
    35 
    36 
    37 using namespace lemon;
    38 
    39 template<class G,class C>
    40 double maxFlow(const G &g,const C &cap,typename G::Node s,typename G::Node t)
    41 {
    42   Lp lp;
    43   
    44   typedef G Graph;
    45   typedef typename G::Node Node;
    46   typedef typename G::NodeIt NodeIt;
    47   typedef typename G::Edge Edge;
    48   typedef typename G::EdgeIt EdgeIt;
    49   typedef typename G::OutEdgeIt OutEdgeIt;
    50   typedef typename G::InEdgeIt InEdgeIt;
    51   
    52   //Define a map on the edges for the variables of the LP problem
    53   typename G::template EdgeMap<Lp::Col> x(g);
    54   lp.addColSet(x);
    55   
    56   //Nonnegativity and capacity constraints
    57   for(EdgeIt e(g);e!=INVALID;++e) {
    58     lp.colUpperBound(x[e],cap[e]);
    59     lp.colLowerBound(x[e],0);
    60   }
    61 
    62 
    63   //Flow conservation constraints for the nodes (except for 's' and 't')
    64   for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) {
    65     Lp::Expr ex;
    66     for(InEdgeIt  e(g,n);e!=INVALID;++e) ex+=x[e];
    67     for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e];
    68     lp.addRow(ex==0);
    69   }
    70   
    71   //Objective function: the flow value entering 't'
    72   Lp::Expr obj;
    73   for(InEdgeIt  e(g,t);e!=INVALID;++e) obj+=x[e];
    74   for(OutEdgeIt e(g,t);e!=INVALID;++e) obj-=x[e];
    75   lp.setObj(obj);
    76 
    77 
    78   //Maximization
    79   lp.max();
    80 
    81 #if DEFAULT_LP==GLPK
    82   lp.presolver(true);
    83   lp.messageLevel(3);
    84 #endif
    85 
    86   std::cout<<"Solver used: "<<default_solver_name<<std::endl;
    87 
    88   //Solve with the underlying solver
    89   lp.solve();
    90 
    91   return lp.primalValue();
    92 }
    93 
    94 int main(int argc, char *argv[]) 
    95 {
    96   if(argc<2)
    97   {
    98       std::cerr << "  USAGE: lp_maxflow_demo input_file.lgf" << std::endl;
    99       std::cerr << "  The file 'input_file.lgf' has to contain a max "
   100 		<< "flow instance in\n"
   101 		<< "  LEMON format (e.g. sample.lgf is such a file)."
   102 		<< std::endl;
   103       return 0;
   104   }
   105 
   106 
   107   //input stream to read the graph from
   108   std::ifstream is(argv[1]);
   109 
   110 
   111   ListGraph g;
   112   ListGraph::Node s;
   113   ListGraph::Node t;
   114   
   115   ListGraph::EdgeMap<double> cap(g);
   116   
   117   GraphReader<ListGraph> reader(is,g);
   118   reader.readNode("source",s).readNode("target",t)
   119     .readEdgeMap("capacity",cap).run();
   120   
   121   std::cout << "Max flow value = " << maxFlow(g,cap,s,t) << std::endl;
   122 
   123 }