c++ - Dijkstra graph with a table of weights on each edge

Question

I have a boost graph with multiples weights for each edges (imagine one set of weights per hour of the day). Every one of those weights values is stored in a propretyEdge class :

class propretyEdge {
    std::map<std::string,double> weights; // Date indexed 
}

I created a graph with those properties, and then filled it with the right values. The problem is now that I want to launch the Dijkstra algorithm over a particular set of weight on the graph : for example a function that could be :

void Dijkstra (string date, parameters ... )

That would use the

weights[date]

value for each Edge of the graph.

I read over and over the documentation, and I couldn't have a clear picture of what I have to do. I surely need to write something like this, but I have no idea were to start :

boost::dijkstra_shortest_paths (
    (*graph_m), 
    vertex_origin_num_l,
    // weight_map (get (edge_weight, (*graph_m)))
    // predecessor_map(boost::make_iterator_property_map(predecessors.begin(), get(boost::vertex_index, (*graph_m)))).
    // distance_map(boost::make_iterator_property_map(distances.begin (), get(vertex_index,(*graph_m) )))
    predecessor_map(predecessorMap).
    distance_map(distanceMap)
);

Thank you for your help.

Edit

Thanks to the wonderful Answer of Sehe, I was able to do exactly what I wanted on MacOS and on Ubuntu.

But when we tried to compile this piece of code on Visual Studio 2012, it appeared that VS wasn't very good at understanding pointer function of boost. So we modified the part of Sehe :

auto dated_weight_f = [&](Graph::edge_descriptor ed) {
    return g[ed].weights.at(date);
};

auto dated_weight_map = make_function_property_map<Graph::edge_descriptor, double>(dated_weight_f);

by :

class dated_weight_f {
public:
  dated_weight_f(Graph* graph_p,std::string date_p){
    graph_m=graph_p;
    date_m=date_p;
  }
  typedef double result_type;
    result_type operator()(Edge edge_p) const{
    return (*graph_m)[edge_p].weights.at(date_m);
  }
private:
  Graph* graph_m;
  std::string date_m;
};

const auto dated_weight_map = make_function_property_map<Edge>(dated_weight_f(graph_m,date_l));

Which had the advantage of not using a pointer function.

Answer 1

Since it's apparently not immediately clear that this question is answered in the other answer, I'll explain.

All you really need is a custom weight_map parameter that is "stateful" and can select a certain value for a given date.

You can make this as complicated as you wish 1, so you could even interpolate/extrapolate a weight given an unknown date 2, but let's for the purpose of this demonstration keep it simple.

Let's define the graph type (roughly) as above:

struct propretyEdge {
    std::map<std::string, double> weights; // Date indexed 
};

using Graph = adjacency_list<vecS, vecS, directedS, no_property, propretyEdge>;

Now, let's generate a random graph, with random weights for 3 different dates:

int main() {
    Graph g;
    std::mt19937 prng { std::random_device{}() };
    generate_random_graph(g, 8, 12, prng);

    uniform_real<double> weight_dist(10,42);
    for (auto e : make_iterator_range(edges(g)))
        for (auto&& date : { "2014-01-01", "2014-02-01", "2014-03-01" })
            g[e].weights[date] = weight_dist(prng);

And, jumping to the goal:

    for (std::string const& date : { "2014-01-01", "2014-02-01", "2014-03-01" }) {
        Dijkstra(date, g, 0);
    }
}

Now how do you implement Dijkstra(...)? Gleaning from the documentation sample, you'd do something like

