graph icon indicating copy to clipboard operation
graph copied to clipboard

`is_connected()` is too slow

Open Wavetrace opened this issue 1 year ago • 1 comments

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)

Wavetrace avatar Nov 12 '24 13:11 Wavetrace

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.

Wavetrace avatar Dec 11 '24 23:12 Wavetrace