COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/demo/lp_maxflow_demo.cc @ 1386:324c291a8daf

Last change on this file since 1386:324c291a8daf was 1381:998e8def9676, checked in by Alpar Juttner, 15 years ago
  • lp_cplex.h, lp_cplex.cc added
  • lp_demo.cc and lp_maxflow_demo.cc uses GLPK is it is found CPLEX otherwise
File size: 1.7 KB
Line 
1#include<lemon/graph_reader.h>
2#include<lemon/list_graph.h>
3
4
5#ifdef HAVE_GLPK
6#include <lemon/lp_glpk.h>
7#elif HAVE_CPLEX
8#include <lemon/lp_cplex.h>
9#endif
10
11using namespace lemon;
12
13#ifdef HAVE_GLPK
14typedef LpGlpk LpDefault;
15#elif HAVE_CPLEX
16typedef LpCplex LpDefault;
17#endif
18
19
20template<class G,class C>
21double maxFlow(const G &g,const C &cap,typename G::Node s,typename G::Node t)
22{
23  LpDefault lp;
24 
25  typedef G Graph;
26  typedef typename G::Node Node;
27  typedef typename G::NodeIt NodeIt;
28  typedef typename G::Edge Edge;
29  typedef typename G::EdgeIt EdgeIt;
30  typedef typename G::OutEdgeIt OutEdgeIt;
31  typedef typename G::InEdgeIt InEdgeIt;
32 
33  typename G::template EdgeMap<LpDefault::Col> x(g);
34  lp.addColSet(x);
35 
36  for(EdgeIt e(g);e!=INVALID;++e) {
37    lp.colUpperBound(x[e],cap[e]);
38    lp.colLowerBound(x[e],0);
39  }
40
41  for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) {
42    LpDefault::Expr ex;
43    for(InEdgeIt  e(g,n);e!=INVALID;++e) ex+=x[e];
44    for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e];
45    lp.addRow(ex==0);
46  }
47  {
48    LpDefault::Expr ex;
49    for(InEdgeIt  e(g,t);e!=INVALID;++e) ex+=x[e];
50    for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e];
51    lp.setObj(ex);
52  }
53  lp.max();
54
55#ifdef HAVE_GLPK
56  lp.presolver(true);
57  lp.messageLevel(3);
58#endif
59
60  lp.solve();
61
62  return lp.primalValue();
63}
64
65int main()
66{
67  ListGraph g;
68  ListGraph::Node s;
69  ListGraph::Node t;
70 
71  ListGraph::EdgeMap<double> cap(g);
72 
73  GraphReader<ListGraph> reader(std::cin,g);
74  reader.addNode("source",s).addNode("target",t)
75    .addEdgeMap("capacity",cap).run();
76 
77  // std::ifstream file("../test/preflow_");
78//   readDimacs(file, g, cap, s, t);
79
80  std::cout << "Max flow value = " << maxFlow(g,cap,s,t) << std::endl;
81
82}
Note: See TracBrowser for help on using the repository browser.