Boost 图自定义索引使用 Dijkstra

问题描述 投票：0回答：1

我正在尝试通过 Boost 图库创建一个图，它具有自定义索引（删除顶点时稳定），

我复制了此处提出的解决方案来创建对我来说非常有效的图如何配置 boost::graph 以使用我自己的（稳定）顶点索引？

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


using namespace boost;

struct Vertex {
    int id;
};

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

// traits
template <> struct boost::graph::internal_vertex_name<Vertex> {
    struct type {
        using result_type = int;
        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}; }
    };
};
typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;


Graph g;

add_vertex(1, g);
add_vertex(2, g);
add_vertex(5, g);
add_vertex(6, g);
add_vertex(7, g);
add_edge(1, 5, 1, g);
add_edge(2, 6, 1, g);
add_edge(2, 7, 2, g);
add_edge(5, 2, 7, g);
add_edge(5, 6, 3, g);
add_edge(6, 7, 1, g);
add_edge(7, 1, 1, g);
add_edge(7, 2, 1, g);


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

但是当我尝试在这张图上使用 Dijkstra 时，乐趣就开始了。 在普通图表上，我会这样使用 Dijkstra

std::vector<vertex_descriptor> p(num_vertices(g));
std::vector<int> d(num_vertices(g));
vertex_descriptor source_idx = vertex(1, g);
dijkstra_shortest_paths(g, source_idx,
                        predecessor_map(boost::make_iterator_property_map(
                                            p.begin(), get(vertex_index, g)))
                            .distance_map(boost::make_iterator_property_map(
                                d.begin(), get(vertex_index, g))));

但是现在我正在更改索引，其中大部分都不起作用，主要是

get(boost::vertex_index, g)
，这会提高
In template: cannot form a reference to 'void'
和
No matching function for call to 'get'

我不知道我需要如何改变它，尝试使用 

get(&Vertex::id, g)
代替，但我明白了 
No matching function for call to 'dijkstra_shortest_paths'

预先感谢您的帮助！

c++ boost-graph
1个回答
0
投票

您似乎在这里混淆了 3 个概念：

  1. 顶点名称
  2. 顶点描述符（和顶点迭代器，它们的语义将它们与此项目符号分组）
  3. 顶点索引

ad 1. 这些名称是您通过 

internal_vertex_name
特质实现的。它们提供了从应用程序域标识符（“名称”，示例中的 
Vertex::id
）到顶点描述符的便捷映射。在数据库术语中，这可以被认为是顶点的“查找索引”，但它不是 BGL 所说的顶点索引。

ad 2. 描述符具有可以通过选择顶点容器选择器来更改的语义。在您的示例中，您确实选择了 

boost::listS
，这确实使描述符和迭代器在突变中保持稳定（删除的顶点除外）。

ad 3. 顶点索引是所有顶点描述符到积分范围 

[0, N)
(N == num_vertices(g)) 的特定唯一映射，一些算法假设这样，因此无论选择何种图模型，它们都可以有效实现。将其视为“对顶点进行编号的一致方式”。对于某些 VertexContainer 选择器（即 
boost::vecS
），索引很简单，Boost 知道如何隐式推导 
vertex_index_t
属性映射以在算法中使用。

问题

在您的代码中，问题是由于 

vertex_index_t
容器选择器，您没有隐式 
listS
属性映射。

到目前为止，最简单的“解决方案”是使用 

vecS
作为您的名称属性，已经可以让您获得稳定的标识 [1]：

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_utility.hpp>
#include <fmt/ranges.h>
#include <ranges>
using std::views::transform;

struct Vertex {
    int id;
};

// traits
template <> struct boost::graph::internal_vertex_name<Vertex> {
    struct type {
        using result_type = int;
        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()(name_t const& id) const { return {id}; }
    };
};

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Vertex,
                                    boost::property<boost::edge_weight_t, int>>;

