1 // -*- c++ -*- |
1 // -*- c++ -*- |
2 #ifndef LEMON_MIN_COST_GEN_FLOW_H |
2 #ifndef LEMON_MIN_COST_GEN_FLOW_H |
3 #define LEMON_MIN_COST_GEN_FLOW_H |
3 #define LEMON_MIN_COST_GEN_FLOW_H |
4 //#include <iostream> |
4 #include <iostream> |
5 //#include <fstream> |
5 //#include <fstream> |
6 |
6 |
7 //#include <lemon/smart_graph.h> |
7 #include <lemon/smart_graph.h> |
8 //#include <lemon/list_graph.h> |
8 #include <lemon/list_graph.h> |
9 //#include <lemon/dimacs.h> |
9 //#include <lemon/dimacs.h> |
10 //#include <lemon/time_measure.h> |
10 //#include <lemon/time_measure.h> |
11 //#include <graph_wrapper.h> |
11 //#include <graph_wrapper.h> |
12 //#include <lemon/preflow.h> |
12 #include <lemon/preflow.h> |
13 //#include <augmenting_flow.h> |
13 //#include <augmenting_flow.h> |
14 //#include <preflow_res.h> |
14 //#include <preflow_res.h> |
|
15 #include <../merge_node_graph_wrapper.h> |
15 #include <lemon/../work/marci/lp/lp_solver_wrapper.h> |
16 #include <lemon/../work/marci/lp/lp_solver_wrapper.h> |
16 |
17 |
17 namespace lemon { |
18 namespace lemon { |
18 |
19 |
19 template<typename Edge, typename EdgeIndexMap> |
20 template<typename Edge, typename EdgeIndexMap> |
49 const LCapMap& _lcapacity, const CapMap& _capacity, |
50 const LCapMap& _lcapacity, const CapMap& _capacity, |
50 FlowMap& _flow, |
51 FlowMap& _flow, |
51 const CostMap& _cost) : |
52 const CostMap& _cost) : |
52 g(_g), excess(_excess), lcapacity(_lcapacity), |
53 g(_g), excess(_excess), lcapacity(_lcapacity), |
53 capacity(_capacity), flow(_flow), cost(_cost) { } |
54 capacity(_capacity), flow(_flow), cost(_cost) { } |
|
55 bool feasible() { |
|
56 // std::cout << "making new vertices..." << std::endl; |
|
57 typedef ListGraph Graph2; |
|
58 Graph2 g2; |
|
59 typedef MergeEdgeGraphWrapper<const Graph, Graph2> GW; |
|
60 // std::cout << "merging..." << std::endl; |
|
61 GW gw(g, g2); |
|
62 typename GW::Node s(INVALID, g2.addNode(), true); |
|
63 typename GW::Node t(INVALID, g2.addNode(), true); |
|
64 typedef SmartGraph Graph3; |
|
65 // std::cout << "making extender graph..." << std::endl; |
|
66 typedef NewEdgeSetGraphWrapper2<GW, Graph3> GWW; |
|
67 // { |
|
68 // checkConcept<StaticGraph, GWW>(); |
|
69 // } |
|
70 GWW gww(gw); |
|
71 typedef AugmentingGraphWrapper<GW, GWW> GWWW; |
|
72 GWWW gwww(gw, gww); |
|
73 |
|
74 // std::cout << "making new edges..." << std::endl; |
|
75 typename GWWW::template EdgeMap<Num> translated_cap(gwww); |
|
76 |
|
77 for (typename GW::EdgeIt e(gw); e!=INVALID; ++e) |
|
78 translated_cap.set(typename GWWW::Edge(e,INVALID,false), |
|
79 capacity[e]-lcapacity[e]); |
|
80 |
|
81 Num expected=0; |
|
82 |
|
83 // std::cout << "making new edges 2..." << std::endl; |
|
84 for (typename Graph::NodeIt n(g); n!=INVALID; ++n) { |
|
85 Num a=0; |
|
86 for (typename Graph::InEdgeIt e(g, n); e!=INVALID; ++e) |
|
87 a+=lcapacity[e]; |
|
88 for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) |
|
89 a-=lcapacity[e]; |
|
90 if (excess[n]>a) { |
|
91 typename GWW::Edge e= |
|
92 gww.addEdge(typename GW::Node(n,INVALID,false), t); |
|
93 translated_cap.set(typename GWWW::Edge(INVALID, e, true), |
|
94 excess[n]-a); |
|
95 } |
|
96 if (excess[n]<a) { |
|
97 typename GWW::Edge e= |
|
98 gww.addEdge(s, typename GW::Node(n,INVALID,false)); |
|
99 translated_cap.set(typename GWWW::Edge(INVALID, e, true), |
|
100 a-excess[n]); |
|
101 expected+=a-excess[n]; |
|
102 } |
|
103 } |
|
104 |
|
105 // std::cout << "preflow..." << std::endl; |
|
106 typename GWWW::template EdgeMap<Num> translated_flow(gwww, 0); |
|
107 Preflow<GWWW, Num> preflow(gwww, s, t, |
|
108 translated_cap, translated_flow); |
|
109 preflow.run(); |
|
110 // std::cout << "fv: " << preflow.flowValue() << std::endl; |
|
111 // std::cout << "expected: " << expected << std::endl; |
|
112 |
|
113 for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) { |
|
114 typename GW::Edge ew(e, INVALID, false); |
|
115 typename GWWW::Edge ewww(ew, INVALID, false); |
|
116 flow.set(e, translated_flow[ewww]+lcapacity[e]); |
|
117 } |
|
118 return (expected>=preflow.flowValue()); |
|
119 } |
54 void run() { |
120 void run() { |
55 LPSolverWrapper lp; |
121 LPSolverWrapper lp; |
56 lp.setMinimize(); |
122 lp.setMinimize(); |
57 typedef LPSolverWrapper::ColIt ColIt; |
123 typedef LPSolverWrapper::ColIt ColIt; |
58 typedef LPSolverWrapper::RowIt RowIt; |
124 typedef LPSolverWrapper::RowIt RowIt; |