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

From: aaron.windsor_at_[hidden]
Date: 2007-09-03 11:04:12

Author: aaron_windsor
Date: 2007-09-03 11:04:05 EDT (Mon, 03 Sep 2007)
New Revision: 39112
URL: http://svn.boost.org/trac/boost/changeset/39112

Log:
Modified odd_components_counter to fix signed/unsigned mismatch on Sandi pgi-6.1 tests.
Text files modified: 
   trunk/boost/graph/max_cardinality_matching.hpp |   309 ++++++++++++++++++++------------------- 
   1 files changed, 158 insertions(+), 151 deletions(-)

Modified: trunk/boost/graph/max_cardinality_matching.hpp
==============================================================================
--- trunk/boost/graph/max_cardinality_matching.hpp	(original)
+++ trunk/boost/graph/max_cardinality_matching.hpp	2007-09-03 11:04:05 EDT (Mon, 03 Sep 2007)
@@ -45,10 +45,10 @@
 
     for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
       {
-    vertex_descriptor_t v = *vi;
-    if (get(mate,v) != graph_traits<Graph>::null_vertex() 
+        vertex_descriptor_t v = *vi;
+        if (get(mate,v) != graph_traits<Graph>::null_vertex() 
             && get(vm,v) < get(vm,get(mate,v)))
-      ++size_of_matching;
+        ++size_of_matching;
       }
     return size_of_matching;
   }
