使用Boost圖的大小變化圖

Question

嗨，我對Boost庫非常陌生。我想從一個用於星型算法的正方形二維地圖建立一個圖（地圖是牆和普通地形都是1和0的數組）。

該圖應該是無向的並隨地圖大小而變化。每個節點有8條邊（地圖邊除外）。

我已經通過了一些例子，但我不明白構建這種尺寸圖的過程，因爲大多數例子在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]