提升最大重量匹配运行时间爆炸

Question

我有一个有 16 个顶点的图，所有顶点都以相等的权重相互连接（120 条边）。当我尝试在此图表上运行增强最大权重匹配时，它无限期地挂起。所有边权重都是整数。我想知道这是否是 boost 的问题，或者预计最大权重匹配需要很长时间才能收敛到派系。此外，将每条边的权重更改为不同也可以解决该问题。这是 Godbolt 的链接 https://godbolt.org/z/Mbf84Yva7 .

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/bipartite.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/maximum_weighted_matching.hpp>
#include <boost/graph/max_cardinality_matching.hpp>
#include <boost/graph/properties.hpp>
#include <boost/variant.hpp>

typedef boost::property<boost::edge_weight_t, int> EdgeWeightProperty;
typedef boost::adjacency_list<boost::vecS,
                              boost::vecS,
                              boost::undirectedS,
                              boost::no_property,
                              EdgeWeightProperty>
  my_graph;

int main() {
      my_graph g;
      for(int i = 0 ; i < 16 ; ++i) {
        boost::add_vertex(g);
      }
      for(int i = 0 ; i < 16 ; ++i) {
        for(int j = 0 ; j < 16 ; ++j) {
            if(i < j) {
                boost::add_edge(i, j, EdgeWeightProperty(5), g);
            }
        }
      }
    std::vector<boost::graph_traits<my_graph>::vertex_descriptor> mate1(boost::num_vertices(g));
    std::cout<<" Running Boost max weight matching on boost graph " << std::endl;
    std::cout<<" Num vertices "<< boost::num_vertices(g) << std::endl;
    std::cout<<" Num edges "<< boost::num_edges(g) << std::endl;
    // boost::edmonds_maximum_cardinality_matching(g, &mate1[0]);
    boost::maximum_weighted_matching(g, &mate1[0]);
    std::cout<<" Done running max weight matching on boost graph" << std::endl;

}

Answer 1

在你的图表中没有一个答案。如果匹配项包含每个顶点 ，则该匹配项与其他所有此类匹配项具有相同的权重。

那么重点是什么？这是一个毫无意义的问题。

如果您想防止挂起，请在调用 boost graph 方法之前在边缘上添加一个小循环以检查它们的权重是否相同。