CODEWITHSUNDEEP
c++boostboost-graph
rytis
rytis

Reputation: 654

How to copy 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)

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?

// 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!

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

Upvotes: 0

Views: 318

Answers (1)

sehe
sehe

Reputation: 392911

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.

Upvotes: 4

Related Questions