c++ - 使用 Boost 图的大小变化图

Question

您好，我是 Boost 库的新手。我想从一个方形二维 map 构建一个图表，该 map 将用于星形算法(该 map 是一个数组，对于墙壁和正常地形都有 1s 和 0s)。

图应该是无向的，随图的大小而变化。每个节点有 8 条边( map 的边除外)。

我已经看过几个示例，但我不明白构建这种大小的图形的过程，因为大多数示例在 boost 图形库文档中看起来像这样(如下所示)。

任何帮助或想法将不胜感激

    #include <iostream>                  // for std::cout
  #include <utility>                   // for std::pair
  #include <algorithm>                 // for std::for_each
  #include <boost/graph/graph_traits.hpp>
  #include <boost/graph/adjacency_list.hpp>
  #include <boost/graph/dijkstra_shortest_paths.hpp>

  using namespace boost;

  int main(int,char*[])
  {
    // create a typedef for the Graph type
    typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;

    // Make convenient labels for the vertices
    enum { A, B, C, D, E, N };
    const int num_vertices = N;
    const char* name = "ABCDE";

    // writing out the edges in the graph
    typedef std::pair<int, int> Edge;
    Edge edge_array[] =
    { Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C),
      Edge(C,E), Edge(B,D), Edge(D,E) };
    const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);

    // declare a graph object
    Graph g(num_vertices);

    // add the edges to the graph object
    for (int i = 0; i < num_edges; ++i){
      add_edge(edge_array[i].first, edge_array[i].second, g);
    }
    return 0;
  }

Answer 1

在第二次阅读问题时，您的问题似乎只是如何添加节点和边。

这是一个查询行数/列数并创建正方形“网格”的开始。我在侧面使用了一个 nodes 矩阵，以便从网格中的 (x,y) 轻松查找到图中的顶点描述符。

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>

using namespace boost;

struct Point {
    int x, y; 
    friend std::ostream& operator<<(std::ostream& os, Point p) {
        return os << "[" << p.x << "," << p.y << "]";
    }
};

int main() {
    using std::vector;
    using Graph             = adjacency_list<setS, vecS, undirectedS, Point>;
    using vertex_descriptor = Graph::vertex_descriptor;

    Graph lattuce;

    int num_rows;
    if (!(std::cin >> num_rows && num_rows > 0))
        return 255;

    vector<vector<vertex_descriptor> > nodes(num_rows, vector<vertex_descriptor>(num_rows));

    for (auto i = 0; i < num_rows; ++i)
        for (auto j = 0; j < num_rows; ++j)
            nodes[i][j] = add_vertex(Point{i,j}, lattuce);

    auto is_valid = [num_rows](Point p) { return (p.x >= 0 && p.x < num_rows) && 
                                                 (p.y >= 0 && p.y < num_rows); };

    for (auto vd : make_iterator_range(vertices(lattuce))) {
        auto p = lattuce[vd];

        for (Point neighbour : {
                Point { p.x - 1, p.y - 1 }, Point { p.x - 1, p.y + 0 }, Point { p.x - 1, p.y + 1 },
                Point { p.x + 0, p.y - 1 }, Point { p.x + 0, p.y + 1 },
                Point { p.x + 1, p.y - 1 }, Point { p.x + 1, p.y + 0 }, Point { p.x + 1, p.y + 1 },
            })
        {
            if (is_valid(neighbour))
                add_edge(nodes[neighbour.x][neighbour.y], vd, lattuce);
        };
    }

    print_graph(lattuce, get(vertex_bundle, lattuce));
}

打印品，例如对于输入 3:

[0,0] <--> [0,1] [1,0] [1,1] 
[0,1] <--> [0,0] [0,2] [1,0] [1,1] [1,2] 
[0,2] <--> [0,1] [1,1] [1,2] 
[1,0] <--> [0,0] [0,1] [1,1] [2,0] [2,1] 
[1,1] <--> [0,0] [0,1] [0,2] [1,0] [1,2] [2,0] [2,1] [2,2] 
[1,2] <--> [0,1] [0,2] [1,1] [2,1] [2,2] 
[2,0] <--> [1,0] [1,1] [2,1] 
[2,1] <--> [1,0] [1,1] [1,2] [2,0] [2,2] 
[2,2] <--> [1,1] [1,2] [2,1]