44 Timer ts; |
44 Timer ts; |
45 |
45 |
46 typedef LPGLPK LPSolver; |
46 typedef LPGLPK LPSolver; |
47 LPSolver lp; |
47 LPSolver lp; |
48 lp.setMaximize(); |
48 lp.setMaximize(); |
49 typedef LPSolver::ColIt ColIt; |
49 typedef LPSolver::Col Col; |
50 typedef LPSolver::RowIt RowIt; |
50 typedef LPSolver::Row Row; |
51 typedef Graph::EdgeMap<ColIt> EdgeIndexMap; |
51 typedef Graph::EdgeMap<Col> EdgeIndexMap; |
52 typedef Graph::NodeMap<RowIt> NodeIndexMap; |
52 typedef Graph::NodeMap<Row> NodeIndexMap; |
53 EdgeIndexMap edge_index_map(g); |
53 EdgeIndexMap edge_index_map(g); |
54 NodeIndexMap node_index_map(g); |
54 NodeIndexMap node_index_map(g); |
55 PrimalMap<Edge, EdgeIndexMap> flow(lp, edge_index_map); |
55 PrimalMap<Edge, EdgeIndexMap> flow(lp, edge_index_map); |
56 |
56 |
57 // nonnegativity of flow and capacity function |
57 // nonnegativity of flow and capacity function |
58 for (Graph::EdgeIt e(g); e!=INVALID; ++e) { |
58 for (Graph::EdgeIt e(g); e!=INVALID; ++e) { |
59 ColIt col_it=lp.addCol(); |
59 Col col=lp.addCol(); |
60 edge_index_map.set(e, col_it); |
60 edge_index_map.set(e, col); |
61 // interesting property in GLPK: |
61 // interesting property in GLPK: |
62 // if you change the order of the following two lines, the |
62 // if you change the order of the following two lines, the |
63 // two runs of GLPK are extremely different |
63 // two runs of GLPK are extremely different |
64 lp.setColLowerBound(col_it, 0); |
64 lp.setColLowerBound(col, 0); |
65 lp.setColUpperBound(col_it, cap[e]); |
65 lp.setColUpperBound(col, cap[e]); |
66 } |
66 } |
67 |
67 |
68 for (Graph::NodeIt n(g); n!=INVALID; ++n) { |
68 for (Graph::NodeIt n(g); n!=INVALID; ++n) { |
69 LPSolver::Expression expr; |
69 LPSolver::Expression expr; |
70 for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) |
70 for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) |
75 if (n==s) { |
75 if (n==s) { |
76 lp.setObjCoeffs(expr); |
76 lp.setObjCoeffs(expr); |
77 } |
77 } |
78 // flow conservation constraints |
78 // flow conservation constraints |
79 if ((n!=s) && (n!=t)) { |
79 if ((n!=s) && (n!=t)) { |
80 RowIt row_it=lp.addRow(); |
80 node_index_map.set(n, lp.addRow(expr == 0.0)); |
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 } |
81 } |
92 } |
82 } |
93 lp.solveSimplex(); |
83 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; |
84 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 } |
85 } |