`is_connected()` is too slow
Abierto
algorithm
performance
priority: medium
- Lenguaje dominante
- C++
- Estrellas
- 392
- Forks
- 239
- Merge medio
- 1 d 11 min
- PR fusionados (30 d)
- 20
Descripción
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)
Guía de contribución
Evaluación
Este issue todavía no se ha evaluado.