Boost Graph过滤图执行Kruskal算法编译失败求助

问题描述 #

使用Boost Graph库时，在filtered_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;
  
  // 创建包含5个节点的完全图
  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;

  // 正常运行
  kruskal_minimum_spanning_tree(G, std::back_inserter(mst), boost::weight_map(wmap));
  
  // 编译失败
  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";  // 输出4
}

编译错误信息 #

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

问题原因与解决方法 #

核心问题 #

Kruskal算法需要访问图的顶点属性元信息，但filtered_graph默认未正确导出底层图的顶点属性类型，导致模板推导失败。另外，原代码中wmap基于原Graph的Edge类型，而filtered_graph的边描述符是filtered_edge_descriptor，类型不匹配，即使编译通过也会引发运行错误。

解决步骤 #

• 显式指定filtered_graph模板参数：
  定义filtered_graph时明确模板参数，避免类型推导歧义：

  using FilteredGraph = boost::filtered_graph<Graph, boost::keep_all, Filter>;
  FilteredGraph G_f(G, boost::keep_all(), Filter());
  

• 适配权重映射到过滤图的边类型：
  为filtered_graph的边创建对应权重映射，通过edge_underlying_t获取底层原边复用原权重逻辑：

  using FilteredEdge = boost::graph_traits<FilteredGraph>::edge_descriptor;
  auto fg_wmap = boost::make_function_property_map<FilteredEdge, double>([&](FilteredEdge const & e) {
      Edge orig_e = boost::get(boost::edge_underlying_t(), G_f, e);
      return wmap[orig_e];
  });
  

• 显式提供顶点索引映射：
  为filtered_graph指定顶点索引映射，避免算法自动推导时触发错误的属性类型查找：

  kruskal_minimum_spanning_tree(G_f, std::back_inserter(fg_mst),
      boost::weight_map(fg_wmap)
      .vertex_index_map(boost::make_function_property_map<Vertex>([](Vertex v) { return v; })));
  

完整修正代码 #

#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>
#include <iostream>
#include <vector>

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;
  
  // 创建包含5个节点的完全图
  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);

  struct Filter
  {
    bool operator()(Vertex const & v) const
    {
      return v != 0 && v != 2;
    }
  };

  using FilteredGraph = boost::filtered_graph<Graph, boost::keep_all, Filter>;
  FilteredGraph G_f(G, boost::keep_all(), Filter());
  boost::print_graph(G_f);

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

  // 原图运行
  kruskal_minimum_spanning_tree(G, std::back_inserter(mst), boost::weight_map(wmap));
  
  // 过滤图运行的修正版本
  using FilteredEdge = boost::graph_traits<FilteredGraph>::edge_descriptor;
  auto fg_wmap = boost::make_function_property_map<FilteredEdge, double>([&](FilteredEdge const & e) {
      Edge orig_e = boost::get(boost::edge_underlying_t(), G_f, e);
      return wmap[orig_e];
  });

  std::vector<FilteredEdge> fg_mst;
  kruskal_minimum_spanning_tree(G_f, std::back_inserter(fg_mst),
      boost::weight_map(fg_wmap)
      .vertex_index_map(boost::make_function_property_map<Vertex>([](Vertex v) { return v; })));
  
  double result = 0;
  for (auto const & e : mst)
    result += wmap[e];
  std::cout << "原图MST总权重: " << result << "\n";  // 输出4

  double fg_result = 0;
  for (auto const & e : fg_mst) {
      Edge orig_e = boost::get(boost::edge_underlying_t(), G_f, e);
      fg_result += wmap[orig_e];
  }
  std::cout << "过滤图MST总权重: " << fg_result << "\n";  // 输出2
}

关键说明 #

• 显式指定filtered_graph模板类型，帮助Boost元编程正确推导属性信息。
• 为过滤图的边单独创建权重映射，确保类型匹配的同时复用原权重逻辑。
• 显式提供顶点索引映射，避免算法尝试自动推导时触发错误的属性类型查找。

内容的提问来源于stack exchange，提问作者Alexander