COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/lp/max_flow_expression.cc @ 1143:4fb22cfa5759

Last change on this file since 1143:4fb22cfa5759 was 1143:4fb22cfa5759, checked in by marci, 15 years ago

The pair of setSomeThing function is getSomeThing.

File size: 3.3 KB
Line 
1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4
5#include <lemon/graph_utils.h>
6#include <lemon/smart_graph.h>
7#include <lemon/list_graph.h>
8#include <lemon/dimacs.h>
9#include <lemon/time_measure.h>
10#include <lp_solver_base.h>
11
12using std::cout;
13using std::endl;
14using namespace lemon;
15
16template<typename Edge, typename EdgeIndexMap>
17class PrimalMap {
18protected:
19  LPGLPK* lp;
20  EdgeIndexMap* edge_index_map;
21public:
22  PrimalMap(LPGLPK& _lp, EdgeIndexMap& _edge_index_map) :
23    lp(&_lp), edge_index_map(&_edge_index_map) { }
24  double operator[](Edge e) const {
25    return lp->getPrimal((*edge_index_map)[e]);
26  }
27};
28
29// Use a DIMACS max flow file as stdin.
30// max_flow_expresion < dimacs_max_flow_file
31
32int main(int, char **) {
33
34  typedef ListGraph Graph;
35  typedef Graph::Node Node;
36  typedef Graph::Edge Edge;
37  typedef Graph::EdgeIt EdgeIt;
38
39  Graph g;
40 
41  Node s, t;
42  Graph::EdgeMap<int> cap(g);
43  readDimacs(std::cin, g, cap, s, t);
44  Timer ts;
45 
46  typedef LPGLPK LPSolver;
47  LPSolver lp;
48  lp.setMaximize();
49  typedef LPSolver::ColIt ColIt;
50  typedef LPSolver::RowIt RowIt;
51  typedef Graph::EdgeMap<ColIt> EdgeIndexMap;
52  typedef Graph::NodeMap<RowIt> NodeIndexMap;
53  EdgeIndexMap edge_index_map(g);
54  NodeIndexMap node_index_map(g);
55  PrimalMap<Edge, EdgeIndexMap> flow(lp, edge_index_map);
56
57  // nonnegativity of flow and capacity function
58  for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
59    ColIt col_it=lp.addCol();
60    edge_index_map.set(e, col_it);
61    // interesting property in GLPK:
62    // if you change the order of the following two lines, the
63    // two runs of GLPK are extremely different
64      lp.setColLowerBound(col_it, 0);
65      lp.setColUpperBound(col_it, cap[e]);
66  }
67 
68  for (Graph::NodeIt n(g); n!=INVALID; ++n) {
69    LPSolver::Expression expr;
70    for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e)
71      expr+=edge_index_map[e];
72    for (Graph::InEdgeIt e(g, n); e!=INVALID; ++e)
73      expr-=edge_index_map[e];
74    // cost function
75    if (n==s) {
76      lp.setObjCoeffs(expr);     
77    }
78    // flow conservation constraints
79    if ((n!=s) && (n!=t)) {
80      RowIt row_it=lp.addRow();
81      node_index_map.set(n, row_it);
82      lp.setRowCoeffs(row_it, expr);
83      lp.setRowLowerBound(row_it, 0.0);
84      lp.setRowUpperBound(row_it, 0.0);
85//       cout << expr << endl;
86//       {
87//      LPSolver::Expression expr;
88//      lp.getRowCoeffs(node_index_map[n], expr);       
89//      cout << expr << endl;
90//       }
91    }
92  }
93  lp.solveSimplex();
94//   cout << "num of nodes: " << countNodes(g) << endl;
95//   cout << "num of edges: " << countEdges(g) << endl;
96//   cout << "num of rows: " << lp.rowNum() << endl;
97//   cout << "num of rows: " << lp.int_row_map.size() << endl;
98//   for (int i=0; i<lp.int_row_map.size(); ++i) {
99//     cout << lp.int_row_map[i] << " " << endl;
100//   }
101//   cout << "num of columns: " << lp.colNum() << endl;
102//   cout << "num of columns: " << lp.int_col_map.size() << endl;
103//   for (int i=0; i<lp.int_col_map.size(); ++i) {
104//     cout << lp.int_col_map[i] << " " << endl;
105//   }
106  cout << "elapsed time: " << ts << endl;
107//   Graph::NodeIt n(g);
108//   ++n;
109//   for(Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) {
110//     cout << edge_index_map[e] << endl;
111//   }
112//   for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) {
113//     cout << edge_index_map[e] << endl;
114//   }
115//   LPSolver::DualExpression expr;
116//   lp.getRowCoeffs(node_index_map[n], expr);
117//   cout << expr << endl;
118}
Note: See TracBrowser for help on using the repository browser.