我想在程序的其他部分使用boost 's dijkstra algorithm (since I' m . 我遇到的问题是将自定义对象（我相信它们被称为 property ）添加到 adjacency_list .
基本上我有一个自定义边缘类，它维护有关边缘和通过它连接的顶点的各种信息 . 我想使用 adjaceny_list 所需的边缘属性存储我的自定义数据对象
我已经成功实现了boost provides的玩具示例 . 我试图使用自定义属性无济于事（boost example，boost properties） . 我已经能够弄清楚如何将我的自定义数据结构包含到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
我知道我的例子有点做作，但它传达了我想要完成的事情 . 我知道我的 edge_descriptor 需要一个自定义数据结构，它被发送到 graph_t typedef .
所以我想改变我的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;
1 回答
好的 . 自https://stackoverflow.com/questions/28889423/boost-adjacency-list-swap-errors-when-using-boost-dijkstra以来，你已经走了很长的路;样本是独立的，可以编译¹
我想我可以连接一些点，希望这会有所帮助 .
1.使用VEdge
对于最简单的选项，我使用 Bundled Properties ，并按如下方式定义
VEdge：现在，我们将图形定义为
如您所见，权重图具有更复杂的类型，如Properties maps from bundled properties中所述 . 你可以得到实际的 Map ：
现在，让我们在
VEdge（A = 0 ... E = 4）的向量中重新创建问题中的测试数据：构造函数有一点点复杂性，只能从边缘找到顶点的数量 . 我使用Boost Range算法来查找最大顶点节点id并传递：
注意如何传递
edges.begin()：它不是"forced to be a an array of edge_property type" . 迭代器会很好 .现在dijkstra需要得到
weight_map参数，因为它不再是默认的内部属性：对于此示例，我将
A转换为0作为起始顶点 . 结果路径与原始路径完全相同完整计划
Live On Coliru
2.使用VEdge *
如果你坚持使用属性中的指针，一些事情会变得更复杂：
您需要管理元素的生命周期
你不能使用
double VEdge::*weight_map_t. 相反，您需要为此调整自定义属性映射：edge_descriptor的边缘属性，如generate_dot_file()所示：VEdge对象复制到包中，因此它可能更有效没有进一步的麻烦（并没有打扰内存泄漏）：
Live On Coliru
¹拍打后silly typos
²自包含 Live On Coliru