@@ -76,10 +76,10 @@
     vertex_iterator_t vi, vi_end;
     for( tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
       {
-    vertex_descriptor_t v = *vi;
-    if (get(mate,v) != graph_traits<Graph>::null_vertex() 
+        vertex_descriptor_t v = *vi;
+        if (get(mate,v) != graph_traits<Graph>::null_vertex() 
             && v != get(mate,get(mate,v)))
-      return false;
+        return false;
       }    
     return true;
   }
@@ -188,7 +188,7 @@
     {
       vertex_iterator_t vi, vi_end;
       for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
-    mate[*vi] = get(arg_mate, *vi);
+        mate[*vi] = get(arg_mate, *vi);
     }
 
 
@@ -206,25 +206,25 @@
       
       vertex_iterator_t vi, vi_end;
       for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
-    {
-      vertex_descriptor_t u = *vi;
+      {
+        vertex_descriptor_t u = *vi;
       
-      origin[u] = u;
-      pred[u] = u;
-      ancestor_of_v[u] = 0;
-      ancestor_of_w[u] = 0;
-      ds.make_set(u);
+        origin[u] = u;
+        pred[u] = u;
+        ancestor_of_v[u] = 0;
+        ancestor_of_w[u] = 0;
+        ds.make_set(u);
       
-      if (mate[u] == graph_traits<Graph>::null_vertex())
+        if (mate[u] == graph_traits<Graph>::null_vertex())
         {
           vertex_state[u] = graph::detail::V_EVEN;
           out_edge_iterator_t ei, ei_end;
           for(tie(ei,ei_end) = out_edges(u,g); ei != ei_end; ++ei)
-        even_edges.push_back( *ei );
+            even_edges.push_back( *ei );
         }
-      else
-        vertex_state[u] = graph::detail::V_UNREACHED;      
-    }
+        else
+          vertex_state[u] = graph::detail::V_UNREACHED;      
+      }
     
       //end initializations
     
@@ -234,40 +234,41 @@
       bool found_alternating_path = false;
       
       while(!even_edges.empty() && !found_alternating_path)
-    {
-      // since we push even edges onto the back of the list as
-      // they're discovered, taking them off the back will search
-      // for augmenting paths depth-first.
-      edge_descriptor_t current_edge = even_edges.back();
-      even_edges.pop_back();
-
-      v = source(current_edge,g);
-      w = target(current_edge,g);
-      
-      vertex_descriptor_t v_prime = origin[ds.find_set(v)];
-      vertex_descriptor_t w_prime = origin[ds.find_set(w)];
-      
-      // because of the way we put all of the edges on the queue,
-      // v_prime should be labeled V_EVEN; the following is a
-      // little paranoid but it could happen...
-      if (vertex_state[v_prime] != graph::detail::V_EVEN)
+      {
+        // since we push even edges onto the back of the list as
+        // they're discovered, taking them off the back will search
+        // for augmenting paths depth-first.
+        edge_descriptor_t current_edge = even_edges.back();
+        even_edges.pop_back();
+
+        v = source(current_edge,g);
+        w = target(current_edge,g);
+      
+        vertex_descriptor_t v_prime = origin[ds.find_set(v)];
+        vertex_descriptor_t w_prime = origin[ds.find_set(w)];
+      
+        // because of the way we put all of the edges on the queue,
+        // v_prime should be labeled V_EVEN; the following is a
+        // little paranoid but it could happen...
+        if (vertex_state[v_prime] != graph::detail::V_EVEN)
         {
           std::swap(v_prime,w_prime);
           std::swap(v,w);
         }
 
-      if (vertex_state[w_prime] == graph::detail::V_UNREACHED)
+        if (vertex_state[w_prime] == graph::detail::V_UNREACHED)
         {
           vertex_state[w_prime] = graph::detail::V_ODD;
           vertex_state[mate[w_prime]] = graph::detail::V_EVEN;
           out_edge_iterator_t ei, ei_end;
           for( tie(ei,ei_end) = out_edges(mate[w_prime], g); ei != ei_end; ++ei)
-        even_edges.push_back(*ei);
+            even_edges.push_back(*ei);
           pred[w_prime] = v;
         }
-          //w_prime == v_prime can happen below if we get an edge that has been
-          //shrunk into a blossom
-      else if (vertex_state[w_prime] == graph::detail::V_EVEN && w_prime != v_prime) 
+        
+		//w_prime == v_prime can happen below if we get an edge that has been
+        //shrunk into a blossom
+        else if (vertex_state[w_prime] == graph::detail::V_EVEN && w_prime != v_prime) 
         {                                                             
           vertex_descriptor_t w_up = w_prime;
           vertex_descriptor_t v_up = v_prime;
@@ -291,42 +292,42 @@
               w_free_ancestor == graph_traits<Graph>::null_vertex()
               )
              )
-        {
-          ancestor_of_w[w_up] = timestamp;
-          ancestor_of_v[v_up] = timestamp;
-
-          if (w_free_ancestor == graph_traits<Graph>::null_vertex())
-            w_up = parent(w_up);
-          if (v_free_ancestor == graph_traits<Graph>::null_vertex())
-            v_up = parent(v_up);
+          {
+            ancestor_of_w[w_up] = timestamp;
+            ancestor_of_v[v_up] = timestamp;
+
+            if (w_free_ancestor == graph_traits<Graph>::null_vertex())
+              w_up = parent(w_up);
+            if (v_free_ancestor == graph_traits<Graph>::null_vertex())
+              v_up = parent(v_up);
           
-          if (mate[v_up] == graph_traits<Graph>::null_vertex())
-            v_free_ancestor = v_up;
-          if (mate[w_up] == graph_traits<Graph>::null_vertex())
-            w_free_ancestor = w_up;
+            if (mate[v_up] == graph_traits<Graph>::null_vertex())
+              v_free_ancestor = v_up;
+            if (mate[w_up] == graph_traits<Graph>::null_vertex())
+              w_free_ancestor = w_up;
           
-          if (ancestor_of_w[v_up] == timestamp)
+            if (ancestor_of_w[v_up] == timestamp)
+              nearest_common_ancestor = v_up;
+            else if (ancestor_of_v[w_up] == timestamp)
+              nearest_common_ancestor = w_up;
+            else if (v_free_ancestor == w_free_ancestor && 
+              v_free_ancestor != graph_traits<Graph>::null_vertex())
             nearest_common_ancestor = v_up;
-          else if (ancestor_of_v[w_up] == timestamp)
-            nearest_common_ancestor = w_up;
-          else if (v_free_ancestor == w_free_ancestor && 
-               v_free_ancestor != graph_traits<Graph>::null_vertex())
-            nearest_common_ancestor = v_up;
-        }
+          }
           
           if (nearest_common_ancestor == graph_traits<Graph>::null_vertex())
-        found_alternating_path = true; //to break out of the loop
+            found_alternating_path = true; //to break out of the loop
           else
-        {
-          //shrink the blossom
-          link_and_set_bridges(w_prime, nearest_common_ancestor, std::make_pair(w,v));
-          link_and_set_bridges(v_prime, nearest_common_ancestor, std::make_pair(v,w));
-        }
+          {
+            //shrink the blossom
+            link_and_set_bridges(w_prime, nearest_common_ancestor, std::make_pair(w,v));
+            link_and_set_bridges(v_prime, nearest_common_ancestor, std::make_pair(v,w));
+          }
         }      
-    }
+      }
       
       if (!found_alternating_path)
