Repository: networkx/networkx

Issue:
hopcroft_karp_matching / to_vertex_cover bug
`to_vertex_cover` must give the **minimum vertex cover** as documented. Wasn't it fixed in #2384 ?
The following code gives random results:

```python
import networkx as nx

nodesU = ['r1','r2','r3','r4','r5','r6','r7','r8']
nodesV = ['c1','c2','c3','c4','c5','c6','c7','c8']
edges = [
        ('r1','c2'),('r1','c4'),('r1','c5'),('r1','c8'),
        ('r2','c1'),('r2','c2'),('r2','c3'),('r2','c6'),('r2','c7'),
        ('r3','c4'),('r3','c5'),
        ('r4','c2'),('r4','c8'),
        ('r5','c2'),('r5','c8'),
        ('r6','c1'),('r6','c2'),('r6','c3'),('r6','c5'),('r6','c6'),('r6','c7'),
        ('r7','c2'),('r7','c8'),
        ('r8','c2'),('r8','c4')]

G = nx.Graph()
G.add_nodes_from(nodesU, bipartite=0)
G.add_nodes_from(nodesV, bipartite=1)
G.add_edges_from(edges)
M = nx.bipartite.hopcroft_karp_matching(G, top_nodes = nodesU)
print('matchings M = ', M)
print('|M|  = ', len(M))

K = nx.bipartite.to_vertex_cover(G, M, top_nodes = nodesU)
print('minimum cover K = ', K)
print('|K|  = ', len(K))
```

Here are the results of multiple runs:
```
matchings M =  {'c1': 'r6', 'r7': 'c2', 'r5': 'c8', 'r1': 'c5', 'r8': 'c4', 'r6': 'c1', 'c5': 'r1', 'c8': 'r5', 'r2': 'c7', 'c7': 'r2', 'c2': 'r7', 'c4': 'r8'}
|M|  =  12
minimum cover K =  {'c1', 'c5', 'c7', 'c2', 'c8', 'c4'}
|K|  =  6

matchings M =  {'c6': 'r6', 'r6': 'c6', 'r1': 'c4', 'r4': 'c2', 'c3': 'r2', 'r5': 'c8', 'c5': 'r3', 'r3': 'c5', 'c8': 'r5', 'r2': 'c3', 'c4': 'r1', 'c2': 'r4'}
|M|  =  12
minimum cover K =  {'c6', 'r6', 'c4', 'c5', 'c2', 'c3', 'c8', 'r2'}
|K|  =  8

matchings M =  {'c8': 'r7', 'r7': 'c8', 'c1': 'r2', 'r3': 'c4', 'r6': 'c7', 'c5': 'r1', 'c2': 'r4', 'c7': 'r6', 'r4': 'c2', 'r2': 'c1', 'c4': 'r3', 'r1': 'c5'}
|M|  =  12
minimum cover K =  {'r2', 'c8', 'c4', 'c2', 'c5'}
|K|  =  5

matchings M =  {'r3': 'c4', 'r6': 'c1', 'r1': 'c5', 'c2': 'r7', 'r7': 'c2', 'c8': 'r5', 'r2': 'c7', 'c5': 'r1', 'r5': 'c8', 'c1': 'r6', 'c7': 'r2', 'c4': 'r3'}
|M|  =  12
minimum cover K =  {'c8', 'c5', 'c7', 'r6', 'c2', 'c4'}
|K|  =  6
```

