c++ - boost::get with boost::filtered_graph on adjacency_list with netsed 属性

Question

我为 boost::adjacency_list 写了一个小包装器:

    template <typename T>
    using VertexWithIndexProperty =            
          boost::property<boost::vertex_index_t, int, T>;

    template <typename VertexProperty, typename EdgeProperty = 
                                    boost::no_property>
    class MutableGraph  : public boost::adjacency_list< boost::setS, 
                             boost::listS, boost::undirectedS, 
                             VertexWithIndexProperty<VertexProperty>, EdgeProperty> {
    public:
         using BoostBase =
          boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS,
                                VertexWithIndexProperty<VertexProperty>,
                                EdgeProperty>;
      MutableGraph() {}
      MutableGraph(std::size_t n) : BoostBase(n) {}
      MutableGraph(const MutableGraph &rhs) : BoostBase(rhs) {}
      MutableGraph &operator=(const MutableGraph &rhs) {
        static_cast<BoostBase *>(this)->operator=(rhs);
        return *this;
      }
    };

然后我按如下方式使用它:我在集合中收集一些 vertex_descriptors 以创建 boost::filtered_graph:`

using Graph = MutableGraph<boost::property<vertex_color_t, int>>;
Graph g;

std::set<int> C, H; //vertex_descriptors I collect

...

auto vertex_index_map = get(vertex_index, g);

std::function<bool(vertex_descriptor)> vertexes_filter =
      [&vertex_index_map, &C, &H](vertex_descriptor v) {

        auto index = vertex_index_map[v];
        return C.find(index) != C.end() || H.find(index) != H.end();
      };

   boost::filtered_graph<Graph, boost::keep_all, decltype(crown_vertexes_filter)>
           auxilary(g, boost::keep_all(), crown_vertexes_filter);

一切正常，但是当我尝试获取顶点的任何 property_map 时，例如:`

auto auxilary_vertex_index_map
          = get(boost::vertex_index, auxilary);

我收到以下错误:

could not convert

    boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, 
boost::listS, boost::undirectedS, 
boost::property<boost::vertex_index_t, int, 
boost::property<boost::vertex_color_t, int> >, 
boost::no_property, boost::no_property, boost::listS>, int, 
int&, boost::vertex_index_t>

to 

 boost::adj_list_vertex_property_map<MutableGraph<
 boost::property<boost::vertex_color_t, int> >,
 int, 
 int&,
 boost::vertex_index_t>

我得到这个错误

template <typename G, typename EP, typename VP, typename Property>
  typename property_map<G, Property>::type
  get(Property p, filtered_graph<G, EP, VP>& g)
  {
    return get(p, const_cast<G&>(g.m_g));
  }

在 filtered_graph.hpp 中。

我不明白为什么会这样，是因为我的包装器还是因为我决定使用嵌套属性而不是捆绑属性。

提前致谢!

Answer 1

嵌套属性被称为“内部属性”。他们不是你的问题。

相反，您的问题出在 VertexContainerSelector 参数 ( boost::listS ) 上。它导致 vertex_descriptor类型为

• 不是整数(现在是不透明类型)
• 不作为分解顶点索引的两倍

您已经知道这一点，这就是您添加一个属性作为顶点索引图的原因。但是，您没有预料到的是，它生成了 vertex_index 的结果类型。属性映射 ( boost::property_map<Graph, vertex_index_t>::type ) 不同，因此 filtered_graph 中的转发包装器不再符合要求:

  template <typename G, typename EP, typename VP, typename Property>
  typename property_map<G, Property>::type
  get(Property p, filtered_graph<G, EP, VP>& g)
  {
    return get(p, const_cast<G&>(g.m_g));
  }

如果您负担得起，只需切换到 vecS ，我会去的。否则，请仔细考虑您的要求和影响。值得注意的是，您的 VertexContainerSelector选择listS结果 vertex_descriptor具有引用和迭代器稳定性。任何vertex_descriptor来自 filtered_graph 的数据应该对主图有效，反之亦然。为什么不只保留相同的 map :

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graph_utility.hpp> // print_graph

template <typename T> using AddIndex = boost::property<boost::vertex_index_t, int, T>;

template <
    typename VertexProperty,
    typename EdgeProperty = boost::no_property, 
    typename Base = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, AddIndex<VertexProperty>, EdgeProperty> >
struct MutableGraph : Base {
    using BoostBase = Base;

    MutableGraph(std::size_t n = 0) : BoostBase(n) {}
    using BoostBase::operator=;
};

int main() {
    using Graph = MutableGraph<boost::property<boost::vertex_color_t, int> >;
    using vertex_descriptor = Graph::vertex_descriptor;
    Graph g;
    auto a = add_vertex({1, 0}, g);
    auto b = add_vertex({2, 0}, g);
    auto c = add_vertex({3, 0}, g);
    auto d = add_vertex({4, 0}, g);
    add_edge(a, b, g);
    add_edge(a, c, g);
    add_edge(b, d, g);

    std::set<int> C{1,2}, H{/*3,*/4}; // vertex_descriptors I collect
    auto id = get(boost::vertex_index, g);
    std::function<bool(vertex_descriptor)> vertexes_filter = [id, &C, &H](vertex_descriptor v) {
        auto index = id[v];
        return C.count(index) || H.count(index);
    };

    boost::filtered_graph<Graph, boost::keep_all, decltype(vertexes_filter)> auxilary(g, boost::keep_all(), vertexes_filter);

    auto aux_id = id;
    print_graph(g,        id,     std::cout << "\n---- Original\n");
    print_graph(auxilary, aux_id, std::cout << "\n---- Filtered\n");
}

打印:

---- Original
1 <--> 2 3 
2 <--> 1 4 
3 <--> 1 
4 <--> 2 

---- Filtered
1 <--> 2 
2 <--> 1 4 
4 <--> 2 

这正是您想要的。

边注

注意代码中的简化。你的MutableGraph类可以写成:

template <
    typename VertexProperty,
    typename EdgeProperty = boost::no_property, 
    typename Base = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, AddIndex<VertexProperty>, EdgeProperty> >
struct MutableGraph : Base {
    using BoostBase = Base;

    MutableGraph(std::size_t n = 0) : BoostBase(n) {}
    using BoostBase::operator=;
};

虽然在这个例子中甚至可以简单地省略这两个成员(编译器仍会正确生成 operator=)。

¹ 过滤后的可能除外...

奖金

根据评论更新:您可以通过专门化 boost::property_map<> 来“自动化”类型转发特点:

namespace boost {
    // overriding the typedef to take the types from the BoostBase instead:
    template <typename Tag, typename... Args>
        struct property_map<MyGraph<Args...>, Tag> : property_map<typename MyGraph<Args...>::BoostBase, Tag> {
        };
}

就是这样。现在您可以在一个不知道它正在处理哪种类型的图形的函数中进行打印:

template <typename WhateverGraph>
void some_naive_user_function(WhateverGraph const& g, std::ostream& os) {
    // we don't know whether WhateverGraph is filtered or not, but we don't care
    print_graph(g, get(boost::vertex_index, g), os);
}

get(boost::vertex_index, g)由于特化才有效:

boost::filtered_graph<Graph, boost::keep_all, decltype(vertexes_filter)> auxilary(g, boost::keep_all(), vertexes_filter);

some_naive_user_function(g,        std::cout << "\n---- Origina (via naive user function)\n");
some_naive_user_function(auxilary, std::cout << "\n---- Filtered (via naive user function)\n");

查看 Live On Coliru