Improve performance of topological sort

[dabbott]

This change improves the performance of topological sort by removing the linear lookups of vertices. I think it was something like O(n^4) with calls to indexOfVertex. I also try to do fewer vertex allocations by using indices everywhere, although this is relatively minor in comparison.

I didn't test exhaustively, but in my use case with ~500 vertices and ~500 edges, sorting went from 12s to 20ms!

[davecom]

Thanks, @dabbott . This is an awesome and straightforward fix!

[kokluch]

Hi @dabbott, is there a coming tag including this enhancement? We've tried it and it's significantly faster. We'd like to integrate it in production code.

[davecom]

Hi @kokluch,
I’ll push out a 3.0.1 version late today including @dabbott’s performance improvement. Thanks for using SwiftGraph.

[davecom]

Hi @kokluch,
This ended up getting pushed as 3.1. It's live now. Out of curiosity, what app are you using SwiftGraph in?
Thanks,
David

[kokluch]

Hi @davecom,
Thanks for the tag :) however it's not a valid spm format so I cannot retrieve it properly. Would you be kind to make it 3.1.0? I would really appreciate.
As for the apps I can't say much but you'll find SwiftGraph license mentioned on the followed apps:
https://apps.apple.com/fr/app/netatmo-security/id951725393
https://apps.apple.com/fr/app/netatmo-weather/id532538499
https://apps.apple.com/fr/app/home-control/id1188809809
This list is not exhaustive.

[davecom]

Hi @kokluch,

Oops, sorry about that. I just pushed a 3.1.0 tag, hopefully that fixes the issue. And thanks for the info, that's very encouraging to know.

Best,
David