I'm using networkx 2.2 on debian/python3 and windows miniconda3.
The graph is from: [http://tryalgo.org/en/matching/2016/08/05/konig/](http://tryalgo.org/en/matching/2016/08/05/konig/)

Also why `hopcroft_karp_matching` returns matchings and opposite edges ?

Discussion:
dschult: Nice!  Thank you!

I'll leave it up to you to say which is more clear, but you might consider (inside of list lookup) an if/else structure like:
```get_valid_edge = lambda depth: unmatched_edges if (depth % 2) else matched_edges```
Or you could even remove the function call `get_valid_edge` by putting the if/else where the function is used and shifting `depth` to start at 1/0 based on `along_matched`.

The test is very helpful!!
Thanks!
rossbar: > Or you could even remove the function call get_valid_edge by putting the if/else where the function is used and shifting depth to start at 1/0 based on along_matched.

IMO this would make things much more readable: +1 for this idea!

I also second the sentiment on the test - very nice!
studentofkyoto: Thanks a ton for the kind and prompt review.

If a bit more aggressive change is allowed, however, I would let the function simply recurse.
Worst case has O(n) depth when n is the number of vertices in the graph in interest, and I am kind of guessing the original intention is not to raise MaximumRecursionDepth but average-case should be O(log k n) where k is number of edges.

I understand the initial implementation was recursive before #2384 and #2386, but it seems like the reason that it was changed to iterative style is not because of `MaximumRecursionDepth`. As far as readability is concerned, I guess bringing recursive style back makes sense.

Also, I find it rather hard to write tests for function `_is_connected_by_alternating_path`. Guide me through with some advices and suggestions, will be much appreciated.
dschult: Recursion is not a good idea for algorithms in Python. Not only is there recursion depth issues (especially if it is O(n)... ), but there are memory and speed concerns. Recursion pushes the stack and loop programming into function and namespace programming, which might work fine in a compiled language setting, but is not ideal in interpreted languages like Python. We've been trying to remove recursive parts of the codebase.

Besides, most graph algorithms deal with stack and loops, so we're used to it. The recursion is not even that much easier to read. But I might be biased there. 

Anyway, if you could return to a stack/loop form instead of recursion I would appreciate it. 

As far as tests for `is_connected_by_alternating_path`, what difficulties are you having? Can you set up a small graph that should return True and another that should return False? Even better is to test each possible way that it could return False or True. But I haven't worked through the logic of the problem to figure out what they all are. That might be too much for a simple unit test setting.
studentofkyoto: Thanks a lot for the guidance.

> We've been trying to remove recursive parts of the codebase.

That was the part that I was wondering the most. Thanks for clearing it out for me.

> Besides, most graph algorithms deal with stack and loops, so we're used to it. The recursion is not even that much easier to read. But I might be biased there.

I understood. I will keep that in mind!
I stripped one commit from the top and force-pushed it.
(Newbie Question: Is it recommended to `reset && push --force` to revert, or make reverting commit?)

> As far as tests for is_connected_by_alternating_path, what difficulties are you having? 

Due to the symmetricity of following line, it will not be able to be tested if `along_matched=True` corresponds to `depth % 2 == 0`:
 https://github.com/networkx/networkx/blob/d9cb95edfad840302288f8a52d4df73beeeee713/networkx/algorithms/bipartite/matching.py#L372-L374

The private function call chain `to_vertex_cover` -> `_connected_by_alternating_paths` -> `_is_connected_by_alternating_path` -> `_alternating_dfs` seemed a bit awkward to me because they are not called anywhere else. But they are useful for sure (at least in my application), and I wish to impose more tests on them. I will make separate PR for them though.


> Even better is to test each possible way that it could return False or True. But I haven't worked through the logic of the problem to figure out what they all are. That might be too much for a simple unit test setting.

If I understood correctly, I ran the test you mentioned in my local:
```python3
import itertools as it
import networkx as nx
import pytest

@pytest.mark.parametrize('n_row, n_col', [(5, 5)])
def test_all_cases(n_row: int, n_col: int):
    # make all possible combination of bipartite graph
    for rights4left in it.product(*([[rs for i in range(1, n_col + 1) for rs in it.combinations(range(n_col), i)],] * n_row)):
        edges = [(i, j) for i, js in enumerate(rights4left) for j in js]

        G = nx.Graph()
        G.add_edges_from([((i, "L"), (j, "R")) for i, j in edges])

        try:
            matching = nx.bipartite.maximum_matching(G)
        except nx.exception.AmbiguousSolution:
            # covered by test cases with smaller `n_row, n_col`
            # Don't have to worry about it
            continue
        vertex_cover = nx.bipartite.to_vertex_cover(G, matching)
        for u, v in G.edges():
            assert u in vertex_cover or v in vertex_cover
```

I agree that it is not nice to include such test in CI.

Patch:
diff --git a/networkx/algorithms/bipartite/matching.py b/networkx/algorithms/bipartite/matching.py
index 279e01604..2059d6bdf 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/tournament.py b/networkx/algorithms/tournament.py
index 2205f5556..cedd2bc06 100644
--- a/networkx/algorithms/tournament.py
+++ b/networkx/algorithms/tournament.py
@@ -276,7 +276,6 @@ def is_reachable(G, s, t):
            tournaments."
            *Electronic Colloquium on Computational Complexity*. 2001.
            <http://eccc.hpi-web.de/report/2001/092/>
-
     """
 
     def two_neighborhood(G, v):


Test patch:
diff --git a/networkx/algorithms/bipartite/tests/test_matching.py b/networkx/algorithms/bipartite/tests/test_matching.py
index d4fcd9802..3c6cc35fd 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()
diff --git a/networkx/algorithms/tests/test_tournament.py b/networkx/algorithms/tests/test_tournament.py
index 8de6f7c3e..42a31f9be 100644
--- a/networkx/algorithms/tests/test_tournament.py
+++ b/networkx/algorithms/tests/test_tournament.py
@@ -1,132 +1,157 @@
 """Unit tests for the :mod:`networkx.algorithms.tournament` module."""
 from itertools import combinations
-
-
+import pytest
 from networkx import DiGraph
 from networkx.algorithms.tournament import is_reachable
 from networkx.algorithms.tournament import is_strongly_connected
 from networkx.algorithms.tournament import is_tournament
 from networkx.algorithms.tournament import random_tournament
 from networkx.algorithms.tournament import hamiltonian_path
+from networkx.algorithms.tournament import score_sequence
+from networkx.algorithms.tournament import tournament_matrix
+from networkx.algorithms.tournament import index_satisfying
+
+
+def test_condition_not_satisfied():
+    condition = lambda x: x > 0
+    iter_in = [0]
+    assert index_satisfying(iter_in, condition) == 1
+
+
+def test_empty_iterable():
+    condition = lambda x: x > 0
+    with pytest.raises(ValueError):
+        index_satisfying([], condition)
 
 
-class TestIsTournament:
-    """Unit tests for the :func:`networkx.tournament.is_tournament`
-    function.
+def test_is_tournament():
+    G = DiGraph()
+    G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (1, 3), (0, 2)])
+    assert is_tournament(G)
+
+
+def test_self_loops():
+    """A tournament must have no self-loops."""
+    G = DiGraph()
+    G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (1, 3), (0, 2)])
+    G.add_edge(0, 0)
+    assert not is_tournament(G)
+
+
+def test_missing_edges():
+    """A tournament must not have any pair of nodes without at least
+    one edge joining the pair.
 
     """
