|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r63189 - in trunk: boost/graph libs/graph/doc libs/graph/doc/figs libs/graph/example libs/graph/test
From: asutton_at_[hidden]
Date: 2010-06-21 11:35:44
Author: asutton
Date: 2010-06-21 11:35:42 EDT (Mon, 21 Jun 2010)
New Revision: 63189
URL: http://svn.boost.org/trac/boost/changeset/63189
Log:
Renaming kolmogorov_max_flow to boykov_kolmogorov_max_flow.
At the request of the authors of the published algorithm, the header
and all associated functions, data types, tests, examples, and docs
should be renamed to boykov_kolmogorov. Branched all of the necessary
documents and renamed all such functions and data types.
Added deprecation warnings to the kolmogorov_max_flow.hpp and to the
kolmogorov_max_flow.html.
Added:
trunk/boost/graph/boykov_kolmogorov_max_flow.hpp
- copied, changed from r63187, /trunk/boost/graph/kolmogorov_max_flow.hpp
trunk/libs/graph/doc/boykov_kolmogorov_max_flow.html
- copied, changed from r63187, /trunk/libs/graph/doc/kolmogorov_max_flow.html
trunk/libs/graph/doc/figs/bk_max_flow.gif
- copied unchanged from r63187, /trunk/libs/graph/doc/figs/kolmogorov_max_flow.gif
trunk/libs/graph/doc/figs/warning.png
- copied unchanged from r63187, /trunk/doc/src/images/warning.png
trunk/libs/graph/example/boykov_kolmogorov-eg.cpp
- copied, changed from r63187, /trunk/libs/graph/example/kolmogorov-eg.cpp
trunk/libs/graph/test/boykov_kolmogorov_max_flow_test.cpp
- copied, changed from r63187, /trunk/libs/graph/test/kolmogorov_max_flow_test.cpp
Text files modified:
trunk/boost/graph/boykov_kolmogorov_max_flow.hpp | 1520 ++++++++++++++++++++-------------------
trunk/boost/graph/kolmogorov_max_flow.hpp | 52
trunk/libs/graph/doc/boykov_kolmogorov_max_flow.html | 120 +-
trunk/libs/graph/doc/kolmogorov_max_flow.html | 71 +
trunk/libs/graph/example/Jamfile.v2 | 3
trunk/libs/graph/example/boykov_kolmogorov-eg.cpp | 15
trunk/libs/graph/test/Jamfile.v2 | 1
trunk/libs/graph/test/boykov_kolmogorov_max_flow_test.cpp | 172 ++-
8 files changed, 1035 insertions(+), 919 deletions(-)
Copied: trunk/boost/graph/boykov_kolmogorov_max_flow.hpp (from r63187, /trunk/boost/graph/kolmogorov_max_flow.hpp)
==============================================================================
--- /trunk/boost/graph/kolmogorov_max_flow.hpp (original)
+++ trunk/boost/graph/boykov_kolmogorov_max_flow.hpp 2010-06-21 11:35:42 EDT (Mon, 21 Jun 2010)
@@ -48,761 +48,819 @@
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/lookup_edge.hpp>
+// The algorithm impelemented here is described in:
+//
+// Boykov, Y., Kolmogorov, V. "An Experimental Comparison of Min-Cut/Max-Flow
+// Algorithms for Energy Minimization in Vision", In IEEE Transactions on
+// Pattern Analysis and Machine Intelligence, vol. 26, no. 9, pp. 1124-1137,
+// Sep 2004.
+//
+// For further reading, also see:
+//
+// Kolmogorov, V. "Graph Based Algorithms for Scene Reconstruction from Two or
+// More Views". PhD thesis, Cornell University, Sep 2003.
+
namespace boost {
- namespace detail {
- template <class Graph,
- class EdgeCapacityMap,
- class ResidualCapacityEdgeMap,
- class ReverseEdgeMap,
- class PredecessorMap,
- class ColorMap,
- class DistanceMap,
- class IndexMap>
- class kolmogorov{
- typedef typename property_traits<EdgeCapacityMap>::value_type tEdgeVal;
- typedef graph_traits<Graph> tGraphTraits;
- typedef typename tGraphTraits::vertex_iterator vertex_iterator;
- typedef typename tGraphTraits::vertex_descriptor vertex_descriptor;
- typedef typename tGraphTraits::edge_descriptor edge_descriptor;
- typedef typename tGraphTraits::edge_iterator edge_iterator;
- typedef typename tGraphTraits::out_edge_iterator out_edge_iterator;
- typedef boost::queue<vertex_descriptor> tQueue; //queue of vertices, used in adoption-stage
- typedef typename property_traits<ColorMap>::value_type tColorValue;
- typedef color_traits<tColorValue> tColorTraits;
- typedef typename property_traits<DistanceMap>::value_type tDistanceVal;
-
- public:
- kolmogorov(Graph& g,
- EdgeCapacityMap cap,
- ResidualCapacityEdgeMap res,
- ReverseEdgeMap rev,
- PredecessorMap pre,
- ColorMap color,
- DistanceMap dist,
- IndexMap idx,
- vertex_descriptor src,
- vertex_descriptor sink):
- m_g(g),
- m_index_map(idx),
- m_cap_map(cap),
- m_res_cap_map(res),
- m_rev_edge_map(rev),
- m_pre_map(pre),
- m_tree_map(color),
- m_dist_map(dist),
- m_source(src),
- m_sink(sink),
- m_active_nodes(),
- m_in_active_list_vec(num_vertices(g), false),
- m_in_active_list_map(make_iterator_property_map(m_in_active_list_vec.begin(), m_index_map)),
- m_has_parent_vec(num_vertices(g), false),
- m_has_parent_map(make_iterator_property_map(m_has_parent_vec.begin(), m_index_map)),
- m_time_vec(num_vertices(g), 0),
- m_time_map(make_iterator_property_map(m_time_vec.begin(), m_index_map)),
- m_flow(0),
- m_time(1),
- m_last_grow_vertex(graph_traits<Graph>::null_vertex()){
- // initialize the color-map with gray-values
- vertex_iterator vi, v_end;
- for(tie(vi, v_end) = vertices(m_g); vi != v_end; ++vi){
- set_tree(*vi, tColorTraits::gray());
- }
- // Initialize flow to zero which means initializing
- // the residual capacity equal to the capacity
- edge_iterator ei, e_end;
- for(tie(ei, e_end) = edges(m_g); ei != e_end; ++ei) {
- m_res_cap_map[*ei] = m_cap_map[*ei];
- assert(m_rev_edge_map[m_rev_edge_map[*ei]] == *ei); //check if the reverse edge map is build up properly
- }
- //init the search trees with the two terminals
- set_tree(m_source, tColorTraits::black());
- set_tree(m_sink, tColorTraits::white());
- m_time_map[m_source] = 1;
- m_time_map[m_sink] = 1;
- }
-
- ~kolmogorov(){}
-
- tEdgeVal max_flow(){
- //augment direct paths from SOURCE->SINK and SOURCE->VERTEX->SINK
- augment_direct_paths();
- //start the main-loop
- while(true){
- bool path_found;
- edge_descriptor connecting_edge;
- tie(connecting_edge, path_found) = grow(); //find a path from source to sink
- if(!path_found){
- //we're finished, no more paths were found
- break;
- }
- ++m_time;
- augment(connecting_edge); //augment that path
- adopt(); //rebuild search tree structure
- }
- return m_flow;
- }
+namespace detail {
- //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)
- protected:
- void augment_direct_paths(){
- //in a first step, we augment all direct paths from source->NODE->sink
- //and additionally paths from source->sink
- //this improves especially graphcuts for segmentation, as most of the nodes have source/sink connects
- //but shouldn't have an impact on other maxflow problems (this is done in grow() anyway)
+template <class Graph,
+ class EdgeCapacityMap,
+ class ResidualCapacityEdgeMap,
+ class ReverseEdgeMap,
+ class PredecessorMap,
+ class ColorMap,
+ class DistanceMap,
+ class IndexMap>
+class bk_max_flow {
+ typedef typename property_traits<EdgeCapacityMap>::value_type tEdgeVal;
+ typedef graph_traits<Graph> tGraphTraits;
+ typedef typename tGraphTraits::vertex_iterator vertex_iterator;
+ typedef typename tGraphTraits::vertex_descriptor vertex_descriptor;
+ typedef typename tGraphTraits::edge_descriptor edge_descriptor;
+ typedef typename tGraphTraits::edge_iterator edge_iterator;
+ typedef typename tGraphTraits::out_edge_iterator out_edge_iterator;
+ typedef boost::queue<vertex_descriptor> tQueue; //queue of vertices, used in adoption-stage
+ typedef typename property_traits<ColorMap>::value_type tColorValue;
+ typedef color_traits<tColorValue> tColorTraits;
+ typedef typename property_traits<DistanceMap>::value_type tDistanceVal;
+
+ public:
+ bk_max_flow(Graph& g,
+ EdgeCapacityMap cap,
+ ResidualCapacityEdgeMap res,
+ ReverseEdgeMap rev,
+ PredecessorMap pre,
+ ColorMap color,
+ DistanceMap dist,
+ IndexMap idx,
+ vertex_descriptor src,
+ vertex_descriptor sink):
+ m_g(g),
+ m_index_map(idx),
+ m_cap_map(cap),
+ m_res_cap_map(res),
+ m_rev_edge_map(rev),
+ m_pre_map(pre),
+ m_tree_map(color),
+ m_dist_map(dist),
+ m_source(src),
+ m_sink(sink),
+ m_active_nodes(),
+ m_in_active_list_vec(num_vertices(g), false),
+ m_in_active_list_map(make_iterator_property_map(m_in_active_list_vec.begin(), m_index_map)),
+ m_has_parent_vec(num_vertices(g), false),
+ m_has_parent_map(make_iterator_property_map(m_has_parent_vec.begin(), m_index_map)),
+ m_time_vec(num_vertices(g), 0),
+ m_time_map(make_iterator_property_map(m_time_vec.begin(), m_index_map)),
+ m_flow(0),
+ m_time(1),
+ m_last_grow_vertex(graph_traits<Graph>::null_vertex()){
+ // initialize the color-map with gray-values
+ vertex_iterator vi, v_end;
+ for(tie(vi, v_end) = vertices(m_g); vi != v_end; ++vi){
+ set_tree(*vi, tColorTraits::gray());
+ }
+ // Initialize flow to zero which means initializing
+ // the residual capacity equal to the capacity
+ edge_iterator ei, e_end;
+ for(tie(ei, e_end) = edges(m_g); ei != e_end; ++ei) {
+ m_res_cap_map[*ei] = m_cap_map[*ei];
+ assert(m_rev_edge_map[m_rev_edge_map[*ei]] == *ei); //check if the reverse edge map is build up properly
+ }
+ //init the search trees with the two terminals
+ set_tree(m_source, tColorTraits::black());
+ set_tree(m_sink, tColorTraits::white());
+ m_time_map[m_source] = 1;
+ m_time_map[m_sink] = 1;
+ }
+
+ tEdgeVal max_flow(){
+ //augment direct paths from SOURCE->SINK and SOURCE->VERTEX->SINK
+ augment_direct_paths();
+ //start the main-loop
+ while(true){
+ bool path_found;
+ edge_descriptor connecting_edge;
+ tie(connecting_edge, path_found) = grow(); //find a path from source to sink
+ if(!path_found){
+ //we're finished, no more paths were found
+ break;
+ }
+ ++m_time;
+ augment(connecting_edge); //augment that path
+ adopt(); //rebuild search tree structure
+ }
+ return m_flow;
+ }
+
+ // the complete class is protected, as we want access to members in
+ // derived test-class (see test/kolmogorov_max_flow_test.cpp)
+ protected:
+ void augment_direct_paths(){
+ // in a first step, we augment all direct paths from source->NODE->sink
+ // and additionally paths from source->sink. This improves especially
+ // graphcuts for segmentation, as most of the nodes have source/sink
+ // connects but shouldn't have an impact on other maxflow problems
+ // (this is done in grow() anyway)
+ out_edge_iterator ei, e_end;
+ for(tie(ei, e_end) = out_edges(m_source, m_g); ei != e_end; ++ei){
+ edge_descriptor from_source = *ei;
+ vertex_descriptor current_node = target(from_source, m_g);
+ if(current_node == m_sink){
+ tEdgeVal cap = m_res_cap_map[from_source];
+ m_res_cap_map[from_source] = 0;
+ m_flow += cap;
+ continue;
+ }
+ edge_descriptor to_sink;
+ bool is_there;
+ tie(to_sink, is_there) = lookup_edge(current_node, m_sink, m_g);
+ if(is_there){
+ tEdgeVal cap_from_source = m_res_cap_map[from_source];
+ tEdgeVal cap_to_sink = m_res_cap_map[to_sink];
+ if(cap_from_source > cap_to_sink){
+ set_tree(current_node, tColorTraits::black());
+ add_active_node(current_node);
+ set_edge_to_parent(current_node, from_source);
+ m_dist_map[current_node] = 1;
+ m_time_map[current_node] = 1;
+ // add stuff to flow and update residuals. we dont need to
+ // update reverse_edges, as incoming/outgoing edges to/from
+ // source/sink don't count for max-flow
+ m_res_cap_map[from_source] -= cap_to_sink;
+ m_res_cap_map[to_sink] = 0;
+ m_flow += cap_to_sink;
+ } else if(cap_to_sink > 0){
+ set_tree(current_node, tColorTraits::white());
+ add_active_node(current_node);
+ set_edge_to_parent(current_node, to_sink);
+ m_dist_map[current_node] = 1;
+ m_time_map[current_node] = 1;
+ // add stuff to flow and update residuals. we dont need to update
+ // reverse_edges, as incoming/outgoing edges to/from source/sink
+ // don't count for max-flow
+ m_res_cap_map[to_sink] -= cap_from_source;
+ m_res_cap_map[from_source] = 0;
+ m_flow += cap_from_source;
+ }
+ } else if(m_res_cap_map[from_source]){
+ // there is no sink connect, so we can't augment this path, but to
+ // avoid adding m_source to the active nodes, we just activate this
+ // node and set the approciate things
+ set_tree(current_node, tColorTraits::black());
+ set_edge_to_parent(current_node, from_source);
+ m_dist_map[current_node] = 1;
+ m_time_map[current_node] = 1;
+ add_active_node(current_node);
+ }
+ }
+ for(tie(ei, e_end) = out_edges(m_sink, m_g); ei != e_end; ++ei){
+ edge_descriptor to_sink = m_rev_edge_map[*ei];
+ vertex_descriptor current_node = source(to_sink, m_g);
+ if(m_res_cap_map[to_sink]){
+ set_tree(current_node, tColorTraits::white());
+ set_edge_to_parent(current_node, to_sink);
+ m_dist_map[current_node] = 1;
+ m_time_map[current_node] = 1;
+ add_active_node(current_node);
+ }
+ }
+ }
+
+ /**
+ * 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
+ * source(returnVal, m_g) is the end of the path found in the source-tree
+ * target(returnVal, m_g) is the beginning of the path found in the sink-tree
+ */
+ std::pair<edge_descriptor, bool> grow(){
+ assert(m_orphans.empty());
+ vertex_descriptor current_node;
+ while((current_node = get_next_active_node()) != graph_traits<Graph>::null_vertex()){ //if there is one
+ assert(get_tree(current_node) != tColorTraits::gray() &&
+ (has_parent(current_node) ||
+ current_node == m_source ||
+ current_node == m_sink));
+
+ if(get_tree(current_node) == tColorTraits::black()){
+ //source tree growing
out_edge_iterator ei, e_end;
- for(tie(ei, e_end) = out_edges(m_source, m_g); ei != e_end; ++ei){
- edge_descriptor from_source = *ei;
- vertex_descriptor current_node = target(from_source, m_g);
- if(current_node == m_sink){
- tEdgeVal cap = m_res_cap_map[from_source];
- m_res_cap_map[from_source] = 0;
- m_flow += cap;
- continue;
- }
- edge_descriptor to_sink;
- bool is_there;
- tie(to_sink, is_there) = lookup_edge(current_node, m_sink, m_g);
- if(is_there){
- tEdgeVal cap_from_source = m_res_cap_map[from_source];
- tEdgeVal cap_to_sink = m_res_cap_map[to_sink];
- if(cap_from_source > cap_to_sink){
- set_tree(current_node, tColorTraits::black());
- add_active_node(current_node);
- set_edge_to_parent(current_node, from_source);
- m_dist_map[current_node] = 1;
- m_time_map[current_node] = 1;
- //add stuff to flow and update residuals
- //we dont need to update reverse_edges, as incoming/outgoing edges to/from source/sink don't count for max-flow
- m_res_cap_map[from_source] -= cap_to_sink;
- m_res_cap_map[to_sink] = 0;
- m_flow += cap_to_sink;
- } else if(cap_to_sink > 0){
- set_tree(current_node, tColorTraits::white());
- add_active_node(current_node);
- set_edge_to_parent(current_node, to_sink);
- m_dist_map[current_node] = 1;
- m_time_map[current_node] = 1;
- //add stuff to flow and update residuals
- //we dont need to update reverse_edges, as incoming/outgoing edges to/from source/sink don't count for max-flow
- m_res_cap_map[to_sink] -= cap_from_source;
- m_res_cap_map[from_source] = 0;
- m_flow += cap_from_source;
+ if(current_node != m_last_grow_vertex){
+ m_last_grow_vertex = current_node;
+ tie(m_last_grow_edge_it, m_last_grow_edge_end) = out_edges(current_node, m_g);
+ }
+ for(; m_last_grow_edge_it != m_last_grow_edge_end; ++m_last_grow_edge_it) {
+ edge_descriptor out_edge = *m_last_grow_edge_it;
+ if(m_res_cap_map[out_edge] > 0){ //check if we have capacity left on this edge
+ vertex_descriptor other_node = target(out_edge, m_g);
+ if(get_tree(other_node) == tColorTraits::gray()){ //it's a free node
+ set_tree(other_node, tColorTraits::black()); //aquire other node to our search tree
+ set_edge_to_parent(other_node, out_edge); //set us as parent
+ m_dist_map[other_node] = m_dist_map[current_node] + 1; //and update the distance-heuristic
+ m_time_map[other_node] = m_time_map[current_node];
+ add_active_node(other_node);
+ } else if(get_tree(other_node) == tColorTraits::black()) {
+ // we do this to get shorter paths. check if we are nearer to
+ // the source as its parent is
+ if(is_closer_to_terminal(current_node, other_node)){
+ set_edge_to_parent(other_node, out_edge);
+ m_dist_map[other_node] = m_dist_map[current_node] + 1;
+ m_time_map[other_node] = m_time_map[current_node];
+ }
+ } else{
+ assert(get_tree(other_node)==tColorTraits::white());
+ //kewl, found a path from one to the other search tree, return
+ // the connecting edge in src->sink dir
+ return std::make_pair(out_edge, true);
}
- } else if(m_res_cap_map[from_source]){
- //there is no sink connect, so we can't augment this path
- //but to avoid adding m_source to the active nodes, we just activate this node and set the approciate things
- set_tree(current_node, tColorTraits::black());
- set_edge_to_parent(current_node, from_source);
- m_dist_map[current_node] = 1;
- m_time_map[current_node] = 1;
- add_active_node(current_node);
}
- }
- for(tie(ei, e_end) = out_edges(m_sink, m_g); ei != e_end; ++ei){
- edge_descriptor to_sink = m_rev_edge_map[*ei];
- vertex_descriptor current_node = source(to_sink, m_g);
- if(m_res_cap_map[to_sink]){
- set_tree(current_node, tColorTraits::white());
- set_edge_to_parent(current_node, to_sink);
- m_dist_map[current_node] = 1;
- m_time_map[current_node] = 1;
- add_active_node(current_node);
+ } //for all out-edges
+ } //source-tree-growing
+ else{
+ assert(get_tree(current_node) == tColorTraits::white());
+ out_edge_iterator ei, e_end;
+ if(current_node != m_last_grow_vertex){
+ m_last_grow_vertex = current_node;
+ tie(m_last_grow_edge_it, m_last_grow_edge_end) = out_edges(current_node, m_g);
+ }
+ for(; m_last_grow_edge_it != m_last_grow_edge_end; ++m_last_grow_edge_it){
+ edge_descriptor in_edge = m_rev_edge_map[*m_last_grow_edge_it];
+ if(m_res_cap_map[in_edge] > 0){ //check if there is capacity left
+ vertex_descriptor other_node = source(in_edge, m_g);
+ if(get_tree(other_node) == tColorTraits::gray()){ //it's a free node
+ set_tree(other_node, tColorTraits::white()); //aquire that node to our search tree
+ set_edge_to_parent(other_node, in_edge); //set us as parent
+ add_active_node(other_node); //activate that node
+ m_dist_map[other_node] = m_dist_map[current_node] + 1; //set its distance
+ m_time_map[other_node] = m_time_map[current_node]; //and time
+ } else if(get_tree(other_node) == tColorTraits::white()){
+ if(is_closer_to_terminal(current_node, other_node)){
+ //we are closer to the sink than its parent is, so we "adopt" him
+ set_edge_to_parent(other_node, in_edge);
+ m_dist_map[other_node] = m_dist_map[current_node] + 1;
+ m_time_map[other_node] = m_time_map[current_node];
+ }
+ } else{
+ assert(get_tree(other_node)==tColorTraits::black());
+ //kewl, found a path from one to the other search tree,
+ // return the connecting edge in src->sink dir
+ return std::make_pair(in_edge, true);
+ }
}
- }
- }
+ } //for all out-edges
+ } //sink-tree growing
- /**
- * 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
- * source(returnVal, m_g) is the end of the path found in the source-tree
- * target(returnVal, m_g) is the beginning of the path found in the sink-tree
- */
- std::pair<edge_descriptor, bool> grow(){
- assert(m_orphans.empty());
- vertex_descriptor current_node;
- while((current_node = get_next_active_node()) != graph_traits<Graph>::null_vertex()){ //if there is one
- assert(get_tree(current_node) != tColorTraits::gray() && (has_parent(current_node) || current_node==m_source || current_node==m_sink));
- if(get_tree(current_node) == tColorTraits::black()){
- //source tree growing
- out_edge_iterator ei, e_end;
- if(current_node != m_last_grow_vertex){
- m_last_grow_vertex = current_node;
- tie(m_last_grow_edge_it, m_last_grow_edge_end) = out_edges(current_node, m_g);
- }
- for(; m_last_grow_edge_it != m_last_grow_edge_end; ++m_last_grow_edge_it){
- edge_descriptor out_edge = *m_last_grow_edge_it;
- if(m_res_cap_map[out_edge] > 0){ //check if we have capacity left on this edge
- vertex_descriptor other_node = target(out_edge, m_g);
- if(get_tree(other_node) == tColorTraits::gray()){ //it's a free node
- set_tree(other_node, tColorTraits::black()); //aquire other node to our search tree
- set_edge_to_parent(other_node, out_edge); //set us as parent
- m_dist_map[other_node] = m_dist_map[current_node] + 1; //and update the distance-heuristic
- m_time_map[other_node] = m_time_map[current_node];
- add_active_node(other_node);
- } else if(get_tree(other_node) == tColorTraits::black()){
- 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
- set_edge_to_parent(other_node, out_edge);
- m_dist_map[other_node] = m_dist_map[current_node] + 1;
- m_time_map[other_node] = m_time_map[current_node];
- }
- } else{
- assert(get_tree(other_node)==tColorTraits::white());
- //kewl, found a path from one to the other search tree, return the connecting edge in src->sink dir
- return std::make_pair(out_edge, true);
- }
+ //all edges of that node are processed, and no more paths were found.
+ // remove if from the front of the active queue
+ finish_node(current_node);
+ } //while active_nodes not empty
+
+ //no active nodes anymore and no path found, we're done
+ return std::make_pair(edge_descriptor(), false);
+ }
+
+ /**
+ * augments path from s->t and updates residual graph
+ * source(e, m_g) is the end of the path found in the source-tree
+ * target(e, m_g) is the beginning of the path found in the sink-tree
+ * this phase generates orphans on satured edges, if the attached verts are
+ * from different search-trees orphans are ordered in distance to
+ * sink/source. first the farest from the source are front_inserted into
+ * the orphans list, 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 verts to the terminals first
+ */
+ void augment(edge_descriptor e) {
+ assert(get_tree(target(e, m_g)) == tColorTraits::white());
+ assert(get_tree(source(e, m_g)) == tColorTraits::black());
+ assert(m_orphans.empty());
+
+ const tEdgeVal bottleneck = find_bottleneck(e);
+ //now we push the found flow through the path
+ //for each edge we saturate we have to look for the verts that belong to that edge, one of them becomes an orphans
+ //now process the connecting edge
+ m_res_cap_map[e] -= bottleneck;
+ assert(m_res_cap_map[e] >= 0);
+ m_res_cap_map[m_rev_edge_map[e]] += bottleneck;
+
+ //now we follow the path back to the source
+ vertex_descriptor current_node = source(e, m_g);
+ while(current_node != m_source){
+ edge_descriptor pred = get_edge_to_parent(current_node);
+ m_res_cap_map[pred] -= bottleneck;
+ assert(m_res_cap_map[pred] >= 0);
+ m_res_cap_map[m_rev_edge_map[pred]] += bottleneck;
+ if(m_res_cap_map[pred] == 0){
+ set_no_parent(current_node);
+ m_orphans.push_front(current_node);
+ }
+ current_node = source(pred, m_g);
+ }
+ //then go forward in the sink-tree
+ current_node = target(e, m_g);
+ while(current_node != m_sink){
+ edge_descriptor pred = get_edge_to_parent(current_node);
+ m_res_cap_map[pred] -= bottleneck;
+ assert(m_res_cap_map[pred] >= 0);
+ m_res_cap_map[m_rev_edge_map[pred]] += bottleneck;
+ if(m_res_cap_map[pred] == 0){
+ set_no_parent(current_node);
+ m_orphans.push_front(current_node);
+ }
+ current_node = target(pred, m_g);
+ }
+ //and add it to the max-flow
+ m_flow += bottleneck;
+ }
+
+ /**
+ * 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)
+ */
+ inline tEdgeVal find_bottleneck(edge_descriptor e){
+ BOOST_USING_STD_MIN();
+ tEdgeVal minimum_cap = m_res_cap_map[e];
+ vertex_descriptor current_node = source(e, m_g);
+ //first go back in the source tree
+ while(current_node != m_source){
+ edge_descriptor pred = get_edge_to_parent(current_node);
+ minimum_cap = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum_cap, m_res_cap_map[pred]);
+ current_node = source(pred, m_g);
+ }
+ //then go forward in the sink-tree
+ current_node = target(e, m_g);
+ while(current_node != m_sink){
+ edge_descriptor pred = get_edge_to_parent(current_node);
+ minimum_cap = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum_cap, m_res_cap_map[pred]);
+ current_node = target(pred, m_g);
+ }
+ return minimum_cap;
+ }
+
+ /**
+ * rebuild search trees
+ * empty the queue of orphans, and find new parents for them or just drop
+ * them from the search trees
+ */
+ void adopt(){
+ while(!m_orphans.empty() || !m_child_orphans.empty()){
+ vertex_descriptor current_node;
+ if(m_child_orphans.empty()){
+ //get the next orphan from the main-queue and remove it
+ current_node = m_orphans.front();
+ m_orphans.pop_front();
+ } else{
+ current_node = m_child_orphans.front();
+ m_child_orphans.pop();
+ }
+ if(get_tree(current_node) == tColorTraits::black()){
+ //we're in the source-tree
+ tDistanceVal min_distance = (std::numeric_limits<tDistanceVal>::max)();
+ edge_descriptor new_parent_edge;
+ out_edge_iterator ei, e_end;
+ for(tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
+ const edge_descriptor in_edge = m_rev_edge_map[*ei];
+ assert(target(in_edge, m_g) == current_node); //we should be the target of this edge
+ if(m_res_cap_map[in_edge] > 0){
+ vertex_descriptor other_node = source(in_edge, m_g);
+ if(get_tree(other_node) == tColorTraits::black() && has_source_connect(other_node)){
+ if(m_dist_map[other_node] < min_distance){
+ min_distance = m_dist_map[other_node];
+ new_parent_edge = in_edge;
}
- } //for all out-edges
- } //source-tree-growing
- else{
- assert(get_tree(current_node) == tColorTraits::white());
- out_edge_iterator ei, e_end;
- if(current_node != m_last_grow_vertex){
- m_last_grow_vertex = current_node;
- tie(m_last_grow_edge_it, m_last_grow_edge_end) = out_edges(current_node, m_g);
}
- for(; m_last_grow_edge_it != m_last_grow_edge_end; ++m_last_grow_edge_it){
- edge_descriptor in_edge = m_rev_edge_map[*m_last_grow_edge_it];
- if(m_res_cap_map[in_edge] > 0){ //check if there is capacity left
- vertex_descriptor other_node = source(in_edge, m_g);
- if(get_tree(other_node) == tColorTraits::gray()){ //it's a free node
- set_tree(other_node, tColorTraits::white()); //aquire that node to our search tree
- set_edge_to_parent(other_node, in_edge); //set us as parent
- add_active_node(other_node); //activate that node
- m_dist_map[other_node] = m_dist_map[current_node] + 1; //set its distance
- m_time_map[other_node] = m_time_map[current_node]; //and time
- } else if(get_tree(other_node) == tColorTraits::white()){
- if(is_closer_to_terminal(current_node, other_node)){
- //we are closer to the sink than its parent is, so we "adopt" him
- set_edge_to_parent(other_node, in_edge);
- m_dist_map[other_node] = m_dist_map[current_node] + 1;
- m_time_map[other_node] = m_time_map[current_node];
- }
- } else{
- assert(get_tree(other_node)==tColorTraits::black());
- //kewl, found a path from one to the other search tree, return the connecting edge in src->sink dir
- return std::make_pair(in_edge, true);
- }
- }
- } //for all out-edges
- } //sink-tree growing
- //all edges of that node are processed, and no more paths were found. so remove if from the front of the active queue
- finish_node(current_node);
- } //while active_nodes not empty
- return std::make_pair(edge_descriptor(), false); //no active nodes anymore and no path found, we're done
- }
-
- /**
- * augments path from s->t and updates residual graph
- * source(e, m_g) is the end of the path found in the source-tree
- * target(e, m_g) is the beginning of the path found in the sink-tree
- * this phase generates orphans on satured edges, if the attached verts are from different search-trees
- * orphans are ordered in distance to sink/source. first the farest from the source are front_inserted into the orphans list,
- * 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
- * verts to the terminals first
- */
- void augment(edge_descriptor e){
- assert(get_tree(target(e, m_g)) == tColorTraits::white());
- assert(get_tree(source(e, m_g)) == tColorTraits::black());
- assert(m_orphans.empty());
-
- const tEdgeVal bottleneck = find_bottleneck(e);
- //now we push the found flow through the path
- //for each edge we saturate we have to look for the verts that belong to that edge, one of them becomes an orphans
- //now process the connecting edge
- m_res_cap_map[e] -= bottleneck;
- assert(m_res_cap_map[e] >= 0);
- m_res_cap_map[m_rev_edge_map[e]] += bottleneck;
-
- //now we follow the path back to the source
- vertex_descriptor current_node = source(e, m_g);
- while(current_node != m_source){
- edge_descriptor pred = get_edge_to_parent(current_node);
- m_res_cap_map[pred] -= bottleneck;
- assert(m_res_cap_map[pred] >= 0);
- m_res_cap_map[m_rev_edge_map[pred]] += bottleneck;
- if(m_res_cap_map[pred] == 0){
- set_no_parent(current_node);
- m_orphans.push_front(current_node);
}
- current_node = source(pred, m_g);
}
- //then go forward in the sink-tree
- current_node = target(e, m_g);
- while(current_node != m_sink){
- edge_descriptor pred = get_edge_to_parent(current_node);
- m_res_cap_map[pred] -= bottleneck;
- assert(m_res_cap_map[pred] >= 0);
- m_res_cap_map[m_rev_edge_map[pred]] += bottleneck;
- if(m_res_cap_map[pred] == 0){
- set_no_parent(current_node);
- m_orphans.push_front(current_node);
- }
- current_node = target(pred, m_g);
- }
- //and add it to the max-flow
- m_flow += bottleneck;
- }
-
- /**
- * 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)
- */
- inline tEdgeVal find_bottleneck(edge_descriptor e){
- BOOST_USING_STD_MIN();
- tEdgeVal minimum_cap = m_res_cap_map[e];
- vertex_descriptor current_node = source(e, m_g);
- //first go back in the source tree
- while(current_node != m_source){
- edge_descriptor pred = get_edge_to_parent(current_node);
- minimum_cap = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum_cap, m_res_cap_map[pred]);
- current_node = source(pred, m_g);
- }
- //then go forward in the sink-tree
- current_node = target(e, m_g);
- while(current_node != m_sink){
- edge_descriptor pred = get_edge_to_parent(current_node);
- minimum_cap = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum_cap, m_res_cap_map[pred]);
- current_node = target(pred, m_g);
- }
- return minimum_cap;
- }
-
- /**
- * rebuild search trees
- * empty the queue of orphans, and find new parents for them or just drop them from the search trees
- */
- void adopt(){
- while(!m_orphans.empty() || !m_child_orphans.empty()){
- vertex_descriptor current_node;
- if(m_child_orphans.empty()){
- //get the next orphan from the main-queue and remove it
- current_node = m_orphans.front();
- m_orphans.pop_front();
- } else{
- current_node = m_child_orphans.front();
- m_child_orphans.pop();
- }
- if(get_tree(current_node) == tColorTraits::black()){
- //we're in the source-tree
- tDistanceVal min_distance = (std::numeric_limits<tDistanceVal>::max)();
- edge_descriptor new_parent_edge;
- out_edge_iterator ei, e_end;
- for(tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
- const edge_descriptor in_edge = m_rev_edge_map[*ei];
- assert(target(in_edge, m_g) == current_node); //we should be the target of this edge
+ if(min_distance != (std::numeric_limits<tDistanceVal>::max)()){
+ set_edge_to_parent(current_node, new_parent_edge);
+ m_dist_map[current_node] = min_distance + 1;
+ m_time_map[current_node] = m_time;
+ } else{
+ m_time_map[current_node] = 0;
+ for(tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
+ edge_descriptor in_edge = m_rev_edge_map[*ei];
+ vertex_descriptor other_node = source(in_edge, m_g);
+ if(get_tree(other_node) == tColorTraits::black() && has_parent(other_node)){
if(m_res_cap_map[in_edge] > 0){
- vertex_descriptor other_node = source(in_edge, m_g);
- if(get_tree(other_node) == tColorTraits::black() && has_source_connect(other_node)){
- if(m_dist_map[other_node] < min_distance){
- min_distance = m_dist_map[other_node];
- new_parent_edge = in_edge;
- }
- }
- }
- }
- if(min_distance != (std::numeric_limits<tDistanceVal>::max)()){
- set_edge_to_parent(current_node, new_parent_edge);
- m_dist_map[current_node] = min_distance + 1;
- m_time_map[current_node] = m_time;
- } else{
- m_time_map[current_node] = 0;
- for(tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
- edge_descriptor in_edge = m_rev_edge_map[*ei];
- vertex_descriptor other_node = source(in_edge, m_g);
- if(get_tree(other_node) == tColorTraits::black() && has_parent(other_node)){
- if(m_res_cap_map[in_edge] > 0){
- add_active_node(other_node);
- }
- if(source(get_edge_to_parent(other_node), m_g) == current_node){
- //we are the parent of that node
- //it has to find a new parent, too
- set_no_parent(other_node);
- m_child_orphans.push(other_node);
- }
- }
+ add_active_node(other_node);
}
- set_tree(current_node, tColorTraits::gray());
- } //no parent found
- } //source-tree-adoption
- else{
- //now we should be in the sink-tree, check that...
- assert(get_tree(current_node) == tColorTraits::white());
- out_edge_iterator ei, e_end;
- edge_descriptor new_parent_edge;
- tDistanceVal min_distance = (std::numeric_limits<tDistanceVal>::max)();
- for(tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
- const edge_descriptor out_edge = *ei;
- if(m_res_cap_map[out_edge] > 0){
- const vertex_descriptor other_node = target(out_edge, m_g);
- if(get_tree(other_node) == tColorTraits::white() && has_sink_connect(other_node))
- if(m_dist_map[other_node] < min_distance){
- min_distance = m_dist_map[other_node];
- new_parent_edge = out_edge;
- }
+ if(source(get_edge_to_parent(other_node), m_g) == current_node){
+ //we are the parent of that node
+ //it has to find a new parent, too
+ set_no_parent(other_node);
+ m_child_orphans.push(other_node);
}
}
- if(min_distance != (std::numeric_limits<tDistanceVal>::max)()){
- set_edge_to_parent(current_node, new_parent_edge);
- m_dist_map[current_node] = min_distance + 1;
- m_time_map[current_node] = m_time;
- } else{
- m_time_map[current_node] = 0;
- for(tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
- const edge_descriptor out_edge = *ei;
- const vertex_descriptor other_node = target(out_edge, m_g);
- if(get_tree(other_node) == tColorTraits::white() && has_parent(other_node)){
- if(m_res_cap_map[out_edge] > 0){
- add_active_node(other_node);
- }
- if(target(get_edge_to_parent(other_node), m_g) == current_node){
- //we were it's parent, so it has to find a new one, too
- set_no_parent(other_node);
- m_child_orphans.push(other_node);
- }
- }
+ }
+ set_tree(current_node, tColorTraits::gray());
+ } //no parent found
+ } //source-tree-adoption
+ else{
+ //now we should be in the sink-tree, check that...
+ assert(get_tree(current_node) == tColorTraits::white());
+ out_edge_iterator ei, e_end;
+ edge_descriptor new_parent_edge;
+ tDistanceVal min_distance = (std::numeric_limits<tDistanceVal>::max)();
+ for(tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
+ const edge_descriptor out_edge = *ei;
+ if(m_res_cap_map[out_edge] > 0){
+ const vertex_descriptor other_node = target(out_edge, m_g);
+ if(get_tree(other_node) == tColorTraits::white() && has_sink_connect(other_node))
+ if(m_dist_map[other_node] < min_distance){
+ min_distance = m_dist_map[other_node];
+ new_parent_edge = out_edge;
}
- set_tree(current_node, tColorTraits::gray());
- } //no parent found
- } //sink-tree adoption
- } //while !orphans.empty()
- } //adopt
-
- /**
- * return next active vertex if there is one, otherwise a null_vertex
- */
- inline vertex_descriptor get_next_active_node(){
- while(true){
- if(m_active_nodes.empty())
- return graph_traits<Graph>::null_vertex();
- vertex_descriptor v = m_active_nodes.front();
-
- 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)
- m_active_nodes.pop();
- m_in_active_list_map[v] = false;
- } else{
- assert(get_tree(v) == tColorTraits::black() || get_tree(v) == tColorTraits::white());
- return v;
}
}
- }
-
- /**
- * adds v as an active vertex, but only if its not in the list already
- */
- inline void add_active_node(vertex_descriptor v){
- assert(get_tree(v) != tColorTraits::gray());
- if(m_in_active_list_map[v]){
- return;
+ if(min_distance != (std::numeric_limits<tDistanceVal>::max)()){
+ set_edge_to_parent(current_node, new_parent_edge);
+ m_dist_map[current_node] = min_distance + 1;
+ m_time_map[current_node] = m_time;
} else{
- m_in_active_list_map[v] = true;
- m_active_nodes.push(v);
- }
- }
+ m_time_map[current_node] = 0;
+ for(tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
+ const edge_descriptor out_edge = *ei;
+ const vertex_descriptor other_node = target(out_edge, m_g);
+ if(get_tree(other_node) == tColorTraits::white() && has_parent(other_node)){
+ if(m_res_cap_map[out_edge] > 0){
+ add_active_node(other_node);
+ }
+ if(target(get_edge_to_parent(other_node), m_g) == current_node){
+ //we were it's parent, so it has to find a new one, too
+ set_no_parent(other_node);
+ m_child_orphans.push(other_node);
+ }
+ }
+ }
+ set_tree(current_node, tColorTraits::gray());
+ } //no parent found
+ } //sink-tree adoption
+ } //while !orphans.empty()
+ } //adopt
+
+ /**
+ * return next active vertex if there is one, otherwise a null_vertex
+ */
+ inline vertex_descriptor get_next_active_node(){
+ while(true){
+ if(m_active_nodes.empty())
+ return graph_traits<Graph>::null_vertex();
+ vertex_descriptor v = m_active_nodes.front();
- /**
- * 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)
- */
- inline void finish_node(vertex_descriptor v){
- assert(m_active_nodes.front() == v);
+ //if it has no parent, this node can't be active (if its not source or sink)
+ if(!has_parent(v) && v != m_source && v != m_sink){
m_active_nodes.pop();
m_in_active_list_map[v] = false;
- m_last_grow_vertex = graph_traits<Graph>::null_vertex();
- }
-
- /**
- * removes a vertex from the queue of active nodes (actually this does nothing,
- * but checks if this node has no parent edge, as this is the criteria for beeing no more active)
- */
- inline void remove_active_node(vertex_descriptor v){
- assert(!has_parent(v));
- }
-
- /**
- * returns the search tree of v; tColorValue::black() for source tree, white() for sink tree, gray() for no tree
- */
- inline tColorValue get_tree(vertex_descriptor v) const {
- return m_tree_map[v];
- }
-
- /**
- * sets search tree of v; tColorValue::black() for source tree, white() for sink tree, gray() for no tree
- */
- inline void set_tree(vertex_descriptor v, tColorValue t){
- m_tree_map[v] = t;
- }
-
- /**
- * returns edge to parent vertex of v;
- */
- inline edge_descriptor get_edge_to_parent(vertex_descriptor v) const{
- return m_pre_map[v];
- }
-
- /**
- * returns true if the edge stored in m_pre_map[v] is a valid entry
- */
- inline bool has_parent(vertex_descriptor v) const{
- return m_has_parent_map[v];
- }
-
- /**
- * sets edge to parent vertex of v;
- */
- inline void set_edge_to_parent(vertex_descriptor v, edge_descriptor f_edge_to_parent){
- assert(m_res_cap_map[f_edge_to_parent] > 0);
- m_pre_map[v] = f_edge_to_parent;
- m_has_parent_map[v] = true;
- }
-
- /**
- * removes the edge to parent of v (this is done by invalidating the entry an additional map)
- */
- inline void set_no_parent(vertex_descriptor v){
- m_has_parent_map[v] = false;
- }
-
- /**
- * checks if vertex v has a connect to the sink-vertex (@var m_sink)
- * @param v the vertex which is checked
- * @return true if a path to the sink was found, false if not
- */
- inline bool has_sink_connect(vertex_descriptor v){
- tDistanceVal current_distance = 0;
- vertex_descriptor current_vertex = v;
- while(true){
- if(m_time_map[current_vertex] == m_time){
- //we found a node which was already checked this round. use it for distance calculations
- current_distance += m_dist_map[current_vertex];
- break;
- }
- if(current_vertex == m_sink){
- m_time_map[m_sink] = m_time;
- break;
- }
- if(has_parent(current_vertex)){
- //it has a parent, so get it
- current_vertex = target(get_edge_to_parent(current_vertex), m_g);
- ++current_distance;
- } else{
- //no path found
- return false;
- }
- }
- current_vertex=v;
- while(m_time_map[current_vertex] != m_time){
- m_dist_map[current_vertex] = current_distance--;
- m_time_map[current_vertex] = m_time;
- current_vertex = target(get_edge_to_parent(current_vertex), m_g);
- }
- return true;
- }
-
- /**
- * checks if vertex v has a connect to the source-vertex (@var m_source)
- * @param v the vertex which is checked
- * @return true if a path to the source was found, false if not
- */
- inline bool has_source_connect(vertex_descriptor v){
- tDistanceVal current_distance = 0;
- vertex_descriptor current_vertex = v;
- while(true){
- if(m_time_map[current_vertex] == m_time){
- //we found a node which was already checked this round. use it for distance calculations
- current_distance += m_dist_map[current_vertex];
- break;
- }
- if(current_vertex == m_source){
- m_time_map[m_source] = m_time;
- break;
- }
- if(has_parent(current_vertex)){
- //it has a parent, so get it
- current_vertex = source(get_edge_to_parent(current_vertex), m_g);
- ++current_distance;
- } else{
- //no path found
- return false;
- }
- }
- current_vertex=v;
- while(m_time_map[current_vertex] != m_time){
- m_dist_map[current_vertex] = current_distance-- ;
- m_time_map[current_vertex] = m_time;
- current_vertex = source(get_edge_to_parent(current_vertex), m_g);
- }
- return true;
- }
+ } else{
+ assert(get_tree(v) == tColorTraits::black() || get_tree(v) == tColorTraits::white());
+ return v;
+ }
+ }
+ }
+
+ /**
+ * adds v as an active vertex, but only if its not in the list already
+ */
+ inline void add_active_node(vertex_descriptor v){
+ assert(get_tree(v) != tColorTraits::gray());
+ if(m_in_active_list_map[v]){
+ return;
+ } else{
+ m_in_active_list_map[v] = true;
+ m_active_nodes.push(v);
+ }
+ }
+
+ /**
+ * 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)
+ */
+ inline void finish_node(vertex_descriptor v){
+ assert(m_active_nodes.front() == v);
+ m_active_nodes.pop();
+ m_in_active_list_map[v] = false;
+ m_last_grow_vertex = graph_traits<Graph>::null_vertex();
+ }
+
+ /**
+ * removes a vertex from the queue of active nodes (actually this does nothing,
+ * but checks if this node has no parent edge, as this is the criteria for
+ * being no more active)
+ */
+ inline void remove_active_node(vertex_descriptor v){
+ assert(!has_parent(v));
+ }
+
+ /**
+ * returns the search tree of v; tColorValue::black() for source tree,
+ * white() for sink tree, gray() for no tree
+ */
+ inline tColorValue get_tree(vertex_descriptor v) const {
+ return m_tree_map[v];
+ }
+
+ /**
+ * sets search tree of v; tColorValue::black() for source tree, white()
+ * for sink tree, gray() for no tree
+ */
+ inline void set_tree(vertex_descriptor v, tColorValue t){
+ m_tree_map[v] = t;
+ }
+
+ /**
+ * returns edge to parent vertex of v;
+ */
+ inline edge_descriptor get_edge_to_parent(vertex_descriptor v) const{
+ return m_pre_map[v];
+ }
+
+ /**
+ * returns true if the edge stored in m_pre_map[v] is a valid entry
+ */
+ inline bool has_parent(vertex_descriptor v) const{
+ return m_has_parent_map[v];
+ }
+
+ /**
+ * sets edge to parent vertex of v;
+ */
+ inline void set_edge_to_parent(vertex_descriptor v, edge_descriptor f_edge_to_parent){
+ assert(m_res_cap_map[f_edge_to_parent] > 0);
+ m_pre_map[v] = f_edge_to_parent;
+ m_has_parent_map[v] = true;
+ }
+
+ /**
+ * removes the edge to parent of v (this is done by invalidating the
+ * entry an additional map)
+ */
+ inline void set_no_parent(vertex_descriptor v){
+ m_has_parent_map[v] = false;
+ }
+
+ /**
+ * checks if vertex v has a connect to the sink-vertex (@var m_sink)
+ * @param v the vertex which is checked
+ * @return true if a path to the sink was found, false if not
+ */
+ inline bool has_sink_connect(vertex_descriptor v){
+ tDistanceVal current_distance = 0;
+ vertex_descriptor current_vertex = v;
+ while(true){
+ if(m_time_map[current_vertex] == m_time){
+ //we found a node which was already checked this round. use it for distance calculations
+ current_distance += m_dist_map[current_vertex];
+ break;
+ }
+ if(current_vertex == m_sink){
+ m_time_map[m_sink] = m_time;
+ break;
+ }
+ if(has_parent(current_vertex)){
+ //it has a parent, so get it
+ current_vertex = target(get_edge_to_parent(current_vertex), m_g);
+ ++current_distance;
+ } else{
+ //no path found
+ return false;
+ }
+ }
+ current_vertex=v;
+ while(m_time_map[current_vertex] != m_time){
+ m_dist_map[current_vertex] = current_distance--;
+ m_time_map[current_vertex] = m_time;
+ current_vertex = target(get_edge_to_parent(current_vertex), m_g);
+ }
+ return true;
+ }
+
+ /**
+ * checks if vertex v has a connect to the source-vertex (@var m_source)
+ * @param v the vertex which is checked
+ * @return true if a path to the source was found, false if not
+ */
+ inline bool has_source_connect(vertex_descriptor v){
+ tDistanceVal current_distance = 0;
+ vertex_descriptor current_vertex = v;
+ while(true){
+ if(m_time_map[current_vertex] == m_time){
+ //we found a node which was already checked this round. use it for distance calculations
+ current_distance += m_dist_map[current_vertex];
+ break;
+ }
+ if(current_vertex == m_source){
+ m_time_map[m_source] = m_time;
+ break;
+ }
+ if(has_parent(current_vertex)){
+ //it has a parent, so get it
+ current_vertex = source(get_edge_to_parent(current_vertex), m_g);
+ ++current_distance;
+ } else{
+ //no path found
+ return false;
+ }
+ }
+ current_vertex=v;
+ while(m_time_map[current_vertex] != m_time){
+ m_dist_map[current_vertex] = current_distance-- ;
+ m_time_map[current_vertex] = m_time;
+ current_vertex = source(get_edge_to_parent(current_vertex), m_g);
+ }
+ return true;
+ }
+
+ /**
+ * returns true, if p is closer to a terminal than q
+ */
+ inline bool is_closer_to_terminal(vertex_descriptor p, vertex_descriptor q){
+ //checks the timestamps first, to build no cycles, and after that the real distance
+ return (m_time_map[q] <= m_time_map[p] && m_dist_map[q] > m_dist_map[p]+1);
+ }
+
+ ////////
+ // member vars
+ ////////
+ Graph& m_g;
+ IndexMap m_index_map;
+ EdgeCapacityMap m_cap_map;
+ ResidualCapacityEdgeMap m_res_cap_map;
+ ReverseEdgeMap m_rev_edge_map;
+ PredecessorMap m_pre_map; //stores paths found in the growth stage
+ ColorMap m_tree_map; //maps each vertex into one of the two search tree or none (gray())
+ DistanceMap m_dist_map; //stores distance to source/sink nodes
+ vertex_descriptor m_source;
+ vertex_descriptor m_sink;
+
+ tQueue m_active_nodes;
+ std::vector<bool> m_in_active_list_vec;
+ iterator_property_map<std::vector<bool>::iterator, IndexMap> m_in_active_list_map;
+
+ std::list<vertex_descriptor> m_orphans;
+ tQueue m_child_orphans; // we use a second queuqe for child orphans, as they are FIFO processed
+
+ std::vector<bool> m_has_parent_vec;
+ iterator_property_map<std::vector<bool>::iterator, IndexMap> m_has_parent_map;
+
+ std::vector<long> m_time_vec; //timestamp of each node, used for sink/source-path calculations
+ iterator_property_map<std::vector<long>::iterator, IndexMap> m_time_map;
+ tEdgeVal m_flow;
+ long m_time;
+ vertex_descriptor m_last_grow_vertex;
+ out_edge_iterator m_last_grow_edge_it;
+ out_edge_iterator m_last_grow_edge_end;
+};
+
+} //namespace boost::detail
+
+/**
+ * non-named-parameter version, given everything
+ * this is the catch all version
+ */
+template<class Graph,
+ class CapacityEdgeMap,
+ class ResidualCapacityEdgeMap,
+ class ReverseEdgeMap, class PredecessorMap,
+ class ColorMap,
+ class DistanceMap,
+ class IndexMap>
+typename property_traits<CapacityEdgeMap>::value_type
+boykov_kolmogorov_max_flow(Graph& g,
+ CapacityEdgeMap cap,
+ ResidualCapacityEdgeMap res_cap,
+ ReverseEdgeMap rev_map,
+ PredecessorMap pre_map,
+ ColorMap color,
+ DistanceMap dist,
+ IndexMap idx,
+ typename graph_traits<Graph>::vertex_descriptor src,
+ typename graph_traits<Graph>::vertex_descriptor sink)
+{
+ typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+ typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
+
+ //as this method is the last one before we instantiate the solver, we do the concept checks here
+ function_requires<VertexListGraphConcept<Graph> >(); //to have vertices(), num_vertices(),
+ function_requires<EdgeListGraphConcept<Graph> >(); //to have edges()
+ function_requires<IncidenceGraphConcept<Graph> >(); //to have source(), target() and out_edges()
+ function_requires<LvaluePropertyMapConcept<CapacityEdgeMap, edge_descriptor> >(); //read flow-values from edges
+ function_requires<Mutable_LvaluePropertyMapConcept<ResidualCapacityEdgeMap, edge_descriptor> >(); //write flow-values to residuals
+ function_requires<LvaluePropertyMapConcept<ReverseEdgeMap, edge_descriptor> >(); //read out reverse edges
+ function_requires<Mutable_LvaluePropertyMapConcept<PredecessorMap, vertex_descriptor> >(); //store predecessor there
+ function_requires<Mutable_LvaluePropertyMapConcept<ColorMap, vertex_descriptor> >(); //write corresponding tree
+ function_requires<Mutable_LvaluePropertyMapConcept<DistanceMap, vertex_descriptor> >(); //write distance to source/sink
+ function_requires<ReadablePropertyMapConcept<IndexMap, vertex_descriptor> >(); //get index 0...|V|-1
+ assert(num_vertices(g) >= 2 && src != sink);
+
+ detail::bk_max_flow<
+ Graph, CapacityEdgeMap, ResidualCapacityEdgeMap, ReverseEdgeMap,
+ PredecessorMap, ColorMap, DistanceMap, IndexMap
+ > algo(g, cap, res_cap, rev_map, pre_map, color, dist, idx, src, sink);
+
+ return algo.max_flow();
+}
+
+/**
+ * non-named-parameter version, given capacity, residucal_capacity,
+ * reverse_edges, and an index map.
+ */
+template<class Graph,
+ class CapacityEdgeMap,
+ class ResidualCapacityEdgeMap,
+ class ReverseEdgeMap,
+ class IndexMap>
+typename property_traits<CapacityEdgeMap>::value_type
+boykov_kolmogorov_max_flow(Graph& g,
+ CapacityEdgeMap cap,
+ ResidualCapacityEdgeMap res_cap,
+ ReverseEdgeMap rev,
+ IndexMap idx,
+ typename graph_traits<Graph>::vertex_descriptor src,
+ typename graph_traits<Graph>::vertex_descriptor sink)
+{
+ typename graph_traits<Graph>::vertices_size_type n_verts = num_vertices(g);
+ std::vector<typename graph_traits<Graph>::edge_descriptor> predecessor_vec(n_verts);
+ std::vector<default_color_type> color_vec(n_verts);
+ std::vector<typename graph_traits<Graph>::vertices_size_type> distance_vec(n_verts);
+ return
+ boykov_kolmogorov_max_flow(
+ g, cap, res_cap, rev,
+ make_iterator_property_map(predecessor_vec.begin(), idx),
+ make_iterator_property_map(color_vec.begin(), idx),
+ make_iterator_property_map(distance_vec.begin(), idx),
+ idx, src, sink);
+}
+
+/**
+ * non-named-parameter version, some given: capacity, residual_capacity,
+ * reverse_edges, color_map and an index map. Use this if you are interested in
+ * the minimum cut, as the color map provides that info.
+ */
+template<class Graph,
+ class CapacityEdgeMap,
+ class ResidualCapacityEdgeMap,
+ class ReverseEdgeMap,
+ class ColorMap,
+ class IndexMap>
+typename property_traits<CapacityEdgeMap>::value_type
+boykov_kolmogorov_max_flow(Graph& g,
+ CapacityEdgeMap cap,
+ ResidualCapacityEdgeMap res_cap,
+ ReverseEdgeMap rev,
+ ColorMap color,
+ IndexMap idx,
+ typename graph_traits<Graph>::vertex_descriptor src,
+ typename graph_traits<Graph>::vertex_descriptor sink)
+{
+ typename graph_traits<Graph>::vertices_size_type n_verts = num_vertices(g);
+ std::vector<typename graph_traits<Graph>::edge_descriptor> predecessor_vec(n_verts);
+ std::vector<typename graph_traits<Graph>::vertices_size_type> distance_vec(n_verts);
+ return
+ boykov_kolmogorov_max_flow(
+ g, cap, res_cap, rev,
+ make_iterator_property_map(predecessor_vec.begin(), idx),
+ color,
+ make_iterator_property_map(distance_vec.begin(), idx),
+ idx, src, sink);
+}
+
+/**
+ * named-parameter version, some given
+ */
+template<class Graph, class P, class T, class R>
+typename property_traits<typename property_map<Graph, edge_capacity_t>::const_type>::value_type
+boykov_kolmogorov_max_flow(Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor src,
+ typename graph_traits<Graph>::vertex_descriptor sink,
+ const bgl_named_params<P, T, R>& params)
+{
+ return
+ boykov_kolmogorov_max_flow(
+ g,
+ choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity),
+ choose_pmap(get_param(params, edge_residual_capacity), g, edge_residual_capacity),
+ choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse),
+ choose_pmap(get_param(params, vertex_predecessor), g, vertex_predecessor),
+ choose_pmap(get_param(params, vertex_color), g, vertex_color),
+ choose_pmap(get_param(params, vertex_distance), g, vertex_distance),
+ choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
+ src, sink);
+}
+
+/**
+ * named-parameter version, none given
+ */
+template<class Graph>
+typename property_traits<typename property_map<Graph, edge_capacity_t>::const_type>::value_type
+boykov_kolmogorov_max_flow(Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor src,
+ typename graph_traits<Graph>::vertex_descriptor sink)
+{
+ bgl_named_params<int, buffer_param_t> params(0); // bogus empty param
+ return boykov_kolmogorov_max_flow(g, src, sink, params);
+}
- /**
- * returns true, if p is closer to a terminal than q
- */
- inline bool is_closer_to_terminal(vertex_descriptor p, vertex_descriptor q){
- //checks the timestamps first, to build no cycles, and after that the real distance
- return (m_time_map[q] <= m_time_map[p] && m_dist_map[q] > m_dist_map[p]+1);
- }
-
- ////////
- // member vars
- ////////
- Graph& m_g;
- IndexMap m_index_map;
- EdgeCapacityMap m_cap_map;
- ResidualCapacityEdgeMap m_res_cap_map;
- ReverseEdgeMap m_rev_edge_map;
- PredecessorMap m_pre_map; //stores paths found in the growth stage
- ColorMap m_tree_map; //maps each vertex into one of the two search tree or none (gray())
- DistanceMap m_dist_map; //stores distance to source/sink nodes
- vertex_descriptor m_source;
- vertex_descriptor m_sink;
-
- tQueue m_active_nodes;
- std::vector<bool> m_in_active_list_vec;
- iterator_property_map<std::vector<bool>::iterator, IndexMap> m_in_active_list_map;
-
- std::list<vertex_descriptor> m_orphans;
- tQueue m_child_orphans; // we use a second queuqe for child orphans, as they are FIFO processed
-
- std::vector<bool> m_has_parent_vec;
- iterator_property_map<std::vector<bool>::iterator, IndexMap> m_has_parent_map;
-
- std::vector<long> m_time_vec; //timestamp of each node, used for sink/source-path calculations
- iterator_property_map<std::vector<long>::iterator, IndexMap> m_time_map;
- tEdgeVal m_flow;
- long m_time;
- vertex_descriptor m_last_grow_vertex;
- out_edge_iterator m_last_grow_edge_it;
- out_edge_iterator m_last_grow_edge_end;
- };
- } //namespace detail
-
- /**
- * non-named-parameter version, given everything
- * this is the catch all version
- */
- template <class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap,
- class PredecessorMap, class ColorMap, class DistanceMap, class IndexMap>
- typename property_traits<CapacityEdgeMap>::value_type
- kolmogorov_max_flow
- (Graph& g,
- CapacityEdgeMap cap,
- ResidualCapacityEdgeMap res_cap,
- ReverseEdgeMap rev_map,
- PredecessorMap pre_map,
- ColorMap color,
- DistanceMap dist,
- IndexMap idx,
- typename graph_traits<Graph>::vertex_descriptor src,
- typename graph_traits<Graph>::vertex_descriptor sink
- )
- {
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
- //as this method is the last one before we instantiate the solver, we do the concept checks here
- function_requires<VertexListGraphConcept<Graph> >(); //to have vertices(), num_vertices(),
- function_requires<EdgeListGraphConcept<Graph> >(); //to have edges()
- function_requires<IncidenceGraphConcept<Graph> >(); //to have source(), target() and out_edges()
- function_requires<LvaluePropertyMapConcept<CapacityEdgeMap, edge_descriptor> >(); //read flow-values from edges
- function_requires<Mutable_LvaluePropertyMapConcept<ResidualCapacityEdgeMap, edge_descriptor> >(); //write flow-values to residuals
- function_requires<LvaluePropertyMapConcept<ReverseEdgeMap, edge_descriptor> >(); //read out reverse edges
- function_requires<Mutable_LvaluePropertyMapConcept<PredecessorMap, vertex_descriptor> >(); //store predecessor there
- function_requires<Mutable_LvaluePropertyMapConcept<ColorMap, vertex_descriptor> >(); //write corresponding tree
- function_requires<Mutable_LvaluePropertyMapConcept<DistanceMap, vertex_descriptor> >(); //write distance to source/sink
- function_requires<ReadablePropertyMapConcept<IndexMap, vertex_descriptor> >(); //get index 0...|V|-1
- assert(num_vertices(g) >= 2 && src != sink);
- detail::kolmogorov<Graph, CapacityEdgeMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap>
- algo(g, cap, res_cap, rev_map, pre_map, color, dist, idx, src, sink);
- return algo.max_flow();
- }
-
- /**
- * non-named-parameter version, given: capacity, residucal_capacity, reverse_edges, and an index map.
- */
- template <class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap, class IndexMap>
- typename property_traits<CapacityEdgeMap>::value_type
- kolmogorov_max_flow
- (Graph& g,
- CapacityEdgeMap cap,
- ResidualCapacityEdgeMap res_cap,
- ReverseEdgeMap rev,
- IndexMap idx,
- typename graph_traits<Graph>::vertex_descriptor src,
- typename graph_traits<Graph>::vertex_descriptor sink)
- {
- typename graph_traits<Graph>::vertices_size_type n_verts = num_vertices(g);
- std::vector<typename graph_traits<Graph>::edge_descriptor> predecessor_vec(n_verts);
- std::vector<default_color_type> color_vec(n_verts);
- std::vector<typename graph_traits<Graph>::vertices_size_type> distance_vec(n_verts);
- return kolmogorov_max_flow
- (g, cap, res_cap, rev,
- make_iterator_property_map(predecessor_vec.begin(), idx),
- make_iterator_property_map(color_vec.begin(), idx),
- make_iterator_property_map(distance_vec.begin(), idx),
- idx, src, sink);
- }
-
- /**
- * non-named-parameter version, some given: capacity, residual_capacity, reverse_edges, color_map and an index map.
- * Use this if you are interested in the minimum cut, as the color map provides that info
- */
- template <class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap, class ColorMap, class IndexMap>
- typename property_traits<CapacityEdgeMap>::value_type
- kolmogorov_max_flow
- (Graph& g,
- CapacityEdgeMap cap,
- ResidualCapacityEdgeMap res_cap,
- ReverseEdgeMap rev,
- ColorMap color,
- IndexMap idx,
- typename graph_traits<Graph>::vertex_descriptor src,
- typename graph_traits<Graph>::vertex_descriptor sink)
- {
- typename graph_traits<Graph>::vertices_size_type n_verts = num_vertices(g);
- std::vector<typename graph_traits<Graph>::edge_descriptor> predecessor_vec(n_verts);
- std::vector<typename graph_traits<Graph>::vertices_size_type> distance_vec(n_verts);
-
- return kolmogorov_max_flow
- (g, cap, res_cap, rev,
- make_iterator_property_map(predecessor_vec.begin(), idx),
- color,
- make_iterator_property_map(distance_vec.begin(), idx),
- idx, src, sink);
- }
-
- /**
- * named-parameter version, some given
- */
- template <class Graph, class P, class T, class R>
- typename property_traits<typename property_map<Graph, edge_capacity_t>::const_type>::value_type
- kolmogorov_max_flow
- (Graph& g,
- typename graph_traits<Graph>::vertex_descriptor src,
- typename graph_traits<Graph>::vertex_descriptor sink,
- const bgl_named_params<P, T, R>& params)
- {
- return kolmogorov_max_flow(g,
- choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity),
- choose_pmap(get_param(params, edge_residual_capacity), g, edge_residual_capacity),
- choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse),
- choose_pmap(get_param(params, vertex_predecessor), g, vertex_predecessor),
- choose_pmap(get_param(params, vertex_color), g, vertex_color),
- choose_pmap(get_param(params, vertex_distance), g, vertex_distance),
- choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
- src, sink);
- }
-
- /**
- * named-parameter version, none given
- */
- template <class Graph>
- typename property_traits<typename property_map<Graph, edge_capacity_t>::const_type>::value_type
- kolmogorov_max_flow
- (Graph& g,
- typename graph_traits<Graph>::vertex_descriptor src,
- typename graph_traits<Graph>::vertex_descriptor sink)
- {
- bgl_named_params<int, buffer_param_t> params(0); // bogus empty param
- return kolmogorov_max_flow(g, src, sink, params);
- }
} // namespace boost
-#endif // BOOST_KOLMOGOROV_MAX_FLOW_HPP
+#endif // BOOST_BOYKOV_KOLMOGOROV_MAX_FLOW_HPP
Modified: trunk/boost/graph/kolmogorov_max_flow.hpp
==============================================================================
--- trunk/boost/graph/kolmogorov_max_flow.hpp (original)
+++ trunk/boost/graph/kolmogorov_max_flow.hpp 2010-06-21 11:35:42 EDT (Mon, 21 Jun 2010)
@@ -32,6 +32,10 @@
#ifndef BOOST_KOLMOGOROV_MAX_FLOW_HPP
#define BOOST_KOLMOGOROV_MAX_FLOW_HPP
+#warning \
+ The kolmogorov_max_flow.hpp header is deprecated and will be removed \
+ in Boost 1.46. Use boykov_kolmogorov_max_flow.hpp instead.
+
#include <boost/config.hpp>
#include <cassert>
#include <vector>
@@ -121,7 +125,7 @@
m_time_map[m_source] = 1;
m_time_map[m_sink] = 1;
}
-
+
~kolmogorov(){}
tEdgeVal max_flow(){
@@ -134,7 +138,7 @@
tie(connecting_edge, path_found) = grow(); //find a path from source to sink
if(!path_found){
//we're finished, no more paths were found
- break;
+ break;
}
++m_time;
augment(connecting_edge); //augment that path
@@ -213,7 +217,7 @@
}
/**
- * 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
+ * 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
* source(returnVal, m_g) is the end of the path found in the source-tree
* target(returnVal, m_g) is the beginning of the path found in the sink-tree
*/
@@ -221,14 +225,14 @@
assert(m_orphans.empty());
vertex_descriptor current_node;
while((current_node = get_next_active_node()) != graph_traits<Graph>::null_vertex()){ //if there is one
- assert(get_tree(current_node) != tColorTraits::gray() && (has_parent(current_node) || current_node==m_source || current_node==m_sink));
- if(get_tree(current_node) == tColorTraits::black()){
+ assert(get_tree(current_node) != tColorTraits::gray() && (has_parent(current_node) || current_node==m_source || current_node==m_sink));
+ if(get_tree(current_node) == tColorTraits::black()){
//source tree growing
out_edge_iterator ei, e_end;
if(current_node != m_last_grow_vertex){
m_last_grow_vertex = current_node;
tie(m_last_grow_edge_it, m_last_grow_edge_end) = out_edges(current_node, m_g);
- }
+ }
for(; m_last_grow_edge_it != m_last_grow_edge_end; ++m_last_grow_edge_it){
edge_descriptor out_edge = *m_last_grow_edge_it;
if(m_res_cap_map[out_edge] > 0){ //check if we have capacity left on this edge
@@ -245,7 +249,7 @@
m_dist_map[other_node] = m_dist_map[current_node] + 1;
m_time_map[other_node] = m_time_map[current_node];
}
- } else{
+ } else{
assert(get_tree(other_node)==tColorTraits::white());
//kewl, found a path from one to the other search tree, return the connecting edge in src->sink dir
return std::make_pair(out_edge, true);
@@ -297,7 +301,7 @@
* target(e, m_g) is the beginning of the path found in the sink-tree
* this phase generates orphans on satured edges, if the attached verts are from different search-trees
* orphans are ordered in distance to sink/source. first the farest from the source are front_inserted into the orphans list,
- * 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
+ * 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
* verts to the terminals first
*/
void augment(edge_descriptor e){
@@ -381,7 +385,7 @@
current_node = m_child_orphans.front();
m_child_orphans.pop();
}
- if(get_tree(current_node) == tColorTraits::black()){
+ if(get_tree(current_node) == tColorTraits::black()){
//we're in the source-tree
tDistanceVal min_distance = (std::numeric_limits<tDistanceVal>::max)();
edge_descriptor new_parent_edge;
@@ -449,7 +453,7 @@
for(tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
const edge_descriptor out_edge = *ei;
const vertex_descriptor other_node = target(out_edge, m_g);
- if(get_tree(other_node) == tColorTraits::white() && has_parent(other_node)){
+ if(get_tree(other_node) == tColorTraits::white() && has_parent(other_node)){
if(m_res_cap_map[out_edge] > 0){
add_active_node(other_node);
}
@@ -468,7 +472,7 @@
/**
* return next active vertex if there is one, otherwise a null_vertex
- */
+ */
inline vertex_descriptor get_next_active_node(){
while(true){
if(m_active_nodes.empty())
@@ -487,7 +491,7 @@
/**
* adds v as an active vertex, but only if its not in the list already
- */
+ */
inline void add_active_node(vertex_descriptor v){
assert(get_tree(v) != tColorTraits::gray());
if(m_in_active_list_map[v]){
@@ -509,8 +513,8 @@
}
/**
- * removes a vertex from the queue of active nodes (actually this does nothing,
- * but checks if this node has no parent edge, as this is the criteria for beeing no more active)
+ * removes a vertex from the queue of active nodes (actually this does nothing,
+ * but checks if this node has no parent edge, as this is the criteria for beeing no more active)
*/
inline void remove_active_node(vertex_descriptor v){
assert(!has_parent(v));
@@ -541,12 +545,12 @@
* returns true if the edge stored in m_pre_map[v] is a valid entry
*/
inline bool has_parent(vertex_descriptor v) const{
- return m_has_parent_map[v];
+ return m_has_parent_map[v];
}
/**
- * sets edge to parent vertex of v;
- */
+ * sets edge to parent vertex of v;
+ */
inline void set_edge_to_parent(vertex_descriptor v, edge_descriptor f_edge_to_parent){
assert(m_res_cap_map[f_edge_to_parent] > 0);
m_pre_map[v] = f_edge_to_parent;
@@ -576,7 +580,7 @@
}
if(current_vertex == m_sink){
m_time_map[m_sink] = m_time;
- break;
+ break;
}
if(has_parent(current_vertex)){
//it has a parent, so get it
@@ -673,12 +677,12 @@
out_edge_iterator m_last_grow_edge_end;
};
} //namespace detail
-
+
/**
* non-named-parameter version, given everything
* this is the catch all version
- */
- template <class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap,
+ */
+ template <class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap,
class PredecessorMap, class ColorMap, class DistanceMap, class IndexMap>
typename property_traits<CapacityEdgeMap>::value_type
kolmogorov_max_flow
@@ -738,7 +742,7 @@
make_iterator_property_map(distance_vec.begin(), idx),
idx, src, sink);
}
-
+
/**
* non-named-parameter version, some given: capacity, residual_capacity, reverse_edges, color_map and an index map.
* Use this if you are interested in the minimum cut, as the color map provides that info
@@ -766,7 +770,7 @@
make_iterator_property_map(distance_vec.begin(), idx),
idx, src, sink);
}
-
+
/**
* named-parameter version, some given
*/
@@ -788,7 +792,7 @@
choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
src, sink);
}
-
+
/**
* named-parameter version, none given
*/
Copied: trunk/libs/graph/doc/boykov_kolmogorov_max_flow.html (from r63187, /trunk/libs/graph/doc/kolmogorov_max_flow.html)
==============================================================================
--- /trunk/libs/graph/doc/kolmogorov_max_flow.html (original)
+++ trunk/libs/graph/doc/boykov_kolmogorov_max_flow.html 2010-06-21 11:35:42 EDT (Mon, 21 Jun 2010)
@@ -2,13 +2,13 @@
<HTML>
<HEAD>
<META HTTP-EQUIV="CONTENT-TYPE" CONTENT="text/html; charset=iso-8859-15">
- <TITLE>Boost Graph Library: Kolmogorov Maximum Flow</TITLE>
+ <TITLE>Boost Graph Library: Boykov-Kolmogorov Maximum Flow</TITLE>
<META NAME="GENERATOR" CONTENT="OpenOffice.org 2.0 (Linux)">
<META NAME="CREATED" CONTENT="20060820;17315200">
<META NAME="CHANGEDBY" CONTENT="Stephan Diederich">
<META NAME="CHANGED" CONTENT="20060820;23125100">
<!--
-// Copyright (c) 2006, Stephan Diederich
+// Copyright (c) 2006 Stephan Diederich
//
// This documentation may be used under either of the following two licences:
//
@@ -55,12 +55,12 @@
<BODY LANG="de-DE" TEXT="#000000" LINK="#0000ee" VLINK="#551a8b" BGCOLOR="#ffffff" DIR="LTR">
<P><IMG SRC="../../../boost.png" NAME="Grafik1" ALT="C++ Boost" ALIGN=BOTTOM WIDTH=277 HEIGHT=86 BORDER=0>
</P>
-<H1><A NAME="sec:kolmogorov_max_flow"></A><TT>kolmogorov_max_flow</TT>
+<H1><A NAME="sec:boykov_kolmogorov_max_flow"></A><TT>boykov_kolmogorov_max_flow</TT>
</H1>
<PRE><I>// named parameter version</I>
template <class Graph, class P, class T, class R>
typename property_traits<typename property_map<Graph, edge_capacity_t>::const_type>::value_type
-kolmogorov_max_flow(Graph& g,
+boykov_kolmogorov_max_flow(Graph& g,
typename graph_traits<Graph>::vertex_descriptor src,
typename graph_traits<Graph>::vertex_descriptor sink,
const bgl_named_params<P, T, R>& params = <I>all defaults</I>)
@@ -69,7 +69,7 @@
template <class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap,
class PredecessorMap, class ColorMap, class DistanceMap, class IndexMap>
typename property_traits<CapacityEdgeMap>::value_type
-kolmogorov_max_flow(Graph& g,
+boykov_kolmogorov_max_flow(Graph& g,
CapacityEdgeMap cap,
ResidualCapacityEdgeMap res_cap,
ReverseEdgeMap rev_map,
@@ -82,37 +82,40 @@
<FONT SIZE=3>Additional overloaded versions for non-named parameters
are provided (without DistanceMap/ColorMap/DistanceMap; for those
iterator_property_maps with the provided index map are used)</FONT></P>
-<P>The <TT>kolmogorov_max_flow()</TT> function calculates the maximum
+<P>The <TT>boykov_kolmogorov_max_flow()</TT> function calculates the maximum
flow of a network. See Section <A HREF="graph_theory_review.html#sec:network-flow-algorithms">Network
Flow Algorithms</A> for a description of maximum flow. The calculated
maximum flow will be the return value of the function. The function
also calculates the flow values <I>f(u,v)</I> for all <I>(u,v)</I> in
<I>E</I>, which are returned in the form of the residual capacity
-<I>r(u,v) = c(u,v) - f(u,v)</I>.
+<I>r(u,v) = c(u,v) - f(u,v)</I>.
</P>
<P><B>Requirements:</B><BR>The directed graph <I>G=(V,E)</I> that
represents the network must include a reverse edge for every edge in
<I>E</I>. That is, the input graph should be <I>G<SUB>in</SUB> =
(V,{E U E<SUP>T</SUP>})</I>. The <TT>ReverseEdgeMap</TT> argument <TT>rev</TT>
must map each edge in the original graph to its reverse edge, that is
-<I>(u,v) -> (v,u)</I> for all <I>(u,v)</I> in <I>E</I>.
+<I>(u,v) -> (v,u)</I> for all <I>(u,v)</I> in <I>E</I>.
</P>
+
<P>Remarks: While the push-relabel method states that each edge in <I>E<SUP>T</SUP></I>
has to have capacity of 0, the reverse edges for this algorithm ARE
allowed to carry capacities. If there are already reverse edges in
the input Graph <I><FONT FACE="Courier New, monospace">G</FONT></I>,
those can be used. This can halve the amount of edges and will
-noticeably increase the performance.<BR><BR><B>Algorithm
-description:</B><BR>Kolmogorov's algorithm is a variety of the
-augmenting-path algorithm. Standard augmenting path algorithms find
-shortest paths from source to sink vertex and augment them by
-substracting the bottleneck capacity found on that path from the
-residual capacities of each edge and adding it to the total flow.
-Additionally the minimum capacity is added to the residual capacity
-of the reverse edges. If no more paths in the residual-edge tree are
-found, the algorithm terminates. Instead of finding a new shortest
-path from source to sink in the graph in each iteration, Kolmogorov's
-version keeps the already found paths as follows:</P>
+noticeably increase the performance.</P>
+
+<P>
+<B>Algorithm description:</B><BR>The Boykov-Kolmogorov max-flow (or often
+BK max-flow) algorithm is a variety of the augmenting-path algorithm. Standard
+augmenting path algorithms find shortest paths from source to sink vertex and
+augment them by substracting the bottleneck capacity found on that path from the
+residual capacities of each edge and adding it to the total flow. Additionally
+the minimum capacity is added to the residual capacity of the reverse edges. If
+no more paths in the residual-edge tree are found, the algorithm terminates.
+Instead of finding a new shortest path from source to sink in the graph in each
+iteration, Kolmogorov's version keeps the already found paths as follows:</P>
+
<P>The algorithm builds up two search trees, a source-tree and a
sink-tree. Each vertex has a label (stored in <I>ColorMap</I>) to
which tree it belongs and a status-flag if this vertex is active or
@@ -151,11 +154,11 @@
found, this vertex becomes a free vertex (marked gray), and it's
children become orphans. The adoption phase terminates if there are
no more orphans.</P>
-<P><IMG SRC="figs/kolmogorov_max_flow.gif" NAME="Grafik2" ALIGN=LEFT WIDTH=827 HEIGHT=311 BORDER=0><BR CLEAR=LEFT><B>Details:</B></P>
+<P><IMG SRC="figs/bk_max_flow.gif" NAME="Grafik2" ALIGN=LEFT WIDTH=827 HEIGHT=311 BORDER=0><BR CLEAR=LEFT><B>Details:</B></P>
<UL>
<LI><P>Marking heuristics: A timestamp is stored for each vertex
which shows in which iteration of the algorithm the distance to the
- corresponding terminal was calculated.
+ corresponding terminal was calculated.
</P>
<UL>
<LI><P>This distance is used and gets calculated in the
@@ -182,35 +185,34 @@
the main queue for the same reason.</P>
</UL>
<P><BR><B>Implementation notes:</B></P>
-<P>The algorithm is mainly implemented as described in the PhD thesis
-of Kolmogorov. Few changes were made for increasing performance:</P>
+<P>The algorithm is mainly implemented as described by Boykov and Kolmogorov in
+[69]. An extended version
+can be found in the PhD Thesis of Kolmogorov [68].
+The following changes are made to improve performance:</P>
<UL>
- <LI><P>initialization: the algorithm first augments all paths from
+ <LI>initialization: the algorithm first augments all paths from
source->sink and all paths from source->VERTEX->sink. This
improves especially graph-cuts used in image vision where nearly
each vertex has a source and sink connect. During this step, all
vertices that have an unsaturated connection from source are added
- to the active vertex list and so the source is not.
- </P>
- <LI><P>active vertices: Kolmogorov uses two lists for active nodes
+ to the active vertex list and so the source is not.</LI>
+ <LI>active vertices: Kolmogorov uses two lists for active nodes
and states that new active vertices are added to the rear of the
second. Fetching an active vertex is done from the beginning of the
first list. If the first list is empty, it is exchanged by the
- second. This implementation uses just one list.</P>
- <LI><P>grow-phase: In the grow phase the first vertex in the
+ second. This implementation uses just one list.</LI>
+ <LI>grow-phase: In the grow phase the first vertex in the
active-list is taken and all outgoing edges are checked if they are
unsaturated. This decreases performance for graphs with high-edge
density. This implementation stores the last accessed edge and
continues with it, if the first vertex in the active-list is the
- same one as during the last grow-phase.</P>
+ same one as during the last grow-phase.</LI>
</UL>
-<P>This algorithm [68, 69] was developed by Boykov and Kolmogorov.
-</P>
<H3>Where Defined</H3>
-<P><TT>boost/graph/kolmogorov_max_flow.hpp</TT>
+<P><TT>boost/graph/boykov_kolmogorov_max_flow.hpp</TT>
</P>
<H3>Parameters</H3>
-<P>IN: <TT>Graph& g</TT>
+<P>IN: <TT>Graph& g</TT>
</P>
<BLOCKQUOTE>A directed graph. The graph's type must be a model of
<A HREF="VertexListGraph.html">Vertex List Graph</A>, <A HREF="EdgeListGraph.html">Edge
@@ -220,46 +222,46 @@
improved if the graph type also models <a href="AdjacencyMatrix.html">Adjacency
Matrix</a>.
</BLOCKQUOTE>
-<P>IN: <TT>vertex_descriptor src</TT>
+<P>IN: <TT>vertex_descriptor src</TT>
</P>
-<BLOCKQUOTE>The source vertex for the flow network graph.
+<BLOCKQUOTE>The source vertex for the flow network graph.
</BLOCKQUOTE>
-<P>IN: <TT>vertex_descriptor sink</TT>
+<P>IN: <TT>vertex_descriptor sink</TT>
</P>
-<BLOCKQUOTE>The sink vertex for the flow network graph.
+<BLOCKQUOTE>The sink vertex for the flow network graph.
</BLOCKQUOTE>
<H3>Named Parameters</H3>
-<P>IN: <TT>edge_capacity(EdgeCapacityMap cap)</TT>
+<P>IN: <TT>edge_capacity(EdgeCapacityMap cap)</TT>
</P>
<BLOCKQUOTE>The edge capacity property map. The type must be a model
of a constant <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue
Property Map</A>. The key type of the map must be the graph's edge
-descriptor type.<BR><B>Default:</B> <TT>get(edge_capacity, g)</TT>
+descriptor type.<BR><B>Default:</B> <TT>get(edge_capacity, g)</TT>
</BLOCKQUOTE>
-<P>OUT: <TT>edge_residual_capacity(ResidualCapacityEdgeMap res)</TT>
+<P>OUT: <TT>edge_residual_capacity(ResidualCapacityEdgeMap res)</TT>
</P>
<BLOCKQUOTE>The edge residual capacity property map. The type must be
a model of a mutable <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue
Property Map</A>. The key type of the map must be the graph's edge
descriptor type.<BR><B>Default:</B> <TT>get(edge_residual_capacity,
-g)</TT>
+g)</TT>
</BLOCKQUOTE>
-<P>IN: <TT>edge_reverse(ReverseEdgeMap rev)</TT>
+<P>IN: <TT>edge_reverse(ReverseEdgeMap rev)</TT>
</P>
<BLOCKQUOTE>An edge property map that maps every edge <I>(u,v)</I> in
the graph to the reverse edge <I>(v,u)</I>. The map must be a model
of constant <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue
Property Map</A>. The key type of the map must be the graph's edge
-descriptor type.<BR><B>Default:</B> <TT>get(edge_reverse, g)</TT>
+descriptor type.<BR><B>Default:</B> <TT>get(edge_reverse, g)</TT>
</BLOCKQUOTE>
-<P>UTIL: <TT>vertex_predecessor(PredecessorMap pre_map)</TT>
+<P>UTIL: <TT>vertex_predecessor(PredecessorMap pre_map)</TT>
</P>
<BLOCKQUOTE>A vertex property map that stores the edge to the vertex'
predecessor. The map must be a model of mutable <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue
Property Map</A>. The key type of the map must be the graph's vertex
descriptor type.<BR><B>Default:</B> <TT>get(vertex_predecessor, g)</TT>
</BLOCKQUOTE>
-<P>OUT/UTIL: <TT>vertex_color(ColorMap color)</TT>
+<P>OUT/UTIL: <TT>vertex_color(ColorMap color)</TT>
</P>
<BLOCKQUOTE>A vertex property map that stores a color for edge
vertex. If the color of a vertex after running the algorithm is black
@@ -267,35 +269,35 @@
sink-tree (used for minimum cuts). The map must be a model of mutable
<A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
Map</A>. The key type of the map must be the graph's vertex
-descriptor type.<BR><B>Default:</B> <TT>get(vertex_color, g)</TT>
+descriptor type.<BR><B>Default:</B> <TT>get(vertex_color, g)</TT>
</BLOCKQUOTE>
-<P>UTIL: <TT>vertex_distance(DistanceMap dist)</TT>
+<P>UTIL: <TT>vertex_distance(DistanceMap dist)</TT>
</P>
<BLOCKQUOTE>A vertex property map that stores the distance to the
corresponding terminal. It's a utility-map for speeding up the
algorithm. The map must be a model of mutable <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue
Property Map</A>. The key type of the map must be the graph's vertex
-descriptor type.<BR><B>Default:</B> <TT>get(vertex_distance, g)</TT>
+descriptor type.<BR><B>Default:</B> <TT>get(vertex_distance, g)</TT>
</BLOCKQUOTE>
-<P>IN: <TT>vertex_index(VertexIndexMap index_map)</TT>
+<P>IN: <TT>vertex_index(VertexIndexMap index_map)</TT>
</P>
<BLOCKQUOTE>Maps each vertex of the graph to a unique integer in the
range <TT>[0, num_vertices(g))</TT>. The map must be a model of
constant LvaluePropertyMap.
The key type of the map must be the graph's vertex descriptor
-type.<BR><B>Default:</B> <TT>get(vertex_index, g)</TT>
+type.<BR><B>Default:</B> <TT>get(vertex_index, g)</TT>
</BLOCKQUOTE>
<H3>Example</H3>
<P>This reads an example maximum flow problem (a graph with edge
capacities) from a file in the DIMACS format (<TT>example/max_flow.dat</TT>).
The source for this example can be found in
-<TT>example/kolmogorov-eg.cpp</TT>.
+<TT>example/boykov_kolmogorov-eg.cpp</TT>.
</P>
<PRE>#include <boost/config.hpp>
#include <iostream>
#include <string>
-#include <boost/graph/kolmogorov_max_flow.hpp>
#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/graph/read_dimacs.hpp>
#include <boost/graph/graph_utility.hpp>
@@ -311,11 +313,11 @@
property < vertex_color_t, boost::default_color_type,
property < vertex_distance_t, long,
property < vertex_predecessor_t, Traits::edge_descriptor > > > > >,
-
+
property < edge_capacity_t, long,
property < edge_residual_capacity_t, long,
property < edge_reverse_t, Traits::edge_descriptor > > > > Graph;
-
+
Graph g;
property_map < Graph, edge_capacity_t >::type
capacity = get(edge_capacity, g);
@@ -327,7 +329,7 @@
std::vector<default_color_type> color(num_vertices(g));
std::vector<long> distance(num_vertices(g));
- long flow = kolmogorov_max_flow(g ,s, t);
+ long flow = boykov_kolmogorov_max_flow(g ,s, t);
std::cout << "c The total flow:" << std::endl;
std::cout << "s " << flow << std::endl << std::endl;
@@ -343,7 +345,7 @@
return EXIT_SUCCESS;
}</PRE><P>
-The output is:
+The output is:
</P>
<PRE>c The total flow:
s 13
@@ -370,7 +372,9 @@
f 7 6 0
f 7 5 0</PRE><H3>
See Also</H3>
-<P STYLE="margin-bottom: 0cm"><TT>edmonds_karp_max_flow()</TT>,<BR><TT>push_relabel_max_flow()</TT>.
+<P STYLE="margin-bottom: 0cm">
+<TT>edmonds_karp_max_flow()</TT>,
+<TT>push_relabel_max_flow()</TT>.
</P>
<HR>
<TABLE CELLPADDING=2 CELLSPACING=2>
Modified: trunk/libs/graph/doc/kolmogorov_max_flow.html
==============================================================================
--- trunk/libs/graph/doc/kolmogorov_max_flow.html (original)
+++ trunk/libs/graph/doc/kolmogorov_max_flow.html 2010-06-21 11:35:42 EDT (Mon, 21 Jun 2010)
@@ -53,14 +53,31 @@
</STYLE>
</HEAD>
<BODY LANG="de-DE" TEXT="#000000" LINK="#0000ee" VLINK="#551a8b" BGCOLOR="#ffffff" DIR="LTR">
-<P><IMG SRC="../../../boost.png" NAME="Grafik1" ALT="C++ Boost" ALIGN=BOTTOM WIDTH=277 HEIGHT=86 BORDER=0>
+
+<P>
+<IMG SRC="../../../boost.png" NAME="Grafik1" ALT="C++ Boost" ALIGN=BOTTOM WIDTH=277 HEIGHT=86 BORDER=0>
</P>
+
+<table align="center" width="75%" style="border:1px solid; border-spacing: 10pt">
+<tr>
+ <td style="vertical-align: top"><img src="figs/warning.png"></td>
+ <td>
+ <b>Warning!</b> This header and its contents are <em>deprecated</em> and
+ will be removed in a future release. Please update your program to use
+ boykov_kolmogorov_max_flow
+ instead. Note that only the name of the algorithm has changed. The template
+ and function parameters will remain the same.
+ </td>
+</tr>
+</table>
+
+
<H1><A NAME="sec:kolmogorov_max_flow"></A><TT>kolmogorov_max_flow</TT>
</H1>
<PRE><I>// named parameter version</I>
template <class Graph, class P, class T, class R>
typename property_traits<typename property_map<Graph, edge_capacity_t>::const_type>::value_type
-kolmogorov_max_flow(Graph& g,
+kolmogorov_max_flow(Graph& g,
typename graph_traits<Graph>::vertex_descriptor src,
typename graph_traits<Graph>::vertex_descriptor sink,
const bgl_named_params<P, T, R>& params = <I>all defaults</I>)
@@ -88,14 +105,14 @@
maximum flow will be the return value of the function. The function
also calculates the flow values <I>f(u,v)</I> for all <I>(u,v)</I> in
<I>E</I>, which are returned in the form of the residual capacity
-<I>r(u,v) = c(u,v) - f(u,v)</I>.
+<I>r(u,v) = c(u,v) - f(u,v)</I>.
</P>
<P><B>Requirements:</B><BR>The directed graph <I>G=(V,E)</I> that
represents the network must include a reverse edge for every edge in
<I>E</I>. That is, the input graph should be <I>G<SUB>in</SUB> =
(V,{E U E<SUP>T</SUP>})</I>. The <TT>ReverseEdgeMap</TT> argument <TT>rev</TT>
must map each edge in the original graph to its reverse edge, that is
-<I>(u,v) -> (v,u)</I> for all <I>(u,v)</I> in <I>E</I>.
+<I>(u,v) -> (v,u)</I> for all <I>(u,v)</I> in <I>E</I>.
</P>
<P>Remarks: While the push-relabel method states that each edge in <I>E<SUP>T</SUP></I>
has to have capacity of 0, the reverse edges for this algorithm ARE
@@ -155,7 +172,7 @@
<UL>
<LI><P>Marking heuristics: A timestamp is stored for each vertex
which shows in which iteration of the algorithm the distance to the
- corresponding terminal was calculated.
+ corresponding terminal was calculated.
</P>
<UL>
<LI><P>This distance is used and gets calculated in the
@@ -190,7 +207,7 @@
improves especially graph-cuts used in image vision where nearly
each vertex has a source and sink connect. During this step, all
vertices that have an unsaturated connection from source are added
- to the active vertex list and so the source is not.
+ to the active vertex list and so the source is not.
</P>
<LI><P>active vertices: Kolmogorov uses two lists for active nodes
and states that new active vertices are added to the rear of the
@@ -210,7 +227,7 @@
<P><TT>boost/graph/kolmogorov_max_flow.hpp</TT>
</P>
<H3>Parameters</H3>
-<P>IN: <TT>Graph& g</TT>
+<P>IN: <TT>Graph& g</TT>
</P>
<BLOCKQUOTE>A directed graph. The graph's type must be a model of
<A HREF="VertexListGraph.html">Vertex List Graph</A>, <A HREF="EdgeListGraph.html">Edge
@@ -220,46 +237,46 @@
improved if the graph type also models <a href="AdjacencyMatrix.html">Adjacency
Matrix</a>.
</BLOCKQUOTE>
-<P>IN: <TT>vertex_descriptor src</TT>
+<P>IN: <TT>vertex_descriptor src</TT>
</P>
-<BLOCKQUOTE>The source vertex for the flow network graph.
+<BLOCKQUOTE>The source vertex for the flow network graph.
</BLOCKQUOTE>
-<P>IN: <TT>vertex_descriptor sink</TT>
+<P>IN: <TT>vertex_descriptor sink</TT>
</P>
-<BLOCKQUOTE>The sink vertex for the flow network graph.
+<BLOCKQUOTE>The sink vertex for the flow network graph.
</BLOCKQUOTE>
<H3>Named Parameters</H3>
-<P>IN: <TT>edge_capacity(EdgeCapacityMap cap)</TT>
+<P>IN: <TT>edge_capacity(EdgeCapacityMap cap)</TT>
</P>
<BLOCKQUOTE>The edge capacity property map. The type must be a model
of a constant <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue
Property Map</A>. The key type of the map must be the graph's edge
-descriptor type.<BR><B>Default:</B> <TT>get(edge_capacity, g)</TT>
+descriptor type.<BR><B>Default:</B> <TT>get(edge_capacity, g)</TT>
</BLOCKQUOTE>
-<P>OUT: <TT>edge_residual_capacity(ResidualCapacityEdgeMap res)</TT>
+<P>OUT: <TT>edge_residual_capacity(ResidualCapacityEdgeMap res)</TT>
</P>
<BLOCKQUOTE>The edge residual capacity property map. The type must be
a model of a mutable <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue
Property Map</A>. The key type of the map must be the graph's edge
descriptor type.<BR><B>Default:</B> <TT>get(edge_residual_capacity,
-g)</TT>
+g)</TT>
</BLOCKQUOTE>
-<P>IN: <TT>edge_reverse(ReverseEdgeMap rev)</TT>
+<P>IN: <TT>edge_reverse(ReverseEdgeMap rev)</TT>
</P>
<BLOCKQUOTE>An edge property map that maps every edge <I>(u,v)</I> in
the graph to the reverse edge <I>(v,u)</I>. The map must be a model
of constant <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue
Property Map</A>. The key type of the map must be the graph's edge
-descriptor type.<BR><B>Default:</B> <TT>get(edge_reverse, g)</TT>
+descriptor type.<BR><B>Default:</B> <TT>get(edge_reverse, g)</TT>
</BLOCKQUOTE>
-<P>UTIL: <TT>vertex_predecessor(PredecessorMap pre_map)</TT>
+<P>UTIL: <TT>vertex_predecessor(PredecessorMap pre_map)</TT>
</P>
<BLOCKQUOTE>A vertex property map that stores the edge to the vertex'
predecessor. The map must be a model of mutable <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue
Property Map</A>. The key type of the map must be the graph's vertex
descriptor type.<BR><B>Default:</B> <TT>get(vertex_predecessor, g)</TT>
</BLOCKQUOTE>
-<P>OUT/UTIL: <TT>vertex_color(ColorMap color)</TT>
+<P>OUT/UTIL: <TT>vertex_color(ColorMap color)</TT>
</P>
<BLOCKQUOTE>A vertex property map that stores a color for edge
vertex. If the color of a vertex after running the algorithm is black
@@ -267,23 +284,23 @@
sink-tree (used for minimum cuts). The map must be a model of mutable
<A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
Map</A>. The key type of the map must be the graph's vertex
-descriptor type.<BR><B>Default:</B> <TT>get(vertex_color, g)</TT>
+descriptor type.<BR><B>Default:</B> <TT>get(vertex_color, g)</TT>
</BLOCKQUOTE>
-<P>UTIL: <TT>vertex_distance(DistanceMap dist)</TT>
+<P>UTIL: <TT>vertex_distance(DistanceMap dist)</TT>
</P>
<BLOCKQUOTE>A vertex property map that stores the distance to the
corresponding terminal. It's a utility-map for speeding up the
algorithm. The map must be a model of mutable <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue
Property Map</A>. The key type of the map must be the graph's vertex
-descriptor type.<BR><B>Default:</B> <TT>get(vertex_distance, g)</TT>
+descriptor type.<BR><B>Default:</B> <TT>get(vertex_distance, g)</TT>
</BLOCKQUOTE>
-<P>IN: <TT>vertex_index(VertexIndexMap index_map)</TT>
+<P>IN: <TT>vertex_index(VertexIndexMap index_map)</TT>
</P>
<BLOCKQUOTE>Maps each vertex of the graph to a unique integer in the
range <TT>[0, num_vertices(g))</TT>. The map must be a model of
constant LvaluePropertyMap.
The key type of the map must be the graph's vertex descriptor
-type.<BR><B>Default:</B> <TT>get(vertex_index, g)</TT>
+type.<BR><B>Default:</B> <TT>get(vertex_index, g)</TT>
</BLOCKQUOTE>
<H3>Example</H3>
<P>This reads an example maximum flow problem (a graph with edge
@@ -311,11 +328,11 @@
property < vertex_color_t, boost::default_color_type,
property < vertex_distance_t, long,
property < vertex_predecessor_t, Traits::edge_descriptor > > > > >,
-
+
property < edge_capacity_t, long,
property < edge_residual_capacity_t, long,
property < edge_reverse_t, Traits::edge_descriptor > > > > Graph;
-
+
Graph g;
property_map < Graph, edge_capacity_t >::type
capacity = get(edge_capacity, g);
@@ -343,7 +360,7 @@
return EXIT_SUCCESS;
}</PRE><P>
-The output is:
+The output is:
</P>
<PRE>c The total flow:
s 13
Modified: trunk/libs/graph/example/Jamfile.v2
==============================================================================
--- trunk/libs/graph/example/Jamfile.v2 (original)
+++ trunk/libs/graph/example/Jamfile.v2 2010-06-21 11:35:42 EDT (Mon, 21 Jun 2010)
@@ -24,4 +24,7 @@
exe fr_layout : fr_layout.cpp ;
exe canonical_ordering : canonical_ordering.cpp ;
exe components_on_edgelist : components_on_edgelist.cpp ;
+exe boykov_kolmogorov-eg : boykov_kolmogorov-eg.cpp ;
+
+# FIXME: Fails due to read_graphviz error...
exe ospf-example : ospf-example.cpp ../build//boost_graph ;
Copied: trunk/libs/graph/example/boykov_kolmogorov-eg.cpp (from r63187, /trunk/libs/graph/example/kolmogorov-eg.cpp)
==============================================================================
--- /trunk/libs/graph/example/kolmogorov-eg.cpp (original)
+++ trunk/libs/graph/example/boykov_kolmogorov-eg.cpp 2010-06-21 11:35:42 EDT (Mon, 21 Jun 2010)
@@ -32,18 +32,18 @@
#include <boost/config.hpp>
#include <iostream>
#include <string>
-#include <boost/graph/kolmogorov_max_flow.hpp>
#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/graph/read_dimacs.hpp>
#include <boost/graph/graph_utility.hpp>
// Use a DIMACS network flow file as stdin.
-// kolmogorov-eg < max_flow.dat
+// boykov_kolmogorov-eg < max_flow.dat
//
// Sample output:
// c The total flow:
// s 13
-//
+//
// c flow values:
// f 0 6 3
// f 0 1 6
@@ -66,8 +66,7 @@
// f 7 6 0
// f 7 5 0
-int
-main()
+int main()
{
using namespace boost;
@@ -78,11 +77,11 @@
property < vertex_color_t, boost::default_color_type,
property < vertex_distance_t, long,
property < vertex_predecessor_t, Traits::edge_descriptor > > > > >,
-
+
property < edge_capacity_t, long,
property < edge_residual_capacity_t, long,
property < edge_reverse_t, Traits::edge_descriptor > > > > Graph;
-
+
Graph g;
property_map < Graph, edge_capacity_t >::type
capacity = get(edge_capacity, g);
@@ -94,7 +93,7 @@
std::vector<default_color_type> color(num_vertices(g));
std::vector<long> distance(num_vertices(g));
- long flow = kolmogorov_max_flow(g ,s, t);
+ long flow = boykov_kolmogorov_max_flow(g ,s, t);
std::cout << "c The total flow:" << std::endl;
std::cout << "s " << flow << std::endl << std::endl;
Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2 (original)
+++ trunk/libs/graph/test/Jamfile.v2 2010-06-21 11:35:42 EDT (Mon, 21 Jun 2010)
@@ -84,6 +84,7 @@
[ run king_ordering.cpp ]
[ run matching_test.cpp ]
[ run max_flow_test.cpp ]
+ [ run boykov_kolmogorov_max_flow_test.cpp ]
[ run kolmogorov_max_flow_test.cpp ]
[ run cycle_ratio_tests.cpp ../build//boost_graph ../../regex/build//boost_regex : $(CYCLE_RATIO_INPUT_FILE) ]
[ run basic_planarity_test.cpp ]
Copied: trunk/libs/graph/test/boykov_kolmogorov_max_flow_test.cpp (from r63187, /trunk/libs/graph/test/kolmogorov_max_flow_test.cpp)
==============================================================================
--- /trunk/libs/graph/test/kolmogorov_max_flow_test.cpp (original)
+++ trunk/libs/graph/test/boykov_kolmogorov_max_flow_test.cpp 2010-06-21 11:35:42 EDT (Mon, 21 Jun 2010)
@@ -36,8 +36,8 @@
#include <fstream>
#include <boost/test/minimal.hpp>
-#include <boost/graph/kolmogorov_max_flow.hpp>
-//boost utilities we use
+#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
+
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/random.hpp>
@@ -49,19 +49,19 @@
template <typename Graph, typename CapacityMap, typename ReverseEdgeMap>
std::pair< typename graph_traits<Graph>::vertex_descriptor,typename graph_traits<Graph>::vertex_descriptor>
-fill_random_max_flow_graph(Graph& g, CapacityMap cap, ReverseEdgeMap rev, typename graph_traits<Graph>::vertices_size_type n_verts,
+fill_random_max_flow_graph(Graph& g, CapacityMap cap, ReverseEdgeMap rev, typename graph_traits<Graph>::vertices_size_type n_verts,
typename graph_traits<Graph>::edges_size_type n_edges, std::size_t seed)
{
typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
const int cap_low = 1;
const int cap_high = 1000;
-
+
//init random numer generator
minstd_rand gen(seed);
//generate graph
generate_random_graph(g, n_verts, n_edges, gen);
-
+
//init an uniform distribution int generator
typedef variate_generator<minstd_rand, uniform_int<int> > tIntGen;
tIntGen int_gen(gen, uniform_int<int>(cap_low, cap_high));
@@ -76,19 +76,19 @@
vertex_descriptor t = graph_traits<Graph>::null_vertex();
while(t == graph_traits<Graph>::null_vertex() || t == s)
t = random_vertex(g, gen);
-
+
//add reverse edges (ugly... how to do better?!)
std::list<edge_descriptor> edges_copy;
- tie(ei, e_end) = edges(g);
+ tie(ei, e_end) = edges(g);
std::copy(ei, e_end, std::back_insert_iterator< std::list<edge_descriptor> >(edges_copy));
while(!edges_copy.empty()){
edge_descriptor old_edge = edges_copy.front();
edges_copy.pop_front();
- vertex_descriptor source_vertex = target(old_edge, g);
+ vertex_descriptor source_vertex = target(old_edge, g);
vertex_descriptor target_vertex = source(old_edge, g);
bool inserted;
edge_descriptor new_edge;
- tie(new_edge,inserted) = add_edge(source_vertex, target_vertex, g);
+ tie(new_edge,inserted) = add_edge(source_vertex, target_vertex, g);
assert(inserted);
rev[old_edge] = new_edge;
rev[new_edge] = old_edge ;
@@ -107,20 +107,20 @@
property<edge_capacity_t, long,
property<edge_residual_capacity_t, long,
property<edge_reverse_t, tVectorTraits::edge_descriptor > > > > tVectorGraph;
-
+
tVectorGraph g;
-
+
graph_traits<tVectorGraph>::vertex_descriptor src,sink;
tie(src,sink) = fill_random_max_flow_graph(g, get(edge_capacity,g), get(edge_reverse, g), n_verts, n_edges, seed);
-
- return kolmogorov_max_flow(g, get(edge_capacity, g),
- get(edge_residual_capacity, g),
- get(edge_reverse, g),
- get(vertex_predecessor, g),
- get(vertex_color, g),
- get(vertex_distance, g),
- get(vertex_index, g),
- src, sink);
+
+ return boykov_kolmogorov_max_flow(g, get(edge_capacity, g),
+ get(edge_residual_capacity, g),
+ get(edge_reverse, g),
+ get(vertex_predecessor, g),
+ get(vertex_color, g),
+ get(vertex_distance, g),
+ get(vertex_index, g),
+ src, sink);
}
long test_adjacency_list_listS(int n_verts, int n_edges, std::size_t seed){
@@ -133,26 +133,26 @@
property<edge_capacity_t, long,
property<edge_residual_capacity_t, long,
property<edge_reverse_t, tListTraits::edge_descriptor > > > > tListGraph;
-
+
tListGraph g;
-
+
graph_traits<tListGraph>::vertex_descriptor src,sink;
tie(src,sink) = fill_random_max_flow_graph(g, get(edge_capacity,g), get(edge_reverse, g), n_verts, n_edges, seed);
-
+
//initialize vertex indices
graph_traits<tListGraph>::vertex_iterator vi,v_end;
graph_traits<tListGraph>::vertices_size_type index = 0;
for(tie(vi, v_end) = vertices(g); vi != v_end; ++vi){
put(vertex_index, g, *vi, index++);
}
- return kolmogorov_max_flow(g, get(edge_capacity, g),
- get(edge_residual_capacity, g),
- get(edge_reverse, g),
- get(vertex_predecessor, g),
- get(vertex_color, g),
- get(vertex_distance, g),
- get(vertex_index, g),
- src, sink);
+ return boykov_kolmogorov_max_flow(g, get(edge_capacity, g),
+ get(edge_residual_capacity, g),
+ get(edge_reverse, g),
+ get(vertex_predecessor, g),
+ get(vertex_color, g),
+ get(vertex_distance, g),
+ get(vertex_index, g),
+ src, sink);
}
template<typename EdgeDescriptor>
@@ -174,19 +174,19 @@
typedef Node<tTraits::edge_descriptor> tVertex;
typedef Link<tTraits::edge_descriptor> tEdge;
typedef adjacency_list<vecS, vecS, directedS, tVertex, tEdge> tBundleGraph;
-
+
tBundleGraph g;
graph_traits<tBundleGraph>::vertex_descriptor src,sink;
tie(src,sink) = fill_random_max_flow_graph(g, get(&tEdge::edge_capacity,g), get(&tEdge::edge_reverse, g), n_verts, n_edges, seed);
- return kolmogorov_max_flow(g, get(&tEdge::edge_capacity, g),
- get(&tEdge::edge_residual_capacity, g),
- get(&tEdge::edge_reverse, g),
- get(&tVertex::vertex_predecessor, g),
- get(&tVertex::vertex_color, g),
- get(&tVertex::vertex_distance, g),
- get(vertex_index, g),
- src, sink);
+ return boykov_kolmogorov_max_flow(g, get(&tEdge::edge_capacity, g),
+ get(&tEdge::edge_residual_capacity, g),
+ get(&tEdge::edge_reverse, g),
+ get(&tVertex::vertex_predecessor, g),
+ get(&tVertex::vertex_color, g),
+ get(&tVertex::vertex_distance, g),
+ get(vertex_index, g),
+ src, sink);
}
long test_overloads(int n_verts, int n_edges, std::size_t seed){
@@ -195,9 +195,9 @@
property<edge_residual_capacity_t, long,
property<edge_reverse_t, tTraits::edge_descriptor> > >tEdgeProperty;
typedef adjacency_list<vecS, vecS, directedS, no_property, tEdgeProperty> tGraph;
-
+
tGraph g;
-
+
graph_traits<tGraph>::vertex_descriptor src,sink;
tie(src,sink) = fill_random_max_flow_graph(g, get(edge_capacity,g), get(edge_reverse, g), n_verts, n_edges, seed);
@@ -205,18 +205,40 @@
std::vector<default_color_type> color_vec(n_verts);
std::vector<graph_traits<tGraph>::vertices_size_type> distance_vec(n_verts);
- long flow_overload_1 = kolmogorov_max_flow(g, get(edge_capacity,g), get(edge_residual_capacity,g), get(edge_reverse,g), get(vertex_index,g), src, sink);
-
- long flow_overload_2 = kolmogorov_max_flow(g, get(edge_capacity,g), get(edge_residual_capacity,g), get(edge_reverse,g),
- &(color_vec[0]), get(vertex_index,g), src, sink);
-
+ long flow_overload_1 =
+ boykov_kolmogorov_max_flow(g,
+ get(edge_capacity,g),
+ get(edge_residual_capacity,g),
+ get(edge_reverse,g),
+ get(vertex_index,g),
+ src, sink);
+
+ long flow_overload_2 =
+ boykov_kolmogorov_max_flow(g,
+ get(edge_capacity,g),
+ get(edge_residual_capacity,g),
+ get(edge_reverse,g),
+ &(color_vec[0]),
+ get(vertex_index,g),
+ src, sink);
+
BOOST_CHECK(flow_overload_1 == flow_overload_2);
return flow_overload_1;
}
-template <class Graph, class EdgeCapacityMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap, class PredecessorMap, class ColorMap,
- class DistanceMap, class IndexMap>
-class kolmogorov_test:public detail::kolmogorov<Graph,EdgeCapacityMap,ResidualCapacityEdgeMap,ReverseEdgeMap,PredecessorMap,ColorMap,DistanceMap,IndexMap>
+template<class Graph,
+ class EdgeCapacityMap,
+ class ResidualCapacityEdgeMap,
+ class ReverseEdgeMap,
+ class PredecessorMap,
+ class ColorMap,
+ class DistanceMap,
+ class IndexMap>
+class boykov_kolmogorov_test
+ : public detail::bk_max_flow<
+ Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap,
+ PredecessorMap, ColorMap, DistanceMap, IndexMap
+ >
{
typedef typename graph_traits<Graph>::edge_descriptor tEdge;
@@ -226,14 +248,20 @@
typedef typename graph_traits<Graph>::out_edge_iterator tOutEdgeIterator;
typedef typename property_traits<ColorMap>::value_type tColorValue;
typedef color_traits<tColorValue> tColorTraits;
- typedef typename property_traits<DistanceMap>::value_type tDistanceVal;
- typedef typename detail::kolmogorov<Graph,EdgeCapacityMap,ResidualCapacityEdgeMap,ReverseEdgeMap,PredecessorMap,ColorMap,DistanceMap,IndexMap> tSuper;
+ typedef typename property_traits<DistanceMap>::value_type tDistanceVal;
+ typedef typename detail::bk_max_flow<
+ Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap,
+ PredecessorMap, ColorMap, DistanceMap, IndexMap
+ > tSuper;
public:
- kolmogorov_test(Graph& g, typename graph_traits<Graph>::vertex_descriptor src, typename graph_traits<Graph>::vertex_descriptor sink):
- detail::kolmogorov<Graph,EdgeCapacityMap,ResidualCapacityEdgeMap,ReverseEdgeMap,PredecessorMap,ColorMap,DistanceMap,IndexMap>
- (g, get(edge_capacity,g), get(edge_residual_capacity,g), get(edge_reverse, g), get(vertex_predecessor, g), get(vertex_color, g),
- get(vertex_distance, g), get(vertex_index, g), src, sink){
- }
+ boykov_kolmogorov_test(Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor src,
+ typename graph_traits<Graph>::vertex_descriptor sink)
+ : tSuper(g, get(edge_capacity,g), get(edge_residual_capacity,g),
+ get(edge_reverse, g), get(vertex_predecessor, g),
+ get(vertex_color, g), get(vertex_distance, g),
+ get(vertex_index, g), src, sink)
+ { }
void invariant_four(tVertex v) const{
//passive nodes in S or T
@@ -346,7 +374,7 @@
//check if flow is the sum of outgoing edges of src
tOutEdgeIterator ei, e_end;
- tEdgeVal src_sum = 0;
+ tEdgeVal src_sum = 0;
for(tie(ei, e_end) = out_edges(this->m_source, this->m_g); ei != e_end; ++ei){
src_sum += this->m_cap_map[*ei] - this->m_res_cap_map[*ei];
}
@@ -373,9 +401,9 @@
property<edge_capacity_t, long,
property<edge_residual_capacity_t, long,
property<edge_reverse_t, tVectorTraits::edge_descriptor > > > > tVectorGraph;
-
+
tVectorGraph g;
-
+
graph_traits<tVectorGraph>::vertex_descriptor src, sink;
tie(src,sink) = fill_random_max_flow_graph(g, get(edge_capacity,g), get(edge_reverse, g), n_verts, n_edges, seed);
@@ -386,33 +414,35 @@
typedef property_map<tVectorGraph, vertex_color_t>::type tVertexColorMap;
typedef property_map<tVectorGraph, vertex_distance_t>::type tDistanceMap;
typedef property_map<tVectorGraph, vertex_index_t>::type tIndexMap;
- typedef kolmogorov_test<tVectorGraph, tEdgeCapMap, tEdgeResCapMap, tRevEdgeMap, tVertexPredMap, tVertexColorMap, tDistanceMap, tIndexMap> tKolmo;
+ typedef boykov_kolmogorov_test<
+ tVectorGraph, tEdgeCapMap, tEdgeResCapMap, tRevEdgeMap, tVertexPredMap,
+ tVertexColorMap, tDistanceMap, tIndexMap
+ > tKolmo;
tKolmo instance(g, src, sink);
return instance.test();
}
int test_main(int argc, char* argv[])
{
- int n_verts = 10;
+ int n_verts = 10;
int n_edges = 500;
std::size_t seed = 1;
-
+
if (argc > 1) n_verts = lexical_cast<int>(argv[1]);
if (argc > 2) n_edges = lexical_cast<int>(argv[2]);
if (argc > 3) seed = lexical_cast<std::size_t>(argv[3]);
//we need at least 2 vertices to create src and sink in random graphs
- //this case is also caught in kolmogorov_max_flow
+ //this case is also caught in boykov_kolmogorov_max_flow
if (n_verts<2)
n_verts = 2;
- /*
- * below are checks for different calls to kolmogorov_max_flow and different graph-types
- */
+ // below are checks for different calls to boykov_kolmogorov_max_flow and different graph-types
+
//checks support of vecS storage
long flow_vecS = test_adjacency_list_vecS(n_verts, n_edges, seed);
std::cout << "vecS flow: " << flow_vecS << std::endl;
- //checks support of listS storage (especially problems with vertex indices)
+ //checks support of listS storage (especially problems with vertex indices)
long flow_listS = test_adjacency_list_listS(n_verts, n_edges, seed);
std::cout << "listS flow: " << flow_listS << std::endl;
BOOST_CHECK(flow_vecS == flow_listS);
@@ -424,9 +454,9 @@
long flow_overloads = test_overloads(n_verts, n_edges, seed);
std::cout << "overloads flow: " << flow_overloads << std::endl;
BOOST_CHECK(flow_bundles == flow_overloads);
- /*
- * excessive test version where kolmogorov's algorithm invariants are checked
- */
+
+ // excessive test version where boykov-kolmogorov's algorithm invariants are
+ // checked
long flow_invariants = test_algorithms_invariant(n_verts, n_edges, seed);
std::cout << "invariants flow: " << flow_invariants << std::endl;
BOOST_CHECK(flow_overloads == flow_invariants);
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk