[Boost-commit] svn:boost r81536 - trunk/boost/graph

Subject: [Boost-commit] svn:boost r81536 - trunk/boost/graph
From: jewillco_at_[hidden]
Date: 2012-11-25 15:13:25

Author: jewillco
Date: 2012-11-25 15:13:25 EST (Sun, 25 Nov 2012)
New Revision: 81536
URL: http://svn.boost.org/trac/boost/changeset/81536

Log:
Applied patch from #7728 to fix B-K max-flow bug; fixes #7728; fixes #3468
Text files modified: 
   trunk/boost/graph/boykov_kolmogorov_max_flow.hpp |    11 +++++++----                             
   1 files changed, 7 insertions(+), 4 deletions(-)

Modified: trunk/boost/graph/boykov_kolmogorov_max_flow.hpp
==============================================================================
--- trunk/boost/graph/boykov_kolmogorov_max_flow.hpp	(original)
+++ trunk/boost/graph/boykov_kolmogorov_max_flow.hpp	2012-11-25 15:13:25 EST (Sun, 25 Nov 2012)
@@ -442,11 +442,11 @@
               for(boost::tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
                 edge_descriptor in_edge = get(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(get_tree(other_node) == tColorTraits::black() && other_node != m_source){
                   if(get(m_res_cap_map, in_edge) > 0){
                     add_active_node(other_node);
                   }
-                  if(source(get_edge_to_parent(other_node), m_g) == current_node){
+                  if(has_parent(other_node) && 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);
@@ -483,11 +483,11 @@
               for(boost::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() && other_node != m_sink){
                   if(get(m_res_cap_map, out_edge) > 0){
                     add_active_node(other_node);
                   }
-                  if(target(get_edge_to_parent(other_node), m_g) == current_node){
+                  if(has_parent(other_node) && 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);
@@ -526,6 +526,9 @@
       inline void add_active_node(vertex_descriptor v){
         BOOST_ASSERT(get_tree(v) != tColorTraits::gray());
         if(get(m_in_active_list_map, v)){
+          if (m_last_grow_vertex == v) {
+              m_last_grow_vertex = graph_traits<Graph>::null_vertex();
+          }
           return;
         } else{
           put(m_in_active_list_map, v, true);