codecov[bot]
commented
2 months ago Codecov Report
All modified and coverable lines are covered by tests :white_check_mark:
Project coverage is 97.28%. Comparing base (
afb8245) to head (b42ab1f).
Additional details and impacted files
```diff @@ Coverage Diff @@ ## master #371 +/- ## ======================================= Coverage 97.28% 97.28% ======================================= Files 118 118 Lines 6876 6876 ======================================= Hits 6689 6689 Misses 187 187 ```:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.
gdalle
Addresses #370.
This implementation has $O(N)$ runtime, while the previous implementation had $O(N^2)$ runtime.
The optimization comes from storing all edges added at each iteration in an indexed table, allowing to draw a random edge in $O(1)$ time, while the previous implementation had to go through (on average) half on the nodes in order to draw a random edge, which takes $O(N)$ time.
On my computer, this implementation uses approximately 16% more memory.
It runs faster than the previous one even on small graphs ($N = 100$).