+    G = DiGraph()
+    G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (1, 3)])
+    assert not is_tournament(G)
+
 
-    def test_is_tournament(self):
-        G = DiGraph()
-        G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (1, 3), (0, 2)])
+def test_bidirectional_edges():
+    """A tournament must not have any pair of nodes with greater
+    than one edge joining the pair.
+
+    """
+    G = DiGraph()
+    G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (1, 3), (0, 2)])
+    G.add_edge(1, 0)
+    assert not is_tournament(G)
+
+
+def test_graph_is_tournament():
+    for _ in range(10):
+        G = random_tournament(5)
         assert is_tournament(G)
 
-    def test_self_loops(self):
-        """A tournament must have no self-loops."""
-        G = DiGraph()
-        G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (1, 3), (0, 2)])
-        G.add_edge(0, 0)
-        assert not is_tournament(G)
 
-    def test_missing_edges(self):
-        """A tournament must not have any pair of nodes without at least
-        one edge joining the pair.
+def test_graph_is_tournament_seed():
+    for _ in range(10):
+        G = random_tournament(5, seed=1)
+        assert is_tournament(G)
 
-        """
-        G = DiGraph()
-        G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (1, 3)])
-        assert not is_tournament(G)
 
-    def test_bidirectional_edges(self):
-        """A tournament must not have any pair of nodes with greater
-        than one edge joining the pair.
+def test_graph_is_tournament_one_node():
+    G = random_tournament(1)
+    assert is_tournament(G)
 
-        """
-        G = DiGraph()
-        G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (1, 3), (0, 2)])
-        G.add_edge(1, 0)
-        assert not is_tournament(G)
 
+def test_graph_is_tournament_zero_node():
+    G = random_tournament(0)
+    assert is_tournament(G)
 
-class TestRandomTournament:
-    """Unit tests for the :func:`networkx.tournament.random_tournament`
-    function.
 
-    """
+def test_hamiltonian_empty_graph():
+    path = hamiltonian_path(DiGraph())
+    assert len(path) == 0
 
-    def test_graph_is_tournament(self):
-        for n in range(10):
-            G = random_tournament(5)
-            assert is_tournament(G)
 
