Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

is_connected() is too slow #398

Open
Wavetrace opened this issue Nov 12, 2024 · 0 comments
Open

is_connected() is too slow #398

Wavetrace opened this issue Nov 12, 2024 · 0 comments
Assignees

Comments

@Wavetrace
Copy link

Wavetrace commented Nov 12, 2024

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 (#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)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants