首页 文章

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

提问于
浏览 次
1

我使用boost图来管理图形，我需要创建一个maxmin树 .
现在我'm trying to use boost dijkstra'的算法，但我使用指向我的类的指针作为顶点属性而不是使用 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
);

附：
我在顶点定义中使用指针，因为我有许多具有相同节点的图形 .
也许有一些方法可以不改变图形定义中的顶点属性？

c++ boost dijkstra boost-graph

1 回答

  • 1

    问：如果我理解正确，我使用make_iterator_property_map来创建外部属性映射，但是为了创建它，我需要传递顶点ID属性映射 . 但我不能通过boost :: get访问它，因为vertex属性是一个指针 . 我应该将什么类型传递给boost :: get（some_type，m_graph）来获取这样的ID映射？

    您制作/满足要求/的任何类型的属性映射 . 您无需将其与图表相关联 . 您可以在需要时将其传递给算法（这也清楚地表明您保证在哪一点上保证图形数据与属性图同步） .

    事实上，我可能会在最后一个问题上得到一个传递 - 维护属性映射的负担 . 也就是说，如果您的索引可以从指针值派生（也许从它指向的结构中检索） .

    你可以使用

    这些类型中的每一种都有相应的推理工厂方法 make_transform_value_property_map ， make_function_property_map 等，这样您就不必手动拼出结果类型 .

    您可以search我的旧答案，以获取有关这些内容的示例 .

    样品：

    回复于

相关问题