1 // -*- C++ -*- |
1 // -*- C++ -*- |
2 |
|
3 /* |
|
4 Heuristics: |
|
5 2 phase |
|
6 gap |
|
7 list 'level_list' on the nodes on level i implemented by hand |
|
8 stack 'active' on the active nodes on level i |
|
9 runs heuristic 'highest label' for H1*n relabels |
|
10 runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label' |
|
11 |
|
12 Parameters H0 and H1 are initialized to 20 and 1. |
|
13 |
|
14 Constructors: |
|
15 |
|
16 Preflow(Graph, Node, Node, CapMap, FlowMap, bool) : bool must be false if |
|
17 FlowMap is not constant zero, and should be true if it is |
|
18 |
|
19 Members: |
|
20 |
|
21 void run() |
|
22 |
|
23 Num flowValue() : returns the value of a maximum flow |
|
24 |
|
25 void minMinCut(CutMap& M) : sets M to the characteristic vector of the |
|
26 minimum min cut. M should be a map of bools initialized to false. ??Is it OK? |
|
27 |
|
28 void maxMinCut(CutMap& M) : sets M to the characteristic vector of the |
|
29 maximum min cut. M should be a map of bools initialized to false. |
|
30 |
|
31 void minCut(CutMap& M) : sets M to the characteristic vector of |
|
32 a min cut. M should be a map of bools initialized to false. |
|
33 |
|
34 */ |
|
35 |
|
36 #ifndef HUGO_MAX_FLOW_H |
2 #ifndef HUGO_MAX_FLOW_H |
37 #define HUGO_MAX_FLOW_H |
3 #define HUGO_MAX_FLOW_H |
38 |
4 |
39 #include <vector> |
5 #include <vector> |
40 #include <queue> |
6 #include <queue> |
45 #include <hugo/invalid.h> |
11 #include <hugo/invalid.h> |
46 #include <hugo/maps.h> |
12 #include <hugo/maps.h> |
47 #include <for_each_macros.h> |
13 #include <for_each_macros.h> |
48 |
14 |
49 /// \file |
15 /// \file |
50 /// \brief Maximum flows. |
16 /// \brief Maximum flow algorithms. |
51 /// \ingroup galgs |
17 /// \ingroup galgs |
52 |
18 |
53 namespace hugo { |
19 namespace hugo { |
54 |
20 |
55 |
21 /// \addtogroup galgs |
56 // ///\author Marton Makai, Jacint Szabo |
22 /// @{ |
57 /// A class for computing max flows and related quantities. |
23 ///Maximum flow algorithms class. |
58 /// \ingroup galgs |
24 |
|
25 ///This class provides various algorithms for finding a flow of |
|
26 ///maximum value in a directed graph. The \e source node, the \e |
|
27 ///target node, the \e capacity of the edges and the \e starting \e |
|
28 ///flow value of the edges can be passed to the algorithm through the |
|
29 ///constructor. It is possible to change these quantities using the |
|
30 ///functions \ref resetSource, \ref resetTarget, \ref resetCap and |
|
31 ///\ref resetFlow. Before any subsequent runs of any algorithm of |
|
32 ///the class \ref resetFlow should be called, otherwise it will |
|
33 ///start from a maximum flow. |
|
34 ///After running an algorithm of the class, the maximum value of a |
|
35 ///value can be obtained by calling \ref flowValue(). The minimum |
|
36 ///value cut can be written into a \c node map of \c bools by |
|
37 ///calling \ref minCut. (\ref minMinCut and \ref maxMinCut writes |
|
38 ///the inclusionwise minimum and maximum of the minimum value |
|
39 ///cuts, resp.) |
|
40 ///\param Graph The undirected graph type the algorithm runs on. |
|
41 ///\param Num The number type of the capacities and the flow values. |
|
42 ///\param CapMap The type of the capacity map. |
|
43 ///\param FlowMap The type of the flow map. |
|
44 ///\author Marton Makai, Jacint Szabo |
59 template <typename Graph, typename Num, |
45 template <typename Graph, typename Num, |
60 typename CapMap=typename Graph::template EdgeMap<Num>, |
46 typename CapMap=typename Graph::template EdgeMap<Num>, |
61 typename FlowMap=typename Graph::template EdgeMap<Num> > |
47 typename FlowMap=typename Graph::template EdgeMap<Num> > |
62 class MaxFlow { |
48 class MaxFlow { |
63 protected: |
49 protected: |
64 typedef typename Graph::Node Node; |
50 typedef typename Graph::Node Node; |
65 typedef typename Graph::NodeIt NodeIt; |
51 typedef typename Graph::NodeIt NodeIt; |
|
52 typedef typename Graph::EdgeIt EdgeIt; |
66 typedef typename Graph::OutEdgeIt OutEdgeIt; |
53 typedef typename Graph::OutEdgeIt OutEdgeIt; |
67 typedef typename Graph::InEdgeIt InEdgeIt; |
54 typedef typename Graph::InEdgeIt InEdgeIt; |
68 |
55 |
69 typedef typename std::vector<std::stack<Node> > VecStack; |
56 typedef typename std::vector<std::stack<Node> > VecStack; |
70 typedef typename Graph::template NodeMap<Node> NNMap; |
57 typedef typename Graph::template NodeMap<Node> NNMap; |
79 typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW; |
66 typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW; |
80 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; |
67 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; |
81 typedef typename ResGW::Edge ResGWEdge; |
68 typedef typename ResGW::Edge ResGWEdge; |
82 //typedef typename ResGW::template NodeMap<bool> ReachedMap; |
69 //typedef typename ResGW::template NodeMap<bool> ReachedMap; |
83 typedef typename Graph::template NodeMap<int> ReachedMap; |
70 typedef typename Graph::template NodeMap<int> ReachedMap; |
|
71 |
|
72 |
|
73 //level works as a bool map in augmenting path algorithms and is |
|
74 //used by bfs for storing reached information. In preflow, it |
|
75 //shows the levels of nodes. |
84 ReachedMap level; |
76 ReachedMap level; |
85 //level works as a bool map in augmenting path algorithms |
77 |
86 //and is used by bfs for storing reached information. |
78 //excess is needed only in preflow |
87 //In preflow, it shows levels of nodes. |
|
88 //typename Graph::template NodeMap<int> level; |
|
89 typename Graph::template NodeMap<Num> excess; |
79 typename Graph::template NodeMap<Num> excess; |
90 // protected: |
80 |
|
81 //fixme |
|
82 // protected: |
91 // MaxFlow() { } |
83 // MaxFlow() { } |
92 // void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, |
84 // void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, |
93 // FlowMap& _flow) |
85 // FlowMap& _flow) |
94 // { |
86 // { |
95 // g=&_G; |
87 // g=&_G; |
106 static const int H0=20; |
98 static const int H0=20; |
107 static const int H1=1; |
99 static const int H1=1; |
108 |
100 |
109 public: |
101 public: |
110 |
102 |
111 ///\todo Document this. |
103 ///Indicates the property of the starting flow. |
112 ///\todo Maybe, it should be PRE_FLOW instead. |
104 |
113 ///- \c NO_FLOW means nothing, |
105 ///Indicates the property of the starting flow. The meanings are as follows: |
114 ///- \c ZERO_FLOW means something, |
106 ///- \c ZERO_FLOW: constant zero flow |
115 ///- \c GEN_FLOW means something else, |
107 ///- \c GEN_FLOW: any flow, i.e. the sum of the in-flows equals to |
116 ///- \c PRE_FLOW is something different. |
108 ///the sum of the out-flows in every node except the \e source and |
|
109 ///the \e target. |
|
110 ///- \c PRE_FLOW: any preflow, i.e. the sum of the in-flows is at |
|
111 ///least the sum of the out-flows in every node except the \e source. |
|
112 ///- \c NO_FLOW: indicates an unspecified edge map. \ref flow will be |
|
113 ///set to the constant zero flow in the beginning of the algorithm in this case. |
117 enum flowEnum{ |
114 enum flowEnum{ |
118 ZERO_FLOW, |
115 ZERO_FLOW, |
119 GEN_FLOW, |
116 GEN_FLOW, |
120 PRE_FLOW, |
117 PRE_FLOW, |
121 NO_FLOW |
118 NO_FLOW |
124 MaxFlow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, |
121 MaxFlow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, |
125 FlowMap& _flow) : |
122 FlowMap& _flow) : |
126 g(&_G), s(_s), t(_t), capacity(&_capacity), |
123 g(&_G), s(_s), t(_t), capacity(&_capacity), |
127 flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {} |
124 flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {} |
128 |
125 |
129 /// A max flow algorithm is run. |
126 ///Runs a maximum flow algorithm. |
130 /// \pre The flow have to satisfy the requirements |
127 |
131 /// stated in fe. |
128 ///Runs a preflow algorithm, which is the fastest maximum flow |
|
129 ///algorithm up-to-date. The default for \c fe is ZERO_FLOW. |
|
130 ///\pre The starting flow must be |
|
131 /// - a constant zero flow if \c fe is \c ZERO_FLOW, |
|
132 /// - an arbitary flow if \c fe is \c GEN_FLOW, |
|
133 /// - an arbitary preflow if \c fe is \c PRE_FLOW, |
|
134 /// - any map if \c fe is NO_FLOW. |
132 void run(flowEnum fe=ZERO_FLOW) { |
135 void run(flowEnum fe=ZERO_FLOW) { |
133 preflow(fe); |
136 preflow(fe); |
134 } |
137 } |
135 |
138 |
136 /// A preflow algorithm is run. |
139 |
137 /// \pre The initial edge-map have to be a |
140 ///Runs a preflow algorithm. |
138 /// zero flow if \c fe is \c ZERO_FLOW, |
141 |
139 /// a flow if \c fe is \c GEN_FLOW, |
142 ///Runs a preflow algorithm. The preflow algorithms provide the |
140 /// a pre-flow if fe is \c PRE_FLOW and |
143 ///fastest way to compute a maximum flow in a directed graph. |
141 /// anything if fe is NO_FLOW. |
144 ///\pre The starting flow must be |
|
145 /// - a constant zero flow if \c fe is \c ZERO_FLOW, |
|
146 /// - an arbitary flow if \c fe is \c GEN_FLOW, |
|
147 /// - an arbitary preflow if \c fe is \c PRE_FLOW, |
|
148 /// - any map if \c fe is NO_FLOW. |
142 void preflow(flowEnum fe) { |
149 void preflow(flowEnum fe) { |
143 preflowPhase0(fe); |
150 preflowPhase1(fe); |
144 preflowPhase1(); |
151 preflowPhase2(); |
145 } |
152 } |
146 |
153 // Heuristics: |
147 /// Run the first phase of preflow, starting from a 0 flow, from a flow, |
154 // 2 phase |
148 /// or from a preflow, of from undefined value according to \c fe. |
155 // gap |
149 void preflowPhase0(flowEnum fe); |
156 // list 'level_list' on the nodes on level i implemented by hand |
150 |
157 // stack 'active' on the active nodes on level i |
151 /// Second phase of preflow. |
158 // runs heuristic 'highest label' for H1*n relabels |
152 void preflowPhase1(); |
159 // runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label' |
|
160 // Parameters H0 and H1 are initialized to 20 and 1. |
|
161 |
|
162 ///Runs the first phase of the preflow algorithm. |
|
163 |
|
164 ///The preflow algorithm consists of two phases, this method runs the |
|
165 ///first phase. After the first phase the maximum flow value and a |
|
166 ///minimum value cut can already be computed, though a maximum flow |
|
167 ///is net yet obtained. So after calling this method \ref flowValue |
|
168 ///and \ref actMinCut gives proper results. |
|
169 ///\warning: \ref minCut, \ref minMinCut and \ref maxMinCut do not |
|
170 ///give minimum value cuts unless calling \ref preflowPhase2. |
|
171 ///\pre The starting flow must be |
|
172 /// - a constant zero flow if \c fe is \c ZERO_FLOW, |
|
173 /// - an arbitary flow if \c fe is \c GEN_FLOW, |
|
174 /// - an arbitary preflow if \c fe is \c PRE_FLOW, |
|
175 /// - any map if \c fe is NO_FLOW. |
|
176 void preflowPhase1( flowEnum fe ); |
|
177 |
|
178 ///Runs the second phase of the preflow algorithm. |
|
179 |
|
180 ///The preflow algorithm consists of two phases, this method runs |
|
181 ///the second phase. After calling \ref preflowPhase1 and then |
|
182 ///\ref preflowPhase2 the methods \ref flowValue, \ref minCut, |
|
183 ///\ref minMinCut and \ref maxMinCut give proper results. |
|
184 ///\pre \ref preflowPhase1 must be called before. |
|
185 void preflowPhase2(); |
153 |
186 |
154 /// Starting from a flow, this method searches for an augmenting path |
187 /// Starting from a flow, this method searches for an augmenting path |
155 /// according to the Edmonds-Karp algorithm |
188 /// according to the Edmonds-Karp algorithm |
156 /// and augments the flow on if any. |
189 /// and augments the flow on if any. |
157 /// The return value shows if the augmentation was succesful. |
190 /// The return value shows if the augmentation was succesful. |
167 /// The same as \c augmentOnBlockingFlow<MutableGraph> but the |
200 /// The same as \c augmentOnBlockingFlow<MutableGraph> but the |
168 /// residual graph is not constructed physically. |
201 /// residual graph is not constructed physically. |
169 /// The return value shows if the augmentation was succesful. |
202 /// The return value shows if the augmentation was succesful. |
170 bool augmentOnBlockingFlow2(); |
203 bool augmentOnBlockingFlow2(); |
171 |
204 |
172 /// Returns the actual flow value. |
205 /// Returns the maximum value of a flow. |
173 /// More precisely, it returns the negative excess of s, thus |
206 |
174 /// this works also for preflows. |
207 /// Returns the maximum value of a flow, by counting the |
|
208 /// over-flow of the target node \ref t. |
|
209 /// It can be called already after running \ref preflowPhase1. |
175 Num flowValue() { |
210 Num flowValue() { |
176 Num a=0; |
211 Num a=0; |
177 FOR_EACH_INC_LOC(InEdgeIt, e, *g, t) a+=(*flow)[e]; |
212 FOR_EACH_INC_LOC(InEdgeIt, e, *g, t) a+=(*flow)[e]; |
178 FOR_EACH_INC_LOC(OutEdgeIt, e, *g, t) a-=(*flow)[e]; |
213 FOR_EACH_INC_LOC(OutEdgeIt, e, *g, t) a-=(*flow)[e]; |
179 return a; |
214 return a; |
180 } |
215 //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan |
181 |
216 } |
182 /// Should be used between preflowPhase0 and preflowPhase1. |
217 |
|
218 ///Returns a minimum value cut after calling \ref preflowPhase1. |
|
219 |
|
220 ///After the first phase of the preflow algorithm the maximum flow |
|
221 ///value and a minimum value cut can already be computed. This |
|
222 ///method can be called after running \ref preflowPhase1 for |
|
223 ///obtaining a minimum value cut. |
|
224 /// \warning Gives proper result only right after calling \ref |
|
225 /// preflowPhase1. |
183 /// \todo We have to make some status variable which shows the |
226 /// \todo We have to make some status variable which shows the |
184 /// actual state |
227 /// actual state |
185 /// of the class. This enables us to determine which methods are valid |
228 /// of the class. This enables us to determine which methods are valid |
186 /// for MinCut computation |
229 /// for MinCut computation |
187 template<typename _CutMap> |
230 template<typename _CutMap> |
270 } |
320 } |
271 } |
321 } |
272 } |
322 } |
273 } |
323 } |
274 |
324 |
275 |
325 ///Returns a minimum value cut. |
276 /// A minimum cut is computed. |
326 |
|
327 ///Sets \c M to the characteristic vector of a minimum value cut. |
|
328 ///\pre M should be a node map of bools initialized to false. |
|
329 ///\pre \c flow must be a maximum flow. |
277 template<typename CutMap> |
330 template<typename CutMap> |
278 void minCut(CutMap& M) { minMinCut(M); } |
331 void minCut(CutMap& M) { minMinCut(M); } |
279 |
332 |
280 /// |
333 ///Resets the source node to \c _s. |
|
334 |
|
335 ///Resets the source node to \c _s. |
|
336 /// |
281 void resetSource(Node _s) { s=_s; } |
337 void resetSource(Node _s) { s=_s; } |
|
338 |
|
339 ///Resets the target node to \c _t. |
|
340 |
|
341 ///Resets the target node to \c _t. |
282 /// |
342 /// |
283 void resetTarget(Node _t) { t=_t; } |
343 void resetTarget(Node _t) { t=_t; } |
284 |
344 |
285 /// capacity-map is changed. |
345 /// Resets the edge map of the capacities to _cap. |
|
346 |
|
347 /// Resets the edge map of the capacities to _cap. |
|
348 /// |
286 void resetCap(const CapMap& _cap) { capacity=&_cap; } |
349 void resetCap(const CapMap& _cap) { capacity=&_cap; } |
287 |
350 |
288 /// flow-map is changed. |
351 /// Resets the edge map of the flows to _flow. |
|
352 |
|
353 /// Resets the edge map of the flows to _flow. |
|
354 /// |
289 void resetFlow(FlowMap& _flow) { flow=&_flow; } |
355 void resetFlow(FlowMap& _flow) { flow=&_flow; } |
290 |
356 |
291 |
357 |
292 private: |
358 private: |
293 |
359 |