如何复制boost :: property_map？

I would like to obtain two sets of shortest paths (one-to-all) derived from one graph, defined as adjacency_list with internal properties (as opposed to bundles)

我想从一个图中获得两组最短路径（一对一），定义为具有内部属性的adjacency_list（与bundle相对）

In theory I could run dijkstra_shortest_paths on two reference nodes, n1 and n2. If I create two property_maps and pass them in sequence to dijkstra_... I get what looks like two views of the same map. Both point to the result of the last run of dijkstra_shortest_paths, so that the older result is gone. What should I do to achieve the desired result?

从理论上讲，我可以在两个参考节点n1和n2上运行dijkstra_shortest_paths。如果我创建两个property_maps并按顺序将它们传递给dijkstra _...我看起来像是同一个地图的两个视图。两者都指向最后一次运行dijkstra_shortest_paths的结果，因此旧的结果消失了。我该怎么做才能达到预期的效果？

// Define some property maps
property_map<ugraph_t,edge_weight_t>::type Weight=get(edge_weight,G);
property_map<ugraph_t,vertex_distance_t>::type Dist1=get(vertex_distance,G);
// One line later, I expect this to be mapped to the SPs w.r.t n1
// Run SP on the first node
dijkstra_shortest_paths(G,n1,predecessor_map(Prev1).distance_map(Dist1).weight_map(Weight));
// New property maps
property_map<ugraph_t,vertex_distance_t>::type Dist2(Dist1); // And now to the second set
property_map<ugraph_t,vertex_predecessor_t>::type Prev2(Prev1); //  But no two sets will result... 
// Run SP on the second node
// This will run fine, but I will lose the first SP set (with or without a copy constructor above)
dijkstra_shortest_paths(G,n2,predecessor_map(Prev2).distance_map(Dist2).weight_map(Weight));

CONCLUSION: If I am not mistaken, a property_map can be thought of as an interface with an iterator so that copying property_maps makes no sense. The solution is to pass a custom container, constructed on the fly. That solution is detailed in the answer by @sehe below for which my many thanks!

结论：如果我没有弄错，可以将property_map视为与迭代器的接口，以便复制property_maps没有意义。解决方案是传递一个自定义容器，即时构建。这个解决方案详见@sehe下面的回答，非常感谢！

NOTE: This only works if the vertex container type is vecS. With listS one has to "manually" copy vertex-by-vertex.

注意：这仅在顶点容器类型为vecS时有效。使用listS，必须“手动”复制顶点到顶点。

1 个解决方案

#1

The distance map is not supposed to be an interior property. Same goes for the predecessor map.

距离图不应该是内部属性。前一个地图也是如此。

They are not logically properties of the graph. They are the result of a query. As such they're property of a combination of query parameters, including the graph, starting node etc.

它们不是图形的逻辑属性。它们是查询的结果。因此，它们是查询参数组合的属性，包括图形，起始节点等。

If you want to save the value of an interior property, just save it in any way you normally would:

如果要保存内部属性的值，只需以通常的方式保存：

std::vector<double> saved_distances(num_vertices(G));
BGL_FORALL_VERTICES(v, G, ugraph_t)
    saved_distances.push_back(Dist1[v]);

Workaround

The workaround with copying the maps:

复制地图的解决方法：

Live On Coliru

住在科利鲁

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/iteration_macros.hpp>

using namespace boost;

using ugraph_traits = graph_traits<adjacency_list<vecS, vecS, directedS> >;
using ugraph_t = adjacency_list<
      vecS, vecS, directedS, 
      property<vertex_distance_t, double, 
        property<vertex_predecessor_t, ugraph_traits::vertex_descriptor>
      >,
      property<edge_weight_t, double>
    >;

int main() {
    ugraph_t G(10);
    ugraph_t::vertex_descriptor n1 = 0, n2 = 1, v;
    (void) n1;
    (void) n2;
    // ...

    property_map<ugraph_t, edge_weight_t>::type Weight       = get(edge_weight,G);
    property_map<ugraph_t, vertex_distance_t>::type Dist1    = get(vertex_distance,G);
    property_map<ugraph_t, vertex_predecessor_t>::type Prev1 = get(vertex_predecessor,G);

    dijkstra_shortest_paths(G, n1,
             predecessor_map(Prev1)
            .distance_map(Dist1)
            .weight_map(Weight)
        );

    std::vector<double>                      saved_distances(num_vertices(G));
    std::vector<ugraph_t::vertex_descriptor> saved_predecessors(num_vertices(G));

    BGL_FORALL_VERTICES(v, G, ugraph_t) { 
        saved_distances.push_back(Dist1[v]);
        saved_predecessors.push_back(Prev1[v]);
    }

    /*
     * // C++11 style
     * for(auto v : make_iterator_range(vertices(G)))
     *     saved_distances[v] = Dist1[v];
     */

    // Run SP on the second node
    dijkstra_shortest_paths(G,n2,predecessor_map(Prev1).distance_map(Dist1).weight_map(Weight));
}

Suggested

I'd suggest making the result maps separate containers, leaving only the edge weight interior:

我建议将结果贴图分开容器，只留下边缘重量：

Live On Coliru

住在科利鲁

Better Yet: refactor to remove duplicated code

更好的是：重构删除重复的代码

So it just becomes

它就变成了

Live On Coliru

住在科利鲁

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

using namespace boost;

using ugraph_t = adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, double> >;
using Vertex   = ugraph_t::vertex_descriptor;

struct ShortestPaths {
    ShortestPaths(size_t num_vertices);
    std::vector<double> distances;
    std::vector<Vertex> predecessors;
};

ShortestPaths GetShortestPaths(ugraph_t const& G, Vertex start);

int main() {
    ugraph_t G(10);
    Vertex n1 = 0, n2 = 1;

    ShortestPaths sp1 = GetShortestPaths(G, n1);
    ShortestPaths sp2 = GetShortestPaths(G, n2);
}

// some other cpp file...:
ShortestPaths::ShortestPaths(size_t num_vertices)
    : distances(num_vertices), predecessors(num_vertices)
{ }

ShortestPaths GetShortestPaths(ugraph_t const& G, Vertex start) {
    ShortestPaths result(num_vertices(G));

    dijkstra_shortest_paths(G, start,
             predecessor_map(make_container_vertex_map(result.predecessors, G))
            .distance_map   (make_container_vertex_map(result.distances, G))
            .weight_map     (get(edge_weight, G))
        );

    return result;
}

Note there is no more need to copy the results. In fact, you don't even need to keep the graph around to keep the result of your query.

请注意，不再需要复制结果。实际上，您甚至不需要保留图形以保持查询结果。