Boost logo

Boost-Commit :

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);
 


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