c++ - boost 图形库 : BFS on a Vertex-filtered graph?

Question

我正在尝试编写广度优先搜索的一个版本，它只搜索我给定图的一个子图。为此，我尝试使用 filtered_graph来自 Boost BGL 的类。

尝试执行此操作时，我遇到了巨大、难看的模板类型错误。

我在想:

1. 如何转换 v ，我在原始图中的起始顶点，变成过滤图中的顶点？
2. 对于 BFS，我的访客类型应该是什么？是MyVisitor<Vertex, SubGraph>就像我一样，还是我需要特定于过滤图的不同顶点类型？ (此处 SubGraph 是过滤图形类型的 typedef)。

下面是我的代码片段，它在 BFS 被注释掉时编译，但在未注释掉时给出错误。

#include <cstdlib>
#include <iostream>
#include <set>
#include <climits>
#include <algorithm>

#include <boost/property_map/property_map.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/filtered_graph.hpp>

#include <vector>

//Adapted from http://stackoverflow.com/questions/14470566/how-to-traverse-graph-in-boost-use-bfs
typedef boost::adjacency_list < boost::vecS, boost::vecS, boost::undirectedS > Graph;
typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;
typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;

/**
  Functor to filter vertices in a graph which are not in the given set
  */
class VertexSetFilter
{
public:
    std::set<Vertex> S;

    VertexSetFilter(std::set<Vertex> inputSet)
    {
        S = inputSet;
    }

    bool operator()(const Vertex& v) const
    {
        return S.find(v) != S.end(); // keep all vertx_descriptors greater than 3
    }
};


template < typename TVertex, typename TGraph >
class MyVisitor : public boost::default_bfs_visitor
{
private:
    int numFound;

public:

    void discover_vertex(TVertex u, const TGraph & g) const
    {
        std::cout << u << std::endl;
    }
    int getNumFound()
    {
        return numFound;
    }
};

int restrictedBFS(std::set<Vertex> S, Vertex v, Graph G)
{
    VertexSetFilter myFilter(S);
    typedef boost::filtered_graph<Graph, boost::keep_all, VertexSetFilter > SubGraph;
    SubGraph filteredG(G, boost::keep_all(), myFilter);

    MyVisitor<Vertex, SubGraph> vis;
    //won't compile when this line is uncommented
    boost::breadth_first_search(filteredG, v, boost::visitor(vis));
    return -1;
}


int main()
{
    std::cout << "Hello";
}

它给出了以下丑陋的模板错误:

In file included from bfs.cc:10:
In file included from /usr/include/boost/graph/filtered_graph.hpp:17:
/usr/include/boost/iterator/filter_iterator.hpp:54:7: error: constructor for 'boost::filter_iterator<VertexSetFilter,
  boost::range_detail::integer_iterator<unsigned long> >' must explicitly initialize the member 'm_predicate'
  which does not have a default constructor
  filter_iterator() { }
  ^
/usr/include/boost/graph/breadth_first_search.hpp:119:68: note: in instantiation of member function
  'boost::filter_iterator<VertexSetFilter, boost::range_detail::integer_iterator<unsigned long>
  >::filter_iterator' requested here
typename boost::graph_traits<VertexListGraph>::vertex_iterator i, i_end;
                                  ^
/usr/include/boost/graph/breadth_first_search.hpp:135:5: note: in instantiation of function template specialization
  'boost::breadth_first_search<boost::filtered_graph<boost::adjacency_list<boost::vecS, boost::vecS,
  boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::keep_all,
  VertexSetFilter>, unsigned long *, boost::queue<unsigned long, std::deque<unsigned long,
  std::allocator<unsigned long> > >, MyVisitor<unsigned long,
  boost::filtered_graph<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property,
  boost::no_property, boost::no_property, boost::listS>, boost::keep_all, VertexSetFilter> >,
  boost::two_bit_color_map<boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned long> > >' requested
  here
breadth_first_search(g, sources, sources + 1, Q, vis, color);
^
/usr/include/boost/graph/breadth_first_search.hpp:257:7: note: in instantiation of function template specialization
  'boost::breadth_first_search<boost::filtered_graph<boost::adjacency_list<boost::vecS, boost::vecS,
  boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::keep_all,
  VertexSetFilter>, boost::queue<unsigned long, std::deque<unsigned long, std::allocator<unsigned long> > >,
  MyVisitor<unsigned long, boost::filtered_graph<boost::adjacency_list<boost::vecS, boost::vecS,
  boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::keep_all,
  VertexSetFilter> >, boost::two_bit_color_map<boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned
  long> > >' requested here
  breadth_first_search
  ^
