如果顶点属性是指针，如何使用 boost::graph dijkstra 算法？

Question

我使用boost graph来管理图，我需要做一个maxmin树。
现在我正在尝试使用 boost dijkstra 的算法，但我使用指向我的 class 的指针作为顶点属性而不是使用 typedef property<vertex_index_t, int> my_prop，我现在无法更改它。
那么如何为我的图表创建 predecessor_map 和 distance_map？

我的代码如下所示（这些前身和距离图不起作用）：

struct LinkStruct {...};
class Node {...};
typedef Node* NodePtr;

typedef adjacency_list<listS, listS, bidirectionalS, NodePtr, LinkStruct> MyGraph;
typedef MyGraph::vertex_descriptor vertex_descriptor;

MyGraph m_graph;
// Fill the graph
{...}

// Dijkstra parameters
std::vector<vertex_descriptor> result_tree(some_struct.size(), MyGraph::null_vertex());
std::vector<uint32_t> result_distances(some_struct.size(), 0);

// Compute maxmin tree
dijkstra_shortest_paths_no_color_map(
    m_graph, // Graph
    root_vertex, // Start vertex
    weight_map( boost::get(&LinkStruct::weight, m_graph) ). // Link property map
    distance_compare( [](uint32_t first, uint32_t second) -> bool {
                                   return first > second; } ). // Compare maxmin path lengths (if maxmin > maxmin)
    distance_combine( [](uint32_t first, uint32_t second) -> uint32_t {
                        return (first > second) ? second : first; } ). // Get min weight of the path
    predecessor_map( make_iterator_property_map(result_tree.begin(),
                                                boost::get(vertex_index, m_graph)) ). // Result tree
    distance_map( make_iterator_property_map(result_distances.begin(),
                                             boost::get(vertex_index, m_graph)) ) // Result distances
);

P.S.
我在顶点定义中使用指针，因为我有很多具有相同节点的图。
也许有一些方法可以在不改变图形定义中的顶点属性的情况下解决？

Answer 1

Q.
If I understant it right, I use make_iterator_property_map to create an external property map, but in order to create it I need to pass the vertex ID property map. But I can't access it through boost::get, because vertex property is a pointer. What type should I pass to boost::get(some_type, m_graph) to get such ID map?

您制作了/满足要求的任何类型的属性地图/。您不需要将其与图形相关联。您可以在需要时将其简单地传递给算法（这也清楚地表明您承诺在什么时候保证图形数据和属性地图同步）。

我刚刚想到，实际上您可以通过最后一个问题 - 维护属性地图的负担。也就是说，如果您的索引可以从指针值派生（可能从它指向的结构中检索）。

您可以使用

这些类型中的每一个都有相应的推导工厂方法make_transform_value_property_map、make_function_property_map等，因此您不必手动拼出结果类型。

您可以 search 我以前的答案，以了解可以用这些来做什么的例子。

样本：

关于属性地图的一般点map set/get requests into C++ class/structure changes

如果顶点属性是指针，如何使用 boost::graph dijkstra 算法？

How to use boost::graph dijkstra's algorithm if vertex properties are pointers?

c++

boost

dijkstra

boost-graph