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