如何可视化boost图并执行dijkstra的最短路径？

Question

我正在尝试用 Dijkstra 的最短路径制作图表。顶点大小稍后可能会有所不同，所以我决定制作一堆循环来创建边。我正在努力可视化点文件中的图形。

我试过了 std::ofstream dot_file("grid.dot"); boost::write_graphviz(dot_file, g);
但这不会生成任何新的网格文件并且不会出错。

此外，我正在尝试应用 Dijkstra 的最短路径函数。但是这一行给我一个错误。
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);
}

我要制作的图表的图像（没有 dijkstra）。

Answer 1

作为第一步，我检查了您的图表创建代码。这似乎不必要地复杂。

进入网格

让我们简化一下，基于观察 vecS 顶点容器选择器意味着连续的整数顶点描述符，从 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;
}

就是这样。它制作了图表。

发布它！

现在您要打印它。让我们这样做：

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;

结果

编辑有话要说

您可以使用 graphviz node/edge 属性来增添趣味。让我们添加颜色并保存它们：

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

让我们也将保存提取到一个函数中：

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);
    }
}

现在的结果是：

请输入 Dijkstra

你有编译失败。它们是由于使用原始指针（&d[0] 例如）作为属性映射。这在很久以前就已被弃用和删除。因此，改为制作显式属性映射，例如：

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";
}

结果是：

完整列表

"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);
}

如何可视化boost图并执行dijkstra的最短路径？

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

c++

boost

graph-theory

dijkstra

进入网格

发布它！

编辑有话要说

请输入 Dijkstra

完整列表