Boost::graph中的Dijkstra算法和自定义对象和属性

Question

我希望使用boost的dijkstra算法（因为我在程序的其他部分中使用了boost）。我的问题是如何将自定义对象（我认为它们被称为property）添加到adjacency_list中。

基本上，我有一个自定义边缘类，它维护与边缘和通过它连接的顶点相关的所有信息。我想将我的自定义数据对象存储在需要adjaceny_list的边缘属性中。

我已经成功地实现了boost提供的玩具示例。我尝试使用自定义属性，但没有成功（boost示例，boost属性）。如果只是将我的VEdge数据结构封装在一个结构体中，我可以接受，我只需要能够检索它。但是我无法弄清楚如何将我的自定义数据结构包含到boost adjaceny_list结构中。

在我的情况下，我有以下程序：

Main.cpp:

#include <iostream>
#include <fstream>
#include "dijkstra.h"
#include <vector>

int
main(int, char *[])
{
  // Generate the vector of edges from elsewhere in the program
  std::vector<VEdge*> edges; //someclass.get_edges();

  td* test = new td(edges);
  test->run_d();

  test->print_path();

  return EXIT_SUCCESS;
}

Dijkstra.cpp:

#include <iostream>
#include <fstream>
#include "dijkstra.h"

using namespace boost;

td::td() {
    kNumArcs = sizeof(kEdgeArray) / sizeof(Edge);
    kNumNodes = 5;
}

td::td(std::vector<VEdge*> edges) {
    // add edges to the edge property here
    for(VEdge* e : edges) {
        // for each edge, add to the kEdgeArray variable in some way
        // The boost example forces the input to be an array of edge_property type.  
        // So here is where I will convert my raw VEdge data structure to 
        // the custom edge_property that I am struggling to understand how to create.
    }
    kNumArcs = sizeof(kEdgeArray) / sizeof(Edge);
    kNumNodes = 5;
}

void td::run_d() {
    kGraph = graph_t(kEdgeArray, kEdgeArray + kNumArcs, kWeights, kNumNodes);

    kWeightMap = get(edge_weight, kGraph);
    kP = std::vector<vertex_descriptor >(num_vertices(kGraph));
    kD = std::vector<int>(num_vertices(kGraph));
    kS = vertex(A, kGraph);

    dijkstra_shortest_paths(kGraph, kS,
            predecessor_map(boost::make_iterator_property_map(kP.begin(), get(boost::vertex_index, kGraph))).
                    distance_map(boost::make_iterator_property_map(kD.begin(), get(boost::vertex_index, kGraph))));
}

void td::print_path() {
    std::cout << "distances and parents:" << std::endl;
    graph_traits < graph_t >::vertex_iterator vi, vend;
    for (boost::tie(vi, vend) = vertices(kGraph); vi != vend; ++vi) {
        std::cout << "distance(" << kName[*vi] << ") = " << kD[*vi] << ", ";
        std::cout << "parent(" << kName[*vi] << ") = " << kName[kP[*vi]] << std::
        endl;
    }
}

void td::generate_dot_file() {
    std::cout << std::endl;

    std::ofstream dot_file("figs/dijkstra-eg.dot");

    dot_file << "digraph D {\n"
            << "  rankdir=LR\n"
            << "  size=\"4,3\"\n"
            << "  ratio=\"fill\"\n"
            << "  edge[style=\"bold\"]\n" << "  node[shape=\"circle\"]\n";

    graph_traits < graph_t >::edge_iterator ei, ei_end;
    for (boost::tie(ei, ei_end) = edges(kGraph); ei != ei_end; ++ei) {
        graph_traits < graph_t >::edge_descriptor e = *ei;
        graph_traits < graph_t >::vertex_descriptor
                u = source(e, kGraph), v = target(e, kGraph);
        dot_file << kName[u] << " -> " << kName[v]
                << "[label=\"" << get(kWeightMap, e) << "\"";
        if (kP[v] == u)
            dot_file << ", color=\"black\"";
        else
            dot_file << ", color=\"grey\"";
        dot_file << "]";
    }
    dot_file << "}";
}

