boostorg / boostorg/graph

`is_connected()` is too slow

Abierto
#398 1 comentario 1 reacción 1 asignado Reclamado por @jeremy-murphy Ver en GitHub
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

Abrir la guía de contribución

Evaluación

Este issue todavía no se ha evaluado.

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.