Repository: networkx/networkx

Issue:
Minimum cycle basis incorrect
<!-- If you have a general question about NetworkX, please use the discussions tab to create a new discussion -->

<!--- Provide a general summary of the issue in the Title above -->

### Current Behavior
Consider the complete weighted graph on the vertices 0, 1, 2, 3 with edge weights
```
01: 1
12: 1
23: 1
03: 1
13: 10
02: 10
```
A cycle basis for this graph is given by the cycles
```
0123
012
013
```
The weights of these cycles are
```
0123: 4
012: 12
013: 12
```

However, the nx.minimum_cycle_basis function returns the basis
`[[0, 1, 2], [0, 1, 3], [0, 2, 3]]`

All of these cycles have weight 12. Thus this is not a minimum cycle basis.

<!--- Tell us what happens instead of the expected behavior -->

### Expected Behavior
A valid minimum cycle basis is 
`[[0, 1, 2], [0, 1, 3], [0, 1, 2, 3]]`

<!--- Tell us what should happen -->

### Steps to Reproduce

<!--- Provide a minimal example that reproduces the bug -->
```python
import networkx as nx
G = nx.Graph()
G.add_weighted_edges_from([(0, 1, 1.), (1, 2, 1.), (2, 3, 1.), (3, 0, 1.), (0, 2, 10.), (1, 3, 10.)])
print(nx.minimum_cycle_basis(G))
# [[0, 1, 2], [0, 1, 3], [0, 2, 3]]
```
### Environment

<!--- Please provide details about your local environment -->

Python version: 3.10.12
NetworkX version: 3.1

### Additional context

<!--- Add any other context about the problem here, screenshots, etc. -->


Discussion:
mbr085: Thank you @dschult . I am impressed. Well done. It seems to work as I expect. I will test it and let you know if I find any problems. 

Patch:
diff --git a/networkx/algorithms/cycles.py b/networkx/algorithms/cycles.py
index 19c1c9959..16c87c43c 100644
--- a/networkx/algorithms/cycles.py
+++ b/networkx/algorithms/cycles.py
@@ -4,7 +4,7 @@ Cycle finding algorithms
 ========================
 """
 
-from collections import defaultdict
+from collections import Counter, defaultdict
 from itertools import combinations, product
 from math import inf
 
@@ -50,7 +50,7 @@ def cycle_basis(G, root=None):
     >>> G = nx.Graph()
     >>> nx.add_cycle(G, [0, 1, 2, 3])
     >>> nx.add_cycle(G, [0, 3, 4, 5])
-    >>> print(nx.cycle_basis(G, 0))
+    >>> nx.cycle_basis(G, 0)
     [[3, 4, 5, 0], [1, 2, 3, 0]]
 
     Notes
@@ -1053,8 +1053,8 @@ def minimum_cycle_basis(G, weight=None):
     >>> G = nx.Graph()
     >>> nx.add_cycle(G, [0, 1, 2, 3])
     >>> nx.add_cycle(G, [0, 3, 4, 5])
-    >>> print([sorted(c) for c in nx.minimum_cycle_basis(G)])
-    [[0, 1, 2, 3], [0, 3, 4, 5]]
+    >>> nx.minimum_cycle_basis(G)
+    [[5, 4, 3, 0], [3, 2, 1, 0]]
 
     References:
         [1] Kavitha, Telikepalli, et al. "An O(m^2n) Algorithm for
@@ -1074,85 +1074,87 @@ def minimum_cycle_basis(G, weight=None):
     )
 
 
-def _min_cycle_basis(comp, weight):
+def _min_cycle_basis(G, weight):
     cb = []
     # We  extract the edges not in a spanning tree. We do not really need a
     # *minimum* spanning tree. That is why we call the next function with
     # weight=None. Depending on implementation, it may be faster as well
-    spanning_tree_edges = list(nx.minimum_spanning_edges(comp, weight=None, data=False))
-    edges_excl = [frozenset(e) for e in comp.edges() if e not in spanning_tree_edges]
-    N = len(edges_excl)
+    tree_edges = list(nx.minimum_spanning_edges(G, weight=None, data=False))
+    chords = G.edges - tree_edges - {(v, u) for u, v in tree_edges}
 
     # We maintain a set of vectors orthogonal to sofar found cycles
-    set_orth = [{edge} for edge in edges_excl]
-    for k in range(N):
+    set_orth = [{edge} for edge in chords]
+    while set_orth:
+        base = set_orth.pop()
         # kth cycle is "parallel" to kth vector in set_orth
-        new_cycle = _min_cycle(comp, set_orth[k], weight=weight)
-        cb.append(list(set().union(*new_cycle)))
+        cycle_edges = _min_cycle(G, base, weight)
+        cb.append([v for u, v in cycle_edges])
+
         # now update set_orth so that k+1,k+2... th elements are
         # orthogonal to the newly found cycle, as per [p. 336, 1]
-        base = set_orth[k]
-        set_orth[k + 1 :] = [
-            orth ^ base if len(orth & new_cycle) % 2 else orth
-            for orth in set_orth[k + 1 :]
+        set_orth = [
+            (
+                {e for e in orth if e not in base if e[::-1] not in base}
+                | {e for e in base if e not in orth if e[::-1] not in orth}
+            )
+            if any((e in orth or e[::-1] in orth) for e in cycle_edges)
+            else orth
+            for orth in set_orth
         ]
     return cb
 
 
-def _min_cycle(G, orth, weight=None):
+def _min_cycle(G, orth, weight):
     """
     Computes the minimum weight cycle in G,
     orthogonal to the vector orth as per [p. 338, 1]
