c++ - 具有自定义顶点属性的图的 boost 支配树

Question

我正在尝试使用 boost::lengauer_tarjan_dominator_tree带有 custom vertex properties 的图表，但连一个简单的例子都无法编译:

#include <vector>
#include <iterator>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dominator_tree.hpp>
#include <boost/property_map/property_map.hpp> 

struct GraphNode
{
    explicit GraphNode(unsigned i) : index {i} {}
    unsigned index;
};

using Graph = boost::adjacency_list<boost::listS, boost::listS, 
                            boost::bidirectionalS, GraphNode, boost::no_property>;

using Vertex = boost::graph_traits<Graph>::vertex_descriptor;

int main()
{
    Graph g {};

    const auto u = boost::add_vertex(GraphNode {0}, g);
    const auto v = boost::add_vertex(GraphNode {1}, g);
    const auto x = boost::add_vertex(GraphNode {2}, g);
    const auto y = boost::add_vertex(GraphNode {3}, g);
    const auto z = boost::add_vertex(GraphNode {4}, g);

    boost::add_edge(u, v, g);
    boost::add_edge(u, x, g);
    boost::add_edge(v, y, g);
    boost::add_edge(x, y, g);
    boost::add_edge(y, z, g);

    const auto index_map = boost::get(&GraphNode::index, g);

    std::vector<Vertex> dom_tree_pred_vector(boost::num_vertices(g),
                                             boost::graph_traits<Graph>::null_vertex());

    auto dom_tree_pred_map = boost::make_iterator_property_map(std::begin(dom_tree_pred_vector),
                                index_map);

    boost::lengauer_tarjan_dominator_tree(g, u, dom_tree_pred_map);
}

我尝试改编自 example文档中给出。

这是错误消息的一部分:

/usr/local/include/boost/graph/detail/adjacency_list.hpp:2544:33: error: cannot form a reference to 'void'
        typedef const value_type& const_reference;
                                ^
/usr/local/include/boost/graph/dominator_tree.hpp:355:31: error: no matching function for call to 'get'
    const IndexMap indexMap = get(vertex_index, g);

我还尝试使用该方法的第二种形式显式传入索引映射，但没有成功。我注意到这个方法接口(interface)似乎与其他图形方法有点不同，例如 depth_first_search ，其中 vertex_index_map 是一个命名参数。

是否可以将此方法与自定义顶点属性一起使用？

Answer 1

问题与以往一样，是使用 vecS 以外的东西作为顶点容器。您会丢失内置 vertex_index 属性，因此必须将其提供给 API。

遗憾的是，该算法不能很好地支持自定义顶点索引映射。您尝试使用 index_map 是正确的，但在内部算法仍然会查找 vertex_index_t 标记的属性。

我能看到这项工作的唯一两种方式是，

1. 手动执行 DFS 阶段(因为即使是 lengauer_tarjan* 的全参数重载也无法将正确的索引映射转发到 DFS)。然后您可以调用 lengauer_tarjan_dominator_tree_without_dfs 实现并获得结果。

2. 或者您可以告诉图书馆您的图表的索引图。

(最后，您可以接受命运并使用 vecS 作为顶点容器选择器。我怀疑这显然不是您想要的。)

演示

使用第二种方法，这可能是最优雅的。以下是要添加的特化/重载:

namespace boost {
    template <>
        struct property_map<Graph, vertex_index_t> {
            typedef typename property_map<Graph, size_t GraphNode::*>::type type;
            typedef typename property_map<Graph, size_t GraphNode::*>::const_type const_type;
        };

    static auto get(vertex_index_t, Graph& g)       { return get(&GraphNode::index, g); }
    static auto get(vertex_index_t, Graph const& g) { return get(&GraphNode::index, g); }
}

Live On Coliru

#include <vector>
#include <iterator>
#include <iostream>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dominator_tree.hpp>
#include <boost/property_map/property_map.hpp> 

struct GraphNode
{
    explicit GraphNode(size_t i) : index {i} {}
    size_t index;
};

using Graph = boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS, GraphNode, boost::no_property>;

namespace boost {
    template <>
        struct property_map<Graph, vertex_index_t> {
            typedef typename property_map<Graph, size_t GraphNode::*>::type type;
            typedef typename property_map<Graph, size_t GraphNode::*>::const_type const_type;
        };

    static property_map<Graph, vertex_index_t>::type       get(vertex_index_t, Graph& g)       { return get(&GraphNode::index, g); }
    static property_map<Graph, vertex_index_t>::const_type get(vertex_index_t, Graph const& g) { return get(&GraphNode::index, g); }
}

using Vertex = boost::graph_traits<Graph>::vertex_descriptor;

int main()
{
    Graph g {};

    const auto u = boost::add_vertex(GraphNode {0}, g);
    const auto v = boost::add_vertex(GraphNode {1}, g);
    const auto x = boost::add_vertex(GraphNode {2}, g);
    const auto y = boost::add_vertex(GraphNode {3}, g);
    const auto z = boost::add_vertex(GraphNode {4}, g);

    boost::add_edge(u, v, g);
    boost::add_edge(u, x, g);
    boost::add_edge(v, y, g);
    boost::add_edge(x, y, g);
    boost::add_edge(y, z, g);

    std::vector<Vertex> dom_pred(num_vertices(g), boost::graph_traits<Graph>::null_vertex());

    auto index_map = boost::get(&GraphNode::index, g); // equivalent to vertex_index_t now
    auto dom_tree_pred_map (boost::make_iterator_property_map(std::begin(dom_pred), index_map));

    // Run main algorithm
    boost::lengauer_tarjan_dominator_tree(g, u, dom_tree_pred_map);

    std::cout << "Result: ";
    for (auto v : dom_pred) {
        if (v == boost::graph_traits<Graph>::null_vertex())
            std::cout << "(root) "; 
        else
            std::cout << g[v].index << " "; 
    }
}

打印

Result: (root) 0 0 0 3