-    return false;
+        return false;
 
       // retrieve the augmenting path and put it in aug_path
       reversed_retrieve_augmenting_path(v, v_free_ancestor);
@@ -335,14 +336,14 @@
       // augment the matching along aug_path
       vertex_descriptor_t a,b;
       while (!aug_path.empty())
-    {
-      a = aug_path.front();
-      aug_path.pop_front();
-      b = aug_path.front();
-      aug_path.pop_front();
-      mate[a] = b;
-      mate[b] = a;
-    }
+      {
+        a = aug_path.front();
+        aug_path.pop_front();
+        b = aug_path.front();
+        aug_path.pop_front();
+        mate[a] = b;
+        mate[b] = a;
+      }
       
       return true;
       
@@ -356,7 +357,7 @@
     {
       vertex_iterator_t vi,vi_end;
       for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
-    put(pm, *vi, mate[*vi]);
+        put(pm, *vi, mate[*vi]);
     }
 
 
@@ -367,7 +368,7 @@
     {
       vertex_iterator_t vi,vi_end;
       for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
-    put(pm, *vi, vertex_state[origin[ds.find_set(*vi)]]);
+        put(pm, *vi, vertex_state[origin[ds.find_set(*vi)]]);
     }
 
 
@@ -379,11 +380,11 @@
     {
       if (vertex_state[x] == graph::detail::V_EVEN 
           && mate[x] != graph_traits<Graph>::null_vertex())
-    return mate[x];
+        return mate[x];
       else if (vertex_state[x] == graph::detail::V_ODD)
-    return origin[ds.find_set(pred[x])];
+        return origin[ds.find_set(pred[x])];
       else
-    return x;
+        return x;
     }
     
     
@@ -394,18 +395,18 @@
                   vertex_pair_t the_bridge)
     {
       for(vertex_descriptor_t v = x; v != stop_vertex; v = parent(v))
-    {
-      ds.union_set(v, stop_vertex);
-      origin[ds.find_set(stop_vertex)] = stop_vertex;
+      {
+        ds.union_set(v, stop_vertex);
+        origin[ds.find_set(stop_vertex)] = stop_vertex;
 
-      if (vertex_state[v] == graph::detail::V_ODD)
+        if (vertex_state[v] == graph::detail::V_ODD)
         {
           bridge[v] = the_bridge;
           out_edge_iterator_t oei, oei_end;
           for(tie(oei, oei_end) = out_edges(v,g); oei != oei_end; ++oei)
-        even_edges.push_back(*oei);
+            even_edges.push_back(*oei);
         }
-    }
+      }
     }
     
 
@@ -426,19 +427,19 @@
     void retrieve_augmenting_path(vertex_descriptor_t v, vertex_descriptor_t w)  
     {
       if (v == w)
-    aug_path.push_back(v);
+        aug_path.push_back(v);
       else if (vertex_state[v] == graph::detail::V_EVEN)
-    {
-      aug_path.push_back(v);
-      aug_path.push_back(mate[v]);
-      retrieve_augmenting_path(pred[mate[v]], w);
-    }
+      {
+        aug_path.push_back(v);
+        aug_path.push_back(mate[v]);
+        retrieve_augmenting_path(pred[mate[v]], w);
+      }
       else //vertex_state[v] == graph::detail::V_ODD 
-    {
-      aug_path.push_back(v);
-      reversed_retrieve_augmenting_path(bridge[v].first, mate[v]);
-      retrieve_augmenting_path(bridge[v].second, w);
-    }
+      {
+        aug_path.push_back(v);
+        reversed_retrieve_augmenting_path(bridge[v].first, mate[v]);
+        retrieve_augmenting_path(bridge[v].second, w);
+      }
     }
 
 
