graph
graph copied to clipboard
`is_connected()` is too slow
is_connected function is documented as
// Is the undirected graph connected?
// Is the directed graph strongly connected?
and achieves this goal by checking if each vertex is reachable from each other one. This is unnecessarily resource-consuming and slow, O(n^3) (or even O(n^4)). You could call this a performance bug.
Please see PR397 (https://github.com/boostorg/graph/pull/397) that fixes this to run in O(N) (O(N+E)).
See the attached log_vec.txt for speed evaluation. log-vec.txt (please tell if you're interested in the program that generates it)
As discussed in PR, it might be more reasonable to make the interface more explicit / less confusing rather than to preserve 100% backward compatibility. PR has been updated with this in mind.