123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167 |
- //=======================================================================
- // Copyright (c) 2018 Yi Ji
- //
- // Distributed under the Boost Software License, Version 1.0.
- // (See accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- //
- //=======================================================================
- #ifndef BOOST_GRAPH_MAXIMUM_WEIGHTED_MATCHING_HPP
- #define BOOST_GRAPH_MAXIMUM_WEIGHTED_MATCHING_HPP
- #include <algorithm> // for std::iter_swap
- #include <boost/shared_ptr.hpp>
- #include <boost/make_shared.hpp>
- #include <boost/graph/max_cardinality_matching.hpp>
- namespace boost
- {
- template <typename Graph, typename MateMap, typename VertexIndexMap>
- typename property_traits<typename property_map<Graph, edge_weight_t>::type>::value_type
- matching_weight_sum(const Graph& g, MateMap mate, VertexIndexMap vm)
- {
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor_t;
- typedef typename property_traits<typename property_map<Graph, edge_weight_t>::type>::value_type edge_property_t;
-
- edge_property_t weight_sum = 0;
- vertex_iterator_t vi, vi_end;
-
- for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
- {
- vertex_descriptor_t v = *vi;
- if (get(mate, v) != graph_traits<Graph>::null_vertex() && get(vm, v) < get(vm, get(mate,v)))
- weight_sum += get(edge_weight, g, edge(v,mate[v],g).first);
- }
- return weight_sum;
- }
-
- template <typename Graph, typename MateMap>
- inline typename property_traits<typename property_map<Graph, edge_weight_t>::type>::value_type
- matching_weight_sum(const Graph& g, MateMap mate)
- {
- return matching_weight_sum(g, mate, get(vertex_index,g));
- }
-
- template <typename Graph, typename MateMap, typename VertexIndexMap>
- class weighted_augmenting_path_finder
- {
- public:
-
- template <typename T>
- struct map_vertex_to_
- {
- typedef boost::iterator_property_map<typename std::vector<T>::iterator, VertexIndexMap> type;
- };
- typedef typename graph::detail::VERTEX_STATE vertex_state_t;
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor_t;
- typedef typename std::vector<vertex_descriptor_t>::const_iterator vertex_vec_iter_t;
- typedef typename graph_traits<Graph>::out_edge_iterator out_edge_iterator_t;
- typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor_t;
- typedef typename graph_traits<Graph>::edge_iterator edge_iterator_t;
- typedef typename property_traits<typename property_map<Graph, edge_weight_t>::type>::value_type edge_property_t;
- typedef std::deque<vertex_descriptor_t> vertex_list_t;
- typedef std::vector<edge_descriptor_t> edge_list_t;
- typedef typename map_vertex_to_<vertex_descriptor_t>::type vertex_to_vertex_map_t;
- typedef typename map_vertex_to_<edge_property_t>::type vertex_to_weight_map_t;
- typedef typename map_vertex_to_<bool>::type vertex_to_bool_map_t;
- typedef typename map_vertex_to_<std::pair<vertex_descriptor_t, vertex_descriptor_t> >::type vertex_to_pair_map_t;
- typedef typename map_vertex_to_<std::pair<edge_descriptor_t, bool> >::type vertex_to_edge_map_t;
- typedef typename map_vertex_to_<vertex_to_edge_map_t>::type vertex_pair_to_edge_map_t;
-
- class blossom
- {
- public:
-
- typedef boost::shared_ptr<blossom> blossom_ptr_t;
- std::vector<blossom_ptr_t> sub_blossoms;
- edge_property_t dual_var;
- blossom_ptr_t father;
- blossom() : dual_var(0), father(blossom_ptr_t()) {}
-
- // get the base vertex of a blossom by recursively getting
- // its base sub-blossom, which is always the first one in
- // sub_blossoms because of how we create and maintain blossoms
- virtual vertex_descriptor_t get_base() const
- {
- const blossom* b = this;
- while (!b->sub_blossoms.empty())
- b = b->sub_blossoms[0].get();
- return b->get_base();
- }
-
- // set a sub-blossom as a blossom's base by exchanging it
- // with its first sub-blossom
- void set_base(const blossom_ptr_t& sub)
- {
- for (blossom_iterator_t bi = sub_blossoms.begin(); bi != sub_blossoms.end(); ++bi)
- {
- if (sub.get() == bi->get())
- {
- std::iter_swap(sub_blossoms.begin(), bi);
- break;
- }
- }
- }
-
- // get all vertices inside recursively
- virtual std::vector<vertex_descriptor_t> vertices() const
- {
- std::vector<vertex_descriptor_t> all_vertices;
- for (typename std::vector<blossom_ptr_t>::const_iterator bi = sub_blossoms.begin(); bi != sub_blossoms.end(); ++bi)
- {
- std::vector<vertex_descriptor_t> some_vertices = (*bi)->vertices();
- all_vertices.insert(all_vertices.end(), some_vertices.begin(), some_vertices.end());
- }
- return all_vertices;
- }
- };
-
- // a trivial_blossom only has one vertex and no sub-blossom;
- // for each vertex v, in_blossom[v] is the trivial_blossom that contains it directly
- class trivial_blossom : public blossom
- {
- public:
- trivial_blossom(vertex_descriptor_t v) : trivial_vertex(v) {}
- virtual vertex_descriptor_t get_base() const
- {
- return trivial_vertex;
- }
-
- virtual std::vector<vertex_descriptor_t> vertices() const
- {
- std::vector<vertex_descriptor_t> all_vertices;
- all_vertices.push_back(trivial_vertex);
- return all_vertices;
- }
-
- private:
-
- vertex_descriptor_t trivial_vertex;
- };
-
- typedef boost::shared_ptr<blossom> blossom_ptr_t;
- typedef typename std::vector<blossom_ptr_t>::iterator blossom_iterator_t;
- typedef typename map_vertex_to_<blossom_ptr_t>::type vertex_to_blossom_map_t;
-
- weighted_augmenting_path_finder(const Graph& arg_g, MateMap arg_mate, VertexIndexMap arg_vm) :
- g(arg_g),
- vm(arg_vm),
- null_edge(std::pair<edge_descriptor_t, bool>(num_edges(g) == 0 ? edge_descriptor_t() : *edges(g).first, false)),
- mate_vector(num_vertices(g)),
- label_S_vector(num_vertices(g), graph_traits<Graph>::null_vertex()),
- label_T_vector(num_vertices(g), graph_traits<Graph>::null_vertex()),
- outlet_vector(num_vertices(g), graph_traits<Graph>::null_vertex()),
- tau_idx_vector(num_vertices(g), graph_traits<Graph>::null_vertex()),
- dual_var_vector(std::vector<edge_property_t>(num_vertices(g), std::numeric_limits<edge_property_t>::min())),
- pi_vector(std::vector<edge_property_t>(num_vertices(g), std::numeric_limits<edge_property_t>::max())),
- gamma_vector(std::vector<edge_property_t>(num_vertices(g), std::numeric_limits<edge_property_t>::max())),
- tau_vector(std::vector<edge_property_t>(num_vertices(g), std::numeric_limits<edge_property_t>::max())),
- in_blossom_vector(num_vertices(g)),
- old_label_vector(num_vertices(g)),
- critical_edge_vectors(num_vertices(g), std::vector<std::pair<edge_descriptor_t, bool> >(num_vertices(g), null_edge)),
-
- mate(mate_vector.begin(), vm),
- label_S(label_S_vector.begin(), vm),
- label_T(label_T_vector.begin(), vm),
- outlet(outlet_vector.begin(), vm),
- tau_idx(tau_idx_vector.begin(), vm),
- dual_var(dual_var_vector.begin(), vm),
- pi(pi_vector.begin(), vm),
- gamma(gamma_vector.begin(), vm),
- tau(tau_vector.begin(), vm),
- in_blossom(in_blossom_vector.begin(), vm),
- old_label(old_label_vector.begin(), vm)
- {
- vertex_iterator_t vi, vi_end;
- edge_iterator_t ei, ei_end;
-
- edge_property_t max_weight = std::numeric_limits<edge_property_t>::min();
- for (boost::tie(ei,ei_end) = edges(g); ei != ei_end; ++ei)
- max_weight = std::max(max_weight, get(edge_weight, g, *ei));
-
- typename std::vector<std::vector<std::pair<edge_descriptor_t, bool> > >::iterator vei;
-
- for (boost::tie(vi,vi_end) = vertices(g), vei = critical_edge_vectors.begin(); vi != vi_end; ++vi, ++vei)
- {
- vertex_descriptor_t u = *vi;
- mate[u] = get(arg_mate, u);
- dual_var[u] = 2*max_weight;
- in_blossom[u] = boost::make_shared<trivial_blossom>(u);
- outlet[u] = u;
- critical_edge_vector.push_back(vertex_to_edge_map_t(vei->begin(), vm));
- }
-
- critical_edge = vertex_pair_to_edge_map_t(critical_edge_vector.begin(), vm);
-
- init();
- }
-
- // return the top blossom where v is contained inside
- blossom_ptr_t in_top_blossom(vertex_descriptor_t v) const
- {
- blossom_ptr_t b = in_blossom[v];
- while (b->father != blossom_ptr_t())
- b = b->father;
- return b;
- }
-
- // check if vertex v is in blossom b
- bool is_in_blossom(blossom_ptr_t b, vertex_descriptor_t v) const
- {
- if (v == graph_traits<Graph>::null_vertex())
- return false;
- blossom_ptr_t vb = in_blossom[v]->father;
- while (vb != blossom_ptr_t())
- {
- if (vb.get() == b.get())
- return true;
- vb = vb->father;
- }
- return false;
- }
-
- // return the base vertex of the top blossom that contains v
- inline vertex_descriptor_t base_vertex(vertex_descriptor_t v) const
- {
- return in_top_blossom(v)->get_base();
- }
-
- // add an existed top blossom of base vertex v into new top
- // blossom b as its sub-blossom
- void add_sub_blossom(blossom_ptr_t b, vertex_descriptor_t v)
- {
- blossom_ptr_t sub = in_top_blossom(v);
- sub->father = b;
- b->sub_blossoms.push_back(sub);
- if (sub->sub_blossoms.empty())
- return;
- for (blossom_iterator_t bi = top_blossoms.begin(); bi != top_blossoms.end(); ++bi)
- {
- if (bi->get() == sub.get())
- {
- top_blossoms.erase(bi);
- break;
- }
- }
- }
-
- // when a top blossom is created or its base vertex getting an S-label,
- // add all edges incident to this blossom into even_edges
- void bloom(blossom_ptr_t b)
- {
- std::vector<vertex_descriptor_t> vertices_of_b = b->vertices();
- vertex_vec_iter_t vi;
- for (vi = vertices_of_b.begin(); vi != vertices_of_b.end(); ++vi)
- {
- out_edge_iterator_t oei, oei_end;
- for (boost::tie(oei,oei_end) = out_edges(*vi, g); oei != oei_end; ++oei)
- {
- if (target(*oei,g) != *vi && mate[*vi] != target(*oei,g))
- even_edges.push_back(*oei);
- }
- }
- }
-
- // assigning a T-label to a non S-vertex, along with outlet and updating pi value
- // if updated pi[v] equals zero, augment the matching from its mate vertex
- void put_T_label(vertex_descriptor_t v, vertex_descriptor_t T_label,
- vertex_descriptor_t outlet_v, edge_property_t pi_v)
- {
- if (label_S[v] != graph_traits<Graph>::null_vertex())
- return;
-
- label_T[v] = T_label;
- outlet[v] = outlet_v;
- pi[v] = pi_v;
-
- vertex_descriptor_t v_mate = mate[v];
- if (pi[v] == 0)
- {
- label_T[v_mate] = graph_traits<Graph>::null_vertex();
- label_S[v_mate] = v;
- bloom(in_top_blossom(v_mate));
- }
- }
-
- // get the missing T-label for a to-be-expanded base vertex
- // the missing T-label is the last vertex of the path from outlet[v] to v
- std::pair<vertex_descriptor_t, vertex_descriptor_t> missing_label(vertex_descriptor_t b_base)
- {
- vertex_descriptor_t missing_outlet = outlet[b_base];
-
- if (outlet[b_base] == b_base)
- return std::make_pair(graph_traits<Graph>::null_vertex(), missing_outlet);
-
- vertex_iterator_t vi, vi_end;
- for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
- old_label[*vi] = std::make_pair(label_T[*vi], outlet[*vi]);
-
- std::pair<vertex_descriptor_t, vertex_state_t> child(outlet[b_base], graph::detail::V_EVEN);
- blossom_ptr_t b = in_blossom[child.first];
- for (; b->father->father != blossom_ptr_t(); b = b->father);
- child.first = b->get_base();
-
- if (child.first == b_base)
- return std::make_pair(graph_traits<Graph>::null_vertex(), missing_outlet);
-
- while (true)
- {
- std::pair<vertex_descriptor_t, vertex_state_t> child_parent = parent(child, true);
-
- for (b = in_blossom[child_parent.first]; b->father->father != blossom_ptr_t(); b = b->father);
- missing_outlet = child_parent.first;
- child_parent.first = b->get_base();
-
- if (child_parent.first == b_base)
- break;
- else
- child = child_parent;
- }
- return std::make_pair(child.first, missing_outlet);
- }
-
- // expand a top blossom, put all its non-trivial sub-blossoms into top_blossoms
- blossom_iterator_t expand_blossom(blossom_iterator_t bi, std::vector<blossom_ptr_t>& new_ones)
- {
- blossom_ptr_t b = *bi;
- for (blossom_iterator_t i = b->sub_blossoms.begin(); i != b->sub_blossoms.end(); ++i)
- {
- blossom_ptr_t sub_blossom = *i;
- vertex_descriptor_t sub_base = sub_blossom->get_base();
- label_S[sub_base] = label_T[sub_base] = graph_traits<Graph>::null_vertex();
- outlet[sub_base] = sub_base;
- sub_blossom->father = blossom_ptr_t();
- // new top blossoms cannot be pushed back into top_blossoms immediately,
- // because push_back() may cause reallocation and then invalid iterators
- if (!sub_blossom->sub_blossoms.empty())
- new_ones.push_back(sub_blossom);
- }
- return top_blossoms.erase(bi);
- }
-
- // when expanding a T-blossom with base v, it requires more operations:
- // supply the missing T-labels for new base vertices by picking the minimum tau from vertices of
- // each corresponding new top-blossoms; when label_T[v] is null or we have a smaller tau from
- // missing_label(v), replace T-label and outlet of v (but don't bloom v)
- blossom_iterator_t expand_T_blossom(blossom_iterator_t bi, std::vector<blossom_ptr_t>& new_ones)
- {
- blossom_ptr_t b = *bi;
-
- vertex_descriptor_t b_base = b->get_base();
- std::pair<vertex_descriptor_t, vertex_descriptor_t> T_and_outlet = missing_label(b_base);
-
- blossom_iterator_t next_bi = expand_blossom(bi, new_ones);
-
- for (blossom_iterator_t i = b->sub_blossoms.begin(); i != b->sub_blossoms.end(); ++i)
- {
- blossom_ptr_t sub_blossom = *i;
- vertex_descriptor_t sub_base = sub_blossom->get_base();
- vertex_descriptor_t min_tau_v = graph_traits<Graph>::null_vertex();
- edge_property_t min_tau = std::numeric_limits<edge_property_t>::max();
-
- std::vector<vertex_descriptor_t> sub_vertices = sub_blossom->vertices();
- for (vertex_vec_iter_t v = sub_vertices.begin(); v != sub_vertices.end(); ++v)
- {
- if (tau[*v] < min_tau)
- {
- min_tau = tau[*v];
- min_tau_v = *v;
- }
- }
-
- if (min_tau < std::numeric_limits<edge_property_t>::max())
- put_T_label(sub_base, tau_idx[min_tau_v], min_tau_v, tau[min_tau_v]);
- }
-
- if (label_T[b_base] == graph_traits<Graph>::null_vertex() || tau[old_label[b_base].second] < pi[b_base])
- boost::tie(label_T[b_base], outlet[b_base]) = T_and_outlet;
-
- return next_bi;
- }
-
- // when vertices v and w are matched to each other by augmenting,
- // we must set v/w as base vertex of any blossom who contains v/w and
- // is a sub-blossom of their lowest (smallest) common blossom
- void adjust_blossom(vertex_descriptor_t v, vertex_descriptor_t w)
- {
- blossom_ptr_t vb = in_blossom[v], wb = in_blossom[w], lowest_common_blossom;
- std::vector<blossom_ptr_t> v_ancestors, w_ancestors;
-
- while (vb->father != blossom_ptr_t())
- {
- v_ancestors.push_back(vb->father);
- vb = vb->father;
- }
- while (wb->father != blossom_ptr_t())
- {
- w_ancestors.push_back(wb->father);
- wb = wb->father;
- }
-
- typename std::vector<blossom_ptr_t>::reverse_iterator i, j;
- i = v_ancestors.rbegin();
- j = w_ancestors.rbegin();
- while (i != v_ancestors.rend() && j != w_ancestors.rend() && i->get() == j->get())
- {
- lowest_common_blossom = *i;
- ++i;++j;
- }
-
- vb = in_blossom[v];
- wb = in_blossom[w];
- while (vb->father != lowest_common_blossom)
- {
- vb->father->set_base(vb);
- vb = vb->father;
- }
- while (wb->father != lowest_common_blossom)
- {
- wb->father->set_base(wb);
- wb = wb->father;
- }
- }
-
- // every edge weight is multiplied by 4 to ensure integer weights
- // throughout the algorithm if all input weights are integers
- inline edge_property_t slack(const edge_descriptor_t& e) const
- {
- vertex_descriptor_t v, w;
- v = source(e, g);
- w = target(e, g);
- return dual_var[v] + dual_var[w] - 4*get(edge_weight, g, e);
- }
-
- // backtrace one step on vertex v along the augmenting path
- // by its labels and its vertex state;
- // boolean parameter "use_old" means whether we are updating labels,
- // if we are, then we use old labels to backtrace and also we
- // don't jump to its base vertex when we reach an odd vertex
- std::pair<vertex_descriptor_t, vertex_state_t> parent(std::pair<vertex_descriptor_t, vertex_state_t> v,
- bool use_old = false) const
- {
- if (v.second == graph::detail::V_EVEN)
- {
- // a paranoid check: label_S shoule be the same as mate in backtracing
- if (label_S[v.first] == graph_traits<Graph>::null_vertex())
- label_S[v.first] = mate[v.first];
- return std::make_pair(label_S[v.first], graph::detail::V_ODD);
- }
- else if (v.second == graph::detail::V_ODD)
- {
- vertex_descriptor_t w = use_old ? old_label[v.first].first : base_vertex(label_T[v.first]);
- return std::make_pair(w, graph::detail::V_EVEN);
- }
- return std::make_pair(v.first, graph::detail::V_UNREACHED);
- }
-
- // backtrace from vertices v and w to their free (unmatched) ancesters,
- // return the nearest common ancestor (null_vertex if none) of v and w
- vertex_descriptor_t nearest_common_ancestor(vertex_descriptor_t v, vertex_descriptor_t w,
- vertex_descriptor_t& v_free_ancestor,
- vertex_descriptor_t& w_free_ancestor) const
- {
- std::pair<vertex_descriptor_t, vertex_state_t> v_up(v, graph::detail::V_EVEN);
- std::pair<vertex_descriptor_t, vertex_state_t> w_up(w, graph::detail::V_EVEN);
- vertex_descriptor_t nca;
- nca = w_free_ancestor = v_free_ancestor = graph_traits<Graph>::null_vertex();
-
- std::vector<bool> ancestor_of_w_vector(num_vertices(g), false);
- std::vector<bool> ancestor_of_v_vector(num_vertices(g), false);
- vertex_to_bool_map_t ancestor_of_w(ancestor_of_w_vector.begin(), vm);
- vertex_to_bool_map_t ancestor_of_v(ancestor_of_v_vector.begin(), vm);
-
- while (nca == graph_traits<Graph>::null_vertex() &&
- (v_free_ancestor == graph_traits<Graph>::null_vertex() ||
- w_free_ancestor == graph_traits<Graph>::null_vertex()))
- {
- ancestor_of_w[w_up.first] = true;
- ancestor_of_v[v_up.first] = true;
-
- 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.first] == graph_traits<Graph>::null_vertex())
- v_free_ancestor = v_up.first;
- if (mate[w_up.first] == graph_traits<Graph>::null_vertex())
- w_free_ancestor = w_up.first;
-
- if (ancestor_of_w[v_up.first] == true || v_up.first == w_up.first)
- nca = v_up.first;
- else if (ancestor_of_v[w_up.first] == true)
- nca = w_up.first;
- else if (v_free_ancestor == w_free_ancestor &&
- v_free_ancestor != graph_traits<Graph>::null_vertex())
- nca = v_up.first;
- }
-
- return nca;
- }
-
- // when a new top blossom b is created by connecting (v, w), we add sub-blossoms into
- // b along backtracing from v_prime and w_prime to stop_vertex (the base vertex);
- // also, we set labels and outlet for each base vertex we pass by
- void make_blossom(blossom_ptr_t b, vertex_descriptor_t w_prime,
- vertex_descriptor_t v_prime, vertex_descriptor_t stop_vertex)
- {
- std::pair<vertex_descriptor_t, vertex_state_t> u(v_prime, graph::detail::V_ODD);
- std::pair<vertex_descriptor_t, vertex_state_t> u_up(w_prime, graph::detail::V_EVEN);
-
- for (; u_up.first != stop_vertex; u = u_up, u_up = parent(u))
- {
- if (u_up.second == graph::detail::V_EVEN)
- {
- if (!in_top_blossom(u_up.first)->sub_blossoms.empty())
- outlet[u_up.first] = label_T[u.first];
- label_T[u_up.first] = outlet[u.first];
- }
- else if (u_up.second == graph::detail::V_ODD)
- label_S[u_up.first] = u.first;
-
- add_sub_blossom(b, u_up.first);
- }
- }
-
- // the design of recursively expanding augmenting path in (reversed_)retrieve_augmenting_path
- // functions is inspired by same functions in max_cardinality_matching.hpp;
- // except that in weighted matching, we use "outlet" vertices instead of "bridge" vertex pairs:
- // if blossom b is the smallest non-trivial blossom that contains its base vertex v, then
- // v and outlet[v] are where augmenting path enters and leaves b
- void retrieve_augmenting_path(vertex_descriptor_t v, vertex_descriptor_t w, vertex_state_t v_state)
- {
- if (v == w)
- aug_path.push_back(v);
- else if (v_state == graph::detail::V_EVEN)
- {
- aug_path.push_back(v);
- retrieve_augmenting_path(label_S[v], w, graph::detail::V_ODD);
- }
- else if (v_state == graph::detail::V_ODD)
- {
- if (outlet[v] == v)
- aug_path.push_back(v);
- else
- reversed_retrieve_augmenting_path(outlet[v], v, graph::detail::V_EVEN);
- retrieve_augmenting_path(label_T[v], w, graph::detail::V_EVEN);
- }
- }
-
- void reversed_retrieve_augmenting_path(vertex_descriptor_t v, vertex_descriptor_t w, vertex_state_t v_state)
- {
- if (v == w)
- aug_path.push_back(v);
- else if (v_state == graph::detail::V_EVEN)
- {
- reversed_retrieve_augmenting_path(label_S[v], w, graph::detail::V_ODD);
- aug_path.push_back(v);
- }
- else if (v_state == graph::detail::V_ODD)
- {
- reversed_retrieve_augmenting_path(label_T[v], w, graph::detail::V_EVEN);
- if (outlet[v] != v)
- retrieve_augmenting_path(outlet[v], v, graph::detail::V_EVEN);
- else
- aug_path.push_back(v);
- }
- }
-
- // correct labels for vertices in the augmenting path
- void relabel(vertex_descriptor_t v)
- {
- blossom_ptr_t b = in_blossom[v]->father;
-
- if (!is_in_blossom(b, mate[v]))
- { // if v is a new base vertex
- std::pair<vertex_descriptor_t, vertex_state_t> u(v, graph::detail::V_EVEN);
- while (label_S[u.first] != u.first && is_in_blossom(b, label_S[u.first]))
- u = parent(u, true);
-
- vertex_descriptor_t old_base = u.first;
- if (label_S[old_base] != old_base)
- { // if old base is not exposed
- label_T[v] = label_S[old_base];
- outlet[v] = old_base;
- }
- else
- { // if old base is exposed then new label_T[v] is not in b,
- // we must (i) make b2 the smallest blossom containing v but not as base vertex
- // (ii) backtrace from b2's new base vertex to b
- label_T[v] = graph_traits<Graph>::null_vertex();
- for (b = b->father; b != blossom_ptr_t() && b->get_base() == v; b = b->father);
- if (b != blossom_ptr_t())
- {
- u = std::make_pair(b->get_base(), graph::detail::V_ODD);
- while (!is_in_blossom(in_blossom[v]->father, old_label[u.first].first))
- u = parent(u, true);
- label_T[v] = u.first;
- outlet[v] = old_label[u.first].first;
- }
- }
- }
- else if (label_S[v] == v || !is_in_blossom(b, label_S[v]))
- { // if v is an old base vertex
- // let u be the new base vertex; backtrace from u's old T-label
- std::pair<vertex_descriptor_t, vertex_state_t> u(b->get_base(), graph::detail::V_ODD);
- while (old_label[u.first].first != graph_traits<Graph>::null_vertex() && old_label[u.first].first != v)
- u = parent(u, true);
- label_T[v] = old_label[u.first].second;
- outlet[v] = v;
- }
- else // if v is neither a new nor an old base vertex
- label_T[v] = label_S[v];
- }
-
- void augmenting(vertex_descriptor_t v, vertex_descriptor_t v_free_ancestor,
- vertex_descriptor_t w, vertex_descriptor_t w_free_ancestor)
- {
- vertex_iterator_t vi, vi_end;
-
- // retrieve the augmenting path and put it in aug_path
- reversed_retrieve_augmenting_path(v, v_free_ancestor, graph::detail::V_EVEN);
- retrieve_augmenting_path(w, w_free_ancestor, graph::detail::V_EVEN);
-
- // augment the matching along aug_path
- vertex_descriptor_t a, b;
- vertex_list_t reversed_aug_path;
- while (!aug_path.empty())
- {
- a = aug_path.front();
- aug_path.pop_front();
- reversed_aug_path.push_back(a);
- b = aug_path.front();
- aug_path.pop_front();
- reversed_aug_path.push_back(b);
-
- mate[a] = b;
- mate[b] = a;
-
- // reset base vertex for every blossom in augment path
- adjust_blossom(a, b);
- }
-
- for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
- old_label[*vi] = std::make_pair(label_T[*vi], outlet[*vi]);
-
- // correct labels for in-blossom vertices along aug_path
- while (!reversed_aug_path.empty())
- {
- a = reversed_aug_path.front();
- reversed_aug_path.pop_front();
-
- if (in_blossom[a]->father != blossom_ptr_t())
- relabel(a);
- }
-
- for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
- {
- vertex_descriptor_t u = *vi;
- if (mate[u] != graph_traits<Graph>::null_vertex())
- label_S[u] = mate[u];
- }
-
- // expand blossoms with zero dual variables
- std::vector<blossom_ptr_t> new_top_blossoms;
- for (blossom_iterator_t bi = top_blossoms.begin(); bi != top_blossoms.end();)
- {
- if ((*bi)->dual_var <= 0)
- bi = expand_blossom(bi, new_top_blossoms);
- else
- ++bi;
- }
- top_blossoms.insert(top_blossoms.end(), new_top_blossoms.begin(), new_top_blossoms.end());
- init();
- }
-
- // create a new blossom and set labels for vertices inside
- void blossoming(vertex_descriptor_t v, vertex_descriptor_t v_prime,
- vertex_descriptor_t w, vertex_descriptor_t w_prime,
- vertex_descriptor_t nca)
- {
- vertex_iterator_t vi, vi_end;
-
- std::vector<bool> is_old_base_vector(num_vertices(g));
- vertex_to_bool_map_t is_old_base(is_old_base_vector.begin(), vm);
- for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
- {
- if (*vi == base_vertex(*vi))
- is_old_base[*vi] = true;
- }
-
- blossom_ptr_t b = boost::make_shared<blossom>();
- add_sub_blossom(b, nca);
-
- label_T[w_prime] = v;
- label_T[v_prime] = w;
- outlet[w_prime] = w;
- outlet[v_prime] = v;
-
- make_blossom(b, w_prime, v_prime, nca);
- make_blossom(b, v_prime, w_prime, nca);
-
- label_T[nca] = graph_traits<Graph>::null_vertex();
- outlet[nca] = nca;
-
- top_blossoms.push_back(b);
- bloom(b);
-
- // set gamma[b_base] = min_slack{critical_edge(b_base, other_base)} where each critical edge
- // is updated before, by argmin{slack(old_bases_in_b, other_base)};
- vertex_vec_iter_t i, j;
- std::vector<vertex_descriptor_t> b_vertices = b->vertices(), old_base_in_b, other_base;
- vertex_descriptor_t b_base = b->get_base();
- for (i = b_vertices.begin(); i != b_vertices.end(); ++i)
- {
- if (is_old_base[*i])
- old_base_in_b.push_back(*i);
- }
- for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
- {
- if (*vi != b_base && *vi == base_vertex(*vi))
- other_base.push_back(*vi);
- }
- for (i = other_base.begin(); i != other_base.end(); ++i)
- {
- edge_property_t min_slack = std::numeric_limits<edge_property_t>::max();
- std::pair<edge_descriptor_t, bool> b_vi = null_edge;
- for (j = old_base_in_b.begin(); j != old_base_in_b.end(); ++j)
- {
- if (critical_edge[*j][*i] != null_edge && min_slack > slack(critical_edge[*j][*i].first))
- {
- min_slack = slack(critical_edge[*j][*i].first);
- b_vi = critical_edge[*j][*i];
- }
- }
- critical_edge[b_base][*i] = critical_edge[*i][b_base] = b_vi;
- }
- gamma[b_base] = std::numeric_limits<edge_property_t>::max();
- for (i = other_base.begin(); i != other_base.end(); ++i)
- {
- if (critical_edge[b_base][*i] != null_edge)
- gamma[b_base] = std::min(gamma[b_base], slack(critical_edge[b_base][*i].first));
- }
- }
-
- void init()
- {
- even_edges.clear();
-
- vertex_iterator_t vi, vi_end;
- typename std::vector<std::vector<std::pair<edge_descriptor_t, bool> > >::iterator vei;
-
- for (boost::tie(vi,vi_end) = vertices(g), vei = critical_edge_vectors.begin(); vi != vi_end; ++vi, ++vei)
- {
- vertex_descriptor_t u = *vi;
- out_edge_iterator_t ei, ei_end;
-
- gamma[u] = tau[u] = pi[u] = std::numeric_limits<edge_property_t>::max();
- std::fill(vei->begin(), vei->end(), null_edge);
-
- if (base_vertex(u) != u)
- continue;
-
- label_S[u] = label_T[u] = graph_traits<Graph>::null_vertex();
- outlet[u] = u;
-
- if (mate[u] == graph_traits<Graph>::null_vertex())
- {
- label_S[u] = u;
- bloom(in_top_blossom(u));
- }
- }
- }
-
- bool augment_matching()
- {
- vertex_descriptor_t v, w, w_free_ancestor, v_free_ancestor;
- v = w = w_free_ancestor = v_free_ancestor = graph_traits<Graph>::null_vertex();
- bool found_alternating_path = false;
-
- // note that we only use edges of zero slack value for augmenting
- while (!even_edges.empty() && !found_alternating_path)
- {
- // 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 = base_vertex(v);
- vertex_descriptor_t w_prime = base_vertex(w);
-
- // w_prime == v_prime implies that we get an edge that has been shrunk into a blossom
- if (v_prime == w_prime)
- continue;
-
- // a paranoid check
- if (label_S[v_prime] == graph_traits<Graph>::null_vertex())
- {
- std::swap(v_prime, w_prime);
- std::swap(v, w);
- }
-
- // w_prime may be unlabeled or have a T-label; replace the existed T-label if the edge slack
- // is smaller than current pi[w_prime] and update it. Note that a T-label is "deserved" only when pi equals zero.
- // also update tau and tau_idx so that tau_idx becomes T-label when a T-blossom is expanded
- if (label_S[w_prime] == graph_traits<Graph>::null_vertex())
- {
- if (slack(current_edge) < pi[w_prime])
- put_T_label(w_prime, v, w, slack(current_edge));
- if (slack(current_edge) < tau[w])
- {
- if (in_blossom[w]->father == blossom_ptr_t() || label_T[w_prime] == v ||
- label_T[w_prime] == graph_traits<Graph>::null_vertex() ||
- nearest_common_ancestor(v_prime, label_T[w_prime],
- v_free_ancestor, w_free_ancestor) == graph_traits<Graph>::null_vertex())
- {
- tau[w] = slack(current_edge);
- tau_idx[w] = v;
- }
- }
- }
-
- else
- {
- if (slack(current_edge) > 0)
- {
- // update gamma and critical_edges when we have a smaller edge slack
- gamma[v_prime] = std::min(gamma[v_prime], slack(current_edge));
- gamma[w_prime] = std::min(gamma[w_prime], slack(current_edge));
- if (critical_edge[v_prime][w_prime] == null_edge ||
- slack(critical_edge[v_prime][w_prime].first) > slack(current_edge))
- {
- critical_edge[v_prime][w_prime] = std::pair<edge_descriptor_t, bool>(current_edge, true);
- critical_edge[w_prime][v_prime] = std::pair<edge_descriptor_t, bool>(current_edge, true);
- }
- continue;
- }
- else if (slack(current_edge) == 0)
- {
- // if nca is null_vertex then we have an augmenting path; otherwise we have
- // a new top blossom with nca as its base vertex
- vertex_descriptor_t nca = nearest_common_ancestor(v_prime, w_prime, v_free_ancestor, w_free_ancestor);
-
- if (nca == graph_traits<Graph>::null_vertex())
- found_alternating_path = true; //to break out of the loop
- else
- blossoming(v, v_prime, w, w_prime, nca);
- }
- }
- }
-
- if (!found_alternating_path)
- return false;
-
- augmenting(v, v_free_ancestor, w, w_free_ancestor);
- return true;
- }
-
- // slack the vertex and blossom dual variables when there is no augmenting path found
- // according to the primal-dual method
- bool adjust_dual()
- {
- edge_property_t delta1, delta2, delta3, delta4, delta;
- delta1 = delta2 = delta3 = delta4 = std::numeric_limits<edge_property_t>::max();
-
- vertex_iterator_t vi, vi_end;
-
- for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
- {
- delta1 = std::min(delta1, dual_var[*vi]);
- delta4 = pi[*vi] > 0 ? std::min(delta4, pi[*vi]) : delta4;
- if (*vi == base_vertex(*vi))
- delta3 = std::min(delta3, gamma[*vi]/2);
- }
-
- for (blossom_iterator_t bi = top_blossoms.begin(); bi != top_blossoms.end(); ++bi)
- {
- vertex_descriptor_t b_base = (*bi)->get_base();
- if (label_T[b_base] != graph_traits<Graph>::null_vertex() && pi[b_base] == 0)
- delta2 = std::min(delta2, (*bi)->dual_var/2);
- }
-
- delta = std::min(std::min(delta1, delta2), std::min(delta3, delta4));
-
- // start updating dual variables, note that the order is important
-
- for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
- {
- vertex_descriptor_t v = *vi, v_prime = base_vertex(v);
-
- if (label_S[v_prime] != graph_traits<Graph>::null_vertex())
- dual_var[v] -= delta;
- else if (label_T[v_prime] != graph_traits<Graph>::null_vertex() && pi[v_prime] == 0)
- dual_var[v] += delta;
-
- if (v == v_prime)
- gamma[v] -= 2*delta;
- }
-
- for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
- {
- vertex_descriptor_t v_prime = base_vertex(*vi);
- if (pi[v_prime] > 0)
- tau[*vi] -= delta;
- }
-
- for (blossom_iterator_t bi = top_blossoms.begin(); bi != top_blossoms.end(); ++bi)
- {
- vertex_descriptor_t b_base = (*bi)->get_base();
- if (label_T[b_base] != graph_traits<Graph>::null_vertex() && pi[b_base] == 0)
- (*bi)->dual_var -= 2*delta;
- if (label_S[b_base] != graph_traits<Graph>::null_vertex())
- (*bi)->dual_var += 2*delta;
- }
-
- for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
- {
- vertex_descriptor_t v = *vi;
- if (pi[v] > 0)
- pi[v] -= delta;
-
- // when some T-vertices have zero pi value, bloom their mates so that matching can be further augmented
- if (label_T[v] != graph_traits<Graph>::null_vertex() && pi[v] == 0)
- put_T_label(v, label_T[v], outlet[v], pi[v]);
- }
-
-
- // optimal solution reached, halt
- if (delta == delta1)
- return false;
-
- // expand odd blossoms with zero dual variables and zero pi value of their base vertices
- if (delta == delta2 && delta != delta3)
- {
- std::vector<blossom_ptr_t> new_top_blossoms;
- for (blossom_iterator_t bi = top_blossoms.begin(); bi != top_blossoms.end();)
- {
- const blossom_ptr_t b = *bi;
- vertex_descriptor_t b_base = b->get_base();
- if (b->dual_var == 0 && label_T[b_base] != graph_traits<Graph>::null_vertex() && pi[b_base] == 0)
- bi = expand_T_blossom(bi, new_top_blossoms);
- else
- ++bi;
- }
- top_blossoms.insert(top_blossoms.end(), new_top_blossoms.begin(), new_top_blossoms.end());
- }
-
- while (true)
- {
- // find a zero-slack critical edge (v, w) of zero gamma values
- std::pair<edge_descriptor_t, bool> best_edge = null_edge;
- std::vector<vertex_descriptor_t> base_nodes;
- for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
- {
- if (*vi == base_vertex(*vi))
- base_nodes.push_back(*vi);
- }
- for (vertex_vec_iter_t i = base_nodes.begin(); i != base_nodes.end(); ++i)
- {
- if (gamma[*i] == 0)
- {
- for (vertex_vec_iter_t j = base_nodes.begin(); j != base_nodes.end(); ++j)
- {
- if (critical_edge[*i][*j] != null_edge && slack(critical_edge[*i][*j].first) == 0)
- best_edge = critical_edge[*i][*j];
- }
- }
- }
-
- // if not found, continue finding other augment matching
- if (best_edge == null_edge)
- {
- bool augmented = augment_matching();
- return augmented || delta != delta1;
- }
- // if found, determine either augmenting or blossoming
- vertex_descriptor_t v = source(best_edge.first, g), w = target(best_edge.first, g);
- vertex_descriptor_t v_prime = base_vertex(v), w_prime = base_vertex(w), v_free_ancestor, w_free_ancestor;
- vertex_descriptor_t nca = nearest_common_ancestor(v_prime, w_prime, v_free_ancestor, w_free_ancestor);
- if (nca == graph_traits<Graph>::null_vertex())
- {
- augmenting(v, v_free_ancestor, w, w_free_ancestor);
- return true;
- }
- else
- blossoming(v, v_prime, w, w_prime, nca);
- }
-
- return false;
- }
-
- template <typename PropertyMap>
- void get_current_matching(PropertyMap pm)
- {
- vertex_iterator_t vi, vi_end;
- for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
- put(pm, *vi, mate[*vi]);
- }
-
- private:
-
- const Graph& g;
- VertexIndexMap vm;
- const std::pair<edge_descriptor_t, bool> null_edge;
-
- // storage for the property maps below
- std::vector<vertex_descriptor_t> mate_vector;
- std::vector<vertex_descriptor_t> label_S_vector, label_T_vector;
- std::vector<vertex_descriptor_t> outlet_vector;
- std::vector<vertex_descriptor_t> tau_idx_vector;
- std::vector<edge_property_t> dual_var_vector;
- std::vector<edge_property_t> pi_vector, gamma_vector, tau_vector;
- std::vector<blossom_ptr_t> in_blossom_vector;
- std::vector<std::pair<vertex_descriptor_t, vertex_descriptor_t> > old_label_vector;
- std::vector<vertex_to_edge_map_t> critical_edge_vector;
- std::vector<std::vector<std::pair<edge_descriptor_t, bool> > > critical_edge_vectors;
-
- // iterator property maps
- vertex_to_vertex_map_t mate;
- vertex_to_vertex_map_t label_S; // v has an S-label -> v can be an even vertex, label_S[v] is its mate
- vertex_to_vertex_map_t label_T; // v has a T-label -> v can be an odd vertex, label_T[v] is its predecessor in aug_path
- vertex_to_vertex_map_t outlet;
- vertex_to_vertex_map_t tau_idx;
- vertex_to_weight_map_t dual_var;
- vertex_to_weight_map_t pi, gamma, tau;
- vertex_to_blossom_map_t in_blossom; // map any vertex v to the trivial blossom containing v
- vertex_to_pair_map_t old_label; // <old T-label, old outlet> before relabeling or expanding T-blossoms
- vertex_pair_to_edge_map_t critical_edge; // an not matched edge (v, w) is critical if v and w belongs to different S-blossoms
-
- vertex_list_t aug_path;
- edge_list_t even_edges;
- std::vector<blossom_ptr_t> top_blossoms;
-
- };
-
- template <typename Graph, typename MateMap, typename VertexIndexMap>
- void maximum_weighted_matching(const Graph& g, MateMap mate, VertexIndexMap vm)
- {
- empty_matching<Graph, MateMap>::find_matching(g, mate);
- weighted_augmenting_path_finder<Graph, MateMap, VertexIndexMap> augmentor(g, mate, vm);
-
- // can have |V| times augmenting at most
- for (std::size_t t = 0; t < num_vertices(g); ++t)
- {
- bool augmented = false;
- while (!augmented)
- {
- augmented = augmentor.augment_matching();
- if (!augmented)
- {
- // halt if adjusting dual variables can't bring potential augment
- if (!augmentor.adjust_dual())
- break;
- }
- }
- if (!augmented)
- break;
- }
-
- augmentor.get_current_matching(mate);
- }
-
- template <typename Graph, typename MateMap>
- inline void maximum_weighted_matching(const Graph& g, MateMap mate)
- {
- maximum_weighted_matching(g, mate, get(vertex_index,g));
- }
-
- // brute-force matcher searches all possible combinations of matched edges to get the maximum weighted matching
- // which can be used for testing on small graphs (within dozens vertices)
- template <typename Graph, typename MateMap, typename VertexIndexMap>
- class brute_force_matching
- {
- public:
-
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor_t;
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
- typedef typename std::vector<vertex_descriptor_t>::iterator vertex_vec_iter_t;
- typedef typename graph_traits<Graph>::edge_iterator edge_iterator_t;
- typedef boost::iterator_property_map<vertex_vec_iter_t, VertexIndexMap> vertex_to_vertex_map_t;
-
- brute_force_matching(const Graph& arg_g, MateMap arg_mate, VertexIndexMap arg_vm) :
- g(arg_g),
- vm(arg_vm),
- mate_vector(num_vertices(g)),
- best_mate_vector(num_vertices(g)),
- mate(mate_vector.begin(), vm),
- best_mate(best_mate_vector.begin(), vm)
- {
- vertex_iterator_t vi,vi_end;
- for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
- best_mate[*vi] = mate[*vi] = get(arg_mate, *vi);
- }
-
- template <typename PropertyMap>
- void find_matching(PropertyMap pm)
- {
- edge_iterator_t ei;
- boost::tie(ei, ei_end) = edges(g);
- select_edge(ei);
-
- vertex_iterator_t vi,vi_end;
- for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
- put(pm, *vi, best_mate[*vi]);
- }
-
- private:
-
- const Graph& g;
- VertexIndexMap vm;
- std::vector<vertex_descriptor_t> mate_vector, best_mate_vector;
- vertex_to_vertex_map_t mate, best_mate;
- edge_iterator_t ei_end;
-
- void select_edge(edge_iterator_t ei)
- {
- if (ei == ei_end)
- {
- if (matching_weight_sum(g, mate) > matching_weight_sum(g, best_mate))
- {
- vertex_iterator_t vi, vi_end;
- for (boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
- best_mate[*vi] = mate[*vi];
- }
- return;
- }
-
- vertex_descriptor_t v, w;
- v = source(*ei, g);
- w = target(*ei, g);
-
- select_edge(++ei);
-
- if (mate[v] == graph_traits<Graph>::null_vertex() &&
- mate[w] == graph_traits<Graph>::null_vertex())
- {
- mate[v] = w;
- mate[w] = v;
- select_edge(ei);
- mate[v] = mate[w] = graph_traits<Graph>::null_vertex();
- }
- }
-
- };
-
- template <typename Graph, typename MateMap, typename VertexIndexMap>
- void brute_force_maximum_weighted_matching(const Graph& g, MateMap mate, VertexIndexMap vm)
- {
- empty_matching<Graph, MateMap>::find_matching(g, mate);
- brute_force_matching<Graph, MateMap, VertexIndexMap> brute_force_matcher(g, mate, vm);
- brute_force_matcher.find_matching(mate);
- }
-
- template <typename Graph, typename MateMap>
- inline void brute_force_maximum_weighted_matching(const Graph& g, MateMap mate)
- {
- brute_force_maximum_weighted_matching(g, mate, get(vertex_index, g));
- }
-
- }
- #endif
|