Dijkstra.h:

#ifndef _TEMPD_H_
#define _TEMPD_H_

#pragma once

#include <boost/config.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/property_map.hpp>

using namespace boost;

typedef adjacency_list < listS, vecS, directedS,
        no_property, property < edge_weight_t, int > > graph_t;
typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
typedef std::pair<int, int> Edge;

struct VEdge{
    // custom variables here
    VNode start;
    VNode end;
    int weight;
    int id;
    // other irrelevant data pertinent to my program that must be preserved
};

struct VNode {
    // custom variables here
    int x;
    int y;
    int id;
    // other irrelevant data pertinent to my program that must be preserved
}

enum nodes { A, B, C, D, E };

class td {
public:
    td();
    td(std::vector<VEdge*>);
    ~td();

    void run_d();

    void print_path();
    void generate_dot_file();
private:
    Edge kEdgeArray[9] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E),
            Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B)
    };
    char kName[5] = {'A','B','C','D','E'};
    int kWeights[9] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 };
    int kNumArcs;
    int kNumNodes;
    vertex_descriptor kS;
    graph_t kGraph;
    std::vector<int> kD;
    std::vector<vertex_descriptor> kP;
    property_map<graph_t, edge_weight_t>::type kWeightMap;
};
#endif

我知道我的示例有些牵强，但它传达了我想要实现的目标。我知道我需要一个自定义数据结构来处理发送到图形typedef中的edge_descriptor。

所以，我想修改我的Dijkstra.h文件，使其看起来像这样：

struct vertex_label_t {vertex_property_tag kind;};
struct edge_label_t {edge_property_tag kind;};

typedef property <vertex_custom_t, VNode*>,
    property <vertex_label_t, string>,
        property <vertex_root_t, ing> > > vertex_p;

typedef property <edge_custom_t, VEdge*>,
    property <edge_label_t, string > > edge_p;

typedef adjacency_list < listS, vecS, directedS,
        vertex_p, edge_p > graph_t;
typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;

- lilott8

---

你不可能说你完全没有提过“这个问题”。它是唯一的构造函数。你不是真的在暗示硬编码的演示边缘就是全部，对吧？此外，边缘和VEdge*元素之间没有任何相关信息，请详细阐述一下。也许可以删除无关的演示代码。 - sehe

当然，我们可以对此进行一些小题大做，但我不在意。如果我说错了话，我向您道歉。最终，我的问题涉及到添加自定义属性到边缘或顶点定义中，这是邻接列表typedef所需的。请参见我的第二段。我在尝试将我的结构/类/对象添加到自定义属性中，以定义邻接列表typedef的边缘/顶点时遇到了问题。没错，通过查看我提供的链接2和3，我知道我可以将自定义属性添加到我的邻接列表中。 - lilott8

你可以。那么问题是什么？我猜你的问题是如何连接这些点。你没有提供足够的信息。请注意，我可以编造一些东西，但如果不是你要找的，恐怕对你没有帮助。 - sehe

我记得这件事。当你查看我的回答的编辑历史记录时，你会发现大约75分钟前我开始打一个提到这个的答案。但是由于信息不足，我无法得出结论，所以我隐藏了这个答案。现在已经过去5分钟了。 - sehe

好的，那差不多是17分钟。解释和提供背景信息总是需要更多时间。 - sehe

Answer 1

好的。自从https://stackoverflow.com/questions/28889423/boost-adjacency-list-swap-errors-when-using-boost-dijkstra以来，您已经走了很长的路; 这个示例是自包含的，可以编译¹

我想我可以连接一些点，并希望这会有所帮助。

1. 使用 VEdge

对于最简单的选项，我会使用Bundled Properties，并将VEdge定义如下：

struct VEdge {
    int id;
    int source, target;
    double weight;
    // custom variables here
};

现在，我们将图形定义为：

using graph_t = boost::adjacency_list<boost::listS, boost::vecS, 
                    boost::directedS, boost::no_property, VEdge>;
using weight_map_t = boost::property_map<graph_t, double VEdge::*>::type;

