CODEWITHSUNDEEP
rustnon-deterministicpetgraph
curiousdannii
curiousdannii

Reputation: 2010

How can I get a deterministic topological sort in Petgraph?

I'm using Petgraph's toposort function to get a sorted list of the graph's nodes. toposort does not however guarantee that all nodes at the same level will be returned in a consistent deterministic order. Is there some other option within Petgraph that will return the nodes in a deterministic order, or would I need to write my own function? (If so, any pointers?)

Upvotes: 3

Views: 818

Answers (1)

curiousdannii
curiousdannii

Reputation: 2010

So toposort (and other algorithms) are sensitive to the order that graph nodes and edges are created. I had been feeding the graph with data from a HashMap, which cannot be iterated in a deterministic order. By switching my data to a BTreeMap the nodes and edges are created in a reliable order, and then algorithms like toposort give deterministic results.

Upvotes: 5

Related Questions