void Dijkstra(std::string const& date, Graph const& g, int vertex_origin_num_l = 0) {

    // magic postponed ...

    std::vector<Graph::vertex_descriptor> p(num_vertices(g));
    std::vector<double>                   d(num_vertices(g));
    std::vector<default_color_type>       color_map(num_vertices(g));

    boost::typed_identity_property_map<Graph::vertex_descriptor> vid; // T* property maps were deprecated

    dijkstra_shortest_paths(g, vertex_origin_num_l,
            weight_map(dated_weight_map).
            predecessor_map(make_iterator_property_map(p.data(),   vid)).
            distance_map(make_iterator_property_map(d.data(),      vid)).
            color_map(make_iterator_property_map(color_map.data(), vid))
        );

Now the only unclear bit here should be dated_weight_map.

Enter Boost Property Maps

As I showed in the linked Is it possible to have several edge weight property maps for one graph BOOST?, you can have all kinds of property maps 3, including invocation of user-defined functions. This is the missing piece:

auto dated_weight_f = [&](Graph::edge_descriptor ed) {
    return g[ed].weights.at(date);
};

auto dated_weight_map = make_function_property_map<Graph::edge_descriptor, double>(dated_weight_f);

Voilà: done

I hope that by now, the correspondence in the question as well as the answer of the linked question is clear. All that's left to do is post the full live sample and the outcome in a pretty picture:

Live On Coliru

#include <boost/property_map/property_map.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <boost/property_map/property_map_iterator.hpp>

#include <random>
#include <boost/graph/random.hpp>

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

using namespace boost;

struct propretyEdge {
    std::map<std::string, double> weights; // Date indexed 
};

using Graph = adjacency_list<vecS, vecS, directedS, no_property, propretyEdge>;

void Dijkstra(std::string const& date, Graph const& g, int vertex_origin_num_l = 0) {

    auto dated_weight_f = [&](Graph::edge_descriptor ed) {
        return g[ed].weights.at(date);
    };

    auto dated_weight_map = make_function_property_map<Graph::edge_descriptor, double>(dated_weight_f);

    std::vector<Graph::vertex_descriptor> p(num_vertices(g));
    std::vector<double>                   d(num_vertices(g));
    std::vector<default_color_type>       color_map(num_vertices(g));

    boost::typed_identity_property_map<Graph::vertex_descriptor> vid; // T* property maps were deprecated

    dijkstra_shortest_paths(g, vertex_origin_num_l,
            weight_map(dated_weight_map).
            predecessor_map(make_iterator_property_map(p.data(),   vid)).
            distance_map(make_iterator_property_map(d.data(),      vid)).
            color_map(make_iterator_property_map(color_map.data(), vid))
        );

    std::cout << "distances and parents for '" + date + "':" << std::endl;
    for (auto vd : make_iterator_range(vertices(g)))
    {
        std::cout << "distance(" << vd << ") = " << d[vd] << ", ";
        std::cout << "parent(" << vd << ") = " << p[vd] << std::endl;
    }
    std::cout << std::endl;

    std::ofstream dot_file("dijkstra-eg-" + date + ".dot");

    dot_file << "digraph D {
"
        "  rankdir=LR
"
        "  size="6,4"
"
        "  ratio="fill"
"
        "  graph[label="shortest path on " + date + ""];
"
        "  edge[style="bold"]
" 
        "  node[shape="circle"]
";

    for (auto ed : make_iterator_range(edges(g))) {
        auto u = source(ed, g),
            v = target(ed, g);

        dot_file 
            << u << " -> " << v << "[label="" << get(dated_weight_map, ed) << """
            << (p[v] == u?", color="black"" : ", color="grey"")
            << "]";
    }
    dot_file << "}";
}

int main() {
    Graph g;
    std::mt19937 prng { std::random_device{}() };
    generate_random_graph(g, 8, 12, prng);

    uniform_real<double> weight_dist(10,42);
    for (auto e : make_iterator_range(edges(g)))
        for (auto&& date : { "2014-01-01", "2014-02-01", "2014-03-01" })
            g[e].weights[date] = weight_dist(prng);

    for (std::string const& date : { "2014-01-01", "2014-02-01", "2014-03-01" }) {
        Dijkstra(date, g, 0);
    }

}

Output, e.g.

---

1 As long as you keep the invariants required by the algorithm you're invoking. In particular, you must return the same weight consistently during the execution, given the same edge. Also, some algorithms don't support negative weight etc.

2 I'd highly suggest using a Boost ICL interval_map in such a case but I digress

3 see also map set/get requests into C++ class/structure changes