search

dominikbraun / graph

A library for creating generic graph data structures and modifying, analyzing, and visualizing them.
https://graph.dominikbraun.io
Apache License 2.0
1.81k stars 94 forks source link

Make StableTopologicalSort sort even less #132

Closed jonjohnsonjr closed 1 year ago

jonjohnsonjr commented 1 year ago

In order to get deterministic order, we don't actually have to sort the entire queue after every pass, we just have to enqueue in a deterministic order.

This change adds a separate frontier that gets sorted before it gets appended to the queue after each pass.

For what it's worth, this doesn't affect performance in a perceivable way for us, so feel free to reject it, but on the same workload as my last PR, this goes from making 242651 comparisons to only 5106 comparisons, which seems fairly close to optimal.

kaniini commented 1 year ago

This is solid work, thanks @jonjohnsonjr !

dominikbraun commented 1 year ago

This change has been released in graph v0.22.3.