"""Unit tests for the :mod:`networkx.algorithms.minors.contraction` module."""
import pytest

import networkx as nx
from networkx.utils import arbitrary_element, nodes_equal, edges_equal


class TestQuotient:
    """Unit tests for computing quotient graphs."""

    def test_quotient_graph_complete_multipartite(self):
        """Tests that the quotient graph of the complete *n*-partite graph
        under the "same neighbors" node relation is the complete graph on *n*
        nodes.

        """
        G = nx.complete_multipartite_graph(2, 3, 4)
        # Two nodes are equivalent if they are not adjacent but have the same
        # neighbor set.

        def same_neighbors(u, v):
            return u not in G[v] and v not in G[u] and G[u] == G[v]

        expected = nx.complete_graph(3)
        actual = nx.quotient_graph(G, same_neighbors)
        # It won't take too long to run a graph isomorphism algorithm on such
        # small graphs.
        assert nx.is_isomorphic(expected, actual)

    def test_quotient_graph_complete_bipartite(self):
        """Tests that the quotient graph of the complete bipartite graph under
        the "same neighbors" node relation is `K_2`.

        """
        G = nx.complete_bipartite_graph(2, 3)
        # Two nodes are equivalent if they are not adjacent but have the same
        # neighbor set.

        def same_neighbors(u, v):
            return u not in G[v] and v not in G[u] and G[u] == G[v]

        expected = nx.complete_graph(2)
        actual = nx.quotient_graph(G, same_neighbors)
        # It won't take too long to run a graph isomorphism algorithm on such
        # small graphs.
        assert nx.is_isomorphic(expected, actual)

    def test_quotient_graph_edge_relation(self):
        """Tests for specifying an alternate edge relation for the quotient
        graph.

        """
        G = nx.path_graph(5)

        def identity(u, v):
            return u == v

        def same_parity(b, c):
            return arbitrary_element(b) % 2 == arbitrary_element(c) % 2

        actual = nx.quotient_graph(G, identity, same_parity)
        expected = nx.Graph()
        expected.add_edges_from([(0, 2), (0, 4), (2, 4)])
        expected.add_edge(1, 3)
        assert nx.is_isomorphic(actual, expected)

    def test_condensation_as_quotient(self):
        """This tests that the condensation of a graph can be viewed as the
        quotient graph under the "in the same connected component" equivalence
        relation.

        """
        # This example graph comes from the file `test_strongly_connected.py`.
        G = nx.DiGraph()
        G.add_edges_from(
            [
                (1, 2),
                (2, 3),
                (2, 11),
                (2, 12),
                (3, 4),
                (4, 3),
                (4, 5),
                (5, 6),
                (6, 5),
                (6, 7),
                (7, 8),
                (7, 9),
                (7, 10),
                (8, 9),
                (9, 7),
                (10, 6),
                (11, 2),
                (11, 4),
                (11, 6),
                (12, 6),
                (12, 11),
            ]
        )
        scc = list(nx.strongly_connected_components(G))
        C = nx.condensation(G, scc)
        component_of = C.graph["mapping"]
        # Two nodes are equivalent if they are in the same connected component.

        def same_component(u, v):
            return component_of[u] == component_of[v]

        Q = nx.quotient_graph(G, same_component)
        assert nx.is_isomorphic(C, Q)

    def test_path(self):
        G = nx.path_graph(6)
        partition = [{0, 1}, {2, 3}, {4, 5}]
        M = nx.quotient_graph(G, partition, relabel=True)
        assert nodes_equal(M, [0, 1, 2])
        assert edges_equal(M.edges(), [(0, 1), (1, 2)])
        for n in M:
            assert M.nodes[n]["nedges"] == 1
            assert M.nodes[n]["nnodes"] == 2
            assert M.nodes[n]["density"] == 1

    def test_path__partition_provided_as_dict_of_lists(self):
        G = nx.path_graph(6)
        partition = {0: [0, 1], 2: [2, 3], 4: [4, 5]}
        M = nx.quotient_graph(G, partition, relabel=True)
        assert nodes_equal(M, [0, 1, 2])
        assert edges_equal(M.edges(), [(0, 1), (1, 2)])
        for n in M:
            assert M.nodes[n]["nedges"] == 1
            assert M.nodes[n]["nnodes"] == 2
            assert M.nodes[n]["density"] == 1

    def test_path__partition_provided_as_dict_of_tuples(self):
        G = nx.path_graph(6)
        partition = {0: (0, 1), 2: (2, 3), 4: (4, 5)}
        M = nx.quotient_graph(G, partition, relabel=True)
        assert nodes_equal(M, [0, 1, 2])
        assert edges_equal(M.edges(), [(0, 1), (1, 2)])
        for n in M:
            assert M.nodes[n]["nedges"] == 1
            assert M.nodes[n]["nnodes"] == 2
            assert M.nodes[n]["density"] == 1

    def test_path__partition_provided_as_dict_of_sets(self):
        G = nx.path_graph(6)
        partition = {0: {0, 1}, 2: {2, 3}, 4: {4, 5}}
        M = nx.quotient_graph(G, partition, relabel=True)
        assert nodes_equal(M, [0, 1, 2])
        assert edges_equal(M.edges(), [(0, 1), (1, 2)])
        for n in M:
            assert M.nodes[n]["nedges"] == 1
            assert M.nodes[n]["nnodes"] == 2
            assert M.nodes[n]["density"] == 1

    def test_multigraph_path(self):
        G = nx.MultiGraph(nx.path_graph(6))
        partition = [{0, 1}, {2, 3}, {4, 5}]
        M = nx.quotient_graph(G, partition, relabel=True)
        assert nodes_equal(M, [0, 1, 2])
        assert edges_equal(M.edges(), [(0, 1), (1, 2)])
        for n in M:
            assert M.nodes[n]["nedges"] == 1
            assert M.nodes[n]["nnodes"] == 2
            assert M.nodes[n]["density"] == 1

    def test_directed_path(self):
        G = nx.DiGraph()
        nx.add_path(G, range(6))
        partition = [{0, 1}, {2, 3}, {4, 5}]
        M = nx.quotient_graph(G, partition, relabel=True)
        assert nodes_equal(M, [0, 1, 2])
        assert edges_equal(M.edges(), [(0, 1), (1, 2)])
        for n in M:
            assert M.nodes[n]["nedges"] == 1
            assert M.nodes[n]["nnodes"] == 2
            assert M.nodes[n]["density"] == 0.5

    def test_directed_multigraph_path(self):
        G = nx.MultiDiGraph()
        nx.add_path(G, range(6))
        partition = [{0, 1}, {2, 3}, {4, 5}]
        M = nx.quotient_graph(G, partition, relabel=True)
        assert nodes_equal(M, [0, 1, 2])
        assert edges_equal(M.edges(), [(0, 1), (1, 2)])
        for n in M:
            assert M.nodes[n]["nedges"] == 1
            assert M.nodes[n]["nnodes"] == 2
            assert M.nodes[n]["density"] == 0.5

    def test_overlapping_blocks(self):
        with pytest.raises(nx.NetworkXException):
            G = nx.path_graph(6)
            partition = [{0, 1, 2}, {2, 3}, {4, 5}]
            nx.quotient_graph(G, partition)

    def test_weighted_path(self):
        G = nx.path_graph(6)
        for i in range(5):
            G[i][i + 1]["weight"] = i + 1
        partition = [{0, 1}, {2, 3}, {4, 5}]
        M = nx.quotient_graph(G, partition, relabel=True)
        assert nodes_equal(M, [0, 1, 2])
        assert edges_equal(M.edges(), [(0, 1), (1, 2)])
        assert M[0][1]["weight"] == 2
        assert M[1][2]["weight"] == 4
        for n in M:
            assert M.nodes[n]["nedges"] == 1
            assert M.nodes[n]["nnodes"] == 2
            assert M.nodes[n]["density"] == 1

    def test_barbell(self):
        G = nx.barbell_graph(3, 0)
        partition = [{0, 1, 2}, {3, 4, 5}]
        M = nx.quotient_graph(G, partition, relabel=True)
        assert nodes_equal(M, [0, 1])
        assert edges_equal(M.edges(), [(0, 1)])
        for n in M:
            assert M.nodes[n]["nedges"] == 3
            assert M.nodes[n]["nnodes"] == 3
            assert M.nodes[n]["density"] == 1

    def test_barbell_plus(self):
        G = nx.barbell_graph(3, 0)
        # Add an extra edge joining the bells.
        G.add_edge(0, 5)
        partition = [{0, 1, 2}, {3, 4, 5}]
        M = nx.quotient_graph(G, partition, relabel=True)
        assert nodes_equal(M, [0, 1])
        assert edges_equal(M.edges(), [(0, 1)])
        assert M[0][1]["weight"] == 2
        for n in M:
            assert M.nodes[n]["nedges"] == 3
            assert M.nodes[n]["nnodes"] == 3
            assert M.nodes[n]["density"] == 1

    def test_blockmodel(self):
        G = nx.path_graph(6)
        partition = [[0, 1], [2, 3], [4, 5]]
        M = nx.quotient_graph(G, partition, relabel=True)
        assert nodes_equal(M.nodes(), [0, 1, 2])
        assert edges_equal(M.edges(), [(0, 1), (1, 2)])
        for n in M.nodes():
            assert M.nodes[n]["nedges"] == 1
            assert M.nodes[n]["nnodes"] == 2
            assert M.nodes[n]["density"] == 1.0

    def test_multigraph_blockmodel(self):
        G = nx.MultiGraph(nx.path_graph(6))
        partition = [[0, 1], [2, 3], [4, 5]]
        M = nx.quotient_graph(G, partition, create_using=nx.MultiGraph(), relabel=True)
        assert nodes_equal(M.nodes(), [0, 1, 2])
        assert edges_equal(M.edges(), [(0, 1), (1, 2)])
        for n in M.nodes():
            assert M.nodes[n]["nedges"] == 1
            assert M.nodes[n]["nnodes"] == 2
            assert M.nodes[n]["density"] == 1.0

    def test_quotient_graph_incomplete_partition(self):
        G = nx.path_graph(6)
        partition = []
        H = nx.quotient_graph(G, partition, relabel=True)
        assert nodes_equal(H.nodes(), [])
        assert edges_equal(H.edges(), [])

        partition = [[0, 1], [2, 3], [5]]
        H = nx.quotient_graph(G, partition, relabel=True)
        assert nodes_equal(H.nodes(), [0, 1, 2])
        assert edges_equal(H.edges(), [(0, 1)])