+    Use (u, 1) to indicate the lifted copy of u (denoted u' in paper).
     """
-    T = nx.Graph()
-
-    nodes_idx = {node: idx for idx, node in enumerate(G.nodes())}
-    idx_nodes = {idx: node for node, idx in nodes_idx.items()}
-
-    nnodes = len(nodes_idx)
+    Gi = nx.Graph()
 
-    # Add 2 copies of each edge in G to T. If edge is in orth, add cross edge;
-    # otherwise in-plane edge
-    for u, v, data in G.edges(data=True):
-        uidx, vidx = nodes_idx[u], nodes_idx[v]
-        edge_w = data.get(weight, 1)
-        if frozenset((u, v)) in orth:
-            T.add_edges_from(
-                [(uidx, nnodes + vidx), (nnodes + uidx, vidx)], weight=edge_w
-            )
+    # Add 2 copies of each edge in G to Gi.
+    # If edge is in orth, add cross edge; otherwise in-plane edge
+    for u, v, wt in G.edges(data=weight, default=1):
+        if (u, v) in orth or (v, u) in orth:
+            Gi.add_edges_from([(u, (v, 1)), ((u, 1), v)], Gi_weight=wt)
         else:
-            T.add_edges_from(
-                [(uidx, vidx), (nnodes + uidx, nnodes + vidx)], weight=edge_w
-            )
+            Gi.add_edges_from([(u, v), ((u, 1), (v, 1))], Gi_weight=wt)
 
-    all_shortest_pathlens = dict(nx.shortest_path_length(T, weight=weight))
-    cross_paths_w_lens = {
-        n: all_shortest_pathlens[n][nnodes + n] for n in range(nnodes)
-    }
+    # find the shortest length in Gi between n and (n, 1) for each n
+    # Note: Use "Gi_weight" for name of weight attribute
+    spl = nx.shortest_path_length
+    lift = {n: spl(Gi, source=n, target=(n, 1), weight="Gi_weight") for n in G}
 
-    # Now compute shortest paths in T, which translates to cyles in G
-    start = min(cross_paths_w_lens, key=cross_paths_w_lens.get)
-    end = nnodes + start
-    min_path = nx.shortest_path(T, source=start, target=end, weight="weight")
+    # Now compute that short path in Gi, which translates to a cycle in G
+    start = min(lift, key=lift.get)
+    end = (start, 1)
+    min_path_i = nx.shortest_path(Gi, source=start, target=end, weight="Gi_weight")
 
-    # Now we obtain the actual path, re-map nodes in T to those in G
-    min_path_nodes = [node if node < nnodes else node - nnodes for node in min_path]
-    # Now remove the edges that occur two times
-    mcycle_pruned = _path_to_cycle(min_path_nodes)
+    # Now we obtain the actual path, re-map nodes in Gi to those in G
+    min_path = [n if n in G else n[0] for n in min_path_i]
 
-    return {frozenset((idx_nodes[u], idx_nodes[v])) for u, v in mcycle_pruned}
-
-
-def _path_to_cycle(path):
-    """
-    Removes the edges from path that occur even number of times.
-    Returns a set of edges
-    """
-    edges = set()
-    for edge in pairwise(path):
-        # Toggle whether to keep the current edge.
-        edges ^= {edge}
-    return edges
+    # Now remove the edges that occur two times
+    # two passes: flag which edges get kept, then build it
+    edgelist = list(pairwise(min_path))
+    edgeset = set()
+    for e in edgelist:
+        if e in edgeset:
+            edgeset.remove(e)
+        elif e[::-1] in edgeset:
+            edgeset.remove(e[::-1])
+        else:
+            edgeset.add(e)
+
+    min_edgelist = []
+    for e in edgelist:
+        if e in edgeset:
+            min_edgelist.append(e)
+            edgeset.remove(e)
+        elif e[::-1] in edgeset:
+            min_edgelist.append(e[::-1])
+            edgeset.remove(e[::-1])
+
+    return min_edgelist
 
 
 @not_implemented_for("directed")


Test patch:
diff --git a/networkx/algorithms/tests/test_cycles.py b/networkx/algorithms/tests/test_cycles.py
index 75557bc40..eae7b07d7 100644
--- a/networkx/algorithms/tests/test_cycles.py
+++ b/networkx/algorithms/tests/test_cycles.py
@@ -4,16 +4,14 @@ from random import shuffle
 
 import pytest
 
-import networkx
 import networkx as nx
-from networkx.algorithms import find_cycle, minimum_cycle_basis
 from networkx.algorithms.traversal.edgedfs import FORWARD, REVERSE
 
 
 class TestCycles:
     @classmethod
     def setup_class(cls):
-        G = networkx.Graph()
+        G = nx.Graph()
         nx.add_cycle(G, [0, 1, 2, 3])
         nx.add_cycle(G, [0, 3, 4, 5])
         nx.add_cycle(G, [0, 1, 6, 7, 8])
@@ -29,30 +27,30 @@ class TestCycles:
 
     def test_cycle_basis(self):
         G = self.G
-        cy = networkx.cycle_basis(G, 0)
+        cy = nx.cycle_basis(G, 0)
         sort_cy = sorted(sorted(c) for c in cy)
         assert sort_cy == [[0, 1, 2, 3], [0, 1, 6, 7, 8], [0, 3, 4, 5]]
-        cy = networkx.cycle_basis(G, 1)
+        cy = nx.cycle_basis(G, 1)
         sort_cy = sorted(sorted(c) for c in cy)
         assert sort_cy == [[0, 1, 2, 3], [0, 1, 6, 7, 8], [0, 3, 4, 5]]
-        cy = networkx.cycle_basis(G, 9)
+        cy = nx.cycle_basis(G, 9)
         sort_cy = sorted(sorted(c) for c in cy)
         assert sort_cy == [[0, 1, 2, 3], [0, 1, 6, 7, 8], [0, 3, 4, 5]]
         # test disconnected graphs
         nx.add_cycle(G, "ABC")
-        cy = networkx.cycle_basis(G, 9)
+        cy = nx.cycle_basis(G, 9)
         sort_cy = sorted(sorted(c) for c in cy[:-1]) + [sorted(cy[-1])]
         assert sort_cy == [[0, 1, 2, 3], [0, 1, 6, 7, 8], [0, 3, 4, 5], ["A", "B", "C"]]
 
     def test_cycle_basis2(self):
         with pytest.raises(nx.NetworkXNotImplemented):
             G = nx.DiGraph()
-            cy = networkx.cycle_basis(G, 0)
+            cy = nx.cycle_basis(G, 0)
 
     def test_cycle_basis3(self):
         with pytest.raises(nx.NetworkXNotImplemented):
             G = nx.MultiGraph()
-            cy = networkx.cycle_basis(G, 0)
+            cy = nx.cycle_basis(G, 0)
 
     def test_cycle_basis_ordered(self):
         # see gh-6654 replace sets with (ordered) dicts
@@ -703,50 +701,50 @@ class TestFindCycle:
 
     def test_graph_nocycle(self):
         G = nx.Graph(self.edges)
-        pytest.raises(nx.exception.NetworkXNoCycle, find_cycle, G, self.nodes)
+        pytest.raises(nx.exception.NetworkXNoCycle, nx.find_cycle, G, self.nodes)
 
     def test_graph_cycle(self):
         G = nx.Graph(self.edges)
         G.add_edge(2, 0)
-        x = list(find_cycle(G, self.nodes))
+        x = list(nx.find_cycle(G, self.nodes))
         x_ = [(0, 1), (1, 2), (2, 0)]
         assert x == x_
 
     def test_graph_orientation_none(self):
         G = nx.Graph(self.edges)
         G.add_edge(2, 0)
-        x = list(find_cycle(G, self.nodes, orientation=None))
+        x = list(nx.find_cycle(G, self.nodes, orientation=None))
         x_ = [(0, 1), (1, 2), (2, 0)]
         assert x == x_
 
     def test_graph_orientation_original(self):
         G = nx.Graph(self.edges)
         G.add_edge(2, 0)
-        x = list(find_cycle(G, self.nodes, orientation="original"))
+        x = list(nx.find_cycle(G, self.nodes, orientation="original"))
         x_ = [(0, 1, FORWARD), (1, 2, FORWARD), (2, 0, FORWARD)]
         assert x == x_
 
     def test_digraph(self):
         G = nx.DiGraph(self.edges)
-        x = list(find_cycle(G, self.nodes))
+        x = list(nx.find_cycle(G, self.nodes))
         x_ = [(0, 1), (1, 0)]
         assert x == x_
 
     def test_digraph_orientation_none(self):
         G = nx.DiGraph(self.edges)
-        x = list(find_cycle(G, self.nodes, orientation=None))
+        x = list(nx.find_cycle(G, self.nodes, orientation=None))
         x_ = [(0, 1), (1, 0)]
         assert x == x_
 
     def test_digraph_orientation_original(self):
         G = nx.DiGraph(self.edges)
-        x = list(find_cycle(G, self.nodes, orientation="original"))
+        x = list(nx.find_cycle(G, self.nodes, orientation="original"))
         x_ = [(0, 1, FORWARD), (1, 0, FORWARD)]
         assert x == x_
 
     def test_multigraph(self):
         G = nx.MultiGraph(self.edges)
-        x = list(find_cycle(G, self.nodes))
+        x = list(nx.find_cycle(G, self.nodes))
         x_ = [(0, 1, 0), (1, 0, 1)]  # or (1, 0, 2)
         # Hash randomization...could be any edge.
         assert x[0] == x_[0]
@@ -754,26 +752,26 @@ class TestFindCycle:
 
     def test_multidigraph(self):
         G = nx.MultiDiGraph(self.edges)
-        x = list(find_cycle(G, self.nodes))
+        x = list(nx.find_cycle(G, self.nodes))
         x_ = [(0, 1, 0), (1, 0, 0)]  # (1, 0, 1)
         assert x[0] == x_[0]
         assert x[1][:2] == x_[1][:2]
 
     def test_digraph_ignore(self):
         G = nx.DiGraph(self.edges)
-        x = list(find_cycle(G, self.nodes, orientation="ignore"))
+        x = list(nx.find_cycle(G, self.nodes, orientation="ignore"))
         x_ = [(0, 1, FORWARD), (1, 0, FORWARD)]
         assert x == x_
 
     def test_digraph_reverse(self):
         G = nx.DiGraph(self.edges)
-        x = list(find_cycle(G, self.nodes, orientation="reverse"))
+        x = list(nx.find_cycle(G, self.nodes, orientation="reverse"))
         x_ = [(1, 0, REVERSE), (0, 1, REVERSE)]
         assert x == x_
 
     def test_multidigraph_ignore(self):
         G = nx.MultiDiGraph(self.edges)
-        x = list(find_cycle(G, self.nodes, orientation="ignore"))
+        x = list(nx.find_cycle(G, self.nodes, orientation="ignore"))
         x_ = [(0, 1, 0, FORWARD), (1, 0, 0, FORWARD)]  # or (1, 0, 1, 1)
         assert x[0] == x_[0]
         assert x[1][:2] == x_[1][:2]
@@ -782,7 +780,7 @@ class TestFindCycle:
     def test_multidigraph_ignore2(self):
         # Loop traversed an edge while ignoring its orientation.
         G = nx.MultiDiGraph([(0, 1), (1, 2), (1, 2)])
-        x = list(find_cycle(G, [0, 1, 2], orientation="ignore"))
+        x = list(nx.find_cycle(G, [0, 1, 2], orientation="ignore"))
         x_ = [(1, 2, 0, FORWARD), (1, 2, 1, REVERSE)]
         assert x == x_
 
@@ -794,7 +792,7 @@ class TestFindCycle:
         G = nx.MultiDiGraph([(0, 1), (1, 2), (2, 3), (4, 2)])
         pytest.raises(
             nx.exception.NetworkXNoCycle,
-            find_cycle,
+            nx.find_cycle,
             G,
             [0, 1, 2, 3, 4],
             orientation="original",
@@ -803,9 +801,9 @@ class TestFindCycle:
     def test_dag(self):
         G = nx.DiGraph([(0, 1), (0, 2), (1, 2)])
         pytest.raises(
-            nx.exception.NetworkXNoCycle, find_cycle, G, orientation="original"
+            nx.exception.NetworkXNoCycle, nx.find_cycle, G, orientation="original"
         )
-        x = list(find_cycle(G, orientation="ignore"))
+        x = list(nx.find_cycle(G, orientation="ignore"))
         assert x == [(0, 1, FORWARD), (1, 2, FORWARD), (0, 2, REVERSE)]
 
     def test_prev_explored(self):
@@ -813,7 +811,7 @@ class TestFindCycle:
 
         G = nx.DiGraph()
         G.add_edges_from([(1, 0), (2, 0), (1, 2), (2, 1)])
-        pytest.raises(nx.NetworkXNoCycle, find_cycle, G, source=0)
+        pytest.raises(nx.NetworkXNoCycle, nx.find_cycle, G, source=0)
         x = list(nx.find_cycle(G, 1))
         x_ = [(1, 2), (2, 1)]
         assert x == x_
@@ -831,8 +829,8 @@ class TestFindCycle:
 
         G = nx.DiGraph()
         G.add_edges_from([(1, 2), (2, 0), (3, 1), (3, 2)])
-        pytest.raises(nx.NetworkXNoCycle, find_cycle, G, source=0)
-        pytest.raises(nx.NetworkXNoCycle, find_cycle, G)
+        pytest.raises(nx.NetworkXNoCycle, nx.find_cycle, G, source=0)
+        pytest.raises(nx.NetworkXNoCycle, nx.find_cycle, G)
 
 
 def assert_basis_equal(a, b):
@@ -848,12 +846,12 @@ class TestMinimumCycles:
         cls.diamond_graph = T
 
     def test_unweighted_diamond(self):
-        mcb = minimum_cycle_basis(self.diamond_graph)
-        assert_basis_equal([sorted(c) for c in mcb], [[1, 2, 4], [2, 3, 4]])
+        mcb = nx.minimum_cycle_basis(self.diamond_graph)
+        assert_basis_equal(mcb, [[2, 4, 1], [3, 4, 2]])
 
     def test_weighted_diamond(self):
-        mcb = minimum_cycle_basis(self.diamond_graph, weight="weight")
-        assert_basis_equal([sorted(c) for c in mcb], [[1, 2, 4], [1, 2, 3, 4]])
+        mcb = nx.minimum_cycle_basis(self.diamond_graph, weight="weight")
+        assert_basis_equal(mcb, [[2, 4, 1], [4, 3, 2, 1]])
 
     def test_dimensionality(self):
         # checks |MCB|=|E|-|V|+|NC|
@@ -864,17 +862,49 @@ class TestMinimumCycles:
             nedges = rg.number_of_edges()
             ncomp = nx.number_connected_components(rg)
 
-            dim_mcb = len(minimum_cycle_basis(rg))
+            dim_mcb = len(nx.minimum_cycle_basis(rg))
             assert dim_mcb == nedges - nnodes + ncomp
 
     def test_complete_graph(self):
         cg = nx.complete_graph(5)
-        mcb = minimum_cycle_basis(cg)
+        mcb = nx.minimum_cycle_basis(cg)
         assert all(len(cycle) == 3 for cycle in mcb)
 
     def test_tree_graph(self):
         tg = nx.balanced_tree(3, 3)
-        assert not minimum_cycle_basis(tg)
+        assert not nx.minimum_cycle_basis(tg)
+
+    def test_petersen_graph(self):
+        G = nx.petersen_graph()
+        mcb = list(nx.minimum_cycle_basis(G))
+        expected = [
+            [4, 9, 7, 5, 0],
+            [1, 2, 3, 4, 0],
+            [1, 6, 8, 5, 0],
+            [4, 3, 8, 5, 0],
+            [1, 6, 9, 4, 0],
+            [1, 2, 7, 5, 0],
+        ]
+        assert len(mcb) == len(expected)
+        assert all(c in expected for c in mcb)
+
+        # check that order of the nodes is a path
+        for c in mcb:
+            assert all(G.has_edge(u, v) for u, v in nx.utils.pairwise(c, cyclic=True))
+
+    def test_gh6787_and_edge_attribute_names(self):
+        G = nx.cycle_graph(4)
+        G.add_weighted_edges_from([(0, 2, 10), (1, 3, 10)], weight="dist")
+        expected = [[1, 3, 0], [3, 2, 1, 0], [1, 2, 0]]
+        mcb = list(nx.minimum_cycle_basis(G, weight="dist"))
+        assert len(mcb) == len(expected)
+        assert all(c in expected for c in mcb)
+
+        # test not using a weight with weight attributes
+        expected = [[1, 3, 0], [1, 2, 0], [3, 2, 0]]
+        mcb = list(nx.minimum_cycle_basis(G))
+        assert len(mcb) == len(expected)
+        assert all(c in expected for c in mcb)
 
 
 class TestGirth: