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 <dschult@colgate.edu>

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 <https://github.com/networkx/networkx/pull/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()