Boost Graph bellman_ford_shortest_paths with labeled_graph

Question

I'm trying to run the Bellman-Ford algorithm using the Boost Library. I have a labeled graph, but I'm getting an exception invalid conversion from ‘void*’ to ‘int. Any help would only be appreciated. Here is my code:

// g++ -std=c++17 -Wall test.c++ -l boost_system && ./a.out 

#include <iostream>                  // for cout
#include <utility>                   // for pair
#include <algorithm>                 // for for_each
#include <vector>                    // For dist[] and pred[]
#include <limits>                    // To reliably indicate infinity
#include <map>
#include <list>

#include <boost/config.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/directed_graph.hpp>
#include <boost/graph/labeled_graph.hpp>
#include <boost/graph/bellman_ford_shortest_paths.hpp>

using namespace boost;
using namespace std;

class Node
{
  public:
    int id;
    int group;
};

struct EdgeProperties {
  double weight;

  EdgeProperties(){}
  EdgeProperties(double w){ weight = w; }
};

typedef labeled_graph<adjacency_list<hash_setS, hash_setS, directedS, Node, EdgeProperties>, int> Graph;

int main(){

    cout << "Calling main()" << endl;

    Graph g;

    // populate the graph
    {
        add_vertex( 0, g );
        g[0].id  = 0;
        g[0].group = 10;
        add_vertex( 1, g );
        g[1].id  = 1;
        g[1].group = 20;
        add_edge_by_label( 0, 1, EdgeProperties(110), g);
        add_edge_by_label( 1, 0, EdgeProperties(222), g);
        print_graph(g, get(&Node::id, g));
        cout << "There are " << num_vertices(g) << " nodes and " << num_edges(g) << " edges in the graph" << endl;
    }

    // number of verticies in the graph
    auto n = num_vertices(g);

    // weight map
    auto ewp = weight_map(get(&EdgeProperties::weight, g.graph()));

    const int source = 0;
    const int target = 1;

    // Distance Map (with n elements of value infinity; source's value is 0)
    auto inf = numeric_limits<double>::max();
    vector<double> dist(n, inf);
    dist[source] = 0.0;

    // Predecessor Map (with n elements)
    vector<int> pred(n);

    bellman_ford_shortest_paths(
        g.graph(), 
        n, 
        ewp
            .distance_map(make_iterator_property_map(dist.begin(), get(&Node::id, g)))
            .predecessor_map(make_iterator_property_map(pred.begin(), get(&Node::id, g)))
    );

    return 0;
}

I saw the example on https://www.boost.org/doc/libs/1_53_0/libs/graph/example/bellman-example.cpp but the example uses not a labeled graph.

Here is a live preview of my code:

https://wandbox.org/permlink/WsQA8A0IyRvGWTIj

Thank you

Answer 1

The source of the problem has been touched upon in the existing answer you accepted.

However, there's more to this.

Firstly, you're pretty much "within your right" to want use Node::id as the vertex index, and there could be many good reasons to use something else than vector as the vertex container selector¹.

Secondly, that stuff should... probably have worked. bellman_ford documents:

The PredecessorMap type must be a Read/Write Property Map which key and vertex types the same as the vertex descriptor type of the graph.

And iterator_property_map documents:

This property map is an adaptor that converts any random access iterator into a Lvalue Property Map. The OffsetMap type is responsible for converting key objects to integers that can be used as offsets with the random access iterator.

Now LValuePropertyMap might in fact be readonly, but in this case it clearly shouldn't be.

When using make_iterator_property_map with the additional id-map parameter, it should in fact be behaving like any associative property map both the key and value types vertex_descriptor as required by the algorithm.

UPDATE See "BONUS" below

I might dive in a little more detail later to see why that didn't work, but for now let's just work around the issue without modifying the graph model:

Live On Coliru

auto gg = g.graph();
auto id = get(&Node::id, gg);
std::map<Graph::vertex_descriptor, Graph::vertex_descriptor> assoc_pred;

bellman_ford_shortest_paths(gg, n,
    weight_map(get(&EdgeProperties::weight, gg))
    .distance_map(make_iterator_property_map(dist.begin(), id))
    .predecessor_map(make_assoc_property_map(assoc_pred))
    );

That works as it should and as expected:

Calling main()
1 --> 0 
0 --> 1 
There are 2 nodes and 2 edges in the graph

BONUS

I found the missing link: the predecessor map was defined with the wrong value-type:

vector<Graph::vertex_descriptor> pred(n);

Will obviously work: Live On Coliru

---

¹ that's subtly different from the vertex descriptor, but related in the sense that the choice of vertex container will usually predict the actual type of vertex descriptor