@@ -447,19 +448,19 @@
     {
 
       if (v == w)
-    aug_path.push_back(v);
+        aug_path.push_back(v);
       else if (vertex_state[v] == graph::detail::V_EVEN)
-    {
-      reversed_retrieve_augmenting_path(pred[mate[v]], w);
-      aug_path.push_back(mate[v]);
-      aug_path.push_back(v);
-    }
+      {
+        reversed_retrieve_augmenting_path(pred[mate[v]], w);
+        aug_path.push_back(mate[v]);
+        aug_path.push_back(v);
+      }
       else //vertex_state[v] == graph::detail::V_ODD 
-    {
-      reversed_retrieve_augmenting_path(bridge[v].second, w);
-      retrieve_augmenting_path(bridge[v].first, mate[v]);
-      aug_path.push_back(v);
-    }
+      {
+        reversed_retrieve_augmenting_path(bridge[v].second, w);
+        retrieve_augmenting_path(bridge[v].first, mate[v]);
+        aug_path.push_back(v);
+      }
     }
 
     
@@ -520,23 +521,23 @@
     {
       vertex_iterator_t vi, vi_end;
       for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
-    put(mate, *vi, graph_traits<Graph>::null_vertex());
+        put(mate, *vi, graph_traits<Graph>::null_vertex());
             
       edge_iterator_t ei, ei_end;
       for( tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
-    {
-      edge_descriptor_t e = *ei;
-      vertex_descriptor_t u = source(e,g);
-      vertex_descriptor_t v = target(e,g);
+      {
+        edge_descriptor_t e = *ei;
+        vertex_descriptor_t u = source(e,g);
+        vertex_descriptor_t v = target(e,g);
       
-      if (get(mate,u) == get(mate,v))  
+        if (get(mate,u) == get(mate,v))  
         //only way equality can hold is if
-            //   mate[u] == mate[v] == null_vertex
+        //   mate[u] == mate[v] == null_vertex
         {
           put(mate,u,v);
           put(mate,v,u);
         }
-    }    
+      }    
     }
   };
   
@@ -581,9 +582,9 @@
       less_than_by_degree(const Graph& g): m_g(g) {}
       bool operator() (const vertex_pair_t x, const vertex_pair_t y)
       {
-    return 
-      out_degree(PairSelector::select_vertex(x), m_g) 
-      < out_degree(PairSelector::select_vertex(y), m_g);
+        return 
+          out_degree(PairSelector::select_vertex(x), m_g) 
+          < out_degree(PairSelector::select_vertex(y), m_g);
       }
     private:
       const Graph& m_g;
@@ -598,17 +599,17 @@
       directed_edges_vector_t edge_list;
       vertex_iterator_t vi, vi_end;
       for(tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
-    put(mate, *vi, graph_traits<Graph>::null_vertex());
+        put(mate, *vi, graph_traits<Graph>::null_vertex());
 
       edge_iterator_t ei, ei_end;
       for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
-    {
-      edge_descriptor_t e = *ei;
-      vertex_descriptor_t u = source(e,g);
-      vertex_descriptor_t v = target(e,g);
-      edge_list.push_back(std::make_pair(u,v));
-      edge_list.push_back(std::make_pair(v,u));
-    }
+      {
+        edge_descriptor_t e = *ei;
+        vertex_descriptor_t u = source(e,g);
+        vertex_descriptor_t v = target(e,g);
+        edge_list.push_back(std::make_pair(u,v));
+        edge_list.push_back(std::make_pair(v,u));
+      }
       
       //sort the edges by the degree of the target, then (using a
       //stable sort) by degree of the source
@@ -619,14 +620,14 @@
       
       //construct the extra greedy matching
       for(typename directed_edges_vector_t::const_iterator itr = edge_list.begin(); itr != edge_list.end(); ++itr)
-    {
-      if (get(mate,itr->first) == get(mate,itr->second)) 
+      {
+        if (get(mate,itr->first) == get(mate,itr->second)) 
         //only way equality can hold is if mate[itr->first] == mate[itr->second] == null_vertex
         {
           put(mate, itr->first, itr->second);
           put(mate, itr->second, itr->first);
         }
-    }    
+      }    
     }
   };
 
