boost.graph：在过滤图上使用 kruskal 算法无法编译

Question

我正在使用 boost graph，并且尝试在过滤图上运行 kruskal_minimum_spanning_tree 算法。遗憾的是它无法编译。

这是一个显示问题的示例：

#include <boost/graph/adjacency_list.hpp>
#include "boost/graph/graph_utility.hpp"
#include <boost/graph/filtered_graph.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>

using Graph  = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
using Vertex = boost::graph_traits<Graph>::vertex_descriptor;
using Edge   = boost::graph_traits<Graph>::edge_descriptor;

int main()
{
  Graph G;
  
  // create a complete graph with 4 nodes.
  for (int i = 0; i < 5 ; ++i)
  {
    for (int j = i+1; j< 5; ++j)
      boost::add_edge(i, j, G);
  }
  boost::print_graph(G);
  /*  0 <--> 1 2 3 4
      1 <--> 0 2 3 4
      2 <--> 0 1 3 4
      3 <--> 0 1 2 4
      4 <--> 0 1 2 3  */

  struct Filter
  {
    bool operator()(Vertex const & v) const
    {
      if (v != 0 && v != 2)
        return true;
      return false;
    }
  };
  boost::filtered_graph G_f(G, boost::keep_all(), Filter());
  boost::print_graph(G_f);
  /* 1 <--> 3 4
     3 <--> 1 4
     4 <--> 1 3  */

  auto wmap = boost::make_function_property_map<Edge, double>([](Edge const & e){ return 1.0; });
  std::vector<Edge> mst;

  // Works:
  kruskal_minimum_spanning_tree(G, std::back_inserter(mst), boost::weight_map(wmap));
  
  // Does not compile:
  kruskal_minimum_spanning_tree(G_f, std::back_inserter(mst), boost::weight_map(wmap));
  
  double result = 0;
  for (auto const & e : mst)
    result += wmap[e];
  std::cout << result << "\n";  // prints 4
}

我可以将 kruskals 算法应用于原始图，并且效果很好。 但是当我尝试在过滤后的图表上运行它时，我收到以下编译错误：

error C2039: 'type': is not a member of 'boost::vertex_property_type<Graph>'
error C2039:         [
error C2039:         with
error C2039:             Graph=boost::filtered_graph<Graph,boost::keep_all,main::Filter>
error C2039:         ]
error C3203: 'type': unspecialized class template can't be used as a template argument for template parameter 'Property', expected a real type

我做错了什么？

Answer 1

我认为问题在于，为了运行 Kruskal 算法，你的图应该有边权重，但你的示例中并非如此：

using Graph  = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
using Vertex = boost::graph_traits<Graph>::vertex_descriptor;
using Edge   = boost::graph_traits<Graph>::edge_descriptor;

应该是这样的：

using namespace boost;
typedef adjacency_list< vecS, vecS, undirectedS, no_property,
    property< edge_weight_t, int > >
    Graph;
typedef graph_traits< Graph >::edge_descriptor Edge;
typedef std::pair< int, int > E;

请查看官方文档中的完整示例：

https://www.boost.org/doc/libs/1_85_0/libs/graph/example/kruskal-example.cpp