如果顶点属性是指针，如何使用boost :: graph dijkstra算法? [英] How to use boost::graph dijkstra's algorithm if vertex properties are pointers?

问题描述

我使用升压图来管理图，并且需要制作一个maxmin树.
现在，我尝试使用boost dijkstra的算法，但是我使用指向类的指针作为顶点属性，而不是使用typedef property<vertex_index_t, int> my_prop，并且现在无法更改.
那么如何为图形创建predecessor_map和distance_map?

I use boost graph to manage graphs and I need to make a maxmin tree.
Now I'm trying to use boost dijkstra's algorithm, but I use a pointer to my class as a vertex property instead of using typedef property<vertex_index_t, int> my_prop, and I can't change it now.
So how can I create predecessor_map and distance_map for my graph?

我的代码如下(并且这些前身和距离图不起作用):

My code looks like this (and these predecessor and distance maps don't work):

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.
我在顶点定义中使用了指针，因为我有很多具有相同节点的图.
也许有一些方法可以在不更改图定义的顶点属性的情况下进行?

P.S.
I use pointer in vertex definition because I have many graphs with the same node.
Maybe there is some way around without changing vertex property in the graph definition?

推荐答案

Q.
如果我没错，我可以使用make_iterator_property_map创建一个外部属性图，但是要创建它，我需要传递顶点ID属性图.但是我无法通过boost :: get访问它，因为顶点属性是一个指针.我应该将哪种类型传递给boost :: get(some_type，m_graph)以获得此类ID映射?

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?

您制作/满足要求的/任何类型的属性映射/.您无需将其与图形关联.您可以在需要时将其简单地传递给算法(这也清楚表明了您承诺将图形数据和属性映射同步的那一点).

You make /any type of propertymap that satisfies the requirement/. You don't need to associate it with the graph. You can simply pass it to the algorithms when you need to (which also makes it clear at which point you promise to have the graph data and the propertymap in synch).

在我看来，实际上您也许可以通过最后一个问题-维护属性图的负担. 也就是说，如果您的索引可以从指针值派生(也许从它指向的结构中检索).

It just occurred to me that in fact you might be able to get a pass on that last issue - the burden of maintaining the property map. That is, if your index can be derived from the pointer value (perhaps retrieved from the struct it points to).

您可以使用

• transform_value_property_map
• function_property_map
• 也许两者都与例如 compose_property_map

• transform_value_property_map
• function_property_map
• perhaps both combined with e.g. compose_property_map

每种类型都有对应的演绎工厂方法make_transform_value_property_map，make_function_property_map等，因此您不必手动拼出结果类型.

Each of these types has a corresponding deducing factory method make_transform_value_property_map, make_function_property_map etc. so that you don't have to manually spell out the resulting types.

您可以搜索我的较早答案，这些示例可以解决这些问题

You can search my older answers for examples of what can be done with these.

样品:

• 带有表的Dijkstra图每个边缘上的权重
• 在Boost Graph中作为功能的重量图Dijkstra算法
• 关于物业地图的一般要点地图集/将请求添加到C ++类/结构更改中

• Dijkstra graph with a table of weights on each edge
• Weight map as function in Boost Graph Dijkstra algorithm
• General point about Property Map map set/get requests into C++ class/structure changes

这篇关于如果顶点属性是指针，如何使用boost :: graph dijkstra算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！