int main() {
    using V = Graph::vertex_descriptor;
    Graph g;

    add_edge(100, 500, 1, g);
    add_edge(200, 600, 1, g);
    add_edge(200, 700, 2, g);
    add_edge(500, 200, 7, g);
    add_edge(500, 600, 3, g);
    add_edge(600, 700, 1, g);
    add_edge(700, 100, 1, g);
    add_edge(700, 200, 1, g);
    assert(num_vertices(g) == 5);

    auto name = get(&Vertex::id, g);
    print_graph(g, name);

    std::vector<V>   p(num_vertices(g));
    std::vector<int> d(num_vertices(g));
    V                source_idx = vertex(1, g);
    dijkstra_shortest_paths(g, source_idx,                   //
                            boost::predecessor_map(p.data()) //
                                .distance_map(d.data()));

    fmt::print("predecessors {} distances {}\n", //
               p | transform([name](V v) { return name[v]; }), d);
}

哪个打印Live On Coliru：

g++ -std=c++20 -O2 -Wall -pedantic -pthread main.cpp -lfmt && ./a.out    
500 --> 200 600     
100 --> 500     
600 --> 700     
200 --> 600 700     
700 --> 100 200     
predecessors [100, 100, 500, 700, 600] distances [1, 0, 4, 6, 5]

注意 如何显着简化图形创建。 

source_idx
是一个用词不当（它不是 索引，而是描述符）。另外，不要通过某个序数神奇地选择一个顶点到内部存储的顶点序列中，而是考虑通过您的名称属性进行寻址：

V source = find_vertex(500, g).value();
dijkstra_shortest_paths(g, source,                       //
                        boost::predecessor_map(p.data()) //
                            .distance_map(d.data()));

手册
vertex_index_t
索引

如果您确实需要存储在突变之间保持有效的描述符，则需要提供人工外部映射：

std::map<V, int> manual_index;
for (auto v : boost::make_iterator_range(vertices(g)))
    manual_index.emplace(v, manual_index.size());

然后您可以使用命名参数来提供：

.vertex_index_map(boost::make_assoc_property_map(manual_index))

但是，由于顶点不是有序的，因此您的前驱/距离映射也需要间接：

V source = find_vertex(500, g).value();

auto vidx = boost::make_assoc_property_map(manual_index);
dijkstra_shortest_paths( //
    g, source,
    boost::predecessor_map(make_safe_iterator_property_map(p.data(), p.size(), vidx))
        .distance_map(make_safe_iterator_property_map(d.data(), d.size(), vidx))
        .vertex_index_map(vidx));

解释前驱映射现在需要通过反向查找

manual_index
来解释前驱向量的索引...也许按照这个速度，一路制作实际的关联属性映射会更容易：

住在Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_utility.hpp>
#include <fmt/ranges.h>
#include <ranges>
using std::views::transform;

struct Vertex {
    int id;
};

// traits
template <> struct boost::graph::internal_vertex_name<Vertex> {
    struct type {
        using result_type = int;
        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()(name_t const& id) const { return {id}; }
    };
};

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

int main() {
    using V = Graph::vertex_descriptor;
    Graph g;

    add_edge(100, 500, 1, g);
    add_edge(200, 600, 1, g);
    add_edge(200, 700, 2, g);
    add_edge(500, 200, 7, g);
    add_edge(500, 600, 3, g);
    add_edge(600, 700, 1, g);
    add_edge(700, 100, 1, g);
    add_edge(700, 200, 1, g);
    assert(num_vertices(g) == 5);

    auto name = get(&Vertex::id, g);
    print_graph(g, name);

    std::map<V, int> manual_index;
    std::map<V, V>   p;
    std::map<V, int> d;
    for (auto v : boost::make_iterator_range(vertices(g)))
        manual_index.emplace(v, manual_index.size());

    V source = find_vertex(500, g).value();

    dijkstra_shortest_paths( //
        g, source,
        boost::predecessor_map(boost::make_assoc_property_map(p))
            .distance_map(boost::make_assoc_property_map(d))
            .vertex_index_map(boost::make_assoc_property_map(manual_index)));

    fmt::print("predecessors {}\ndistances {}\n", //
               p | transform([name](auto p) { return std::pair(name[p.first], name[p.second]); }),
               d | transform([name](auto p) { return std::pair(name[p.first], p.second); }));
}

印刷

500 --> 200 600 
100 --> 500 
600 --> 700 
200 --> 600 700 
700 --> 100 200 
predecessors [(500, 500), (100, 700), (600, 500), (200, 700), (700, 600)]
distances [(500, 0), (100, 5), (600, 3), (200, 5), (700, 4)]

[1] 具有 O(log n) 查找

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.