### view env/lib/python3.9/site-packages/networkx/algorithms/bipartite/tests/test_matching.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
line wrap: on
line source
```
"""Unit tests for the :mod:`networkx.algorithms.bipartite.matching` module."""
import itertools

import networkx as nx

import pytest

from networkx.algorithms.bipartite.matching import eppstein_matching
from networkx.algorithms.bipartite.matching import hopcroft_karp_matching
from networkx.algorithms.bipartite.matching import maximum_matching
from networkx.algorithms.bipartite.matching import minimum_weight_full_matching
from networkx.algorithms.bipartite.matching import to_vertex_cover

class TestMatching:
"""Tests for bipartite matching algorithms."""

def setup(self):
"""Creates a bipartite graph for use in testing matching algorithms.

The bipartite graph has a maximum cardinality matching that leaves
vertex 1 and vertex 10 unmatched. The first six numbers are the left
vertices and the next six numbers are the right vertices.

"""
self.simple_graph = nx.complete_bipartite_graph(2, 3)
self.simple_solution = {0: 2, 1: 3, 2: 0, 3: 1}

edges = [(0, 7), (0, 8), (2, 6), (2, 9), (3, 8), (4, 8), (4, 9), (5, 11)]
self.top_nodes = set(range(6))
self.graph = nx.Graph()

# Example bipartite graph from issue 2127
G = nx.Graph()
[
(1, "C"),
(1, "B"),
(0, "G"),
(1, "F"),
(1, "E"),
(0, "C"),
(1, "D"),
(1, "I"),
(0, "A"),
(0, "D"),
(0, "F"),
(0, "E"),
(0, "H"),
(1, "G"),
(1, "A"),
(0, "I"),
(0, "B"),
(1, "H"),
]
)
G.add_edge((1, "C"), (0, "A"))
G.add_edge((1, "B"), (0, "A"))
G.add_edge((0, "G"), (1, "I"))
G.add_edge((0, "G"), (1, "H"))
G.add_edge((1, "F"), (0, "A"))
G.add_edge((1, "F"), (0, "C"))
G.add_edge((1, "F"), (0, "E"))
G.add_edge((1, "E"), (0, "A"))
G.add_edge((1, "E"), (0, "C"))
G.add_edge((0, "C"), (1, "D"))
G.add_edge((0, "C"), (1, "I"))
G.add_edge((0, "C"), (1, "G"))
G.add_edge((0, "C"), (1, "H"))
G.add_edge((1, "D"), (0, "A"))
G.add_edge((1, "I"), (0, "A"))
G.add_edge((1, "I"), (0, "E"))
G.add_edge((0, "A"), (1, "G"))
G.add_edge((0, "A"), (1, "H"))
G.add_edge((0, "E"), (1, "G"))
G.add_edge((0, "E"), (1, "H"))
self.disconnected_graph = G

def check_match(self, matching):
"""Asserts that the matching is what we expect from the bipartite graph
constructed in the :meth:`setup` fixture.

"""
# For the sake of brevity, rename `matching` to `M`.
M = matching
matched_vertices = frozenset(itertools.chain(*M.items()))
# Assert that the maximum number of vertices (10) is matched.
assert matched_vertices == frozenset(range(12)) - {1, 10}
# Assert that no vertex appears in two edges, or in other words, that
# the matching (u, v) and (v, u) both appear in the matching
# dictionary.
assert all(u == M[M[u]] for u in range(12) if u in M)

def check_vertex_cover(self, vertices):
"""Asserts that the given set of vertices is the vertex cover we
expected from the bipartite graph constructed in the :meth:`setup`
fixture.

"""
# By Konig's theorem, the number of edges in a maximum matching equals
# the number of vertices in a minimum vertex cover.
assert len(vertices) == 5
# Assert that the set is truly a vertex cover.
for (u, v) in self.graph.edges():
assert u in vertices or v in vertices
# TODO Assert that the vertices are the correct ones.

def test_eppstein_matching(self):
"""Tests that David Eppstein's implementation of the Hopcroft--Karp
algorithm produces a maximum cardinality matching.

"""
self.check_match(eppstein_matching(self.graph, self.top_nodes))

def test_hopcroft_karp_matching(self):
"""Tests that the Hopcroft--Karp algorithm produces a maximum
cardinality matching in a bipartite graph.

"""
self.check_match(hopcroft_karp_matching(self.graph, self.top_nodes))

def test_to_vertex_cover(self):
"""Test for converting a maximum matching to a minimum vertex cover."""
matching = maximum_matching(self.graph, self.top_nodes)
vertex_cover = to_vertex_cover(self.graph, matching, self.top_nodes)
self.check_vertex_cover(vertex_cover)

def test_eppstein_matching_simple(self):
match = eppstein_matching(self.simple_graph)
assert match == self.simple_solution

def test_hopcroft_karp_matching_simple(self):
match = hopcroft_karp_matching(self.simple_graph)
assert match == self.simple_solution

def test_eppstein_matching_disconnected(self):
with pytest.raises(nx.AmbiguousSolution):
match = eppstein_matching(self.disconnected_graph)

def test_hopcroft_karp_matching_disconnected(self):
with pytest.raises(nx.AmbiguousSolution):
match = hopcroft_karp_matching(self.disconnected_graph)

def test_issue_2127(self):
"""Test from issue 2127"""
# Build the example DAG
G = nx.DiGraph()

tc = nx.transitive_closure(G)
btc = nx.Graph()

# Create a bipartite graph based on the transitive closure of G
for v in tc.nodes():

for u, v in tc.edges():
btc.add_edge((0, u), (1, v))

top_nodes = {n for n in btc if n == 0}
matching = hopcroft_karp_matching(btc, top_nodes)
vertex_cover = to_vertex_cover(btc, matching, top_nodes)
independent_set = set(G) - {v for _, v in vertex_cover}
assert {"B", "D", "F", "I", "H"} == independent_set

def test_vertex_cover_issue_2384(self):
G = nx.Graph([(0, 3), (1, 3), (1, 4), (2, 3)])
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()
c = object()
d = object()
e = object()
G = nx.Graph([(a, d), (b, d), (b, e), (c, d)])
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_eppstein_matching():
"""Test in accordance to issue #1927"""
G = nx.Graph()
G.add_nodes_from(["a", 2, 3, 4], bipartite=0)
G.add_nodes_from([1, "b", "c"], bipartite=1)
G.add_edges_from([("a", 1), ("a", "b"), (2, "b"), (2, "c"), (3, "c"), (4, 1)])
matching = eppstein_matching(G)
assert len(matching) == len(maximum_matching(G))
assert all(x in set(matching.keys()) for x in set(matching.values()))

class TestMinimumWeightFullMatching:
@classmethod
def setup_class(cls):
global scipy
scipy = pytest.importorskip("scipy")

def test_minimum_weight_full_matching_incomplete_graph(self):
B = nx.Graph()
matching = minimum_weight_full_matching(B)
assert matching == {1: 4, 2: 3, 4: 1, 3: 2}

def test_minimum_weight_full_matching_with_no_full_matching(self):
B = nx.Graph()
B.add_nodes_from([1, 2, 3], bipartite=0)
B.add_nodes_from([4, 5, 6], bipartite=1)
with pytest.raises(ValueError):
minimum_weight_full_matching(B)

def test_minimum_weight_full_matching_square(self):
G = nx.complete_bipartite_graph(3, 3)
matching = minimum_weight_full_matching(G)
assert matching == {0: 4, 1: 3, 2: 5, 4: 0, 3: 1, 5: 2}

def test_minimum_weight_full_matching_smaller_left(self):
G = nx.complete_bipartite_graph(3, 4)
matching = minimum_weight_full_matching(G)
assert matching == {0: 4, 1: 6, 2: 5, 4: 0, 5: 2, 6: 1}

def test_minimum_weight_full_matching_smaller_top_nodes_right(self):
G = nx.complete_bipartite_graph(3, 4)
matching = minimum_weight_full_matching(G, top_nodes=[3, 4, 5, 6])
assert matching == {0: 4, 1: 6, 2: 5, 4: 0, 5: 2, 6: 1}

def test_minimum_weight_full_matching_smaller_right(self):
G = nx.complete_bipartite_graph(4, 3)
matching = minimum_weight_full_matching(G)
assert matching == {1: 4, 2: 6, 3: 5, 4: 1, 5: 3, 6: 2}

def test_minimum_weight_full_matching_negative_weights(self):
G = nx.complete_bipartite_graph(2, 2)