Boost Graph : Test if two vertices are adjacent

Question

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

Answer 1

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.