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_BOYKOV_KOLMOGOROV_MAX_FLOW_HPP
33 #define BOOST_BOYKOV_KOLMOGOROV_MAX_FLOW_HPP
35 #include <boost/config.hpp>
36 #include <boost/assert.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>
49 #include <boost/graph/lookup_edge.hpp>
50 #include <boost/concept/assert.hpp>
52 // The algorithm impelemented here is described in:
54 // Boykov, Y., Kolmogorov, V. "An Experimental Comparison of Min-Cut/Max-Flow
55 // Algorithms for Energy Minimization in Vision", In IEEE Transactions on
56 // Pattern Analysis and Machine Intelligence, vol. 26, no. 9, pp. 1124-1137,
59 // For further reading, also see:
61 // Kolmogorov, V. "Graph Based Algorithms for Scene Reconstruction from Two or
62 // More Views". PhD thesis, Cornell University, Sep 2003.
70 template < class Graph, class EdgeCapacityMap,
71 class ResidualCapacityEdgeMap, class ReverseEdgeMap,
72 class PredecessorMap, class ColorMap, class DistanceMap,
77 typename property_traits< EdgeCapacityMap >::value_type tEdgeVal;
78 typedef graph_traits< Graph > tGraphTraits;
79 typedef typename tGraphTraits::vertex_iterator vertex_iterator;
80 typedef typename tGraphTraits::vertex_descriptor vertex_descriptor;
81 typedef typename tGraphTraits::edge_descriptor edge_descriptor;
82 typedef typename tGraphTraits::edge_iterator edge_iterator;
83 typedef typename tGraphTraits::out_edge_iterator out_edge_iterator;
84 typedef boost::queue< vertex_descriptor >
85 tQueue; // queue of vertices, used in adoption-stage
86 typedef typename property_traits< ColorMap >::value_type tColorValue;
87 typedef color_traits< tColorValue > tColorTraits;
89 typename property_traits< DistanceMap >::value_type tDistanceVal;
92 bk_max_flow(Graph& g, EdgeCapacityMap cap, ResidualCapacityEdgeMap res,
93 ReverseEdgeMap rev, PredecessorMap pre, ColorMap color,
94 DistanceMap dist, IndexMap idx, vertex_descriptor src,
95 vertex_descriptor sink)
100 , m_rev_edge_map(rev)
107 , m_in_active_list_vec(num_vertices(g), false)
108 , m_in_active_list_map(make_iterator_property_map(
109 m_in_active_list_vec.begin(), m_index_map))
110 , m_has_parent_vec(num_vertices(g), false)
112 make_iterator_property_map(m_has_parent_vec.begin(), m_index_map))
113 , m_time_vec(num_vertices(g), 0)
115 make_iterator_property_map(m_time_vec.begin(), m_index_map))
118 , m_last_grow_vertex(graph_traits< Graph >::null_vertex())
120 // initialize the color-map with gray-values
121 vertex_iterator vi, v_end;
122 for (boost::tie(vi, v_end) = vertices(m_g); vi != v_end; ++vi)
124 set_tree(*vi, tColorTraits::gray());
126 // Initialize flow to zero which means initializing
127 // the residual capacity equal to the capacity
128 edge_iterator ei, e_end;
129 for (boost::tie(ei, e_end) = edges(m_g); ei != e_end; ++ei)
131 put(m_res_cap_map, *ei, get(m_cap_map, *ei));
132 BOOST_ASSERT(get(m_rev_edge_map, get(m_rev_edge_map, *ei))
133 == *ei); // check if the reverse edge map is build up
136 // init the search trees with the two terminals
137 set_tree(m_source, tColorTraits::black());
138 set_tree(m_sink, tColorTraits::white());
139 put(m_time_map, m_source, 1);
140 put(m_time_map, m_sink, 1);
145 // augment direct paths from SOURCE->SINK and SOURCE->VERTEX->SINK
146 augment_direct_paths();
147 // start the main-loop
151 edge_descriptor connecting_edge;
152 boost::tie(connecting_edge, path_found)
153 = grow(); // find a path from source to sink
156 // we're finished, no more paths were found
160 augment(connecting_edge); // augment that path
161 adopt(); // rebuild search tree structure
166 // the complete class is protected, as we want access to members in
167 // derived test-class (see test/boykov_kolmogorov_max_flow_test.cpp)
169 void augment_direct_paths()
171 // in a first step, we augment all direct paths from
172 // source->NODE->sink and additionally paths from source->sink. This
173 // improves especially graphcuts for segmentation, as most of the
174 // nodes have source/sink connects but shouldn't have an impact on
175 // other maxflow problems (this is done in grow() anyway)
176 out_edge_iterator ei, e_end;
177 for (boost::tie(ei, e_end) = out_edges(m_source, m_g); ei != e_end;
180 edge_descriptor from_source = *ei;
181 vertex_descriptor current_node = target(from_source, m_g);
182 if (current_node == m_sink)
184 tEdgeVal cap = get(m_res_cap_map, from_source);
185 put(m_res_cap_map, from_source, 0);
189 edge_descriptor to_sink;
191 boost::tie(to_sink, is_there)
192 = lookup_edge(current_node, m_sink, m_g);
195 tEdgeVal cap_from_source = get(m_res_cap_map, from_source);
196 tEdgeVal cap_to_sink = get(m_res_cap_map, to_sink);
197 if (cap_from_source > cap_to_sink)
199 set_tree(current_node, tColorTraits::black());
200 add_active_node(current_node);
201 set_edge_to_parent(current_node, from_source);
202 put(m_dist_map, current_node, 1);
203 put(m_time_map, current_node, 1);
204 // add stuff to flow and update residuals. we dont need
205 // to update reverse_edges, as incoming/outgoing edges
206 // to/from source/sink don't count for max-flow
207 put(m_res_cap_map, from_source,
208 get(m_res_cap_map, from_source) - cap_to_sink);
209 put(m_res_cap_map, to_sink, 0);
210 m_flow += cap_to_sink;
212 else if (cap_to_sink > 0)
214 set_tree(current_node, tColorTraits::white());
215 add_active_node(current_node);
216 set_edge_to_parent(current_node, to_sink);
217 put(m_dist_map, current_node, 1);
218 put(m_time_map, current_node, 1);
219 // add stuff to flow and update residuals. we dont need
220 // to update reverse_edges, as incoming/outgoing edges
221 // to/from source/sink don't count for max-flow
222 put(m_res_cap_map, to_sink,
223 get(m_res_cap_map, to_sink) - cap_from_source);
224 put(m_res_cap_map, from_source, 0);
225 m_flow += cap_from_source;
228 else if (get(m_res_cap_map, from_source))
230 // there is no sink connect, so we can't augment this path,
231 // but to avoid adding m_source to the active nodes, we just
232 // activate this node and set the approciate things
233 set_tree(current_node, tColorTraits::black());
234 set_edge_to_parent(current_node, from_source);
235 put(m_dist_map, current_node, 1);
236 put(m_time_map, current_node, 1);
237 add_active_node(current_node);
240 for (boost::tie(ei, e_end) = out_edges(m_sink, m_g); ei != e_end;
243 edge_descriptor to_sink = get(m_rev_edge_map, *ei);
244 vertex_descriptor current_node = source(to_sink, m_g);
245 if (get(m_res_cap_map, to_sink))
247 set_tree(current_node, tColorTraits::white());
248 set_edge_to_parent(current_node, to_sink);
249 put(m_dist_map, current_node, 1);
250 put(m_time_map, current_node, 1);
251 add_active_node(current_node);
257 * Returns a pair of an edge and a boolean. if the bool is true, the
258 * edge is a connection of a found path from s->t , read "the link" and
259 * source(returnVal, m_g) is the end of the path found in the
260 * source-tree target(returnVal, m_g) is the beginning of the path found
263 std::pair< edge_descriptor, bool > grow()
265 BOOST_ASSERT(m_orphans.empty());
266 vertex_descriptor current_node;
267 while ((current_node = get_next_active_node())
268 != graph_traits< Graph >::null_vertex())
270 BOOST_ASSERT(get_tree(current_node) != tColorTraits::gray()
271 && (has_parent(current_node) || current_node == m_source
272 || current_node == m_sink));
274 if (get_tree(current_node) == tColorTraits::black())
276 // source tree growing
277 out_edge_iterator ei, e_end;
278 if (current_node != m_last_grow_vertex)
280 m_last_grow_vertex = current_node;
281 boost::tie(m_last_grow_edge_it, m_last_grow_edge_end)
282 = out_edges(current_node, m_g);
284 for (; m_last_grow_edge_it != m_last_grow_edge_end;
285 ++m_last_grow_edge_it)
287 edge_descriptor out_edge = *m_last_grow_edge_it;
288 if (get(m_res_cap_map, out_edge) > 0)
289 { // check if we have capacity left on this edge
290 vertex_descriptor other_node
291 = target(out_edge, m_g);
292 if (get_tree(other_node) == tColorTraits::gray())
293 { // it's a free node
295 tColorTraits::black()); // aquire other node
299 other_node, out_edge); // set us as parent
300 put(m_dist_map, other_node,
301 get(m_dist_map, current_node)
302 + 1); // and update the
303 // distance-heuristic
304 put(m_time_map, other_node,
305 get(m_time_map, current_node));
306 add_active_node(other_node);
308 else if (get_tree(other_node)
309 == tColorTraits::black())
311 // we do this to get shorter paths. check if we
312 // are nearer to the source as its parent is
313 if (is_closer_to_terminal(
314 current_node, other_node))
316 set_edge_to_parent(other_node, out_edge);
317 put(m_dist_map, other_node,
318 get(m_dist_map, current_node) + 1);
319 put(m_time_map, other_node,
320 get(m_time_map, current_node));
325 BOOST_ASSERT(get_tree(other_node)
326 == tColorTraits::white());
327 // kewl, found a path from one to the other
328 // search tree, return
329 // the connecting edge in src->sink dir
330 return std::make_pair(out_edge, true);
333 } // for all out-edges
334 } // source-tree-growing
338 get_tree(current_node) == tColorTraits::white());
339 out_edge_iterator ei, e_end;
340 if (current_node != m_last_grow_vertex)
342 m_last_grow_vertex = current_node;
343 boost::tie(m_last_grow_edge_it, m_last_grow_edge_end)
344 = out_edges(current_node, m_g);
346 for (; m_last_grow_edge_it != m_last_grow_edge_end;
347 ++m_last_grow_edge_it)
349 edge_descriptor in_edge
350 = get(m_rev_edge_map, *m_last_grow_edge_it);
351 if (get(m_res_cap_map, in_edge) > 0)
352 { // check if there is capacity left
353 vertex_descriptor other_node = source(in_edge, m_g);
354 if (get_tree(other_node) == tColorTraits::gray())
355 { // it's a free node
357 tColorTraits::white()); // aquire that node
361 other_node, in_edge); // set us as parent
363 other_node); // activate that node
364 put(m_dist_map, other_node,
365 get(m_dist_map, current_node)
366 + 1); // set its distance
367 put(m_time_map, other_node,
368 get(m_time_map, current_node)); // and time
370 else if (get_tree(other_node)
371 == tColorTraits::white())
373 if (is_closer_to_terminal(
374 current_node, other_node))
376 // we are closer to the sink than its parent
377 // is, so we "adopt" him
378 set_edge_to_parent(other_node, in_edge);
379 put(m_dist_map, other_node,
380 get(m_dist_map, current_node) + 1);
381 put(m_time_map, other_node,
382 get(m_time_map, current_node));
387 BOOST_ASSERT(get_tree(other_node)
388 == tColorTraits::black());
389 // kewl, found a path from one to the other
391 // return the connecting edge in src->sink dir
392 return std::make_pair(in_edge, true);
395 } // for all out-edges
396 } // sink-tree growing
398 // all edges of that node are processed, and no more paths were
400 // remove if from the front of the active queue
401 finish_node(current_node);
402 } // while active_nodes not empty
404 // no active nodes anymore and no path found, we're done
405 return std::make_pair(edge_descriptor(), false);
409 * augments path from s->t and updates residual graph
410 * source(e, m_g) is the end of the path found in the source-tree
411 * target(e, m_g) is the beginning of the path found in the sink-tree
412 * this phase generates orphans on satured edges, if the attached verts
413 * are from different search-trees orphans are ordered in distance to
414 * sink/source. first the farest from the source are front_inserted into
415 * the orphans list, and after that the sink-tree-orphans are
416 * front_inserted. when going to adoption stage the orphans are
417 * popped_front, and so we process the nearest verts to the terminals
420 void augment(edge_descriptor e)
422 BOOST_ASSERT(get_tree(target(e, m_g)) == tColorTraits::white());
423 BOOST_ASSERT(get_tree(source(e, m_g)) == tColorTraits::black());
424 BOOST_ASSERT(m_orphans.empty());
426 const tEdgeVal bottleneck = find_bottleneck(e);
427 // now we push the found flow through the path
428 // for each edge we saturate we have to look for the verts that
429 // belong to that edge, one of them becomes an orphans now process
430 // the connecting edge
431 put(m_res_cap_map, e, get(m_res_cap_map, e) - bottleneck);
432 BOOST_ASSERT(get(m_res_cap_map, e) >= 0);
433 put(m_res_cap_map, get(m_rev_edge_map, e),
434 get(m_res_cap_map, get(m_rev_edge_map, e)) + bottleneck);
436 // now we follow the path back to the source
437 vertex_descriptor current_node = source(e, m_g);
438 while (current_node != m_source)
440 edge_descriptor pred = get_edge_to_parent(current_node);
441 put(m_res_cap_map, pred, get(m_res_cap_map, pred) - bottleneck);
442 BOOST_ASSERT(get(m_res_cap_map, pred) >= 0);
443 put(m_res_cap_map, get(m_rev_edge_map, pred),
444 get(m_res_cap_map, get(m_rev_edge_map, pred)) + bottleneck);
445 if (get(m_res_cap_map, pred) == 0)
447 set_no_parent(current_node);
448 m_orphans.push_front(current_node);
450 current_node = source(pred, m_g);
452 // then go forward in the sink-tree
453 current_node = target(e, m_g);
454 while (current_node != m_sink)
456 edge_descriptor pred = get_edge_to_parent(current_node);
457 put(m_res_cap_map, pred, get(m_res_cap_map, pred) - bottleneck);
458 BOOST_ASSERT(get(m_res_cap_map, pred) >= 0);
459 put(m_res_cap_map, get(m_rev_edge_map, pred),
460 get(m_res_cap_map, get(m_rev_edge_map, pred)) + bottleneck);
461 if (get(m_res_cap_map, pred) == 0)
463 set_no_parent(current_node);
464 m_orphans.push_front(current_node);
466 current_node = target(pred, m_g);
468 // and add it to the max-flow
469 m_flow += bottleneck;
473 * returns the bottleneck of a s->t path (end_of_path is last vertex in
474 * source-tree, begin_of_path is first vertex in sink-tree)
476 inline tEdgeVal find_bottleneck(edge_descriptor e)
478 BOOST_USING_STD_MIN();
479 tEdgeVal minimum_cap = get(m_res_cap_map, e);
480 vertex_descriptor current_node = source(e, m_g);
481 // first go back in the source tree
482 while (current_node != m_source)
484 edge_descriptor pred = get_edge_to_parent(current_node);
485 minimum_cap = min BOOST_PREVENT_MACRO_SUBSTITUTION(
486 minimum_cap, get(m_res_cap_map, pred));
487 current_node = source(pred, m_g);
489 // then go forward in the sink-tree
490 current_node = target(e, m_g);
491 while (current_node != m_sink)
493 edge_descriptor pred = get_edge_to_parent(current_node);
494 minimum_cap = min BOOST_PREVENT_MACRO_SUBSTITUTION(
495 minimum_cap, get(m_res_cap_map, pred));
496 current_node = target(pred, m_g);
502 * rebuild search trees
503 * empty the queue of orphans, and find new parents for them or just
504 * drop them from the search trees
508 while (!m_orphans.empty() || !m_child_orphans.empty())
510 vertex_descriptor current_node;
511 if (m_child_orphans.empty())
513 // get the next orphan from the main-queue and remove it
514 current_node = m_orphans.front();
515 m_orphans.pop_front();
519 current_node = m_child_orphans.front();
520 m_child_orphans.pop();
522 if (get_tree(current_node) == tColorTraits::black())
524 // we're in the source-tree
525 tDistanceVal min_distance
526 = (std::numeric_limits< tDistanceVal >::max)();
527 edge_descriptor new_parent_edge;
528 out_edge_iterator ei, e_end;
529 for (boost::tie(ei, e_end) = out_edges(current_node, m_g);
532 const edge_descriptor in_edge
533 = get(m_rev_edge_map, *ei);
534 BOOST_ASSERT(target(in_edge, m_g)
535 == current_node); // we should be the target of this
537 if (get(m_res_cap_map, in_edge) > 0)
539 vertex_descriptor other_node = source(in_edge, m_g);
540 if (get_tree(other_node) == tColorTraits::black()
541 && has_source_connect(other_node))
543 if (get(m_dist_map, other_node) < min_distance)
545 min_distance = get(m_dist_map, other_node);
546 new_parent_edge = in_edge;
552 != (std::numeric_limits< tDistanceVal >::max)())
554 set_edge_to_parent(current_node, new_parent_edge);
555 put(m_dist_map, current_node, min_distance + 1);
556 put(m_time_map, current_node, m_time);
560 put(m_time_map, current_node, 0);
561 for (boost::tie(ei, e_end)
562 = out_edges(current_node, m_g);
565 edge_descriptor in_edge = get(m_rev_edge_map, *ei);
566 vertex_descriptor other_node = source(in_edge, m_g);
567 if (get_tree(other_node) == tColorTraits::black()
568 && other_node != m_source)
570 if (get(m_res_cap_map, in_edge) > 0)
572 add_active_node(other_node);
574 if (has_parent(other_node)
576 get_edge_to_parent(other_node), m_g)
579 // we are the parent of that node
580 // it has to find a new parent, too
581 set_no_parent(other_node);
582 m_child_orphans.push(other_node);
586 set_tree(current_node, tColorTraits::gray());
588 } // source-tree-adoption
591 // now we should be in the sink-tree, check that...
593 get_tree(current_node) == tColorTraits::white());
594 out_edge_iterator ei, e_end;
595 edge_descriptor new_parent_edge;
596 tDistanceVal min_distance
597 = (std::numeric_limits< tDistanceVal >::max)();
598 for (boost::tie(ei, e_end) = out_edges(current_node, m_g);
601 const edge_descriptor out_edge = *ei;
602 if (get(m_res_cap_map, out_edge) > 0)
604 const vertex_descriptor other_node
605 = target(out_edge, m_g);
606 if (get_tree(other_node) == tColorTraits::white()
607 && has_sink_connect(other_node))
608 if (get(m_dist_map, other_node) < min_distance)
610 min_distance = get(m_dist_map, other_node);
611 new_parent_edge = out_edge;
616 != (std::numeric_limits< tDistanceVal >::max)())
618 set_edge_to_parent(current_node, new_parent_edge);
619 put(m_dist_map, current_node, min_distance + 1);
620 put(m_time_map, current_node, m_time);
624 put(m_time_map, current_node, 0);
625 for (boost::tie(ei, e_end)
626 = out_edges(current_node, m_g);
629 const edge_descriptor out_edge = *ei;
630 const vertex_descriptor other_node
631 = target(out_edge, m_g);
632 if (get_tree(other_node) == tColorTraits::white()
633 && other_node != m_sink)
635 if (get(m_res_cap_map, out_edge) > 0)
637 add_active_node(other_node);
639 if (has_parent(other_node)
641 get_edge_to_parent(other_node), m_g)
644 // we were it's parent, so it has to find a
646 set_no_parent(other_node);
647 m_child_orphans.push(other_node);
651 set_tree(current_node, tColorTraits::gray());
653 } // sink-tree adoption
654 } // while !orphans.empty()
658 * return next active vertex if there is one, otherwise a null_vertex
660 inline vertex_descriptor get_next_active_node()
664 if (m_active_nodes.empty())
665 return graph_traits< Graph >::null_vertex();
666 vertex_descriptor v = m_active_nodes.front();
668 // if it has no parent, this node can't be active (if its not
670 if (!has_parent(v) && v != m_source && v != m_sink)
672 m_active_nodes.pop();
673 put(m_in_active_list_map, v, false);
677 BOOST_ASSERT(get_tree(v) == tColorTraits::black()
678 || get_tree(v) == tColorTraits::white());
685 * adds v as an active vertex, but only if its not in the list already
687 inline void add_active_node(vertex_descriptor v)
689 BOOST_ASSERT(get_tree(v) != tColorTraits::gray());
690 if (get(m_in_active_list_map, v))
692 if (m_last_grow_vertex == v)
694 m_last_grow_vertex = graph_traits< Graph >::null_vertex();
700 put(m_in_active_list_map, v, true);
701 m_active_nodes.push(v);
706 * finish_node removes a node from the front of the active queue (its
707 * called in grow phase, if no more paths can be found using this node)
709 inline void finish_node(vertex_descriptor v)
711 BOOST_ASSERT(m_active_nodes.front() == v);
712 m_active_nodes.pop();
713 put(m_in_active_list_map, v, false);
714 m_last_grow_vertex = graph_traits< Graph >::null_vertex();
718 * removes a vertex from the queue of active nodes (actually this does
719 * nothing, but checks if this node has no parent edge, as this is the
720 * criteria for being no more active)
722 inline void remove_active_node(vertex_descriptor v)
724 BOOST_ASSERT(!has_parent(v));
728 * returns the search tree of v; tColorValue::black() for source tree,
729 * white() for sink tree, gray() for no tree
731 inline tColorValue get_tree(vertex_descriptor v) const
733 return get(m_tree_map, v);
737 * sets search tree of v; tColorValue::black() for source tree, white()
738 * for sink tree, gray() for no tree
740 inline void set_tree(vertex_descriptor v, tColorValue t)
742 put(m_tree_map, v, t);
746 * returns edge to parent vertex of v;
748 inline edge_descriptor get_edge_to_parent(vertex_descriptor v) const
750 return get(m_pre_map, v);
754 * returns true if the edge stored in m_pre_map[v] is a valid entry
756 inline bool has_parent(vertex_descriptor v) const
758 return get(m_has_parent_map, v);
762 * sets edge to parent vertex of v;
764 inline void set_edge_to_parent(
765 vertex_descriptor v, edge_descriptor f_edge_to_parent)
767 BOOST_ASSERT(get(m_res_cap_map, f_edge_to_parent) > 0);
768 put(m_pre_map, v, f_edge_to_parent);
769 put(m_has_parent_map, v, true);
773 * removes the edge to parent of v (this is done by invalidating the
774 * entry an additional map)
776 inline void set_no_parent(vertex_descriptor v)
778 put(m_has_parent_map, v, false);
782 * checks if vertex v has a connect to the sink-vertex (@var m_sink)
783 * @param v the vertex which is checked
784 * @return true if a path to the sink was found, false if not
786 inline bool has_sink_connect(vertex_descriptor v)
788 tDistanceVal current_distance = 0;
789 vertex_descriptor current_vertex = v;
792 if (get(m_time_map, current_vertex) == m_time)
794 // we found a node which was already checked this round. use
795 // it for distance calculations
796 current_distance += get(m_dist_map, current_vertex);
799 if (current_vertex == m_sink)
801 put(m_time_map, m_sink, m_time);
804 if (has_parent(current_vertex))
806 // it has a parent, so get it
808 = target(get_edge_to_parent(current_vertex), m_g);
818 while (get(m_time_map, current_vertex) != m_time)
820 put(m_dist_map, current_vertex, current_distance);
822 put(m_time_map, current_vertex, m_time);
824 = target(get_edge_to_parent(current_vertex), m_g);
830 * checks if vertex v has a connect to the source-vertex (@var m_source)
831 * @param v the vertex which is checked
832 * @return true if a path to the source was found, false if not
834 inline bool has_source_connect(vertex_descriptor v)
836 tDistanceVal current_distance = 0;
837 vertex_descriptor current_vertex = v;
840 if (get(m_time_map, current_vertex) == m_time)
842 // we found a node which was already checked this round. use
843 // it for distance calculations
844 current_distance += get(m_dist_map, current_vertex);
847 if (current_vertex == m_source)
849 put(m_time_map, m_source, m_time);
852 if (has_parent(current_vertex))
854 // it has a parent, so get it
856 = source(get_edge_to_parent(current_vertex), m_g);
866 while (get(m_time_map, current_vertex) != m_time)
868 put(m_dist_map, current_vertex, current_distance);
870 put(m_time_map, current_vertex, m_time);
872 = source(get_edge_to_parent(current_vertex), m_g);
878 * returns true, if p is closer to a terminal than q
880 inline bool is_closer_to_terminal(
881 vertex_descriptor p, vertex_descriptor q)
883 // checks the timestamps first, to build no cycles, and after that
885 return (get(m_time_map, q) <= get(m_time_map, p)
886 && get(m_dist_map, q) > get(m_dist_map, p) + 1);
893 IndexMap m_index_map;
894 EdgeCapacityMap m_cap_map;
895 ResidualCapacityEdgeMap m_res_cap_map;
896 ReverseEdgeMap m_rev_edge_map;
897 PredecessorMap m_pre_map; // stores paths found in the growth stage
898 ColorMap m_tree_map; // maps each vertex into one of the two search tree
900 DistanceMap m_dist_map; // stores distance to source/sink nodes
901 vertex_descriptor m_source;
902 vertex_descriptor m_sink;
904 tQueue m_active_nodes;
905 std::vector< bool > m_in_active_list_vec;
906 iterator_property_map< std::vector< bool >::iterator, IndexMap >
907 m_in_active_list_map;
909 std::list< vertex_descriptor > m_orphans;
910 tQueue m_child_orphans; // we use a second queuqe for child orphans, as
911 // they are FIFO processed
913 std::vector< bool > m_has_parent_vec;
914 iterator_property_map< std::vector< bool >::iterator, IndexMap >
917 std::vector< long > m_time_vec; // timestamp of each node, used for
918 // sink/source-path calculations
919 iterator_property_map< std::vector< long >::iterator, IndexMap >
923 vertex_descriptor m_last_grow_vertex;
924 out_edge_iterator m_last_grow_edge_it;
925 out_edge_iterator m_last_grow_edge_end;
928 } // namespace boost::detail
931 * non-named-parameter version, given everything
932 * this is the catch all version
934 template < class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap,
935 class ReverseEdgeMap, class PredecessorMap, class ColorMap,
936 class DistanceMap, class IndexMap >
937 typename property_traits< CapacityEdgeMap >::value_type
938 boykov_kolmogorov_max_flow(Graph& g, CapacityEdgeMap cap,
939 ResidualCapacityEdgeMap res_cap, ReverseEdgeMap rev_map,
940 PredecessorMap pre_map, ColorMap color, DistanceMap dist, IndexMap idx,
941 typename graph_traits< Graph >::vertex_descriptor src,
942 typename graph_traits< Graph >::vertex_descriptor sink)
944 typedef typename graph_traits< Graph >::vertex_descriptor vertex_descriptor;
945 typedef typename graph_traits< Graph >::edge_descriptor edge_descriptor;
947 // as this method is the last one before we instantiate the solver, we do
948 // the concept checks here
949 BOOST_CONCEPT_ASSERT(
950 (VertexListGraphConcept< Graph >)); // to have vertices(),
952 BOOST_CONCEPT_ASSERT((EdgeListGraphConcept< Graph >)); // to have edges()
953 BOOST_CONCEPT_ASSERT(
954 (IncidenceGraphConcept< Graph >)); // to have source(), target() and
956 BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< CapacityEdgeMap,
957 edge_descriptor >)); // read flow-values from edges
958 BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept< ResidualCapacityEdgeMap,
959 edge_descriptor >)); // write flow-values to residuals
960 BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< ReverseEdgeMap,
961 edge_descriptor >)); // read out reverse edges
962 BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept< PredecessorMap,
963 vertex_descriptor >)); // store predecessor there
964 BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept< ColorMap,
965 vertex_descriptor >)); // write corresponding tree
966 BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept< DistanceMap,
967 vertex_descriptor >)); // write distance to source/sink
968 BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< IndexMap,
969 vertex_descriptor >)); // get index 0...|V|-1
970 BOOST_ASSERT(num_vertices(g) >= 2 && src != sink);
972 detail::bk_max_flow< Graph, CapacityEdgeMap, ResidualCapacityEdgeMap,
973 ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >
974 algo(g, cap, res_cap, rev_map, pre_map, color, dist, idx, src, sink);
976 return algo.max_flow();
980 * non-named-parameter version, given capacity, residual_capacity,
981 * reverse_edges, and an index map.
983 template < class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap,
984 class ReverseEdgeMap, class IndexMap >
985 typename property_traits< CapacityEdgeMap >::value_type
986 boykov_kolmogorov_max_flow(Graph& g, CapacityEdgeMap cap,
987 ResidualCapacityEdgeMap res_cap, ReverseEdgeMap rev, IndexMap idx,
988 typename graph_traits< Graph >::vertex_descriptor src,
989 typename graph_traits< Graph >::vertex_descriptor sink)
991 typename graph_traits< Graph >::vertices_size_type n_verts
993 std::vector< typename graph_traits< Graph >::edge_descriptor >
994 predecessor_vec(n_verts);
995 std::vector< default_color_type > color_vec(n_verts);
996 std::vector< typename graph_traits< Graph >::vertices_size_type >
997 distance_vec(n_verts);
998 return boykov_kolmogorov_max_flow(g, cap, res_cap, rev,
999 make_iterator_property_map(predecessor_vec.begin(), idx),
1000 make_iterator_property_map(color_vec.begin(), idx),
1001 make_iterator_property_map(distance_vec.begin(), idx), idx, src, sink);
1005 * non-named-parameter version, some given: capacity, residual_capacity,
1006 * reverse_edges, color_map and an index map. Use this if you are interested in
1007 * the minimum cut, as the color map provides that info.
1009 template < class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap,
1010 class ReverseEdgeMap, class ColorMap, class IndexMap >
1011 typename property_traits< CapacityEdgeMap >::value_type
1012 boykov_kolmogorov_max_flow(Graph& g, CapacityEdgeMap cap,
1013 ResidualCapacityEdgeMap res_cap, ReverseEdgeMap rev, ColorMap color,
1014 IndexMap idx, typename graph_traits< Graph >::vertex_descriptor src,
1015 typename graph_traits< Graph >::vertex_descriptor sink)
1017 typename graph_traits< Graph >::vertices_size_type n_verts
1019 std::vector< typename graph_traits< Graph >::edge_descriptor >
1020 predecessor_vec(n_verts);
1021 std::vector< typename graph_traits< Graph >::vertices_size_type >
1022 distance_vec(n_verts);
1023 return boykov_kolmogorov_max_flow(g, cap, res_cap, rev,
1024 make_iterator_property_map(predecessor_vec.begin(), idx), color,
1025 make_iterator_property_map(distance_vec.begin(), idx), idx, src, sink);
1029 * named-parameter version, some given
1031 template < class Graph, class P, class T, class R >
1032 typename property_traits<
1033 typename property_map< Graph, edge_capacity_t >::const_type >::value_type
1034 boykov_kolmogorov_max_flow(Graph& g,
1035 typename graph_traits< Graph >::vertex_descriptor src,
1036 typename graph_traits< Graph >::vertex_descriptor sink,
1037 const bgl_named_params< P, T, R >& params)
1039 return boykov_kolmogorov_max_flow(g,
1040 choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity),
1041 choose_pmap(get_param(params, edge_residual_capacity), g,
1042 edge_residual_capacity),
1043 choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse),
1045 get_param(params, vertex_predecessor), g, vertex_predecessor),
1046 choose_pmap(get_param(params, vertex_color), g, vertex_color),
1047 choose_pmap(get_param(params, vertex_distance), g, vertex_distance),
1048 choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
1053 * named-parameter version, none given
1055 template < class Graph >
1056 typename property_traits<
1057 typename property_map< Graph, edge_capacity_t >::const_type >::value_type
1058 boykov_kolmogorov_max_flow(Graph& g,
1059 typename graph_traits< Graph >::vertex_descriptor src,
1060 typename graph_traits< Graph >::vertex_descriptor sink)
1062 bgl_named_params< int, buffer_param_t > params(0); // bogus empty param
1063 return boykov_kolmogorov_max_flow(g, src, sink, params);
1066 } // namespace boost
1068 #endif // BOOST_BOYKOV_KOLMOGOROV_MAX_FLOW_HPP