Search code examples
c++boostgraph-theorydijkstra

How to visualize the boost graph and perform dijkstra's shortest path?

I am trying to make a graph with Dijkstra's shortest path. Vertex size can differ later, so I decided to make a bunch of loops to create edges. I am struggling with visualizing the graph in dot file.

I tried std::ofstream dot_file("grid.dot"); boost::write_graphviz(dot_file, g);
But this won't make any new grid file and gives no error.

Also, I am trying to apply Dijkstra's shortest path function. But this line gives me an error.
dijkstra_shortest_paths(g, vtx_distance, predecessor_map(&p[0]).distance_map(&d[0]));

#include <stdint.h>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

using namespace std;
using namespace boost;

int main() {
    struct Vertex {int index;};
    struct Edge {int weight;};
    typedef adjacency_list<vecS, vecS, bidirectionalS, Vertex, Edge> Graph;
    Graph g;
    typedef graph_traits < Graph >::vertex_descriptor vertex_t;
    typedef graph_traits < Graph >::edge_descriptor edge_t;
    typedef graph_traits <Graph> Traits;


    vector<int> vertices; 
    int size = 9;
    int size_x = 3;
    int size_y = 3;
    for (int i = 0; i < size; i++){
        vertices.push_back(i);
    }
    vector<vertex_t> vtx;
    for (int i = 0; i<vertices.size(); i++) {
        vertex_t tmp = add_vertex(g);
        g[tmp].index = vertices.at(i);
        vtx.push_back(tmp); 
    }

 //Add edge in horizontal
    for (int i = 0; i<vertices.size(); i++){
        if (vertices[i] % size_x !=2){
            add_edge(vtx[i], vtx[i + 1], g);
        }
    }
 //Add edge in vertical
    for (int i = 0; i<vertices.size(); i++){
    if (vertices[i] < size - size_y){
        add_edge(vtx[i], vtx[i + size_x], g);
    }
}
//Add edge in diagonal 1
for (int i = 0; i<vertices.size(); i++){
    if (vertices[i] % size_x != 2 && vertices[i] < size - size_y){
        add_edge(vtx[i], vtx[i + 1 + size_x], g);
    }
}
//Add edge in diagonal 2
for (int i = 0; i<vertices.size(); i++){
    if (vertices[i] % size_x != 0 && vertices[i] < size - size_y){
        add_edge(vtx[i], vtx[i - 1 + size_x], g);
    }
}

vector<int> d(num_vertices(g));
vector<vertex_t> p(num_vertices(g));
vertex_t vtx_distance = vertex(0, g);

dijkstra_shortest_paths(g, vtx_distance, predecessor_map(&p[0]).distance_map(&d[0]));

std::cout << "distances and parents:" << std::endl;


//    std::ofstream file("grid.dot");
    std::ofstream dot_file("grid.dot");
    boost::write_graphviz(dot_file, g);
}

Image of the graph I want to make (without dijkstra).
enter image description here

Solution

  • As a first step I reviewed your graph creation code. It seems unnecessarily complicated.

    Getting On The Grid

    Let's simplify, based on the observation that vecS vertex container selector implies contiguous integral vertex descriptors, starting at 0:

    Graph make_grid(size_t size_x, int size_y)
{
    Graph g(size_x * size_y);

    using boost::make_iterator_range;
    for (auto v : boost::make_iterator_range(vertices(g)))
        g[v].index = v;

    auto col     = [=](vertex_t v) { return v % size_x; };
    auto row     = [=](vertex_t v) { return v / size_x; };
    auto lastcol = [=](vertex_t v) { return col(v) == size_x - 1; };
    auto lastrow = [=](vertex_t v) { return row(v) == size_y - 1; };

    // Add edges
    for (auto v : boost::make_iterator_range(vertices(g))) {
        if (not lastrow(v))
            add_edge(v, v + size_x, g); // vertical
        if (not lastcol(v))
            add_edge(v, v + 1, g); // horizontal
        if (not(lastrow(v) || lastcol(v)))
            add_edge(v, v + 1 + size_x, g); // down-right
        if (not(lastrow(v) || 0 == col(v)))
            add_edge(v, v - 1 + size_x, g); // down-left
    }
    return g;
}

    That's all. It makes the graph.

    Publish It!

    Now you want to print it. Let's do that:

    std::ofstream dot_file("grid.dot");
boost::write_graphviz(dot_file, g);
if (auto code = system("neato -T png grid.dot -o grid.png"))
    return code;

    Results in

    enter image description here

    The Editor Wants A Word

    You can spice things up with graphviz node/edge attributes. Let's add colors and save those as well:

    struct Edge { int weight; std::string color; };

...
// generating different color edges per direction
if (not lastrow(v))
    add_edge(v, v + size_x, Edge{weightgen(), "red"}, g); // vertical
if (not lastcol(v))
    add_edge(v, v + 1, Edge{weightgen(), "green"}, g); // horizontal
if (not(lastrow(v) || lastcol(v)))
    add_edge(v, v + 1 + size_x, Edge{weightgen(), "blue"}, g); // down-right
