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.

[anurudhp]

@mpharrigan should the bloq author ensure that each unique bloq in the BloqCountT occurs only once? i.e. is something like this valid:

counts = set()
if condition_1: counts.add((XGate(), 1))
if condition_2: counts.add((XGate(), 2))
return counts

This luckily works as long as the frequencies are different, but fails if they are equal.

[fdmalone]

^^^ I've been caught out by this before

[mpharrigan]

@anurudhp I think that's what this issue is about. If we change it to use dictionaries, you'd have to do something like

counts = defaultdict(lambda: 0)
if condition_1: counts[XGate()] += 1
if condition_2: counts[XGate()] += 2
return counts

[mpharrigan]

My latest thoughts: I think this is still a good idea. IMO, the execution of this change should go through a mini deprecation cycle. Since build_call_graph is not supposed to be called by users directly, we can change its definition to return either a set or a dict; and change the internal uses of the function to turn sets into dictionaries; emit a deprecation warning if a set is encountered; and change all the existing implementations at our leisure to use dictionaries; eventually remove the type annotation for set; and even more eventually, remove the defensive coding within the consumers of build_call_graph.

[mpharrigan]

This is done thanks to @dstrain115