From 8b87a5b099e2ff9769d8074b350dc27c96434d8e Mon Sep 17 00:00:00 2001 From: Efrem Braun Date: Fri, 21 Apr 2023 14:16:11 -0400 Subject: Make cycle_basis() deterministic (#6654) Replace sets with dict keys to make cycle_basis deterministic with respect to node ordering. Co-authored-by: Dan Schult --- doc/release/release_dev.rst | 3 +++ networkx/algorithms/cycles.py | 7 ++++--- networkx/algorithms/tests/test_cycles.py | 11 +++++++++++ 3 files changed, 18 insertions(+), 3 deletions(-) diff --git a/doc/release/release_dev.rst b/doc/release/release_dev.rst index 59bffe0c..36021135 100644 --- a/doc/release/release_dev.rst +++ b/doc/release/release_dev.rst @@ -23,6 +23,9 @@ X contributors. Highlights include: Improvements ------------ +- [`#6654 `_] + Function ``cycle_basis`` switched from using Python sets to dicts so the + results are now deterministic (not dependent on order reported by a set). API Changes ----------- diff --git a/networkx/algorithms/cycles.py b/networkx/algorithms/cycles.py index 6c5f7d48..fb6b7170 100644 --- a/networkx/algorithms/cycles.py +++ b/networkx/algorithms/cycles.py @@ -64,11 +64,11 @@ def cycle_basis(G, root=None): -------- simple_cycles """ - gnodes = set(G.nodes()) + gnodes = dict.fromkeys(G) # set-like object that maintains node order cycles = [] while gnodes: # loop over connected components if root is None: - root = gnodes.pop() + root = gnodes.popitem()[0] stack = [root] pred = {root: root} used = {root: set()} @@ -92,7 +92,8 @@ def cycle_basis(G, root=None): cycle.append(p) cycles.append(cycle) used[nbr].add(z) - gnodes -= set(pred) + for node in pred: + gnodes.pop(node, None) root = None return cycles diff --git a/networkx/algorithms/tests/test_cycles.py b/networkx/algorithms/tests/test_cycles.py index 3c4108f5..a493528c 100644 --- a/networkx/algorithms/tests/test_cycles.py +++ b/networkx/algorithms/tests/test_cycles.py @@ -53,6 +53,17 @@ class TestCycles: G = nx.MultiGraph() cy = networkx.cycle_basis(G, 0) + def test_cycle_basis_ordered(self): + # see gh-6654 replace sets with (ordered) dicts + G = nx.cycle_graph(5) + G.update(nx.cycle_graph(range(3, 8))) + cbG = nx.cycle_basis(G) + + perm = {1: 0, 0: 1} # switch 0 and 1 + H = nx.relabel_nodes(G, perm) + cbH = [[perm.get(n, n) for n in cyc] for cyc in nx.cycle_basis(H)] + assert cbG == cbH + def test_cycle_basis_self_loop(self): """Tests the function for graphs with self loops""" G = nx.Graph() -- cgit v1.2.1