retworkx 0.8.0

# Licensed under the Apache License, Version 2.0 (the "License"); you may
# not use this file except in compliance with the License. You may obtain
# a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
# License for the specific language governing permissions and limitations
# under the License.

# These tests are adapated from the networkx test cases:
# https://github.com/networkx/networkx/blob/3351206a3ce5b3a39bb2fc451e93ef545b96c95b/networkx/algorithms/tests/test_matching.py

import random
import unittest

import retworkx
import networkx


def match_dict_to_set(match):
    return {(u, v) for (u, v) in set(map(frozenset, match.items()))}


class TestMaxWeightMatching(unittest.TestCase):

    def compare_match_sets(self, rx_match, expected_match):
        for (u, v) in rx_match:
            if (u, v) not in expected_match and \
                    (v, u) not in expected_match:
                self.fail("Element %s and it's reverse %s not found in "
                          "expected output.\nretworkx output: %s\nexpected "
                          "output: %s" % (
                              (u, v), (v, u), rx_match, expected_match))

    def compare_rx_nx_sets(self, rx_graph, rx_matches, nx_matches, seed,
                           nx_graph):

        def get_rx_weight(edge):
            weight = rx_graph.get_edge_data(*edge)
            if weight is None:
                return 1
            return weight

        def get_nx_weight(edge):
            weight = nx_graph.get_edge_data(*edge)
            if not weight:
                return 1
            return weight['weight']

        not_match = False
        for (u, v) in rx_matches:
            if (u, v) not in nx_matches:
                if (v, u) not in nx_matches:
                    print("seed %s failed. Element %s and it's "
                          "reverse %s not found in networkx output.\nretworkx"
                          " output: %s\nnetworkx output: %s\nedge list: %s\n"
                          "falling back to checking for a valid solution" % (
                              seed, (u, v), (v, u), rx_matches,
                              nx_matches, list(rx_graph.weighted_edge_list())))
                    not_match = True
                    break
        if not_match:
            self.assertTrue(retworkx.is_matching(rx_graph, rx_matches),
                            "%s is not a valid matching" % rx_matches)
            self.assertTrue(retworkx.is_maximal_matching(rx_graph, rx_matches),
                            "%s is not a maximal matching" % rx_matches)
            self.assertEqual(sum(map(get_rx_weight, rx_matches)),
                             sum(map(get_nx_weight, nx_matches)))

    def test_empty_graph(self):
        graph = retworkx.PyGraph()
        self.assertEqual(retworkx.max_weight_matching(graph), set())

    def test_single_edge(self):
        graph = retworkx.PyGraph()
        graph.add_nodes_from([0, 1])
        graph.add_edges_from([(0, 1, 1)])
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, verify_optimum=True),
            {(0, 1), })

    def test_single_edge_no_verification(self):
        graph = retworkx.PyGraph()
        graph.add_nodes_from([0, 1])
        graph.add_edges_from([(0, 1, 1)])
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, verify_optimum=False),
            {(0, 1), })

    def test_single_self_edge(self):
        graph = retworkx.PyGraph()
        graph.extend_from_weighted_edge_list([(0, 0, 100)])
        self.assertEqual(retworkx.max_weight_matching(graph), set())

    def test_small_graph(self):
        graph = retworkx.PyGraph()
        graph.extend_from_weighted_edge_list([(1, 2, 10), (2, 3, 11)])
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, weight_fn=lambda x: x,
                                         verify_optimum=True),
            {(2, 3), })

    def test_path_graph(self):
        graph = retworkx.PyGraph()
        graph.extend_from_weighted_edge_list(
            [(1, 2, 5), (2, 3, 11), (3, 4, 5)])
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, weight_fn=lambda x: x,
                                         verify_optimum=True),
            {(2, 3), })
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, True, weight_fn=lambda x: x,
                                         verify_optimum=True),
            {(1, 2), (3, 4)})

    def test_negative_weights(self):
        graph = retworkx.PyGraph()
        graph.extend_from_weighted_edge_list([
            (1, 2, 2),
            (1, 3, -2),
            (2, 3, 1),
            (2, 4, -1),
            (3, 4, -6),
        ])
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, weight_fn=lambda x: x,
                                         verify_optimum=True),
            {(1, 2), })
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, True, weight_fn=lambda x: x,
                                         verify_optimum=True),
            {(1, 3), (2, 4)})

    def test_s_blossom(self):
        graph = retworkx.PyGraph()
        graph.extend_from_weighted_edge_list([
            (0, 1, 8),
            (0, 2, 9),
            (1, 2, 10),
            (2, 3, 7),
        ])
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, weight_fn=lambda x: x,
                                         verify_optimum=True),
            {(0, 1), (2, 3)})
        graph.extend_from_weighted_edge_list([(0, 5, 5), (3, 4, 6)])
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, weight_fn=lambda x: x,
                                         verify_optimum=True),
            {(0, 5), (1, 2), (3, 4)})

    def test_s_t_blossom(self):
        graph = retworkx.PyGraph()
        graph.extend_from_weighted_edge_list([
            (1, 2, 9),
            (1, 3, 8),
            (2, 3, 10),
            (1, 4, 5),
            (4, 5, 4),
            (1, 6, 3),
        ])
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, weight_fn=lambda x: x,
                                         verify_optimum=True),
            {(1, 6), (2, 3), (4, 5)})
        graph.remove_edge(1, 6)
        graph.remove_edge(4, 5)
        graph.extend_from_weighted_edge_list([(4, 5, 3), (1, 6, 4)])
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, weight_fn=lambda x: x,
                                         verify_optimum=True),
            {(1, 6), (2, 3), (4, 5)})
        graph.remove_edge(1, 6)
        graph.add_edge(3, 6, 4)
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, weight_fn=lambda x: x,
                                         verify_optimum=True),
            {(1, 2), (3, 6), (4, 5)})

    def test_s_t_blossom_with_removed_nodes(self):
        graph = retworkx.PyGraph()
        graph.extend_from_weighted_edge_list([
            (1, 2, 9),
            (1, 3, 8),
            (2, 3, 10),
            (1, 4, 5),
            (4, 5, 4),
            (1, 6, 3),
        ])
        node_id = graph.add_node(None)
        graph.remove_node(5)
        graph.add_edge(4, node_id, 4)
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, weight_fn=lambda x: x,
                                         verify_optimum=True),
            {(1, 6), (2, 3), (4, 7)})
        graph.remove_edge(1, 6)
        graph.remove_edge(4, 7)
        graph.extend_from_weighted_edge_list([(4, node_id, 3), (1, 6, 4)])
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, weight_fn=lambda x: x,
                                         verify_optimum=True),
            {(1, 6), (2, 3), (4, 7)})
        graph.remove_edge(1, 6)
        graph.add_edge(3, 6, 4)
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, weight_fn=lambda x: x,
                                         verify_optimum=True),
            {(1, 2), (3, 6), (4, 7)})

    def test_nested_s_blossom(self):
        graph = retworkx.PyGraph()
        graph.extend_from_weighted_edge_list([
            (1, 2, 9),
            (1, 3, 9),
            (2, 3, 10),
            (2, 4, 8),
            (3, 5, 8),
            (4, 5, 10),
            (5, 6, 6),
        ])
        expected = {(1, 3), (2, 4), (5, 6)}
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, weight_fn=lambda x: x,
                                         verify_optimum=True),
            expected)

    def test_nested_s_blossom_relabel(self):
        graph = retworkx.PyGraph()
        graph.extend_from_weighted_edge_list([
            (1, 2, 10),
            (1, 7, 10),
            (2, 3, 12),
            (3, 4, 20),
            (3, 5, 20),
            (4, 5, 25),
            (5, 6, 10),
            (6, 7, 10),
            (7, 8, 8),
        ])
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, weight_fn=lambda x: x,
                                         verify_optimum=True),
            {(1, 2), (3, 4), (5, 6), (7, 8)})

    def test_nested_s_blossom_expand(self):
        graph = retworkx.PyGraph()
        graph.extend_from_weighted_edge_list([
            (1, 2, 8),
            (1, 3, 8),
            (2, 3, 10),
            (2, 4, 12),
            (3, 5, 12),
            (4, 5, 14),
            (4, 6, 12),
            (5, 7, 12),
            (6, 7, 14),
            (7, 8, 12),
        ])
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, weight_fn=lambda x: x,
                                         verify_optimum=True),
            {(1, 2), (3, 5), (4, 6), (7, 8)})

    def test_s_blossom_relabel_expand(self):
        graph = retworkx.PyGraph()
        graph.extend_from_weighted_edge_list([
            (1, 2, 23),
            (1, 5, 22),
            (1, 6, 15),
            (2, 3, 25),
            (3, 4, 22),
            (4, 5, 25),
            (4, 8, 14),
            (5, 7, 13),
        ])
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, weight_fn=lambda x: x,
                                         verify_optimum=True),
            {(1, 6), (2, 3), (4, 8), (5, 7)})

    def test_nested_s_blossom_relabel_expand(self):
        graph = retworkx.PyGraph()
        graph.extend_from_weighted_edge_list([
            (1, 2, 19),
            (1, 3, 20),
            (1, 8, 8),
            (2, 3, 25),
            (2, 4, 18),
            (3, 5, 18),
            (4, 5, 13),
            (4, 7, 7),
            (5, 6, 7),
        ])
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, weight_fn=lambda x: x,
                                         verify_optimum=True),
            match_dict_to_set(
                {1: 8, 2: 3, 3: 2, 4: 7, 5: 6, 6: 5, 7: 4, 8: 1}))

    def test_blossom_relabel_multiple_paths(self):
        graph = retworkx.PyGraph()
        graph.extend_from_weighted_edge_list([
            (1, 2, 45),
            (1, 5, 45),
            (2, 3, 50),
            (3, 4, 45),
            (4, 5, 50),
            (1, 6, 30),
            (3, 9, 35),
            (4, 8, 35),
            (5, 7, 26),
            (9, 10, 5),
        ])
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, weight_fn=lambda x: x,
                                         verify_optimum=True),
            match_dict_to_set(
                {1: 6, 2: 3, 3: 2, 4: 8, 5: 7, 6: 1, 7: 5, 8: 4, 9: 10,
                 10: 9}))

    def test_blossom_relabel_multiple_path_alternate(self):
        graph = retworkx.PyGraph()
        graph.extend_from_weighted_edge_list([
            (1, 2, 45),
            (1, 5, 45),
            (2, 3, 50),
            (3, 4, 45),
            (4, 5, 50),
            (1, 6, 30),
            (3, 9, 35),
            (4, 8, 26),
            (5, 7, 40),
            (9, 10, 5),
        ])
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, weight_fn=lambda x: x,
                                         verify_optimum=True),
            match_dict_to_set(
                {1: 6, 2: 3, 3: 2, 4: 8, 5: 7, 6: 1, 7: 5, 8: 4, 9: 10,
                 10: 9}))

    def test_blossom_relabel_multiple_paths_least_slack(self):
        graph = retworkx.PyGraph()
        graph.extend_from_weighted_edge_list([
            (1, 2, 45),
            (1, 5, 45),
            (2, 3, 50),
            (3, 4, 45),
            (4, 5, 50),
            (1, 6, 30),
            (3, 9, 35),
            (4, 8, 28),
            (5, 7, 26),
            (9, 10, 5),
        ])
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, weight_fn=lambda x: x,
                                         verify_optimum=True),
            match_dict_to_set(
                {1: 6, 2: 3, 3: 2, 4: 8, 5: 7, 6: 1, 7: 5, 8: 4, 9: 10,
                 10: 9}))

    def test_nested_blossom_expand_recursively(self):
        graph = retworkx.PyGraph()
        graph.extend_from_weighted_edge_list([
            (1, 2, 40),
            (1, 3, 40),
            (2, 3, 60),
            (2, 4, 55),
            (3, 5, 55),
            (4, 5, 50),
            (1, 8, 15),
            (5, 7, 30),
            (7, 6, 10),
            (8, 10, 10),
            (4, 9, 30),
        ])
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, weight_fn=lambda x: x,
                                         verify_optimum=True),
            match_dict_to_set(
                {1: 2, 2: 1, 3: 5, 4: 9, 5: 3, 6: 7, 7: 6, 8: 10, 9: 4,
                 10: 8}))

    def test_nested_blossom_augmented(self):
        graph = retworkx.PyGraph()
        graph.extend_from_weighted_edge_list([
            (1, 2, 45),
            (1, 7, 45),
            (2, 3, 50),
            (3, 4, 45),
            (4, 5, 95),
            (4, 6, 94),
            (5, 6, 94),
            (6, 7, 50),
            (1, 8, 30),
            (3, 11, 35),
            (5, 9, 36),
            (7, 10, 26),
            (11, 12, 5),
        ])
        expected = {
            1: 8,
            2: 3,
            3: 2,
            4: 6,
            5: 9,
            6: 4,
            7: 10,
            8: 1,
            9: 5,
            10: 7,
            11: 12,
            12: 11,
        }
        self.compare_match_sets(
            retworkx.max_weight_matching(graph, weight_fn=lambda x: x,
                                         verify_optimum=True),
            match_dict_to_set(expected))

    def test_gnp_random_against_networkx(self):
        for i in range(1024):
            with self.subTest(i=i):
                rx_graph = retworkx.undirected_gnp_random_graph(10, .75,
                                                                seed=42 + i)
                nx_graph = networkx.Graph(list(rx_graph.edge_list()))
                nx_matches = networkx.max_weight_matching(nx_graph)
                rx_matches = retworkx.max_weight_matching(rx_graph,
                                                          verify_optimum=True)
                self.compare_rx_nx_sets(rx_graph, rx_matches, nx_matches,
                                        42 + i, nx_graph)

    def test_gnp_random_against_networkx_with_weight(self):
        for i in range(1024):
            with self.subTest(i=i):
                random.seed(i)
                rx_graph = retworkx.undirected_gnp_random_graph(10, .75,
                                                                seed=42 + i)
                for edge in rx_graph.edge_list():
                    rx_graph.update_edge(*edge, random.randint(0, 5000))
                nx_graph = networkx.Graph(
                    [(x[0], x[1],
                     {'weight': x[2]}) for x in rx_graph.weighted_edge_list()])
                nx_matches = networkx.max_weight_matching(nx_graph)
                rx_matches = retworkx.max_weight_matching(
                    rx_graph, weight_fn=lambda x: x, verify_optimum=True)
                self.compare_rx_nx_sets(rx_graph, rx_matches, nx_matches,
                                        42 + i, nx_graph)

    def test_gnp_random_against_networkx_with_negative_weight(self):
        for i in range(1024):
            with self.subTest(i=i):
                random.seed(i)
                rx_graph = retworkx.undirected_gnp_random_graph(10, .75,
                                                                seed=42 + i)
                for edge in rx_graph.edge_list():
                    rx_graph.update_edge(*edge, random.randint(-5000, 5000))
                nx_graph = networkx.Graph(
                    [(x[0], x[1],
                     {'weight': x[2]}) for x in rx_graph.weighted_edge_list()])
                nx_matches = networkx.max_weight_matching(nx_graph)
                rx_matches = retworkx.max_weight_matching(
                    rx_graph, weight_fn=lambda x: x, verify_optimum=True)
                self.compare_rx_nx_sets(rx_graph, rx_matches, nx_matches,
                                        42 + i, nx_graph)

    def test_gnp_random_against_networkx_max_cardinality(self):
        rx_graph = retworkx.undirected_gnp_random_graph(10, .78, seed=428)
        nx_graph = networkx.Graph(list(rx_graph.edge_list()))
        nx_matches = networkx.max_weight_matching(
            nx_graph, maxcardinality=True)
        rx_matches = retworkx.max_weight_matching(
            rx_graph, max_cardinality=True, verify_optimum=True)
        self.compare_rx_nx_sets(rx_graph, rx_matches, nx_matches, 428,
                                nx_graph)

    def test_gnp_random_against_networkx_with_weight_max_cardinality(self):
        for i in range(1024):
            with self.subTest(i=i):
                random.seed(i)
                rx_graph = retworkx.undirected_gnp_random_graph(10, .75,
                                                                seed=42 + i)
                for edge in rx_graph.edge_list():
                    rx_graph.update_edge(*edge, random.randint(0, 5000))
                nx_graph = networkx.Graph(
                    [(x[0], x[1],
                     {'weight': x[2]}) for x in rx_graph.weighted_edge_list()])
                nx_matches = networkx.max_weight_matching(nx_graph,
                                                          maxcardinality=True)
                rx_matches = retworkx.max_weight_matching(
                    rx_graph, weight_fn=lambda x: x, max_cardinality=True,
                    verify_optimum=True)
                self.compare_rx_nx_sets(rx_graph, rx_matches, nx_matches,
                                        42 + i, nx_graph)

    def test_gnp_random__networkx_with_negative_weight_max_cardinality(self):
        for i in range(1024):
            with self.subTest(i=i):
                random.seed(i)
                rx_graph = retworkx.undirected_gnp_random_graph(10, .75,
                                                                seed=42 + i)
                for edge in rx_graph.edge_list():
                    rx_graph.update_edge(*edge, random.randint(-5000, 5000))
                nx_graph = networkx.Graph(
                    [(x[0], x[1],
                     {'weight': x[2]}) for x in rx_graph.weighted_edge_list()])
                nx_matches = networkx.max_weight_matching(nx_graph,
                                                          maxcardinality=True)
                rx_matches = retworkx.max_weight_matching(
                    rx_graph, weight_fn=lambda x: x, max_cardinality=True,
                    verify_optimum=True)
                self.compare_rx_nx_sets(rx_graph, rx_matches, nx_matches,
                                        42 + i, nx_graph)

    def test_gnm_random_against_networkx(self):
        rx_graph = retworkx.undirected_gnm_random_graph(10, 13, seed=42)
        nx_graph = networkx.Graph(list(rx_graph.edge_list()))
        nx_matches = networkx.max_weight_matching(nx_graph)
        rx_matches = retworkx.max_weight_matching(rx_graph,
                                                  verify_optimum=True)
        self.compare_rx_nx_sets(rx_graph, rx_matches, nx_matches, 42,
                                nx_graph)

    def test_gnm_random_against_networkx_max_cardinality(self):
        rx_graph = retworkx.undirected_gnm_random_graph(10, 12, seed=42)
        nx_graph = networkx.Graph(list(rx_graph.edge_list()))
        nx_matches = networkx.max_weight_matching(
            nx_graph, maxcardinality=True)
        rx_matches = retworkx.max_weight_matching(
            rx_graph, max_cardinality=True, verify_optimum=True)
        self.compare_rx_nx_sets(rx_graph, rx_matches, nx_matches, 42,
                                nx_graph)