if (not(lastrow(v) || 0 == col(v)))
    add_edge(v, v - 1 + size_x, Edge{weightgen(), "brown"}, g); // down-left

    Let's extract saving to a function as well:

    void save(std::string const name, Graph const& g) {
    std::ofstream dot_file(name + ".dot");

    boost::dynamic_properties dp;
    dp.property("node_id",   get(boost::vertex_index, g));
    dp.property("label",     get(&Edge::weight,       g));
    dp.property("color",     get(&Edge::color,        g));
    dp.property("fontcolor", get(&Edge::color,        g));
    boost::write_graphviz_dp(dot_file, g, dp);

    std::ostringstream cmd;
    cmd << "neato -T png " //
        << std::quoted(name + ".dot", '\'') << " -o "
        << std::quoted(name + ".png", '\'');

    if (auto code = system(cmd.str().c_str())) {
        if (code == -1)
            ::perror(name.data());
        ::exit(code);
    }
}

    Now the result is: enter image description here

    Enter Dijkstra

    you have compilation failures. They're due to the use of raw pointers (&d[0] e.g.) as property maps. This has been deprecated and removed long time ago. So, make explicit property maps instead, e.g.:

    auto vidx = get(boost::vertex_index, g);
auto wmap = get(&Edge::weight, g);
auto dmap = boost::make_iterator_property_map(d.begin(), vidx);
auto pmap = boost::make_iterator_property_map(p.begin(), vidx);

dijkstra_shortest_paths(         //
    g,                           //
    V{0},                        //
    boost::predecessor_map(pmap) //
        .distance_map(dmap)      //
        .weight_map(wmap));

    That compiles. I'm not too sure what exactly about the output you'd like to have visualized. Perhaps we can grey out any edges that are not in the path?

    for (auto e : make_iterator_range(edges(g))) {
    auto v = source(e,g), u = target(e,g);
    if (p.at(u) != v)
        g[e].color = "lightgrey";
}

    And the result is:

    enter image description here

    FULL LISTING

    "Live" On Coliru

    #include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graphviz.hpp>
#include <iostream>

struct Vertex { int index;  };
struct Edge { int weight; std::string color; };

using Graph    = boost::adjacency_list< //
    boost::vecS, boost::vecS, boost::bidirectionalS, Vertex, Edge>;

using Traits   = boost::graph_traits<Graph>;
using V = Traits::vertex_descriptor;
using E = Traits::edge_descriptor;

Graph make_grid(size_t size_x, size_t size_y)
{
    Graph g(size_x * size_y);

    using boost::make_iterator_range;
    for (auto v : boost::make_iterator_range(vertices(g)))
        g[v].index = v;

    auto col     = [=](V v) { return v % size_x; };
    auto row     = [=](V v) { return v / size_x; };
    auto lastcol = [=](V v) { return col(v) == size_x - 1; };
    auto lastrow = [=](V v) { return row(v) == size_y - 1; };

    // Add edges
    auto weightgen = [] { return rand() % 5 + 1; };
    for (auto v : boost::make_iterator_range(vertices(g))) {
        if (not lastrow(v))
            add_edge(v, v + size_x, Edge{weightgen(), "red"}, g); // vertical
        if (not lastcol(v))
            add_edge(v, v + 1, Edge{weightgen(), "green"}, g); // horizontal
        if (not(lastrow(v) || lastcol(v)))
            add_edge(v, v + 1 + size_x, Edge{weightgen(), "blue"}, g); // down-right
        if (not(lastrow(v) || 0 == col(v)))
            add_edge(v, v - 1 + size_x, Edge{weightgen(), "brown"}, g); // down-left
    }
    return g;
}

void save(std::string const name, Graph& g) {
    std::ofstream dot_file(name + ".dot");

    boost::dynamic_properties dp;
    dp.property("node_id",   get(boost::vertex_index, g));
    dp.property("label",     get(&Edge::weight,       g));
    dp.property("color",     get(&Edge::color,        g));
    dp.property("fontcolor", get(&Edge::color,        g));

    boost::write_graphviz_dp(dot_file, g, dp);

    std::ostringstream cmd;
    cmd << "neato -T png " //
        << std::quoted(name + ".dot", '\'') << " -o "
        << std::quoted(name + ".png", '\'');

    if (auto code = system(cmd.str().c_str())) {
        if (code == -1)
            ::perror(name.data());
        ::exit(code);
    }
}

int main() {
    Graph g = make_grid(3, 3);

    save("grid", g);

    std::vector<int> d(num_vertices(g));
    std::vector<V>   p(num_vertices(g));

    auto vidx = get(boost::vertex_index, g);
    auto wmap = get(&Edge::weight, g);
    auto dmap = boost::make_iterator_property_map(d.begin(), vidx);
    auto pmap = boost::make_iterator_property_map(p.begin(), vidx);

    dijkstra_shortest_paths(         //
        g,                           //
        V{0},                        //
        boost::predecessor_map(pmap) //
            .distance_map(dmap)      //
            .weight_map(wmap));

    for (auto e : make_iterator_range(edges(g))) {
        auto v = source(e,g), u = target(e,g);
        if (p.at(u) != v)
            g[e].color = "lightgrey";
    }

    save("path", g);
}