这与我昨天关于使用整数索引访问顶点的问题有关 . 那个帖子在这里:Accessing specific vertices in boost::graph
那里的解决方案表明使用vecS作为顶点的类型,确实可以使用整数索引访问特定顶点 . 我想知道是否有类似的方法由boost使用整数索引有效地访问任意边 .
附件是描述前者(具有整数索引的顶点的有效访问)并基于开发者显式维护两个数组( from[]
和 to[]
)来访问边缘的代码,这两个数组分别存储边缘的源和目标 .
代码创建以下图表:
#include <boost/config.hpp>
#include <iostream>
#include <fstream>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
using namespace boost;
typedef adjacency_list_traits<vecS, vecS, directedS> Traits;
typedef adjacency_list<
vecS, vecS, directedS,
property<
vertex_name_t, std::string,
property<vertex_index_t, int,
property<vertex_color_t, boost::default_color_type,
property<vertex_distance_t, double,
property<vertex_predecessor_t, Traits::edge_descriptor> > > > >,
property<
edge_index_t, int,
property<edge_capacity_t, double,
property<edge_weight_t, double,
property<edge_residual_capacity_t, double,
property<edge_reverse_t, Traits::edge_descriptor> > > > > >
Graph;
int main() {
int nonodes = 4;
const int maxnoedges = 4;//I want to avoid using this.
Graph g(nonodes);
property_map<Graph, edge_index_t>::type E = get(edge_index, g);
int from[maxnoedges], to[maxnoedges];//I want to avoid using this.
// Create edges
Traits::edge_descriptor ed;
int eindex = 0;
ed = (add_edge(0, 1, g)).first;
from[eindex] = 0; to[eindex] = 1;//I want to avoid using this.
E[ed] = eindex++;
ed = (add_edge(0, 2, g)).first;
from[eindex] = 0; to[eindex] = 2;//I want to avoid using this.
E[ed] = eindex++;
ed = (add_edge(1, 3, g)).first;
from[eindex] = 1; to[eindex] = 3;//I want to avoid using this.
E[ed] = eindex++;
ed = (add_edge(2, 3, g)).first;
from[eindex] = 2; to[eindex] = 3;//I want to avoid using this.
E[ed] = eindex++;
graph_traits < Graph >::out_edge_iterator ei, e_end;
for (int vindex = 0; vindex < num_vertices(g); vindex++) {
printf("Number of outedges for vertex %d is %d\n", vindex, out_degree(vindex, g));
for (tie(ei, e_end) = out_edges(vindex, g); ei != e_end; ++ei)
printf("From %d to %d\n", source(*ei, g), target(*ei, g));
}
printf("Number of edges is %d\n", num_edges(g));
//Is there any efficient method boost provides
//in lieu of having to explicitly maintain from and to arrays
//on part of the developer?
for (int eindex = 0; eindex < num_edges(g); eindex++)
printf("Edge %d is from %d to %d\n", eindex, from[eindex], to[eindex]);
}
代码构建和编译没有错误 . for
循环与 vindex
正常工作 out_edges
和 out_degree
工作正常作为参数整数索引 .
有没有办法为下一个使用boost :: graph数据结构直接打印边的 for
循环做同样的事情?
我查看了以下处理类似问题的主题:
Boost graph library: Get edge_descriptor or access edge by index of type int
建议的答案是使用 unordered_map
. 使用它是否有任何权衡,而不是拥有 from[]
和 to[]
数组?是否有任何其他计算有效的访问边缘的方法?
1 回答
你只能这样做
使用不同的图形模型
外部边缘索引
概念
你可能对AdjacencyMatrix concept感兴趣 . 它并不完全是整数边缘ID,但是
AdjacencyMatrix
也可以通过源/目标顶点查找边缘 .要获得真正的整体边缘描述符,您可能需要编写自己的图形模型类(对一组现有BGL概念进行建模) . 您可能也对
grid_graph<>
感兴趣(每个顶点有一组固定的编号边,其中顶点是网格) .邻接清单
这里's a modification from the previous answer showing an external index. It'类似于您的解决方案 . 我选择
bimap
所以至少你得到反向查找"automagically" .现在你可以按边缘id进行循环:
您可以通过它的id直接查找边缘:
反向查找有点多余,因为您可以非常轻松地使用BGL执行相同操作:
Live On Coliru
印花
邻接矩阵
除了更改模型外,保持一切相同:
现在,您可以获得按顶点查找的附加功能:
Live On Coliru
打印