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 |
---|