1 // Copyright (c) 2006, Stephan Diederich
3 // This code may be used under either of the following two licences:
5 // Permission is hereby granted, free of charge, to any person
6 // obtaining a copy of this software and associated documentation
7 // files (the "Software"), to deal in the Software without
8 // restriction, including without limitation the rights to use,
9 // copy, modify, merge, publish, distribute, sublicense, and/or
10 // sell copies of the Software, and to permit persons to whom the
11 // Software is furnished to do so, subject to the following
14 // The above copyright notice and this permission notice shall be
15 // included in all copies or substantial portions of the Software.
17 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
19 // OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
21 // HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
22 // WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
23 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24 // OTHER DEALINGS IN THE SOFTWARE. OF SUCH DAMAGE.
28 // Distributed under the Boost Software License, Version 1.0.
29 // (See accompanying file LICENSE_1_0.txt or copy at
30 // http://www.boost.org/LICENSE_1_0.txt)
32 #ifndef BOOST_KOLMOGOROV_MAX_FLOW_HPP
33 #define BOOST_KOLMOGOROV_MAX_FLOW_HPP
35 #include <boost/config.hpp>
41 #include <algorithm> // for std::min and std::max
43 #include <boost/pending/queue.hpp>
44 #include <boost/limits.hpp>
45 #include <boost/property_map/property_map.hpp>
46 #include <boost/none_t.hpp>
47 #include <boost/graph/graph_concepts.hpp>
48 #include <boost/graph/named_function_params.hpp>
53 template <class Graph
,
54 class EdgeCapacityMap
,
55 class ResidualCapacityEdgeMap
,
62 typedef typename property_traits
<EdgeCapacityMap
>::value_type tEdgeVal
;
63 typedef graph_traits
<Graph
> tGraphTraits
;
64 typedef typename
tGraphTraits::vertex_iterator vertex_iterator
;
65 typedef typename
tGraphTraits::vertex_descriptor vertex_descriptor
;
66 typedef typename
tGraphTraits::edge_descriptor edge_descriptor
;
67 typedef typename
tGraphTraits::edge_iterator edge_iterator
;
68 typedef typename
tGraphTraits::out_edge_iterator out_edge_iterator
;
69 typedef boost::queue
<vertex_descriptor
> tQueue
; //queue of vertices, used in adoption-stage
70 typedef typename property_traits
<ColorMap
>::value_type tColorValue
;
71 typedef color_traits
<tColorValue
> tColorTraits
;
72 typedef typename property_traits
<DistanceMap
>::value_type tDistanceVal
;
77 ResidualCapacityEdgeMap res
,
83 vertex_descriptor src
,
84 vertex_descriptor sink
):
96 m_in_active_list_vec(num_vertices(g
), false),
97 m_in_active_list_map(make_iterator_property_map(m_in_active_list_vec
.begin(), m_index_map
)),
98 m_has_parent_vec(num_vertices(g
), false),
99 m_has_parent_map(make_iterator_property_map(m_has_parent_vec
.begin(), m_index_map
)),
100 m_time_vec(num_vertices(g
), 0),
101 m_time_map(make_iterator_property_map(m_time_vec
.begin(), m_index_map
)),
104 m_last_grow_vertex(graph_traits
<Graph
>::null_vertex()){
105 // initialize the color-map with gray-values
106 vertex_iterator vi
, v_end
;
107 for(tie(vi
, v_end
) = vertices(m_g
); vi
!= v_end
; ++vi
){
108 set_tree(*vi
, tColorTraits::gray());
110 // Initialize flow to zero which means initializing
111 // the residual capacity equal to the capacity
112 edge_iterator ei
, e_end
;
113 for(tie(ei
, e_end
) = edges(m_g
); ei
!= e_end
; ++ei
) {
114 m_res_cap_map
[*ei
] = m_cap_map
[*ei
];
115 assert(m_rev_edge_map
[m_rev_edge_map
[*ei
]] == *ei
); //check if the reverse edge map is build up properly
117 //init the search trees with the two terminals
118 set_tree(m_source
, tColorTraits::black());
119 set_tree(m_sink
, tColorTraits::white());
120 m_time_map
[m_source
] = 1;
121 m_time_map
[m_sink
] = 1;
127 //augment direct paths from SOURCE->SINK and SOURCE->VERTEX->SINK
128 augment_direct_paths();
129 //start the main-loop
132 edge_descriptor connecting_edge
;
133 tie(connecting_edge
, path_found
) = grow(); //find a path from source to sink
135 //we're finished, no more paths were found
139 augment(connecting_edge
); //augment that path
140 adopt(); //rebuild search tree structure
145 //the complete class is protected, as we want access to members in derived test-class (see $(BOOST_ROOT)/libs/graph/test/kolmogorov_max_flow_test.cpp)
147 void augment_direct_paths(){
148 //in a first step, we augment all direct paths from source->NODE->sink
149 //and additionally paths from source->sink
150 //this improves especially graphcuts for segmentation, as most of the nodes have source/sink connects
151 //but shouldn't have an impact on other maxflow problems (this is done in grow() anyway)
152 out_edge_iterator ei
, e_end
;
153 for(tie(ei
, e_end
) = out_edges(m_source
, m_g
); ei
!= e_end
; ++ei
){
154 edge_descriptor from_source
= *ei
;
155 vertex_descriptor current_node
= target(from_source
, m_g
);
156 if(current_node
== m_sink
){
157 tEdgeVal cap
= m_res_cap_map
[from_source
];
158 m_res_cap_map
[from_source
] = 0;
162 edge_descriptor to_sink
;
164 tie(to_sink
, is_there
) = edge(current_node
, m_sink
, m_g
);
166 tEdgeVal cap_from_source
= m_res_cap_map
[from_source
];
167 tEdgeVal cap_to_sink
= m_res_cap_map
[to_sink
];
168 if(cap_from_source
> cap_to_sink
){
169 set_tree(current_node
, tColorTraits::black());
170 add_active_node(current_node
);
171 set_edge_to_parent(current_node
, from_source
);
172 m_dist_map
[current_node
] = 1;
173 m_time_map
[current_node
] = 1;
174 //add stuff to flow and update residuals
175 //we dont need to update reverse_edges, as incoming/outgoing edges to/from source/sink don't count for max-flow
176 m_res_cap_map
[from_source
] -= cap_to_sink
;
177 m_res_cap_map
[to_sink
] = 0;
178 m_flow
+= cap_to_sink
;
179 } else if(cap_to_sink
> 0){
180 set_tree(current_node
, tColorTraits::white());
181 add_active_node(current_node
);
182 set_edge_to_parent(current_node
, to_sink
);
183 m_dist_map
[current_node
] = 1;
184 m_time_map
[current_node
] = 1;
185 //add stuff to flow and update residuals
186 //we dont need to update reverse_edges, as incoming/outgoing edges to/from source/sink don't count for max-flow
187 m_res_cap_map
[to_sink
] -= cap_from_source
;
188 m_res_cap_map
[from_source
] = 0;
189 m_flow
+= cap_from_source
;
191 } else if(m_res_cap_map
[from_source
]){
192 //there is no sink connect, so we can't augment this path
193 //but to avoid adding m_source to the active nodes, we just activate this node and set the approciate things
194 set_tree(current_node
, tColorTraits::black());
195 set_edge_to_parent(current_node
, from_source
);
196 m_dist_map
[current_node
] = 1;
197 m_time_map
[current_node
] = 1;
198 add_active_node(current_node
);
201 for(tie(ei
, e_end
) = out_edges(m_sink
, m_g
); ei
!= e_end
; ++ei
){
202 edge_descriptor to_sink
= m_rev_edge_map
[*ei
];
203 vertex_descriptor current_node
= source(to_sink
, m_g
);
204 if(m_res_cap_map
[to_sink
]){
205 set_tree(current_node
, tColorTraits::white());
206 set_edge_to_parent(current_node
, to_sink
);
207 m_dist_map
[current_node
] = 1;
208 m_time_map
[current_node
] = 1;
209 add_active_node(current_node
);
215 * returns a pair of an edge and a boolean. if the bool is true, the edge is a connection of a found path from s->t , read "the link" and
216 * source(returnVal, m_g) is the end of the path found in the source-tree
217 * target(returnVal, m_g) is the beginning of the path found in the sink-tree
219 std::pair
<edge_descriptor
, bool> grow(){
220 assert(m_orphans
.empty());
221 vertex_descriptor current_node
;
222 while((current_node
= get_next_active_node()) != graph_traits
<Graph
>::null_vertex()){ //if there is one
223 assert(get_tree(current_node
) != tColorTraits::gray() && (has_parent(current_node
) || current_node
==m_source
|| current_node
==m_sink
));
224 if(get_tree(current_node
) == tColorTraits::black()){
225 //source tree growing
226 out_edge_iterator ei
, e_end
;
227 if(current_node
!= m_last_grow_vertex
){
228 m_last_grow_vertex
= current_node
;
229 tie(m_last_grow_edge_it
, m_last_grow_edge_end
) = out_edges(current_node
, m_g
);
231 for(; m_last_grow_edge_it
!= m_last_grow_edge_end
; ++m_last_grow_edge_it
){
232 edge_descriptor out_edge
= *m_last_grow_edge_it
;
233 if(m_res_cap_map
[out_edge
] > 0){ //check if we have capacity left on this edge
234 vertex_descriptor other_node
= target(out_edge
, m_g
);
235 if(get_tree(other_node
) == tColorTraits::gray()){ //it's a free node
236 set_tree(other_node
, tColorTraits::black()); //aquire other node to our search tree
237 set_edge_to_parent(other_node
, out_edge
); //set us as parent
238 m_dist_map
[other_node
] = m_dist_map
[current_node
] + 1; //and update the distance-heuristic
239 m_time_map
[other_node
] = m_time_map
[current_node
];
240 add_active_node(other_node
);
241 } else if(get_tree(other_node
) == tColorTraits::black()){
242 if(is_closer_to_terminal(current_node
, other_node
)){ //we do this to get shorter paths. check if we are nearer to the source as its parent is
243 set_edge_to_parent(other_node
, out_edge
);
244 m_dist_map
[other_node
] = m_dist_map
[current_node
] + 1;
245 m_time_map
[other_node
] = m_time_map
[current_node
];
248 assert(get_tree(other_node
)==tColorTraits::white());
249 //kewl, found a path from one to the other search tree, return the connecting edge in src->sink dir
250 return std::make_pair(out_edge
, true);
253 } //for all out-edges
254 } //source-tree-growing
256 assert(get_tree(current_node
) == tColorTraits::white());
257 out_edge_iterator ei
, e_end
;
258 if(current_node
!= m_last_grow_vertex
){
259 m_last_grow_vertex
= current_node
;
260 tie(m_last_grow_edge_it
, m_last_grow_edge_end
) = out_edges(current_node
, m_g
);
262 for(; m_last_grow_edge_it
!= m_last_grow_edge_end
; ++m_last_grow_edge_it
){
263 edge_descriptor in_edge
= m_rev_edge_map
[*m_last_grow_edge_it
];
264 if(m_res_cap_map
[in_edge
] > 0){ //check if there is capacity left
265 vertex_descriptor other_node
= source(in_edge
, m_g
);
266 if(get_tree(other_node
) == tColorTraits::gray()){ //it's a free node
267 set_tree(other_node
, tColorTraits::white()); //aquire that node to our search tree
268 set_edge_to_parent(other_node
, in_edge
); //set us as parent
269 add_active_node(other_node
); //activate that node
270 m_dist_map
[other_node
] = m_dist_map
[current_node
] + 1; //set its distance
271 m_time_map
[other_node
] = m_time_map
[current_node
]; //and time
272 } else if(get_tree(other_node
) == tColorTraits::white()){
273 if(is_closer_to_terminal(current_node
, other_node
)){
274 //we are closer to the sink than its parent is, so we "adopt" him
275 set_edge_to_parent(other_node
, in_edge
);
276 m_dist_map
[other_node
] = m_dist_map
[current_node
] + 1;
277 m_time_map
[other_node
] = m_time_map
[current_node
];
280 assert(get_tree(other_node
)==tColorTraits::black());
281 //kewl, found a path from one to the other search tree, return the connecting edge in src->sink dir
282 return std::make_pair(in_edge
, true);
285 } //for all out-edges
286 } //sink-tree growing
287 //all edges of that node are processed, and no more paths were found. so remove if from the front of the active queue
288 finish_node(current_node
);
289 } //while active_nodes not empty
290 return std::make_pair(edge_descriptor(), false); //no active nodes anymore and no path found, we're done
294 * augments path from s->t and updates residual graph
295 * source(e, m_g) is the end of the path found in the source-tree
296 * target(e, m_g) is the beginning of the path found in the sink-tree
297 * this phase generates orphans on satured edges, if the attached verts are from different search-trees
298 * orphans are ordered in distance to sink/source. first the farest from the source are front_inserted into the orphans list,
299 * and after that the sink-tree-orphans are front_inserted. when going to adoption stage the orphans are popped_front, and so we process the nearest
300 * verts to the terminals first
302 void augment(edge_descriptor e
){
303 assert(get_tree(target(e
, m_g
)) == tColorTraits::white());
304 assert(get_tree(source(e
, m_g
)) == tColorTraits::black());
305 assert(m_orphans
.empty());
307 const tEdgeVal bottleneck
= find_bottleneck(e
);
308 //now we push the found flow through the path
309 //for each edge we saturate we have to look for the verts that belong to that edge, one of them becomes an orphans
310 //now process the connecting edge
311 m_res_cap_map
[e
] -= bottleneck
;
312 assert(m_res_cap_map
[e
] >= 0);
313 m_res_cap_map
[m_rev_edge_map
[e
]] += bottleneck
;
315 //now we follow the path back to the source
316 vertex_descriptor current_node
= source(e
, m_g
);
317 while(current_node
!= m_source
){
318 edge_descriptor pred
= get_edge_to_parent(current_node
);
319 m_res_cap_map
[pred
] -= bottleneck
;
320 assert(m_res_cap_map
[pred
] >= 0);
321 m_res_cap_map
[m_rev_edge_map
[pred
]] += bottleneck
;
322 if(m_res_cap_map
[pred
] == 0){
323 set_no_parent(current_node
);
324 m_orphans
.push_front(current_node
);
326 current_node
= source(pred
, m_g
);
328 //then go forward in the sink-tree
329 current_node
= target(e
, m_g
);
330 while(current_node
!= m_sink
){
331 edge_descriptor pred
= get_edge_to_parent(current_node
);
332 m_res_cap_map
[pred
] -= bottleneck
;
333 assert(m_res_cap_map
[pred
] >= 0);
334 m_res_cap_map
[m_rev_edge_map
[pred
]] += bottleneck
;
335 if(m_res_cap_map
[pred
] == 0){
336 set_no_parent(current_node
);
337 m_orphans
.push_front(current_node
);
339 current_node
= target(pred
, m_g
);
341 //and add it to the max-flow
342 m_flow
+= bottleneck
;
346 * returns the bottleneck of a s->t path (end_of_path is last vertex in source-tree, begin_of_path is first vertex in sink-tree)
348 inline tEdgeVal
find_bottleneck(edge_descriptor e
){
349 BOOST_USING_STD_MIN();
350 tEdgeVal minimum_cap
= m_res_cap_map
[e
];
351 vertex_descriptor current_node
= source(e
, m_g
);
352 //first go back in the source tree
353 while(current_node
!= m_source
){
354 edge_descriptor pred
= get_edge_to_parent(current_node
);
355 minimum_cap
= min
BOOST_PREVENT_MACRO_SUBSTITUTION(minimum_cap
, m_res_cap_map
[pred
]);
356 current_node
= source(pred
, m_g
);
358 //then go forward in the sink-tree
359 current_node
= target(e
, m_g
);
360 while(current_node
!= m_sink
){
361 edge_descriptor pred
= get_edge_to_parent(current_node
);
362 minimum_cap
= min
BOOST_PREVENT_MACRO_SUBSTITUTION(minimum_cap
, m_res_cap_map
[pred
]);
363 current_node
= target(pred
, m_g
);
369 * rebuild search trees
370 * empty the queue of orphans, and find new parents for them or just drop them from the search trees
373 while(!m_orphans
.empty() || !m_child_orphans
.empty()){
374 vertex_descriptor current_node
;
375 if(m_child_orphans
.empty()){
376 //get the next orphan from the main-queue and remove it
377 current_node
= m_orphans
.front();
378 m_orphans
.pop_front();
380 current_node
= m_child_orphans
.front();
381 m_child_orphans
.pop();
383 if(get_tree(current_node
) == tColorTraits::black()){
384 //we're in the source-tree
385 tDistanceVal min_distance
= (std::numeric_limits
<tDistanceVal
>::max
)();
386 edge_descriptor new_parent_edge
;
387 out_edge_iterator ei
, e_end
;
388 for(tie(ei
, e_end
) = out_edges(current_node
, m_g
); ei
!= e_end
; ++ei
){
389 const edge_descriptor in_edge
= m_rev_edge_map
[*ei
];
390 assert(target(in_edge
, m_g
) == current_node
); //we should be the target of this edge
391 if(m_res_cap_map
[in_edge
] > 0){
392 vertex_descriptor other_node
= source(in_edge
, m_g
);
393 if(get_tree(other_node
) == tColorTraits::black() && has_source_connect(other_node
)){
394 if(m_dist_map
[other_node
] < min_distance
){
395 min_distance
= m_dist_map
[other_node
];
396 new_parent_edge
= in_edge
;
401 if(min_distance
!= (std::numeric_limits
<tDistanceVal
>::max
)()){
402 set_edge_to_parent(current_node
, new_parent_edge
);
403 m_dist_map
[current_node
] = min_distance
+ 1;
404 m_time_map
[current_node
] = m_time
;
406 m_time_map
[current_node
] = 0;
407 for(tie(ei
, e_end
) = out_edges(current_node
, m_g
); ei
!= e_end
; ++ei
){
408 edge_descriptor in_edge
= m_rev_edge_map
[*ei
];
409 vertex_descriptor other_node
= source(in_edge
, m_g
);
410 if(get_tree(other_node
) == tColorTraits::black() && has_parent(other_node
)){
411 if(m_res_cap_map
[in_edge
] > 0){
412 add_active_node(other_node
);
414 if(source(get_edge_to_parent(other_node
), m_g
) == current_node
){
415 //we are the parent of that node
416 //it has to find a new parent, too
417 set_no_parent(other_node
);
418 m_child_orphans
.push(other_node
);
422 set_tree(current_node
, tColorTraits::gray());
424 } //source-tree-adoption
426 //now we should be in the sink-tree, check that...
427 assert(get_tree(current_node
) == tColorTraits::white());
428 out_edge_iterator ei
, e_end
;
429 edge_descriptor new_parent_edge
;
430 tDistanceVal min_distance
= (std::numeric_limits
<tDistanceVal
>::max
)();
431 for(tie(ei
, e_end
) = out_edges(current_node
, m_g
); ei
!= e_end
; ++ei
){
432 const edge_descriptor out_edge
= *ei
;
433 if(m_res_cap_map
[out_edge
] > 0){
434 const vertex_descriptor other_node
= target(out_edge
, m_g
);
435 if(get_tree(other_node
) == tColorTraits::white() && has_sink_connect(other_node
))
436 if(m_dist_map
[other_node
] < min_distance
){
437 min_distance
= m_dist_map
[other_node
];
438 new_parent_edge
= out_edge
;
442 if(min_distance
!= (std::numeric_limits
<tDistanceVal
>::max
)()){
443 set_edge_to_parent(current_node
, new_parent_edge
);
444 m_dist_map
[current_node
] = min_distance
+ 1;
445 m_time_map
[current_node
] = m_time
;
447 m_time_map
[current_node
] = 0;
448 for(tie(ei
, e_end
) = out_edges(current_node
, m_g
); ei
!= e_end
; ++ei
){
449 const edge_descriptor out_edge
= *ei
;
450 const vertex_descriptor other_node
= target(out_edge
, m_g
);
451 if(get_tree(other_node
) == tColorTraits::white() && has_parent(other_node
)){
452 if(m_res_cap_map
[out_edge
] > 0){
453 add_active_node(other_node
);
455 if(target(get_edge_to_parent(other_node
), m_g
) == current_node
){
456 //we were it's parent, so it has to find a new one, too
457 set_no_parent(other_node
);
458 m_child_orphans
.push(other_node
);
462 set_tree(current_node
, tColorTraits::gray());
464 } //sink-tree adoption
465 } //while !orphans.empty()
469 * return next active vertex if there is one, otherwise a null_vertex
471 inline vertex_descriptor
get_next_active_node(){
473 if(m_active_nodes
.empty())
474 return graph_traits
<Graph
>::null_vertex();
475 vertex_descriptor v
= m_active_nodes
.front();
477 if(!has_parent(v
) && v
!= m_source
&& v
!= m_sink
){ //if it has no parent, this node can't be active(if its not source or sink)
478 m_active_nodes
.pop();
479 m_in_active_list_map
[v
] = false;
481 assert(get_tree(v
) == tColorTraits::black() || get_tree(v
) == tColorTraits::white());
488 * adds v as an active vertex, but only if its not in the list already
490 inline void add_active_node(vertex_descriptor v
){
491 assert(get_tree(v
) != tColorTraits::gray());
492 if(m_in_active_list_map
[v
]){
495 m_in_active_list_map
[v
] = true;
496 m_active_nodes
.push(v
);
501 * finish_node removes a node from the front of the active queue (its called in grow phase, if no more paths can be found using this node)
503 inline void finish_node(vertex_descriptor v
){
504 assert(m_active_nodes
.front() == v
);
505 m_active_nodes
.pop();
506 m_in_active_list_map
[v
] = false;
507 m_last_grow_vertex
= graph_traits
<Graph
>::null_vertex();
511 * removes a vertex from the queue of active nodes (actually this does nothing,
512 * but checks if this node has no parent edge, as this is the criteria for beeing no more active)
514 inline void remove_active_node(vertex_descriptor v
){
515 assert(!has_parent(v
));
519 * returns the search tree of v; tColorValue::black() for source tree, white() for sink tree, gray() for no tree
521 inline tColorValue
get_tree(vertex_descriptor v
) const {
522 return m_tree_map
[v
];
526 * sets search tree of v; tColorValue::black() for source tree, white() for sink tree, gray() for no tree
528 inline void set_tree(vertex_descriptor v
, tColorValue t
){
533 * returns edge to parent vertex of v;
535 inline edge_descriptor
get_edge_to_parent(vertex_descriptor v
) const{
540 * returns true if the edge stored in m_pre_map[v] is a valid entry
542 inline bool has_parent(vertex_descriptor v
) const{
543 return m_has_parent_map
[v
];
547 * sets edge to parent vertex of v;
549 inline void set_edge_to_parent(vertex_descriptor v
, edge_descriptor f_edge_to_parent
){
550 assert(m_res_cap_map
[f_edge_to_parent
] > 0);
551 m_pre_map
[v
] = f_edge_to_parent
;
552 m_has_parent_map
[v
] = true;
556 * removes the edge to parent of v (this is done by invalidating the entry an additional map)
558 inline void set_no_parent(vertex_descriptor v
){
559 m_has_parent_map
[v
] = false;
563 * checks if vertex v has a connect to the sink-vertex (@var m_sink)
564 * @param v the vertex which is checked
565 * @return true if a path to the sink was found, false if not
567 inline bool has_sink_connect(vertex_descriptor v
){
568 tDistanceVal current_distance
= 0;
569 vertex_descriptor current_vertex
= v
;
571 if(m_time_map
[current_vertex
] == m_time
){
572 //we found a node which was already checked this round. use it for distance calculations
573 current_distance
+= m_dist_map
[current_vertex
];
576 if(current_vertex
== m_sink
){
577 m_time_map
[m_sink
] = m_time
;
580 if(has_parent(current_vertex
)){
581 //it has a parent, so get it
582 current_vertex
= target(get_edge_to_parent(current_vertex
), m_g
);
590 while(m_time_map
[current_vertex
] != m_time
){
591 m_dist_map
[current_vertex
] = current_distance
--;
592 m_time_map
[current_vertex
] = m_time
;
593 current_vertex
= target(get_edge_to_parent(current_vertex
), m_g
);
599 * checks if vertex v has a connect to the source-vertex (@var m_source)
600 * @param v the vertex which is checked
601 * @return true if a path to the source was found, false if not
603 inline bool has_source_connect(vertex_descriptor v
){
604 tDistanceVal current_distance
= 0;
605 vertex_descriptor current_vertex
= v
;
607 if(m_time_map
[current_vertex
] == m_time
){
608 //we found a node which was already checked this round. use it for distance calculations
609 current_distance
+= m_dist_map
[current_vertex
];
612 if(current_vertex
== m_source
){
613 m_time_map
[m_source
] = m_time
;
616 if(has_parent(current_vertex
)){
617 //it has a parent, so get it
618 current_vertex
= source(get_edge_to_parent(current_vertex
), m_g
);
626 while(m_time_map
[current_vertex
] != m_time
){
627 m_dist_map
[current_vertex
] = current_distance
-- ;
628 m_time_map
[current_vertex
] = m_time
;
629 current_vertex
= source(get_edge_to_parent(current_vertex
), m_g
);
635 * returns true, if p is closer to a terminal than q
637 inline bool is_closer_to_terminal(vertex_descriptor p
, vertex_descriptor q
){
638 //checks the timestamps first, to build no cycles, and after that the real distance
639 return (m_time_map
[q
] <= m_time_map
[p
] && m_dist_map
[q
] > m_dist_map
[p
]+1);
646 IndexMap m_index_map
;
647 EdgeCapacityMap m_cap_map
;
648 ResidualCapacityEdgeMap m_res_cap_map
;
649 ReverseEdgeMap m_rev_edge_map
;
650 PredecessorMap m_pre_map
; //stores paths found in the growth stage
651 ColorMap m_tree_map
; //maps each vertex into one of the two search tree or none (gray())
652 DistanceMap m_dist_map
; //stores distance to source/sink nodes
653 vertex_descriptor m_source
;
654 vertex_descriptor m_sink
;
656 tQueue m_active_nodes
;
657 std::vector
<bool> m_in_active_list_vec
;
658 iterator_property_map
<std::vector
<bool>::iterator
, IndexMap
> m_in_active_list_map
;
660 std::list
<vertex_descriptor
> m_orphans
;
661 tQueue m_child_orphans
; // we use a second queuqe for child orphans, as they are FIFO processed
663 std::vector
<bool> m_has_parent_vec
;
664 iterator_property_map
<std::vector
<bool>::iterator
, IndexMap
> m_has_parent_map
;
666 std::vector
<long> m_time_vec
; //timestamp of each node, used for sink/source-path calculations
667 iterator_property_map
<std::vector
<long>::iterator
, IndexMap
> m_time_map
;
670 vertex_descriptor m_last_grow_vertex
;
671 out_edge_iterator m_last_grow_edge_it
;
672 out_edge_iterator m_last_grow_edge_end
;
677 * non-named-parameter version, given everything
678 * this is the catch all version
680 template <class Graph
, class CapacityEdgeMap
, class ResidualCapacityEdgeMap
, class ReverseEdgeMap
,
681 class PredecessorMap
, class ColorMap
, class DistanceMap
, class IndexMap
>
682 typename property_traits
<CapacityEdgeMap
>::value_type
686 ResidualCapacityEdgeMap res_cap
,
687 ReverseEdgeMap rev_map
,
688 PredecessorMap pre_map
,
692 typename graph_traits
<Graph
>::vertex_descriptor src
,
693 typename graph_traits
<Graph
>::vertex_descriptor sink
696 typedef typename graph_traits
<Graph
>::vertex_descriptor vertex_descriptor
;
697 typedef typename graph_traits
<Graph
>::edge_descriptor edge_descriptor
;
698 //as this method is the last one before we instantiate the solver, we do the concept checks here
699 function_requires
<VertexListGraphConcept
<Graph
> >(); //to have vertices(), num_vertices(),
700 function_requires
<EdgeListGraphConcept
<Graph
> >(); //to have edges()
701 function_requires
<IncidenceGraphConcept
<Graph
> >(); //to have source(), target() and out_edges()
702 function_requires
<LvaluePropertyMapConcept
<CapacityEdgeMap
, edge_descriptor
> >(); //read flow-values from edges
703 function_requires
<Mutable_LvaluePropertyMapConcept
<ResidualCapacityEdgeMap
, edge_descriptor
> >(); //write flow-values to residuals
704 function_requires
<LvaluePropertyMapConcept
<ReverseEdgeMap
, edge_descriptor
> >(); //read out reverse edges
705 function_requires
<Mutable_LvaluePropertyMapConcept
<PredecessorMap
, vertex_descriptor
> >(); //store predecessor there
706 function_requires
<Mutable_LvaluePropertyMapConcept
<ColorMap
, vertex_descriptor
> >(); //write corresponding tree
707 function_requires
<Mutable_LvaluePropertyMapConcept
<DistanceMap
, vertex_descriptor
> >(); //write distance to source/sink
708 function_requires
<ReadablePropertyMapConcept
<IndexMap
, vertex_descriptor
> >(); //get index 0...|V|-1
709 assert(num_vertices(g
) >= 2 && src
!= sink
);
710 detail::kolmogorov
<Graph
, CapacityEdgeMap
, ResidualCapacityEdgeMap
, ReverseEdgeMap
, PredecessorMap
, ColorMap
, DistanceMap
, IndexMap
>
711 algo(g
, cap
, res_cap
, rev_map
, pre_map
, color
, dist
, idx
, src
, sink
);
712 return algo
.max_flow();
716 * non-named-parameter version, given: capacity, residucal_capacity, reverse_edges, and an index map.
718 template <class Graph
, class CapacityEdgeMap
, class ResidualCapacityEdgeMap
, class ReverseEdgeMap
, class IndexMap
>
719 typename property_traits
<CapacityEdgeMap
>::value_type
723 ResidualCapacityEdgeMap res_cap
,
726 typename graph_traits
<Graph
>::vertex_descriptor src
,
727 typename graph_traits
<Graph
>::vertex_descriptor sink
)
729 typename graph_traits
<Graph
>::vertices_size_type n_verts
= num_vertices(g
);
730 std::vector
<typename graph_traits
<Graph
>::edge_descriptor
> predecessor_vec(n_verts
);
731 std::vector
<default_color_type
> color_vec(n_verts
);
732 std::vector
<typename graph_traits
<Graph
>::vertices_size_type
> distance_vec(n_verts
);
733 return kolmogorov_max_flow
734 (g
, cap
, res_cap
, rev
,
735 make_iterator_property_map(predecessor_vec
.begin(), idx
),
736 make_iterator_property_map(color_vec
.begin(), idx
),
737 make_iterator_property_map(distance_vec
.begin(), idx
),
742 * non-named-parameter version, some given: capacity, residual_capacity, reverse_edges, color_map and an index map.
743 * Use this if you are interested in the minimum cut, as the color map provides that info
745 template <class Graph
, class CapacityEdgeMap
, class ResidualCapacityEdgeMap
, class ReverseEdgeMap
, class ColorMap
, class IndexMap
>
746 typename property_traits
<CapacityEdgeMap
>::value_type
750 ResidualCapacityEdgeMap res_cap
,
754 typename graph_traits
<Graph
>::vertex_descriptor src
,
755 typename graph_traits
<Graph
>::vertex_descriptor sink
)
757 typename graph_traits
<Graph
>::vertices_size_type n_verts
= num_vertices(g
);
758 std::vector
<typename graph_traits
<Graph
>::edge_descriptor
> predecessor_vec(n_verts
);
759 std::vector
<typename graph_traits
<Graph
>::vertices_size_type
> distance_vec(n_verts
);
761 return kolmogorov_max_flow
762 (g
, cap
, res_cap
, rev
,
763 make_iterator_property_map(predecessor_vec
.begin(), idx
),
765 make_iterator_property_map(distance_vec
.begin(), idx
),
770 * named-parameter version, some given
772 template <class Graph
, class P
, class T
, class R
>
773 typename property_traits
<typename property_map
<Graph
, edge_capacity_t
>::const_type
>::value_type
776 typename graph_traits
<Graph
>::vertex_descriptor src
,
777 typename graph_traits
<Graph
>::vertex_descriptor sink
,
778 const bgl_named_params
<P
, T
, R
>& params
)
780 return kolmogorov_max_flow(g
,
781 choose_const_pmap(get_param(params
, edge_capacity
), g
, edge_capacity
),
782 choose_pmap(get_param(params
, edge_residual_capacity
), g
, edge_residual_capacity
),
783 choose_const_pmap(get_param(params
, edge_reverse
), g
, edge_reverse
),
784 choose_pmap(get_param(params
, vertex_predecessor
), g
, vertex_predecessor
),
785 choose_pmap(get_param(params
, vertex_color
), g
, vertex_color
),
786 choose_pmap(get_param(params
, vertex_distance
), g
, vertex_distance
),
787 choose_const_pmap(get_param(params
, vertex_index
), g
, vertex_index
),
792 * named-parameter version, none given
794 template <class Graph
>
795 typename property_traits
<typename property_map
<Graph
, edge_capacity_t
>::const_type
>::value_type
798 typename graph_traits
<Graph
>::vertex_descriptor src
,
799 typename graph_traits
<Graph
>::vertex_descriptor sink
)
801 bgl_named_params
<int, buffer_param_t
> params(0); // bogus empty param
802 return kolmogorov_max_flow(g
, src
, sink
, params
);
806 #endif // BOOST_KOLMOGOROV_MAX_FLOW_HPP