boost.graph: Using kruskal algorithm on filtered graph doesn't compile

i am using boost graph and i am trying to run kruskal_minimum_spanning_tree algorithm on a filtered graph. Sadly it doesn't compile.

Here is an example showing the problem:

#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
}

I can apply kruskals algorithm to the original graph and it works just fine. But when i try to run it on the filtered graph i get the following compilation error:

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

What am i doing wrong?

That's a bug. The documentation states that the default value for the vertex index map is vertex_index_map(VertexIndexMap i_map).

Just passing it explicitly works around the issue.

Meanwhile, I'd replace the function property map with a constant. You can leverage CTAD some more to avoid the Filter type. This might not be what you need, but still good to know:

Coliru

#include <boost/graph/graph_utility.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <numeric> // std::accumulate

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;

void do_the_thing(auto const& g) {
    boost::print_graph(g);

    auto wmap = boost::make_constant_property<Edge>(1.0);
    std::vector<Edge> mst;

    kruskal_minimum_spanning_tree(                         //
        g, std::back_inserter(mst),                        //
        weight_map(wmap)                                   //
            .vertex_index_map(get(boost::vertex_index, g)) //
    );

    // std::cout << std::accumulate(mst.begin(), mst.end(), 0.0, [&](double
    // acc, Edge e) { return acc + wmap[e]; });
    std::cout << mst.size() << "\n";
}

int main() {
    Graph G(4);

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

    do_the_thing(G);
    boost::filtered_graph G_f( //
        G, boost::keep_all(), std::function([](Vertex const& v) {
            if (v != 0 && v != 2)
                return true;
            return false;
        }));
    do_the_thing(G_f);
}

Printing

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
4
1 <--> 3 4
3 <--> 1 4
4 <--> 1 3
2