Boost Graph : Test if two vertices are adjacent

问题:

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

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

回答2:

BGL is a highly generic library. You can adapt most any datastructure for use with its algorithms.

You can vary the edge container. You don't mention it, but I'm assuming you've been looking at the interface/complexity guarantees for boost::adjacency_list.

Indeed the edge membership test will be O(n) even if you use setS for the edge container selector. This is mostly because adjacency lists store outgoing edges are per vertex. So in worst case, each vertex contains at most one outgoing edge and the search is practically O(n) [1]

In this case you simply want to select another graph implementation.

The documentation page on Graph Concepts is a good starting point to find out about which concepts are expected. As well as, which models supply those concepts.

In the worst case you can adapt your data structure for use with Boost Graph algorithms. E.g. you could store all edges in a simple std::[unordered_]set<std::pair<VID, VID> > and adapt it to model the EdgeListGraph concept.

That way you will have performant lookups.

---

[1] of course this also means, in best case the search is whatever your set implementation affords: O(log n) because all edges could originate from the same vertex...