Boost图：测试两个顶点是否相邻 [英] Boost Graph : Test if two vertices are adjacent

问题描述

我是新使用C ++ boost库特别是boost图库，需要尝试编码一些算法，我通常检查两个顶点的邻接和处理其他图形概念，如计算图形不变量。
我知道的是，我们可以用相邻的顶点迭代函数： adjacent_vertices（u，g）但我正在寻找一种有效的方法来测试if两个顶点u，v相邻或不相似，不进行线性搜索

解决方案

以下是用于生成数据的代码这个情节。每个数据点是100个随机图的中等密度，每个图的100个随机边缘检查。注意对数轴

。

最好的选择最终取决于你的特定应用程序，因为对于其他操作，结构的排序速度不同。换句话说，避免过早优化。

I'm new in using C++ boost library in particularly the boost graph library which a needed to try coding some algorithms where i commonly check the adjacency of two vertices and dealing with other graph concepts like computing graph invariants. What i know is that we can iterate through adjacent vertices with the function : adjacent_vertices(u, g) but i'm searching for an efficient way to test if two vertices u, v are adjacent or not without doing linear search

解决方案

The AdjacencyMatrix concept gives a complexity guarantee that the edge() function must return in constant time.

To check if two vertices v and w are adjacent in G, you write edge(v, w, G).second, since the function returns a pair where the second value indicates if the edge exists.

The edge() function is implemented for other graph representations as well. Here is a graph that shows how different representations compare with regard to performance of checking vertex adjacency:

Here is the code used to generate the data for this plot. Each data point is 100 random graphs of medium density, with 100 random edge checks per each graph. Note the logarithmic y axis.

What is the best choice will eventually depend on your particular application, because for other operations the ordering of structures by speed is different. In other words, avoid premature optimization.

这篇关于Boost图：测试两个顶点是否相邻的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！