我正在为某个项目使用Boost Graph库,我想找出边在图中重复的次数。例如
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Node_Info, Edge_Info > Graph_t;
//node_info and Edge_info are external node and edge properties (structures)
假设我有两个节点,node1和node2,并且它们之间有一条边(node1,node2)。每个边的edge属性包含一个时间戳开始、结束。。并且在具有不同时间戳的图中可以存在许多这样的边。例如
edge1 = (node1, node2) with start = 100, end = 200.
edge2 = (node1, node2) with start = 250, end = 400.
我知道,在boost图中,给定两个顶点,我们可以使用以下公式来确定图中是否存在边。
std::pair < edge_t, bool > p = boost::edge( node1, node2, myGraph );
if(p.second == 1) cout << "edge exists!" << endl;
else cout << " does not exist " << endl;
但这可能意味着,即使存在具有不同边缘属性的多个边缘,它也只返回任何一个边缘-->问题
有人能提出如何在两个给定节点之间获得这样多条边的想法吗?谢谢
有几种方法可以做到这一点。
1) 只需检查所有到达所需目标的边缘:
boost::graph_traits<Graph_t>::out_edge_iterator ei, ei_end;
boost::tie(ei, ei_end) = out_edges( node1, myGraph );
int parallel_count = 0;
for( ; ei != ei_end; ++ei) {
if( target(*ei, myGraph) == node2 ) {
cout << "Found edge (node1, node2) with property: " << myGraph[*ei] << endl;
++parallel_count;
};
};
cout << "There are a total of " << parallel_count << " parallel edges." << endl;
2) 指定boost::multisetS
作为adjacency_list
的OutEdgeListS
模板参数,这将启用一个名为edge_range
的额外函数,该函数为从u
出来并进入v
的所有"平行"边返回一系列迭代器,如文档页面所示:
std::pair<out_edge_iterator, out_edge_iterator> edge_range(vertex_descriptor u, vertex_descriptor v, const adjacency_list& g)
返回一对出边迭代器,该迭代器给出从u到v的所有平行边的范围。此函数仅在相邻列表的OutEdgeList是根据目标顶点对出边进行排序并允许平行边的容器时才起作用。multisetS选择器选择这样一个容器。
此函数仅适用于multisetS
的原因是,为了(轻松地)为平行边提供一系列迭代器,需要将边分组在一起,multisetS
就是这样,因为它们是按顶点描述符排序的,因此,所有平行出的边都分组在一起。这是唯一能提供此功能的容器选择,否则,您必须使用选项(1)(注意:如果您真的经常使用此选项,创建filter_iterator
(请参阅文档)可能会很有用)。