JuliaGraphs / Graphs.jl

An optimized graphs package for the Julia programming language
http://juliagraphs.org/Graphs.jl/
Other
451 stars 87 forks source link

[OPTIM] perm_greedy_color (and thus all coloring algorithms) is running in O(n^2) instead of O(n) #378

Closed AntoineBut closed 1 month ago

AntoineBut commented 2 months ago

It shouldn't.

Internal method uses a Vector instead of a Set, profiling shows 90+% of time is spent on emptying that vector between iterations:

Capture d'écran 2024-05-26 185352

gdalle commented 1 month ago

Fixed by #379