boostorg / boostorg/graph

`is_connected()` is too slow

Open
#398 1 comment 1 reaction 1 assignee Claimed by @jeremy-murphy View on GitHub
algorithm performance priority: medium
Dominant language
C++
Stars
392
Forks
239
Avg merge
1d 11m
Merged PRs (30d)
20

Description

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](https://github.com/user-attachments/files/17717572/log-vec.txt)
(please tell if you're interested in the program that generates it)

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.