[BUG] _categorical_exact does not always give the same result

[savyajha]

Describe the bug
When I run the test suite on nixos, the test_categorical_exact (and no other) fails repeatedly. It always fails in the same manner.

As I had found out while trying to debug this, turns out that the shortest_path function from networkx is not deterministic if there are multiple shortest paths available. There is a stack overflow answer which goes into more details. Turns out this particular lack of determinism is hitting us on nixos and causing the test to fail.

So the question is that if the function is using a shortest path and not the shortest path as may be on other systems, would that fall under bounds of expected behaviour?

To Reproduce
Run the test_categorical_exact on nixos. To drill into what wasn't working properly I broke down the _categorical_exact function and ran its steps manually which told me it was the path generation which was the problem.

[jmschrei]

Great work in debugging that issue. Do you have a suggestion for how to always get the same deterministic path out of that function? I agree that it's not sufficient to get a shortest path -- for reproducibility reasons, you need to get the same shortest path, or at least have it governed by a seed.

[savyajha]

The one way I can think of is to change that particular line to path = sorted(nx.all_shortest_paths(order_graph, source=(), target=tuple(range(d)), weight="weight"))[1], for example. This will sort all of them out and give you the same one.

I'm not sure if there is a better way of doing it.

[jmschrei]

Thanks. Would you mind checking to make sure that works on your machines? I'm in a bit of a time crunch due to faculty applications but I'll try to get to this soon, once you confirm.

[savyajha]

I'll check and get back. Good luck with the applications!

[savyajha]

I've opened a PR with the changes which seem to work. These changes lead to all the affected tests passing on both Fedora and NixOS.

[jmschrei]

I just released v1.0.2 containing your changes. Let me know if it works on your end.

[savyajha]

I just released v1.0.2 containing your changes. Let me know if it works on your end.

I just realised I made a typo in the PR I submitted which would cause the code to fail in case there was only one shortest path. I'm going to submit a PR with that typo (and therefore all the tests) changed.

[savyajha]

Apologies, here's the new PR: #1060

Edit: Also, version 1.0.2 and v1.0.2 with this patch applied both work on both Fedora and nixos for me. I also see they've passed your CI testing.

[savyajha]

Apologies for the ping, @jmschrei, but if you've got the time, please do have a look at the PR linked in my previous comment. It fixes an issue I'd overlooked in my first PR.

[jmschrei]

I'll release a new version this weekend. I'm trying to fix one other bug before doing so.