src/demo/lp_demo.cc
author deba
Sat, 09 Apr 2005 19:27:48 +0000
changeset 1330 52ef02524468
parent 1322 cfc26d103bcf
permissions -rw-r--r--
Heap concept moved to namespace concept.
alpar@1309
     1
#include<lemon/lp_glpk.h>
alpar@1309
     2
#include<lemon/graph_reader.h>
alpar@1309
     3
#include<lemon/list_graph.h>
alpar@1309
     4
alpar@1309
     5
using namespace lemon;
alpar@1309
     6
alpar@1309
     7
template<class G,class C>
alpar@1309
     8
double maxFlow(const G &g,const C &cap,typename G::Node s,typename G::Node t)
alpar@1309
     9
{
alpar@1309
    10
  LpGlpk lp;
alpar@1309
    11
  
alpar@1309
    12
  typedef G Graph;
alpar@1309
    13
  typedef typename G::Node Node;
alpar@1309
    14
  typedef typename G::NodeIt NodeIt;
alpar@1309
    15
  typedef typename G::Edge Edge;
alpar@1309
    16
  typedef typename G::EdgeIt EdgeIt;
alpar@1309
    17
  typedef typename G::OutEdgeIt OutEdgeIt;
alpar@1309
    18
  typedef typename G::InEdgeIt InEdgeIt;
alpar@1309
    19
  
alpar@1309
    20
  typename G::template EdgeMap<LpGlpk::Col> x(g);
alpar@1309
    21
  lp.addColSet(x);
alpar@1309
    22
  
alpar@1309
    23
  for(EdgeIt e(g);e!=INVALID;++e) {
alpar@1309
    24
    lp.colUpperBound(x[e],cap[e]);
alpar@1309
    25
    lp.colLowerBound(x[e],0);
alpar@1309
    26
  }
alpar@1309
    27
alpar@1309
    28
  for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) {
alpar@1309
    29
    LpGlpk::Expr ex;
alpar@1309
    30
    for(InEdgeIt  e(g,n);e!=INVALID;++e) ex+=x[e];
alpar@1309
    31
    for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e];
alpar@1309
    32
    lp.addRow(ex==0);
alpar@1309
    33
  }
alpar@1309
    34
  {
alpar@1309
    35
    LpGlpk::Expr ex;
alpar@1309
    36
    for(InEdgeIt  e(g,t);e!=INVALID;++e) ex+=x[e];
alpar@1309
    37
    for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e];
alpar@1309
    38
    lp.setObj(ex);
alpar@1309
    39
  }
alpar@1322
    40
  lp.max();
alpar@1326
    41
alpar@1326
    42
  lp.presolver(true);
alpar@1326
    43
  
alpar@1326
    44
  lp.messageLevel(3);
alpar@1326
    45
alpar@1309
    46
  lp.solve();
alpar@1309
    47
alpar@1322
    48
  return lp.primalValue();
alpar@1309
    49
}
alpar@1309
    50
alpar@1309
    51
int main() 
alpar@1309
    52
{
alpar@1309
    53
  ListGraph g;
alpar@1322
    54
  ListGraph::Node s;
alpar@1322
    55
  ListGraph::Node t;
alpar@1322
    56
  
alpar@1309
    57
  ListGraph::EdgeMap<double> cap(g);
alpar@1309
    58
  
alpar@1309
    59
  GraphReader<ListGraph> reader(std::cin,g);
alpar@1322
    60
  reader.addNode("source",s).addNode("target",t)
alpar@1322
    61
    .addEdgeMap("capacity",cap).run();
alpar@1309
    62
  
alpar@1322
    63
  // std::ifstream file("../test/preflow_");
alpar@1322
    64
//   readDimacs(file, g, cap, s, t);
alpar@1322
    65
alpar@1322
    66
  std::cout << "Max flow value = " << maxFlow(g,cap,s,t) << std::endl;
alpar@1309
    67
alpar@1309
    68
}