class TestContraction:
    """Unit tests for node and edge contraction functions."""

    def test_undirected_node_contraction(self):
        """Tests for node contraction in an undirected graph."""
        G = nx.cycle_graph(4)
        actual = nx.contracted_nodes(G, 0, 1)
        expected = nx.cycle_graph(3)
        expected.add_edge(0, 0)
        assert nx.is_isomorphic(actual, expected)

    def test_directed_node_contraction(self):
        """Tests for node contraction in a directed graph."""
        G = nx.DiGraph(nx.cycle_graph(4))
        actual = nx.contracted_nodes(G, 0, 1)
        expected = nx.DiGraph(nx.cycle_graph(3))
        expected.add_edge(0, 0)
        expected.add_edge(0, 0)
        assert nx.is_isomorphic(actual, expected)

    def test_undirected_node_contraction_no_copy(self):
        """Tests for node contraction in an undirected graph
        by making changes in place."""
        G = nx.cycle_graph(4)
        actual = nx.contracted_nodes(G, 0, 1, copy=False)
        expected = nx.cycle_graph(3)
        expected.add_edge(0, 0)
        assert nx.is_isomorphic(actual, G)
        assert nx.is_isomorphic(actual, expected)

    def test_directed_node_contraction_no_copy(self):
        """Tests for node contraction in a directed graph
        by making changes in place."""
        G = nx.DiGraph(nx.cycle_graph(4))
        actual = nx.contracted_nodes(G, 0, 1, copy=False)
        expected = nx.DiGraph(nx.cycle_graph(3))
        expected.add_edge(0, 0)
        expected.add_edge(0, 0)
        assert nx.is_isomorphic(actual, G)
        assert nx.is_isomorphic(actual, expected)

    def test_create_multigraph(self):
        """Tests that using a MultiGraph creates multiple edges."""
        G = nx.path_graph(3, create_using=nx.MultiGraph())
        G.add_edge(0, 1)
        G.add_edge(0, 0)
        G.add_edge(0, 2)
        actual = nx.contracted_nodes(G, 0, 2)
        expected = nx.MultiGraph()
        expected.add_edge(0, 1)
        expected.add_edge(0, 1)
        expected.add_edge(0, 1)
        expected.add_edge(0, 0)
        expected.add_edge(0, 0)
        assert edges_equal(actual.edges, expected.edges)

    def test_multigraph_keys(self):
        """Tests that multiedge keys are reset in new graph."""
        G = nx.path_graph(3, create_using=nx.MultiGraph())
        G.add_edge(0, 1, 5)
        G.add_edge(0, 0, 0)
        G.add_edge(0, 2, 5)
        actual = nx.contracted_nodes(G, 0, 2)
        expected = nx.MultiGraph()
        expected.add_edge(0, 1, 0)
        expected.add_edge(0, 1, 5)
        expected.add_edge(0, 1, 2)  # keyed as 2 b/c 2 edges already in G
        expected.add_edge(0, 0, 0)
        expected.add_edge(0, 0, 1)  # this comes from (0, 2, 5)
        assert edges_equal(actual.edges, expected.edges)

    def test_node_attributes(self):
        """Tests that node contraction preserves node attributes."""
        G = nx.cycle_graph(4)
        # Add some data to the two nodes being contracted.
        G.nodes[0]["foo"] = "bar"
        G.nodes[1]["baz"] = "xyzzy"
        actual = nx.contracted_nodes(G, 0, 1)
        # We expect that contracting the nodes 0 and 1 in C_4 yields K_3, but
        # with nodes labeled 0, 2, and 3, and with a self-loop on 0.
        expected = nx.complete_graph(3)
        expected = nx.relabel_nodes(expected, {1: 2, 2: 3})
        expected.add_edge(0, 0)
        cdict = {1: {"baz": "xyzzy"}}
        expected.nodes[0].update(dict(foo="bar", contraction=cdict))
        assert nx.is_isomorphic(actual, expected)
        assert actual.nodes == expected.nodes

    def test_edge_attributes(self):
        """Tests that node contraction preserves edge attributes."""
        # Shape: src1 --> dest <-- src2
        G = nx.DiGraph([("src1", "dest"), ("src2", "dest")])
        G["src1"]["dest"]["value"] = "src1-->dest"
        G["src2"]["dest"]["value"] = "src2-->dest"
        H = nx.MultiDiGraph(G)

        G = nx.contracted_nodes(G, "src1", "src2")  # New Shape: src1 --> dest
        assert G.edges[("src1", "dest")]["value"] == "src1-->dest"
        assert (
            G.edges[("src1", "dest")]["contraction"][("src2", "dest")]["value"]
            == "src2-->dest"
        )

        H = nx.contracted_nodes(H, "src1", "src2")  # New Shape: src1 -(x2)-> dest
        assert len(H.edges(("src1", "dest"))) == 2

    def test_without_self_loops(self):
        """Tests for node contraction without preserving self-loops."""
        G = nx.cycle_graph(4)
        actual = nx.contracted_nodes(G, 0, 1, self_loops=False)
        expected = nx.complete_graph(3)
        assert nx.is_isomorphic(actual, expected)

    def test_contract_selfloop_graph(self):
        """Tests for node contraction when nodes have selfloops."""
        G = nx.cycle_graph(4)
        G.add_edge(0, 0)
        actual = nx.contracted_nodes(G, 0, 1)
        expected = nx.complete_graph([0, 2, 3])
        expected.add_edge(0, 0)
        expected.add_edge(0, 0)
        assert edges_equal(actual.edges, expected.edges)
        actual = nx.contracted_nodes(G, 1, 0)
        expected = nx.complete_graph([1, 2, 3])
        expected.add_edge(1, 1)
        expected.add_edge(1, 1)
        assert edges_equal(actual.edges, expected.edges)

    def test_undirected_edge_contraction(self):
        """Tests for edge contraction in an undirected graph."""
        G = nx.cycle_graph(4)
        actual = nx.contracted_edge(G, (0, 1))
        expected = nx.complete_graph(3)
        expected.add_edge(0, 0)
        assert nx.is_isomorphic(actual, expected)

    def test_multigraph_edge_contraction(self):
        """Tests for edge contraction in a multigraph"""
        G = nx.cycle_graph(4)
        actual = nx.contracted_edge(G, (0, 1, 0))
        expected = nx.complete_graph(3)
        expected.add_edge(0, 0)
        assert nx.is_isomorphic(actual, expected)

    def test_nonexistent_edge(self):
        """Tests that attempting to contract a non-existent edge raises an
        exception.

        """
        with pytest.raises(ValueError):
            G = nx.cycle_graph(4)
            nx.contracted_edge(G, (0, 2))
