您能否发布示例代码以使用BGL对有向图进行分级? levelization的定义:Vertex具有属性“int level” . 在图形的BFS遍历期间,当一个顶点被“检查”时,查看它的前任顶点的级别,取最大值,递增,并将其分配给该顶点的“级别” .
如果你的意思是BFS深度,那么这已经内置了以增强BFS并且可以轻松获得 .
只需使用向量来存储深度和深度BFS访问者,就像我做的这个例子:
#include <iostream> #include <vector> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/breadth_first_search.hpp> using namespace std; using namespace boost; typedef adjacency_list < vecS, vecS, directedS, property< vertex_index_t, size_t> , property< edge_index_t, size_t > > Graph; typedef graph_traits<Graph>::vertex_descriptor Vertex; typedef graph_traits<Graph>::edge_descriptor Edge; int main(int argc, char* argv[]){ Graph G; vector<Vertex> verts; for(size_t i = 0; i < 9; ++i){ Vertex v = add_vertex(G); verts.push_back(v); } /* 0 0 / \ 1 1 4 / \ 2 2 5 / \ 3 3 6 \ 4 7 \ 5 8 */ add_edge(verts.at(0),verts.at(1),G); add_edge(verts.at(1),verts.at(2),G); add_edge(verts.at(2),verts.at(3),G); add_edge(verts.at(0),verts.at(4),G); add_edge(verts.at(4),verts.at(5),G); add_edge(verts.at(5),verts.at(6),G); add_edge(verts.at(6),verts.at(7),G); add_edge(verts.at(7),verts.at(8),G); cout << "vertices " << num_vertices(G) << endl; cout << "edges " << num_edges(G) << endl; //store depths vector<size_t> d(num_vertices(G)); //get an index map, from Graph definition property< vertex_index_t, size_t> typedef boost::property_map< Graph, boost::vertex_index_t>::type VertexIndexMap; VertexIndexMap v_index = get(boost::vertex_index, G); // Create the external property map, this map wraps the storage vector d boost::iterator_property_map< std::vector< size_t >::iterator, VertexIndexMap > d_map(d.begin(), v_index); //Start at 0 boost::breadth_first_search(G, verts.at(0), boost::visitor(boost::make_bfs_visitor( boost::record_distances(d_map, boost::on_tree_edge()) ))); cout << "Starting at 0" << endl; for(size_t i = 0; i < 9; ++i){ //depth (level) of BFS cout << "vertex " << i << "\t" << d.at(i) << endl; } vector<size_t> d2(num_vertices(G)); cout << "Starting at 4" << endl; // Create the external property map, this map wraps the storage vector d boost::iterator_property_map< std::vector< size_t >::iterator, VertexIndexMap > d2_map(d2.begin(), v_index); //start at 4 boost::breadth_first_search(G, verts.at(4), boost::visitor(boost::make_bfs_visitor( boost::record_distances(d2_map, boost::on_tree_edge()) ))); for(size_t i = 0; i < 9; ++i){ //depth (level) of BFS cout << "vertex " << i << "\t" << d2.at(i) << endl; } }
输出应如下所示:顶点9边缘8从0开始顶点0 0顶点1 1顶点2 2顶点3 3顶点4 1顶点5 2顶点6 3顶点7 4顶点8 5从4开始顶点0 0顶点1 0顶点2 0顶点3 0顶点4 0顶点5 1顶点6 2顶点7 3顶点8 4
当您从4开始时,其他顶点无法到达(定向),因此向量包含默认值(在本例中为0) . 这应该也适用于无向 .
1 回答
如果你的意思是BFS深度,那么这已经内置了以增强BFS并且可以轻松获得 .
只需使用向量来存储深度和深度BFS访问者,就像我做的这个例子:
输出应如下所示:
顶点9
边缘8
从0开始
顶点0 0
顶点1 1
顶点2 2
顶点3 3
顶点4 1
顶点5 2
顶点6 3
顶点7 4
顶点8 5
从4开始
顶点0 0
顶点1 0
顶点2 0
顶点3 0
顶点4 0
顶点5 1
顶点6 2
顶点7 3
顶点8 4
当您从4开始时,其他顶点无法到达(定向),因此向量包含默认值(在本例中为0) . 这应该也适用于无向 .