/usr/include/boost/graph/breadth_first_search.hpp:312:9: note: in instantiation of function template specialization
  'boost::detail::bfs_helper<boost::filtered_graph<boost::adjacency_list<boost::vecS, boost::vecS,
  boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::keep_all,
  VertexSetFilter>, boost::two_bit_color_map<boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned long>
  >, MyVisitor<unsigned long, boost::filtered_graph<boost::adjacency_list<boost::vecS, boost::vecS,
  boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::keep_all,
  VertexSetFilter> >, MyVisitor<unsigned long, boost::filtered_graph<boost::adjacency_list<boost::vecS,
  boost::vecS, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>,
  boost::keep_all, VertexSetFilter> >, boost::graph_visitor_t, boost::no_property>' requested here
    bfs_helper
    ^
/usr/include/boost/graph/breadth_first_search.hpp:344:30: note: in instantiation of function template specialization
  'boost::detail::bfs_dispatch<boost::param_not_found>::apply<boost::filtered_graph<boost::adjacency_list<boost::vecS,
  boost::vecS, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>,
  boost::keep_all, VertexSetFilter>, MyVisitor<unsigned long,
  boost::filtered_graph<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property,
  boost::no_property, boost::no_property, boost::listS>, boost::keep_all, VertexSetFilter> >,
  boost::graph_visitor_t, boost::no_property>' requested here