正如您所看到的，权重图的类型有点复杂，详见捆绑属性的属性映射。您可以获取实际地图：

weight_map_t kWeightMap = boost::get(&VEdge::weight, kGraph);

现在，让我们在一个VEdge向量中重新创建你问题中的测试数据（A=0...E=4）：

std::vector<VEdge> edges {
    { 2100, 0, 2, 1 },
    { 2101, 1, 1, 2 },
    { 2102, 1, 3, 1 },
    { 2103, 1, 4, 2 },
    { 2104, 2, 1, 7 },
    { 2105, 2, 3, 3 },
    { 2106, 3, 4, 1 },
    { 2107, 4, 0, 1 },
    { 2108, 4, 1, 1 },
};

test_dijkstra test(edges);

构造函数有一点复杂，需要从边数中计算出顶点数。我使用了Boost Range算法来查找最大顶点节点ID并传递它：

test_dijkstra::test_dijkstra(std::vector<VEdge> edges) {
    using namespace boost::adaptors;

    size_t max_node;

    boost::partial_sort_copy(
            edges | transformed([](VEdge const &e) -> size_t { return std::max(e.source, e.target); }),
            boost::make_iterator_range(&max_node, &max_node + 1),
            std::greater<size_t>());

    auto e = edges | transformed([](VEdge const &ve) { return std::make_pair(ve.source, ve.target); });
    kGraph = graph_t(e.begin(), e.end(), edges.begin(), max_node + 1);
}

注意，edges.begin() 可以被传递：它不是“被强制为 edge_property 类型的数组”。迭代器也可以使用。

现在 dijkstra 需要获取 weight_map 参数，因为它不再是默认的内部属性。

void test_dijkstra::run_dijkstra() {

    weight_map_t kWeightMap = boost::get(&VEdge::weight, kGraph);

    vertex_descriptor kS    = vertex(0, kGraph);
    kP                      = std::vector<vertex_descriptor>(num_vertices(kGraph));
    kD                      = std::vector<int>(num_vertices(kGraph));

    dijkstra_shortest_paths(
        kGraph, kS,
            predecessor_map(boost::make_iterator_property_map(kP.begin(), get(boost::vertex_index, kGraph)))
        .distance_map(boost::make_iterator_property_map(kD.begin(), get(boost::vertex_index, kGraph)))
        .weight_map(kWeightMap));
}

对于这个示例，我将起始顶点A翻译为0。结果路径与原始路径完全相同²。

完整程序

在 Coliru 上运行

#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/adaptors.hpp>
#include <fstream>
#include <iostream>

struct VEdge {
    int id;
    int source, target;
    double weight;
    // custom variables here
};

class test_dijkstra {
    using graph_t           = boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, boost::no_property, VEdge>;
    using vertex_descriptor = boost::graph_traits<graph_t>::vertex_descriptor;
    using edge_descriptor   = boost::graph_traits<graph_t>::edge_descriptor;
    using weight_map_t      = boost::property_map<graph_t, double VEdge::*>::type;

  public:
    test_dijkstra(std::vector<VEdge>);
    ~test_dijkstra() {}

    void run_dijkstra();

    void print_path();
    void generate_dot_file();

  private:
    graph_t kGraph;

    std::vector<int> kD;
    std::vector<vertex_descriptor> kP;
};

test_dijkstra::test_dijkstra(std::vector<VEdge> edges) {
    using namespace boost::adaptors;

    size_t max_node;

    boost::partial_sort_copy(
            edges | transformed([](VEdge const &e) -> size_t { return std::max(e.source, e.target); }),
            boost::make_iterator_range(&max_node, &max_node + 1),
            std::greater<size_t>());

    auto e = edges | transformed([](VEdge const &ve) { return std::make_pair(ve.source, ve.target); });
    kGraph = graph_t(e.begin(), e.end(), edges.begin(), max_node + 1);
}

