如何在命名图上使用提升图算法？

Question

我正在尝试编译一个简单的代码示例，它使用 BFS 遍历 命名图 并回答我的 .

我认为主要问题是为算法提供正确的索引映射。

代码（没有命名图特征样板）如下：

Graph g;

// add a few named vertices
auto v1 = add_vertex(1111, g);
auto v2 = add_vertex(2222, g);  
auto v3 = add_vertex(3333, g);

// add 2 edges
add_edge(1111, 2222, g);
add_edge(2222, 3333, g);

simple_bfs_visitor bfs_visitor_instance{};
//boost::breadth_first_search(g, v1, boost::visitor(bfs_visitor_instance)); // fails to compile
//boost::breadth_first_search(g, v1, boost::visitor(bfs_visitor_instance).vertex_index_map(boost::get(&Vertex::id, g))); // compiles but fails with exception

有人可以举例说明如何在提供的图上调用图算法吗？

我将感谢对所涉及概念的解释，因为我无法理解属性地图/索引地图等各种术语如何发挥作用以及它们在使用命名图形时有何不同。

这是完整的（不工作的）代码：

struct Vertex
{
    size_t      id;
    std::string other = "default-constructed";
};
// traits
template <> struct boost::graph::internal_vertex_name<Vertex> {
    struct type {
        using result_type = size_t;
        result_type const& operator()(Vertex const& bundle) const {
            return bundle.id;
        }
    };
};

template <> struct boost::graph::internal_vertex_constructor<Vertex> {
    struct type {
    private:
        using extractor = typename internal_vertex_name<Vertex>::type;
        using name_t = std::decay_t<typename extractor::result_type>;

    public:
        using argument_type = name_t;
        using result_type = Vertex;

        result_type operator()(const name_t& id) const { return { id }; }
    };
};

using Graph = boost::adjacency_list<boost::vecS, boost::listS, boost::directedS, Vertex>;

class simple_bfs_visitor : public boost::default_bfs_visitor
{
public:
    void discover_vertex(const Graph::vertex_descriptor& v, const Graph& g) const
    {
        std::cout << "hi from bfs" << '\n';
    }
};

void Func()
{
    Graph g;

    // add a few named vertices
    auto v1 = add_vertex(1111, g);
    auto v2 = add_vertex(2222, g);  
    auto v3 = add_vertex(3333, g);

    // add 2 edges
    add_edge(1111, 2222, g);
    add_edge(2222, 3333, g);

    simple_bfs_visitor bfs_visitor_instance{};
    //boost::breadth_first_search(g, v1, boost::visitor(bfs_visitor_instance)); // fails to compile
    //boost::breadth_first_search(g, v1, boost::visitor(bfs_visitor_instance).vertex_index_map(boost::get(&Vertex::id, g))); // fails with exception
}

Answer 1

前几天我警告过你：

我选择listS是因为。然而，这意味着没有隐含的 vertex_index_t 属性.
如果你做到了vecS，那么你将
在PS。我记得。这很好地解释了为什么如果你像在你的例子中那样强制它（get(&Vertex::id, g)）它不会顺利。

检查一些东西

在 3. 下，让我们检查 breadth_first_search 的文档，是的，它明确指出：

IN: vertex_index_map(VertexIndexMap i_map)

This maps each vertex to an integer in the range [0, num_vertices(g)).

所以，不要做你想做的事！它将导致 Undefined Behaviour。但请继续阅读：

This parameter is only necessary when the default color property map is used. The type VertexIndexMap must be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.

Default: get(vertex_index, g). Note: if you use this default, make sure your graph has an internal vertex_index property. For example, adjacency_list with VertexList=listS does not have an internal vertex_index property.

不幸的消息：你所有的问题都被准确地指出来了。

好消息：我们有 3 个选项来修复它：

传递自己的色图
传递一个外部顶点索引
使adjacency_list再次使用vecS，但避免重载冲突

1。传递你自己的颜色图

您可以查看文档了解要求。最简单的满足方式：

std::map<V, boost::default_color_type> colors;
auto color_map = boost::make_assoc_property_map(colors);

现在你称它为：

breadth_first_search(                    //
    g, v1,                               //
    boost::visitor(bfs_visitor_instance) //
        .vertex_color_map(color_map)     //
);

2。传递你自己的顶点索引

相反，您可以提供一个索引。非常相似：

std::map<V, int> index;
auto index_map = boost::make_assoc_property_map(index);

但是这次你必须确保地图是按照预期填充的！

// important: remember to make the data up-to-date!
for (auto v : boost::make_iterator_range(vertices(g)))
    index_map[v] = index.size();

我们再次称呼它：

breadth_first_search(                    //
    g, v1,                               //
    boost::visitor(bfs_visitor_instance) //
        .vertex_index_map(index_map)     //
);

2b。间奏曲

当然，您可以同时提供两者，但这不是必需的。如果你多次调用 BFS 或者想使用你自己的数据结构（比如 flat_map<V, color, small_vector<V, N> > 这样你就可以避免那里的所有分配），这可能是一种优化：

breadth_first_search(                    //
    g, v1,                               //
    boost::visitor(bfs_visitor_instance) //
        .vertex_color_map(color_map)     //
        .vertex_index_map(index_map)     //
);

3。使用 VecS...

这对描述符的稳定性有影响，但至少让我们展示一下。我建议对 id 使用包装器类型：

struct Id {
    size_t _val;
    Id(size_t v = {}) : _val(v) {}