detail::bfs_dispatch<C>::apply(ng, s, params,
            ^
bfs.cc:65:12: note: in instantiation of function template specialization
  'boost::breadth_first_search<boost::filtered_graph<boost::adjacency_list<boost::vecS, boost::vecS,
  boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::keep_all,
  VertexSetFilter>, MyVisitor<unsigned long, boost::filtered_graph<boost::adjacency_list<boost::vecS,
  boost::vecS, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>,
  boost::keep_all, VertexSetFilter> >, boost::graph_visitor_t, boost::no_property>' requested here
boost::breadth_first_search(filteredG, v, boost::visitor(vis));
      ^
/usr/include/boost/iterator/filter_iterator.hpp:106:17: note: member is declared here
  Predicate m_predicate;
        ^
bfs.cc:22:7: note: 'VertexSetFilter' declared here
class VertexSetFilter
  ^
In file included from bfs.cc:10:
/usr/include/boost/graph/filtered_graph.hpp:69:7: error: constructor for
  'boost::detail::out_edge_predicate<boost::keep_all, VertexSetFilter,
  boost::filtered_graph<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property,
  boost::no_property, boost::no_property, boost::listS>, boost::keep_all, VertexSetFilter> >' must explicitly
  initialize the member 'm_vertex_pred' which does not have a default constructor
  out_edge_predicate() { }
  ^
/usr/include/boost/iterator/filter_iterator.hpp:54:7: note: in instantiation of member function
  'boost::detail::out_edge_predicate<boost::keep_all, VertexSetFilter,
  boost::filtered_graph<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property,
  boost::no_property, boost::no_property, boost::listS>, boost::keep_all, VertexSetFilter> >::out_edge_predicate'
  requested here
  filter_iterator() { }
  ^
/usr/include/boost/graph/breadth_first_search.hpp:71:41: note: in instantiation of member function
  'boost::filter_iterator<boost::detail::out_edge_predicate<boost::keep_all, VertexSetFilter,
  boost::filtered_graph<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property,
  boost::no_property, boost::no_property, boost::listS>, boost::keep_all, VertexSetFilter> >,
  boost::detail::out_edge_iter<__gnu_cxx::__normal_iterator<boost::detail::stored_edge_iter<unsigned long,
  std::_List_iterator<boost::list_edge<unsigned long, boost::no_property> >, boost::no_property> *,
  std::vector<boost::detail::stored_edge_iter<unsigned long, std::_List_iterator<boost::list_edge<unsigned long,
  boost::no_property> >, boost::no_property>, std::allocator<boost::detail::stored_edge_iter<unsigned long,
  std::_List_iterator<boost::list_edge<unsigned long, boost::no_property> >, boost::no_property> > > >, unsigned
  long, boost::detail::edge_desc_impl<boost::undirected_tag, unsigned long>, long> >::filter_iterator' requested
  here
typename GTraits::out_edge_iterator ei, ei_end;
                    ^
/usr/include/boost/graph/breadth_first_search.hpp:124:5: note: in instantiation of function template specialization
  'boost::breadth_first_visit<boost::filtered_graph<boost::adjacency_list<boost::vecS, boost::vecS,
  boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::keep_all,
  VertexSetFilter>, boost::queue<unsigned long, std::deque<unsigned long, std::allocator<unsigned long> > >,
  MyVisitor<unsigned long, boost::filtered_graph<boost::adjacency_list<boost::vecS, boost::vecS,
  boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::keep_all,
  VertexSetFilter> >, boost::two_bit_color_map<boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned
  long> >, unsigned long *>' requested here
breadth_first_visit(g, sources_begin, sources_end, Q, vis, color);
^
/usr/include/boost/graph/breadth_first_search.hpp:135:5: note: in instantiation of function template specialization
  'boost::breadth_first_search<boost::filtered_graph<boost::adjacency_list<boost::vecS, boost::vecS,
  boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::keep_all,
  VertexSetFilter>, unsigned long *, boost::queue<unsigned long, std::deque<unsigned long,
  std::allocator<unsigned long> > >, MyVisitor<unsigned long,
  boost::filtered_graph<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property,
  boost::no_property, boost::no_property, boost::listS>, boost::keep_all, VertexSetFilter> >,
  boost::two_bit_color_map<boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned long> > >' requested
  here
breadth_first_search(g, sources, sources + 1, Q, vis, color);
^
/usr/include/boost/graph/breadth_first_search.hpp:257:7: note: in instantiation of function template specialization
  'boost::breadth_first_search<boost::filtered_graph<boost::adjacency_list<boost::vecS, boost::vecS,
  boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::keep_all,
  VertexSetFilter>, boost::queue<unsigned long, std::deque<unsigned long, std::allocator<unsigned long> > >,
  MyVisitor<unsigned long, boost::filtered_graph<boost::adjacency_list<boost::vecS, boost::vecS,
  boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::keep_all,
  VertexSetFilter> >, boost::two_bit_color_map<boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned
  long> > >' requested here
  breadth_first_search
  ^
/usr/include/boost/graph/breadth_first_search.hpp:312:9: note: in instantiation of function template specialization
  'boost::detail::bfs_helper<boost::filtered_graph<boost::adjacency_list<boost::vecS, boost::vecS,
  boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::keep_all,
  VertexSetFilter>, boost::two_bit_color_map<boost::vec_adj_list_vertex_id_map<boost::no_property, unsigned long>
  >, MyVisitor<unsigned long, boost::filtered_graph<boost::adjacency_list<boost::vecS, boost::vecS,
  boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::keep_all,
  VertexSetFilter> >, MyVisitor<unsigned long, boost::filtered_graph<boost::adjacency_list<boost::vecS,
  boost::vecS, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>,
  boost::keep_all, VertexSetFilter> >, boost::graph_visitor_t, boost::no_property>' requested here
    bfs_helper
    ^
/usr/include/boost/graph/breadth_first_search.hpp:344:30: note: in instantiation of function template specialization
  'boost::detail::bfs_dispatch<boost::param_not_found>::apply<boost::filtered_graph<boost::adjacency_list<boost::vecS,
  boost::vecS, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>,
  boost::keep_all, VertexSetFilter>, MyVisitor<unsigned long,
  boost::filtered_graph<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property,
  boost::no_property, boost::no_property, boost::listS>, boost::keep_all, VertexSetFilter> >,
  boost::graph_visitor_t, boost::no_property>' requested here
detail::bfs_dispatch<C>::apply(ng, s, params,
            ^
bfs.cc:65:12: note: in instantiation of function template specialization
  'boost::breadth_first_search<boost::filtered_graph<boost::adjacency_list<boost::vecS, boost::vecS,
  boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::keep_all,
  VertexSetFilter>, MyVisitor<unsigned long, boost::filtered_graph<boost::adjacency_list<boost::vecS,
  boost::vecS, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>,
  boost::keep_all, VertexSetFilter> >, boost::graph_visitor_t, boost::no_property>' requested here
boost::breadth_first_search(filteredG, v, boost::visitor(vis));
      ^
/usr/include/boost/graph/filtered_graph.hpp:79:23: note: member is declared here
  VertexPredicate m_vertex_pred;
          ^
bfs.cc:22:7: note: 'VertexSetFilter' declared here
class VertexSetFilter
  ^
2 errors generated.

Answer 1

错误一开始就告诉您，VertexSetFilter 必须有默认构造函数。此外，documentation on boost::filtered_graph阅读:

Also, the predicate must be Default Constructible [1].
[1] The reason for requiring Default Constructible in the EdgePredicate and VertexPredicate types is that these predicates are stored by-value (for performance reasons) in the filter iterator adaptor, and iterators are required to be Default Constructible by the C++ Standard.

因此，您只需为 VertexSetFilter 添加默认构造函数，例如

VertexSetFilter() = default;

这也在上面链接访问的示例中完成。