demo/lp_maxflow_demo.cc
author deba
Wed, 01 Mar 2006 10:25:30 +0000
changeset 1991 d7442141d9ef
parent 1875 98698b69a902
child 2369 6ae1a97055a2
permissions -rw-r--r--
The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.

The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.

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