Fix to_vertex_cover (#4667)

Fix _alternating_dfs which manifested as defect in to_vertex_cover

2 files changed, 17 insertions, 7 deletions

diff --git a/networkx/algorithms/bipartite/matching.py b/networkx/algorithms/bipartite/matching.py
index 279e0160..2059d6bd 100644
--- a/networkx/algorithms/bipartite/matching.py
+++ b/networkx/algorithms/bipartite/matching.py
@@ -346,14 +346,14 @@ def _is_connected_by_alternating_path(G, v, matched_edges, unmatched_edges, targ
         will continue only through edges *not* in the given matching.
 
         """
-        if along_matched:
-            edges = itertools.cycle([matched_edges, unmatched_edges])
-        else:
-            edges = itertools.cycle([unmatched_edges, matched_edges])
         visited = set()
-        stack = [(u, iter(G[u]), next(edges))]
+        # Follow matched edges when depth is even,
+        # and follow unmatched edges when depth is odd.
+        initial_depth = 0 if along_matched else 1
+        stack = [(u, iter(G[u]), initial_depth)]
         while stack:
-            parent, children, valid_edges = stack[-1]
+            parent, children, depth = stack[-1]
+            valid_edges = matched_edges if depth % 2 else unmatched_edges
             try:
                 child = next(children)
                 if child not in visited:
@@ -361,7 +361,7 @@ def _is_connected_by_alternating_path(G, v, matched_edges, unmatched_edges, targ
                         if child in targets:
                             return True
                         visited.add(child)
-                        stack.append((child, iter(G[child]), next(edges)))
+                        stack.append((child, iter(G[child]), depth + 1))
             except StopIteration:
                 stack.pop()
         return False
diff --git a/networkx/algorithms/bipartite/tests/test_matching.py b/networkx/algorithms/bipartite/tests/test_matching.py
index d4fcd980..3c6cc35f 100644
--- a/networkx/algorithms/bipartite/tests/test_matching.py
+++ b/networkx/algorithms/bipartite/tests/test_matching.py
@@ -180,6 +180,16 @@ class TestMatching:
         for u, v in G.edges():
             assert u in vertex_cover or v in vertex_cover
 
+    def test_vertex_cover_issue_3306(self):
+        G = nx.Graph()
+        edges = [(0, 2), (1, 0), (1, 1), (1, 2), (2, 2)]
+        G.add_edges_from([((i, "L"), (j, "R")) for i, j in edges])
+
+        matching = maximum_matching(G)
+        vertex_cover = to_vertex_cover(G, matching)
+        for u, v in G.edges():
+            assert u in vertex_cover or v in vertex_cover
+
     def test_unorderable_nodes(self):
         a = object()
         b = object()