嗨,我对Boost库很陌生。我想从一个方形二维 map 构建一个图形,该图形将用于星形算法(该 map 是墙壁和法线地形均为1和0的数组)。
该图应是无向的,并应随 map 的大小而变化。每个节点都有8条边( map 的边除外)。
我已经看过一些示例,但是我不理解构建这种大小图形的过程,因为大多数示例在boost graph库文档中看起来都像这样(如下图所示)。
任何帮助或想法将不胜感激
#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;
}
最佳答案
在对问题进行二读时,您的问题似乎仅仅是在添加节点和边。
这是一个查询行/列数并创建正方形“网格”的开始。我在侧面使用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]