@@ -642,7 +643,7 @@
     {
       vertex_iterator_t vi, vi_end;
       for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
-    put(mate, *vi, graph_traits<Graph>::null_vertex());
+        put(mate, *vi, graph_traits<Graph>::null_vertex());
     }
   };
   
@@ -666,29 +667,29 @@
     {
     public:
       odd_components_counter(SizeType& c_count):
-    m_count(c_count)
+        m_count(c_count)
       {
-    m_count = 0;
+        m_count = 0;
       }
       
       template <class Vertex, class Graph>
       void start_vertex(Vertex v, Graph&) 
-      {  
-    addend = -1; 
+      {
+        m_parity = false; 
       }
       
       template <class Vertex, class Graph>
       void discover_vertex(Vertex u, Graph&) 
       {
-    addend *= -1;
-    m_count += addend;
+        m_parity = !m_parity;
+		m_parity ? ++m_count : --m_count;
       }
       
     protected:
       SizeType& m_count;
       
     private:
-      SizeType addend;
+      bool m_parity;
       
     };
 
@@ -728,21 +729,27 @@
     typedef typename map_vertex_to_<vertex_descriptor_t>::type 
       vertex_to_vertex_map_t;
 
+
     template <typename VertexStateMap>
     struct non_odd_vertex {
       //this predicate is used to create a filtered graph that
       //excludes vertices labeled "graph::detail::V_ODD"
       non_odd_vertex() : vertex_state(0) { }
-      non_odd_vertex(VertexStateMap* arg_vertex_state) 
+  
+	  non_odd_vertex(VertexStateMap* arg_vertex_state) 
         : vertex_state(arg_vertex_state) { }
-      template <typename Vertex>
-      bool operator()(const Vertex& v) const {
-    BOOST_ASSERT(vertex_state);
-    return get(*vertex_state, v) != graph::detail::V_ODD;
+
+	  template <typename Vertex>
+      bool operator()(const Vertex& v) const 
+	  {
+        BOOST_ASSERT(vertex_state);
+        return get(*vertex_state, v) != graph::detail::V_ODD;
       }
+
       VertexStateMap* vertex_state;
     };
 
+
     static bool verify_matching(const Graph& g, MateMap mate, VertexIndexMap vm)
     {
       //For any graph G, let o(G) be the number of connected
@@ -763,7 +770,7 @@
 
       //first, make sure it's a valid matching
       if (!is_a_matching(g,mate,vm))
-      return false;
+        return false;
 
       //We'll try to augment the matching once. This serves two
       //purposes: first, if we find some augmenting path, the matching
@@ -775,7 +782,7 @@
       edmonds_augmenting_path_finder<Graph,MateMap,VertexIndexMap>
         augmentor(g,mate,vm);
       if (augmentor.augment_matching())
-      return false;
+        return false;
 
       std::vector<int> vertex_state_vector(num_vertices(g));
       vertex_to_int_map_t vertex_state(vertex_state_vector.begin(), vm);
@@ -785,8 +792,8 @@
       v_size_t num_odd_vertices = 0;
       vertex_iterator_t vi, vi_end;
       for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
-    if (vertex_state[*vi] == graph::detail::V_ODD)
-      ++num_odd_vertices;
+        if (vertex_state[*vi] == graph::detail::V_ODD)
+          ++num_odd_vertices;
 
       //count the number of connected components with odd cardinality
       //in the graph without graph::detail::V_ODD vertices
@@ -798,9 +805,9 @@
       depth_first_search(fg, visitor(occ).vertex_index_map(vm));
 
       if (2 * matching_size(g,mate,vm) == num_vertices(g) + num_odd_vertices - num_odd_components)
-    return true;
+        return true;
       else
-    return false;
+        return false;
     }
   };
 
@@ -822,7 +829,7 @@
     bool not_maximum_yet = true;
     while(not_maximum_yet)
       {
-    not_maximum_yet = augmentor.augment_matching();
+        not_maximum_yet = augmentor.augment_matching();
       }
     augmentor.get_current_matching(mate);