在BOOST图中找到给定2个顶点的多个边-Java 学习之路

我正在为一些项目使用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属性包含一个时间戳start，end ..并且图中可能有许多这样的边具有不同的时间戳 . 例如 .

edge1 = (node1, node2) with start = 100, end = 200.
edge2 = (node1, node2) with start = 250, end = 400.

我知道在增强图中，给定两个顶点，我们可以使用以下内容查找图中是否存在边 .

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 回答

7
有几种方法可以做到这一点 .

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 的所有"parallel"边缘的一系列迭代器，并进入 v ，如documentation page所述：

std :: pair <out_edge_iterator，out_edge_iterator>
edge_range（vertex_descriptor u，vertex_descriptor v，
const adjacency_list＆g）
返回一对外边迭代器，它给出从u到v的所有并行边的范围 . 此函数仅在adjacency_list的OutEdgeList是根据目标顶点对外边缘进行排序的容器时才有效，并允许平行边 . multisetS选择器选择这样的容器 .

此函数仅适用于 multisetS 的原因是因为为了向平行边提供（容易）一系列迭代器，您需要将边组合在一起，这是 multisetS 的情况，因为它们按顶点描述符排序因此，所有平行的外边缘都被组合在一起 . 这是唯一能给你这个的容器选择，否则，你必须使用选项（1）（注意：创建一个 filter_iterator （参见docs）如果你真的经常使用它可以派上用场） .
回复于 2024-04-28T16:00:54+08:00

在BOOST图中找到给定2个顶点的多个边

1 回答

相关问题