Dijkstra Graph with a Table of Weights on Each Edge

Dijkstra graph with a table of weights on each edge

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 ¹, so you could even interpolate/extrapolate a weight given an unknown date ², 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 ³, 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 {\n"
        "  rankdir=LR\n"
        "  size=\"6,4\"\n"
        "  ratio=\"fill\"\n"
        "  graph[label=\"shortest path on " + date + "\"];\n"
        "  edge[style=\"bold\"]\n" 
        "  node[shape=\"circle\"]\n";

    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.

---

¹ 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.

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

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

Weight map as function in Boost Graph Dijkstra algorithm

There are a number of property map flavours. In particular one is the transform_value_property_map can be used here.

Simple Approach C++03

Assuming c++03 you'd write:

Live On Coliru

#include <boost/property_map/transform_value_property_map.hpp>
#include <boost/bind.hpp>

// ...

boost::dijkstra_shortest_paths(g, a, boost::predecessor_map(&preds[0]).weight_map(
            boost::make_transform_value_property_map(
                boost::bind(&Edge::getWeight ,_1, 2), 
                boost::get(boost::edge_bundle, g))
        ));

Cleaner C++11

Live On Coliru

auto wmap = make_transform_value_property_map([](Edge& e) { return e.getWeight(2); }, get(boost::edge_bundle, g));
boost::dijkstra_shortest_paths(g, a, boost::predecessor_map(&preds[0]).weight_map(wmap));

You can drop the boost/bind.hpp include.

Bonus: drop the getWeight() member function

Live On Coliru

You don't actually need it. You could write a Phoenix actor in-place:

#include <boost/phoenix.hpp>
using boost::phoenix::arg_names::arg1;

auto wmap = make_transform_value_property_map(2 * (&arg1->*&Edge::weight), get(boost::edge_bundle, g));

Or use c++11 again:

Live On Coliru

auto wmap = make_transform_value_property_map([](Edge& e) { return e.weight * 2; }, get(boost::edge_bundle, g));

Dijkstra path weight

You mean that the graphical representation of the graph doesn't correspond to the weight each path has ?

They don't have too... the visual representation is just a representation, nothing else. It isn't oblied be equivalent of the weight.

You could redraw the graph anyway you like, just making sure that the connections between the vertices are kept.

Edit: and it doesn't matter what kind of graph you're dealing with, be it Dijkstra or any other. You can even fidn graphs where the direction matters: From A to B the weight can be 10 and from B to A the weight can be 30. No problem.

Edit 2: the image just shows how the vertices connect to each other. The image doesn't need to be in scale with the graph that is stored in your program. Sometimes you'll have graphs with so many vertices and edges that you won't be able to represent it in a good way. What matters for your programing problems are the vertices, the edges, and it's weights. The image is just a rough representation of it. You can redraw the image as you like, you just have to make sure to put all vertices, all edges, and all weights for each edge.

How would increasing the edge weight on a graph affect the Dijkstra's algorithm?

If (s,y), (y, z), (y, x), (x, t) are the only edges in this graph, then yes: this only increases the weight (or distance) of the shortest path of s to t, since there is only one such path.

How to make a weighted graph of the London Underground

A fairly simple representation would be to use a MultiValueDictionary, i.e. a dictionary that maps a single value to a collection of values. You can make your own wrapper around a Dictionary<TKey, List<T>>, or use one from Microsoft.Experimental.Collections. For example:

MultiValueDictionary<Station, (Station station, double time)) edges;

void AddConnection(Station from, Station to, double time){
   edges.Add(from, (to, time));
   edges.Add(to, (from, time));
}

Other possible representations include

• Table, just a large 2D matrix where each cell defines the time to traverse between the row and column-station, or a invalid value if a connection does not exist. Downside is that this will be unnecessary large, since most stations are only connected to two other stations.
• Objects, Create a station object with a list of connections to other stations.

You should probably take a file defining your stations, and define a function to parse this file and construct your graph. Hopefully you already have such a file, so you don't have to enter each edge by hand

Once you have a basic implementation in place I would suggest trying to make your algorithm work with kind of graph representations. You might also try to make your implementation generic, to work with any kind of node. The signature I use look something like this:

    public class Djikstra<T>  where T : IEquatable<T>
    {
        public (T FoundNode, double TotalCost) Search(
            IEnumerable<T> from,
            IEnumerable<T> to,
            Func<T, IReadOnlyCollection<(T Node, double Cost)>> graphIterator)
}

When used with a multivalueDictionary this would be called something like this

djikstra.Search(new []{fromStation}, new []{toStation}, n => edges[n]);

Shortest path with one skippable edge

First use Dijkstra to find the length S(v) of shortest path from s to v for every vertex v. Then use Dijkstra to find the length T(v) of shortest path from v to t for every vertex v. Then for every edge (v, w) find the sum S(v) + T(w) by using the rules above. Finally, choose the minimum path.

Note: In this approach we nullify the edge (v,w) weight and find the shortest path through (v,w)

---

Related Topics