void test_dijkstra::run_dijkstra() {

    weight_map_t kWeightMap = boost::get(&VEdge::weight, kGraph);

    vertex_descriptor kS    = vertex(0, kGraph);
    kP                      = std::vector<vertex_descriptor>(num_vertices(kGraph));
    kD                      = std::vector<int>(num_vertices(kGraph));

    dijkstra_shortest_paths(
        kGraph, kS,
            predecessor_map(boost::make_iterator_property_map(kP.begin(), get(boost::vertex_index, kGraph)))
           .distance_map(boost::make_iterator_property_map(kD.begin(), get(boost::vertex_index, kGraph)))
           .weight_map(kWeightMap));
}

void test_dijkstra::print_path() {
    std::cout << "distances and parents:" << std::endl;
    boost::graph_traits<graph_t>::vertex_iterator vi, vend;

    for (boost::tie(vi, vend) = vertices(kGraph); vi != vend; ++vi) {
        std::cout << "distance(" << *vi << ") = " << kD[*vi] << ", ";
        std::cout << "parent(" << *vi << ") = " << kP[*vi] << "\n";
    }
}

void test_dijkstra::generate_dot_file() {
    weight_map_t kWeightMap = boost::get(&VEdge::weight, kGraph);

    std::ofstream dot_file("figs/dijkstra-eg.dot");

    dot_file << "digraph D {\n"
             << "  rankdir=LR\n"
             << "  size=\"4,3\"\n"
             << "  ratio=\"fill\"\n"
             << "  edge[style=\"bold\"]\n"
             << "  node[shape=\"circle\"]\n";

    boost::graph_traits<graph_t>::edge_iterator ei, ei_end;
    for (boost::tie(ei, ei_end) = edges(kGraph); ei != ei_end; ++ei) {
        boost::graph_traits<graph_t>::edge_descriptor e = *ei;
        boost::graph_traits<graph_t>::vertex_descriptor u = source(e, kGraph), v = target(e, kGraph);
        dot_file << u << " -> " << v << "[label=\"" << get(kWeightMap, e) << "\"";

        if (kP[v] == u)
            dot_file << ", color=\"black\"";
        else
            dot_file << ", color=\"grey\"";
        dot_file << "]";
    }
    dot_file << "}";
}

int main() {
    std::vector<VEdge> edges {
        { 2100, 0, 2, 1 },
        { 2101, 1, 1, 2 },
        { 2102, 1, 3, 1 },
        { 2103, 1, 4, 2 },
        { 2104, 2, 1, 7 },
        { 2105, 2, 3, 3 },
        { 2106, 3, 4, 1 },
        { 2107, 4, 0, 1 },
        { 2108, 4, 1, 1 },
    };

    test_dijkstra test(edges);
    test.run_dijkstra();

    test.print_path();
    test.generate_dot_file();
}

2. 使用VEdge*

如果您坚持在属性中使用指针，那么有几件事情会变得更加复杂：

• you'll need to manage the lifetime of the elements

• you can't use the double VEdge::* weight_map_t. Instead, you'll need to adapt a custom propertymap for this:

  auto kWeightMap = boost::make_transform_value_property_map(
              [](VEdge* ve) { return ve->weight; },
              boost::get(boost::edge_bundle, kGraph)
          );
  

• On the bright side, you can use the short-hand indexer notation to evaluate edge properties from an edge_descriptor as shown in generate_dot_file():

  dot_file << u << " -> " << v << "[label=\"" << kGraph[e]->weight << "\"";
  

• Of course this approach avoids copying the VEdge objects into the bundle, so it could be more efficient

不再拖延（也不必担心内存泄漏）：

在Coliru上运行

#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/adaptors.hpp>

#include <boost/property_map/transform_value_property_map.hpp>

#include <fstream>
#include <iostream>

struct VEdge {
    int id;
    int source, target;
    double weight;
    // custom variables here
};

class test_dijkstra {
    using graph_t           = boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, boost::no_property, VEdge*>;
    using vertex_descriptor = boost::graph_traits<graph_t>::vertex_descriptor;
    using edge_descriptor   = boost::graph_traits<graph_t>::edge_descriptor;

  public:
    test_dijkstra(std::vector<VEdge*>);
    ~test_dijkstra() {}

    void run_dijkstra();

