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