-    def test_graph_is_tournament_seed(self):
-        for n in range(10):
-            G = random_tournament(5, seed=1)
-            assert is_tournament(G)
+def test_path_is_hamiltonian():
+    G = DiGraph()
+    G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (1, 3), (0, 2)])
+    path = hamiltonian_path(G)
+    assert len(path) == 4
+    assert all(v in G[u] for u, v in zip(path, path[1:]))
 
 
-class TestHamiltonianPath:
-    """Unit tests for the :func:`networkx.tournament.hamiltonian_path`
-    function.
+def test_hamiltonian_cycle():
+    """Tests that :func:`networkx.tournament.hamiltonian_path`
+    returns a Hamiltonian cycle when provided a strongly connected
+    tournament.
 
     """
+    G = DiGraph()
+    G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (1, 3), (0, 2)])
+    path = hamiltonian_path(G)
+    assert len(path) == 4
+    assert all(v in G[u] for u, v in zip(path, path[1:]))
+    assert path[0] in G[path[-1]]
 
-    def test_path_is_hamiltonian(self):
-        G = DiGraph()
-        G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (1, 3), (0, 2)])
-        path = hamiltonian_path(G)
-        assert len(path) == 4
-        assert all(v in G[u] for u, v in zip(path, path[1:]))
 
-    def test_hamiltonian_cycle(self):
-        """Tests that :func:`networkx.tournament.hamiltonian_path`
-        returns a Hamiltonian cycle when provided a strongly connected
-        tournament.
+def test_score_sequence_edge():
+    G = DiGraph([(0, 1)])
+    assert score_sequence(G) == [0, 1]
 
-        """
-        G = DiGraph()
-        G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (1, 3), (0, 2)])
-        path = hamiltonian_path(G)
-        assert len(path) == 4
-        assert all(v in G[u] for u, v in zip(path, path[1:]))
-        assert path[0] in G[path[-1]]
 
+def test_score_sequence_triangle():
+    G = DiGraph([(0, 1), (1, 2), (2, 0)])
+    assert score_sequence(G) == [1, 1, 1]
 
-class TestReachability:
-    """Unit tests for the :func:`networkx.tournament.is_reachable`
-    function.
 
-    """
+def test_tournament_matrix():
+    np = pytest.importorskip("numpy")
+    npt = pytest.importorskip("numpy.testing")
+    G = DiGraph([(0, 1)])
+    m = tournament_matrix(G)
+    npt.assert_array_equal(m.todense(), np.array([[0, 1], [-1, 0]]))
 
-    def test_reachable_pair(self):
-        """Tests for a reachable pair of nodes."""
-        G = DiGraph([(0, 1), (1, 2), (2, 0)])
-        assert is_reachable(G, 0, 2)
 
-    def test_same_node_is_reachable(self):
-        """Tests that a node is always reachable from itself."""
-        # G is an arbitrary tournament on ten nodes.
-        G = DiGraph(sorted(p) for p in combinations(range(10), 2))
-        assert all(is_reachable(G, v, v) for v in G)
+def test_reachable_pair():
+    """Tests for a reachable pair of nodes."""
+    G = DiGraph([(0, 1), (1, 2), (2, 0)])
+    assert is_reachable(G, 0, 2)
 
-    def test_unreachable_pair(self):
-        """Tests for an unreachable pair of nodes."""
-        G = DiGraph([(0, 1), (0, 2), (1, 2)])
-        assert not is_reachable(G, 1, 0)
 
+def test_same_node_is_reachable():
+    """Tests that a node is always reachable from it."""
+    # G is an arbitrary tournament on ten nodes.
+    G = DiGraph(sorted(p) for p in combinations(range(10), 2))
+    assert all(is_reachable(G, v, v) for v in G)
 
-class TestStronglyConnected:
-    """Unit tests for the
-    :func:`networkx.tournament.is_strongly_connected` function.
 
-    """
+def test_unreachable_pair():
+    """Tests for an unreachable pair of nodes."""
+    G = DiGraph([(0, 1), (0, 2), (1, 2)])
+    assert not is_reachable(G, 1, 0)
+
+
+def test_is_strongly_connected():
+    """Tests for a strongly connected tournament."""
+    G = DiGraph([(0, 1), (1, 2), (2, 0)])
+    assert is_strongly_connected(G)
 
-    def test_is_strongly_connected(self):
-        """Tests for a strongly connected tournament."""
-        G = DiGraph([(0, 1), (1, 2), (2, 0)])
-        assert is_strongly_connected(G)
 
-    def test_not_strongly_connected(self):
-        """Tests for a tournament that is not strongly connected."""
-        G = DiGraph([(0, 1), (0, 2), (1, 2)])
-        assert not is_strongly_connected(G)
+def test_not_strongly_connected():
+    """Tests for a tournament that is not strongly connected."""
+    G = DiGraph([(0, 1), (0, 2), (1, 2)])
+    assert not is_strongly_connected(G)