9 //#include <graph_wrapper.h> |
9 //#include <graph_wrapper.h> |
10 #include <lemon/preflow.h> |
10 #include <lemon/preflow.h> |
11 #include <augmenting_flow.h> |
11 #include <augmenting_flow.h> |
12 //#include <preflow_res.h> |
12 //#include <preflow_res.h> |
13 #include <lp_solver_wrapper.h> |
13 #include <lp_solver_wrapper.h> |
|
14 #include <min_cost_gen_flow.h> |
14 |
15 |
15 // Use a DIMACS max flow file as stdin. |
16 // Use a DIMACS max flow file as stdin. |
16 // max_flow_demo < dimacs_max_flow_file |
17 // max_flow_demo < dimacs_max_flow_file |
17 |
18 |
18 using namespace lemon; |
19 using namespace lemon; |
19 |
|
20 namespace lemon { |
|
21 |
|
22 template<typename Edge, typename EdgeIndexMap> |
|
23 class PrimalMap { |
|
24 protected: |
|
25 LPSolverWrapper* lp; |
|
26 EdgeIndexMap* edge_index_map; |
|
27 public: |
|
28 PrimalMap(LPSolverWrapper& _lp, EdgeIndexMap& _edge_index_map) : |
|
29 lp(&_lp), edge_index_map(&_edge_index_map) { } |
|
30 double operator[](Edge e) const { |
|
31 return lp->getPrimal((*edge_index_map)[e]); |
|
32 } |
|
33 }; |
|
34 |
|
35 // excess: rho-delta |
|
36 template <typename Graph, typename Num, |
|
37 typename Excess=typename Graph::template NodeMap<Num>, |
|
38 typename LCapMap=typename Graph::template EdgeMap<Num>, |
|
39 typename CapMap=typename Graph::template EdgeMap<Num>, |
|
40 typename FlowMap=typename Graph::template EdgeMap<Num>, |
|
41 typename CostMap=typename Graph::template EdgeMap<Num> > |
|
42 class MinCostGenFlow { |
|
43 protected: |
|
44 const Graph& g; |
|
45 const Excess& excess; |
|
46 const LCapMap& lcapacity; |
|
47 const CapMap& capacity; |
|
48 FlowMap& flow; |
|
49 const CostMap& cost; |
|
50 public: |
|
51 MinCostGenFlow(const Graph& _g, const Excess& _excess, |
|
52 const LCapMap& _lcapacity, const CapMap& _capacity, |
|
53 FlowMap& _flow, |
|
54 const CostMap& _cost) : |
|
55 g(_g), excess(_excess), lcapacity(_lcapacity), |
|
56 capacity(_capacity), flow(_flow), cost(_cost) { } |
|
57 void run() { |
|
58 LPSolverWrapper lp; |
|
59 lp.setMinimize(); |
|
60 typedef LPSolverWrapper::ColIt ColIt; |
|
61 typedef LPSolverWrapper::RowIt RowIt; |
|
62 typedef typename Graph::template EdgeMap<ColIt> EdgeIndexMap; |
|
63 EdgeIndexMap edge_index_map(g); |
|
64 PrimalMap<typename Graph::Edge, EdgeIndexMap> lp_flow(lp, edge_index_map); |
|
65 for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) { |
|
66 ColIt col_it=lp.addCol(); |
|
67 edge_index_map.set(e, col_it); |
|
68 if (lcapacity[e]==capacity[e]) |
|
69 lp.setColBounds(col_it, LPX_FX, lcapacity[e], capacity[e]); |
|
70 else |
|
71 lp.setColBounds(col_it, LPX_DB, lcapacity[e], capacity[e]); |
|
72 lp.setObjCoef(col_it, cost[e]); |
|
73 } |
|
74 for (typename Graph::NodeIt n(g); n!=INVALID; ++n) { |
|
75 typename Graph::template EdgeMap<Num> coeffs(g, 0); |
|
76 for (typename Graph::InEdgeIt e(g, n); e!=INVALID; ++e) |
|
77 coeffs.set(e, coeffs[e]+1); |
|
78 for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) |
|
79 coeffs.set(e, coeffs[e]-1); |
|
80 RowIt row_it=lp.addRow(); |
|
81 typename std::vector< std::pair<ColIt, double> > row; |
|
82 //std::cout << "node:" <<g.id(n)<<std::endl; |
|
83 for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) { |
|
84 if (coeffs[e]!=0) { |
|
85 //std::cout << " edge:" <<g.id(e)<<" "<<coeffs[e]; |
|
86 row.push_back(std::make_pair(edge_index_map[e], coeffs[e])); |
|
87 } |
|
88 } |
|
89 //std::cout << std::endl; |
|
90 lp.setRowCoeffs(row_it, row.begin(), row.end()); |
|
91 lp.setRowBounds(row_it, LPX_FX, 0.0, 0.0); |
|
92 } |
|
93 lp.solveSimplex(); |
|
94 //std::cout << lp.colNum() << std::endl; |
|
95 //std::cout << lp.rowNum() << std::endl; |
|
96 //std::cout << "flow value: "<< lp.getObjVal() << std::endl; |
|
97 for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) |
|
98 flow.set(e, lp_flow[e]); |
|
99 } |
|
100 }; |
|
101 |
|
102 } |
|
103 |
20 |
104 int main(int, char **) { |
21 int main(int, char **) { |
105 |
22 |
106 typedef ListGraph MutableGraph; |
23 typedef ListGraph MutableGraph; |
107 typedef SmartGraph Graph; |
24 typedef SmartGraph Graph; |