    void print_path();
    void generate_dot_file();

  private:
    graph_t kGraph;

    std::vector<int> kD;
    std::vector<vertex_descriptor> kP;
};

test_dijkstra::test_dijkstra(std::vector<VEdge*> edges) {
    using namespace boost::adaptors;

    size_t max_node;

    boost::partial_sort_copy(
            edges | transformed([](VEdge const* e) -> size_t { return std::max(e->source, e->target); }),
            boost::make_iterator_range(&max_node, &max_node + 1),
            std::greater<size_t>());

    auto e = edges | transformed([](VEdge const *ve) { return std::make_pair(ve->source, ve->target); });
    kGraph = graph_t(e.begin(), e.end(), edges.begin(), max_node + 1);
}

void test_dijkstra::run_dijkstra() {

    auto kWeightMap = boost::make_transform_value_property_map(
                [](VEdge* ve) { return ve->weight; },
                boost::get(boost::edge_bundle, kGraph)
            );

    vertex_descriptor kS    = vertex(0, kGraph);
    kP                      = std::vector<vertex_descriptor>(num_vertices(kGraph));
    kD                      = std::vector<int>(num_vertices(kGraph));

    dijkstra_shortest_paths(
        kGraph, kS,
            predecessor_map(boost::make_iterator_property_map(kP.begin(), get(boost::vertex_index, kGraph)))
           .distance_map(boost::make_iterator_property_map(kD.begin(), get(boost::vertex_index, kGraph)))
           .weight_map(kWeightMap));
}

void test_dijkstra::print_path() {
    std::cout << "distances and parents:" << std::endl;
    boost::graph_traits<graph_t>::vertex_iterator vi, vend;

    for (boost::tie(vi, vend) = vertices(kGraph); vi != vend; ++vi) {
        std::cout << "distance(" << *vi << ") = " << kD[*vi] << ", ";
        std::cout << "parent(" << *vi << ") = " << kP[*vi] << "\n";
    }
}

void test_dijkstra::generate_dot_file() {

    std::ofstream dot_file("figs/dijkstra-eg.dot");

    dot_file << "digraph D {\n"
             << "  rankdir=LR\n"
             << "  size=\"4,3\"\n"
             << "  ratio=\"fill\"\n"
             << "  edge[style=\"bold\"]\n"
             << "  node[shape=\"circle\"]\n";

    boost::graph_traits<graph_t>::edge_iterator ei, ei_end;
    for (boost::tie(ei, ei_end) = edges(kGraph); ei != ei_end; ++ei) {
        boost::graph_traits<graph_t>::edge_descriptor e = *ei;
        boost::graph_traits<graph_t>::vertex_descriptor u = source(e, kGraph), v = target(e, kGraph);
        dot_file << u << " -> " << v << "[label=\"" << kGraph[e]->weight << "\"";

        if (kP[v] == u)
            dot_file << ", color=\"black\"";
        else
            dot_file << ", color=\"grey\"";
        dot_file << "]";
    }
    dot_file << "}";
}

int main() {
    std::vector<VEdge*> edges {
        new VEdge { 2100, 0, 2, 1 },
        new VEdge { 2101, 1, 1, 2 },
        new VEdge { 2102, 1, 3, 1 },
        new VEdge { 2103, 1, 4, 2 },
        new VEdge { 2104, 2, 1, 7 },
        new VEdge { 2105, 2, 3, 3 },
        new VEdge { 2106, 3, 4, 1 },
        new VEdge { 2107, 4, 0, 1 },
        new VEdge { 2108, 4, 1, 1 },
    };

    test_dijkstra test(edges);
    test.run_dijkstra();

    test.print_path();
    test.generate_dot_file();
}

---

在纠正 愚蠢的错别字 后

² 独立的 Live On Coliru

- sehe

---

哇。我不会撒谎，如果没有这个提升文档，我可能永远也不会把它拼凑起来。非常感谢你！ - lilott8

略微相关的是，我认为这对于boost::kruskal方法来说应该非常相似，这个假设正确吗？ - lilott8

是的，那是我会赞同的假设。 - sehe