Passing only an element of a std::vector property to a BGL algorithm

Question

I have a graph with multiple edge weightings stored as

namespace boost {
    enum edge_weightvector_t {
        edge_weightvector = 1337
    };
    BOOST_INSTALL_PROPERTY(edge, weightvector);
}

typedef boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::undirectedS,
    boost::no_property,
    boost::property<boost::edge_weightvector_t, std::vector<int> >
> graph_t;

The weightings are all pushed onto the vector.

Now I want to call the prim_minimum_spanning_tree() function on the graph, with the first elements in the vector used as weightings.

How can I perform a correct function call?

Answer 1

I've did it now by first copying the desired weightings to an additional property, then running the algorithm and copying back afterwards. It is ugly, but it does the trick in my case.

Answer 2

I recently tried to do the same (to use a vector property) and failed to run algorithms only with one of the values. However, I found that using exterior properties is a good approach that won't lead to unnecessary copy actions and to pass the property map explicitly to the algorithm.

If you use random access containers you can use boost::iterator_property_map that will wrap that container and make it a property_map. Instead of edge descriptors it requires 0-based edge indices for the efficient mapping between edges and property values. Here is the punchline, further done you find the complete example:

// ... 
EdgeIndexMap edgeIds = get(edge_index, g);
// ...
typedef std::vector<int> Weights;
typedef std::vector<Weights> WeightsVector;
typedef iterator_property_map <Weights::iterator, EdgeIndexMap> WeightMap;
// ...
Weights weights; // = ...
WeightMap wm(weights.begin(), edgeIds);
// ...
some_bgl_algorithm(g, wm);

And here a complete example:

  using namespace boost;

  void sampleExteriorProperties()
  {
     typedef adjacency_list<vecS, vecS, undirectedS,
                            no_property,
                            //property<edge_index_t, int, property<edge_weight_t, int> >
                            property<edge_index_t, std::size_t>
                            > Graph;
     typedef graph_traits<Graph>::edge_descriptor Edge;
     typedef graph_traits<Graph>::edge_iterator EdgeIterator;
     typedef property_map<Graph, edge_index_t>::type EdgeIndexMap;
     //typedef property_map<Graph, edge_weight_t>::type WeightMap;

     const int NVERTICES = 5;
     const int NEDGES = 8;

     Graph g(NVERTICES);

     // Add edges WITH indexes.
     int edgeIndex = 0;
     add_edge(0, 1, edgeIndex++, g);
     add_edge(0, 2, edgeIndex++, g);
     add_edge(0, 3, edgeIndex++, g);
     add_edge(1, 2, edgeIndex++, g);
     add_edge(1, 4, edgeIndex++, g);
     add_edge(2, 3, edgeIndex++, g);
     add_edge(2, 4, edgeIndex++, g);
     add_edge(3, 4, edgeIndex++, g);

     // Weights: there must be a weight for every edge.
     // Weights will be later on accessed by edge index.
     assert(num_edges(g) == NEDGES);
     typedef std::vector<int> Weights;
     typedef std::vector<Weights> WeightsVector;
     WeightsVector weightVector({ { 2, 3, 5, 7, 9, 11, 13, 17 },
                                  { 8, 7, 6, 5, 4, 3, 2, 1 }
                                });

     EdgeIndexMap edgeIds = get(edge_index, g);

     for (Weights &weights : weightVector)
     {
        // Use the iterator_property_map to read the properties from a
        // random access container. Remember: Edge ids are used to access
        // the correct value from the container!
        typedef iterator_property_map <Weights::iterator, EdgeIndexMap> WeightMap;
        WeightMap wm(weights.begin(), edgeIds);

        EdgeIterator eIt, eItEnd;
        tie(eIt, eItEnd) = edges(g);
        while (eIt!=eItEnd)
        {
           std::cout << *eIt << ": " << wm[*eIt] << " ";
           ++eIt;
        }
        std::cout << std::endl;

        // Explicitly pass the exterior map to the algorithm.
        std::vector<Edge> mstEdges;
        kruskal_minimum_spanning_tree(g, std::back_inserter(mstEdges),
                                      weight_map(wm));

        std::for_each(mstEdges.begin(), mstEdges.end(),
                      [](const Edge &val){std::cout << val << " ";});
        std::cout << std::endl;
     }

  }