bloq.call_graph() should preserve ordering of successors across calls / build_call_graph should return a Dict instead of Set

[tanujkhattar]

Every time you call bloq.call_graph() you can get a different nx.DiGraph where the ordering of successors of a node is different. This happens because build_call_graph returns a Set instead of a Dict so iterating over a set to get the call graph destroys ordering.

I encountered this when writing tests for #732 where the output of get_flame_graph_data is different across calls because the DFS ordering of nodes in bloq.call_graph is different.

@mpharrigan What's the reason to destroy ordering? Is this by design? Can we preserve ordering? I agree that most properties of the call graph analysis shouldn't depend upon the ordering but I think it's still nice to preserve the order across calls.

[mpharrigan]

Are sets not ordered in Python? either a list of 2-tuples or a dict would be fine. I think the point of the "set" was to encode that order doesn't matter. Perhaps a more important property is that each bloq appears only once, which isn't captured by set.

It's possible that networkx will shuffle things later anyways, so if you want determinism I suggest throwing in some sorteds.

[tanujkhattar]

Are sets not ordered in Python?

Nope. Dicts are, but sets aren't. I vote for a dict instead of a list of 2-tuples.

Perhaps a more important property is that each bloq appears only once, which isn't captured by set.

That's true, and a dict would capture that as well.

It's possible that networkx will shuffle things later anyways

I think it's less likely if we just traverse the graph and not modify it. But we can deal with any potential indeterminism due to networkx when we encounter it. AFAIK, this shouldn't be an issue.