    // relay some common operations
    friend std::ostream& operator<<(std::ostream& os, Id const& id) { return os << "Id:" << id._val; }
    friend size_t hash_value(Id const& id) { return boost::hash_value(id._val); }
    auto operator<=>(Id const&) const = default;
};

我们需要 hash/equality 来查找名称，operator<< 来打印图表。当然，实现是微不足道的。

有了它，一切都“正常工作”，因为 Graph 有一个内部隐式 vertex_index:

boost::breadth_first_search(g, v1, boost::visitor(bfs_visitor_instance));

以上所有的实时列表

Live On Coliru

编译两次，定义或不定义USE_VCES：

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>

#ifndef USE_VECS
    using VertexS = boost::listS;
    using Id      = size_t;
#else
    using VertexS = boost::vecS;
    struct Id {
        size_t _val;
        Id(size_t v = {}) : _val(v) {}

        // relay some common operations
        friend std::ostream& operator<<(std::ostream& os, Id const& id) { return os << "Id:" << id._val; }
        friend size_t hash_value(Id const& id) { return boost::hash_value(id._val); }
        auto operator<=>(Id const&) const = default;
    };
#endif

struct Vertex {
    Id id;
    std::string other = "default-constructed";
};

using Graph =
    boost::adjacency_list<boost::vecS, VertexS, boost::directedS, Vertex>;

// traits
template <> struct boost::graph::internal_vertex_name<Vertex> {
    struct type {
        using result_type = decltype(Vertex::id);
        result_type const& operator()(Vertex const& bundle) const {
            return bundle.id;
        }
    };
};

template <> struct boost::graph::internal_vertex_constructor<Vertex> {
    struct type {
      private:
        using extractor = typename internal_vertex_name<Vertex>::type;
        using name_t    = std::decay_t<typename extractor::result_type>;

      public:
        using argument_type = name_t;
        using result_type = Vertex;

        result_type operator()(const name_t& id) const { return {id}; }
    };
};

using V = Graph::vertex_descriptor;

struct simple_bfs_visitor : boost::default_bfs_visitor {
    void discover_vertex(V, const Graph&) const {
        std::cout << "hi from bfs" << '\n';
    }
};

int main() {
    Graph g;

    V v1 = add_vertex(1111, g);
    /*V v2 =*/ add_vertex(2222, g);
    /*V v3 =*/ add_vertex(3333, g);

    add_edge(Id{1111}, Id{2222}, g);
    add_edge(Id{2222}, Id{3333}, g);

    print_graph(g, get(&Vertex::id, g), std::cout << "---\n");
    print_graph(g, get(&Vertex::other, g), std::cout << "---\n");

    simple_bfs_visitor bfs_visitor_instance{};

    // 1. bring your own colors
    std::map<V, boost::default_color_type> colors;
    auto color_map = boost::make_assoc_property_map(colors);

    breadth_first_search(                    //
        g, v1,                               //
        boost::visitor(bfs_visitor_instance) //
            .vertex_color_map(color_map)     //
    );

    // 2. bring your own index
    std::map<V, int> index;
    auto index_map = boost::make_assoc_property_map(index);

    // important: remember to make the data up-to-date!
    for (auto v : boost::make_iterator_range(vertices(g)))
        index_map[v] = index.size();

    breadth_first_search(                    //
        g, v1,                               //
        boost::visitor(bfs_visitor_instance) //
            .vertex_index_map(index_map)     //
    );

    // 2b. bring your own
    breadth_first_search(                    //
        g, v1,                               //
        boost::visitor(bfs_visitor_instance) //
            .vertex_color_map(color_map)     //
            .vertex_index_map(index_map)     //
    );

#ifdef USE_VECS
    // 3. use vecS but not `size_t` as the Id:
    boost::breadth_first_search(g, v1, boost::visitor(bfs_visitor_instance));
#endif
}

编译并运行:

g++ -std=c++20 -O2 -Wall -pedantic -pthread main.cpp -DUSE_VECS -o vecS.exe
g++ -std=c++20 -O2 -Wall -pedantic -pthread main.cpp -o listS.exe
set -x
./vecS.exe
./listS.exe

版画

./vecS.exe
./listS.exe
+ ./vecS.exe
---
Id:1111 --> Id:2222 
Id:2222 --> Id:3333 
Id:3333 --> 
---
default-constructed --> default-constructed 
default-constructed --> default-constructed 
default-constructed --> 
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
+ ./listS.exe
---
1111 --> 2222 
2222 --> 3333 
3333 --> 
---
default-constructed --> default-constructed 
default-constructed --> default-constructed 
default-constructed --> 
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs
hi from bfs

如何在命名图上使用提升图算法？

How to use boost graph algorithm on a named graph?

c++

boost

breadth-first-search

boost-graph

检查一些东西

IN: `vertex_index_map(VertexIndexMap i_map)`

1。传递你自己的颜色图

2。传递你自己的顶点索引

2b。间奏曲

3。使用 VecS...

以上所有的实时列表

如何在命名图上使用提升图算法？

How to use boost graph algorithm on a named graph?

c++

boost

breadth-first-search

boost-graph

检查一些东西

IN: vertex_index_map(VertexIndexMap i_map)

1。传递你自己的颜色图

2。传递你自己的顶点索引

2b。间奏曲

3。使用 VecS...

以上所有的实时列表

IN: `vertex_index_map(VertexIndexMap i_map)`