`is_connected()` is too slow
- Langage dominant
- C++
- Étoiles
- 392
- Forks
- 239
- Merge moyen
- 1 j 11 min
- PR mergées (30 j)
- 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)
Guide de contribution
Ouvrir le guide de contribution
Évaluation
Cette issue n'a pas encore été évaluée.