import pytest

import networkx as nx


def test_selfloops_raises():
    G = nx.ladder_graph(3)
    G.add_edge(0, 0)
    with pytest.raises(nx.NetworkXError, match=".*not bipartite"):
        nx.bipartite.maximal_extendability(G)


def test_disconnected_raises():
    G = nx.ladder_graph(3)
    G.add_node("a")
    with pytest.raises(nx.NetworkXError, match=".*not connected"):
        nx.bipartite.maximal_extendability(G)


def test_not_bipartite_raises():
    G = nx.complete_graph(5)
    with pytest.raises(nx.NetworkXError, match=".*not bipartite"):
        nx.bipartite.maximal_extendability(G)


def test_no_perfect_matching_raises():
    G = nx.Graph([(0, 1), (0, 2)])
    with pytest.raises(nx.NetworkXError, match=".*not contain a perfect matching"):
        nx.bipartite.maximal_extendability(G)


def test_residual_graph_not_strongly_connected_raises():
    G = nx.Graph([(1, 2), (2, 3), (3, 4)])
    with pytest.raises(
        nx.NetworkXError, match="The residual graph of G is not strongly connected"
    ):
        nx.bipartite.maximal_extendability(G)


def test_ladder_graph_is_1():
    G = nx.ladder_graph(3)
    assert nx.bipartite.maximal_extendability(G) == 1


def test_cubical_graph_is_2():
    G = nx.cubical_graph()
    assert nx.bipartite.maximal_extendability(G) == 2


def test_k_is_3():
    G = nx.Graph(
        [
            (1, 6),
            (1, 7),
            (1, 8),
            (1, 9),
            (2, 6),
            (2, 7),
            (2, 8),
            (2, 10),
            (3, 6),
            (3, 8),
            (3, 9),
            (3, 10),
            (4, 7),
            (4, 8),
            (4, 9),
            (4, 10),
            (5, 6),
            (5, 7),
            (5, 9),
            (5, 10),
        ]
    )
    assert nx.bipartite.maximal_extendability(G) == 3


def test_k_is_4():
    G = nx.Graph(
        [
            (8, 1),
            (8, 2),
            (8, 3),
            (8, 4),
            (8, 5),
            (9, 1),
            (9, 2),
            (9, 3),
            (9, 4),
            (9, 7),
            (10, 1),
            (10, 2),
            (10, 3),
            (10, 4),
            (10, 6),
            (11, 1),
            (11, 2),
            (11, 5),
            (11, 6),
            (11, 7),
            (12, 1),
            (12, 3),
            (12, 5),
            (12, 6),
            (12, 7),
            (13, 2),
            (13, 4),
            (13, 5),
            (13, 6),
            (13, 7),
            (14, 3),
            (14, 4),
            (14, 5),
            (14, 6),
            (14, 7),
        ]
    )
    assert nx.bipartite.maximal_extendability(G) == 4


def test_k_is_5():
    G = nx.Graph(
        [
            (8, 1),
            (8, 2),
            (8, 3),
            (8, 4),
            (8, 5),
            (8, 6),
            (9, 1),
            (9, 2),
            (9, 3),
            (9, 4),
            (9, 5),
            (9, 7),
            (10, 1),
            (10, 2),
            (10, 3),
            (10, 4),
            (10, 6),
            (10, 7),
            (11, 1),
            (11, 2),
            (11, 3),
            (11, 5),
            (11, 6),
            (11, 7),
            (12, 1),
            (12, 2),
            (12, 4),
            (12, 5),
            (12, 6),
            (12, 7),
            (13, 1),
            (13, 3),
            (13, 4),
            (13, 5),
            (13, 6),
            (13, 7),
            (14, 2),
            (14, 3),
            (14, 4),
            (14, 5),
            (14, 6),
            (14, 7),
        ]
    )
    assert nx.bipartite.maximal_extendability(G) == 5


def test_k_is_6():
    G = nx.Graph(
        [
            (9, 1),
            (9, 2),
            (9, 3),
            (9, 4),
            (9, 5),
            (9, 6),
            (9, 7),
            (10, 1),
            (10, 2),
            (10, 3),
            (10, 4),
            (10, 5),
            (10, 6),
            (10, 8),
            (11, 1),
            (11, 2),
            (11, 3),
            (11, 4),
            (11, 5),
            (11, 7),
            (11, 8),
            (12, 1),
            (12, 2),
            (12, 3),
            (12, 4),
            (12, 6),
            (12, 7),
            (12, 8),
            (13, 1),
            (13, 2),
            (13, 3),
            (13, 5),
            (13, 6),
            (13, 7),
            (13, 8),
            (14, 1),
            (14, 2),
            (14, 4),
            (14, 5),
            (14, 6),
            (14, 7),
            (14, 8),
            (15, 1),
            (15, 3),
            (15, 4),
            (15, 5),
            (15, 6),
            (15, 7),
            (15, 8),
            (16, 2),
            (16, 3),
            (16, 4),
            (16, 5),
            (16, 6),
            (16, 7),
            (16, 8),
        ]
    )
    assert nx.bipartite.maximal_extendability(G) == 6


def test_k_is_7():
    G = nx.Graph(
        [
            (1, 11),
            (1, 12),
            (1, 13),
            (1, 14),
            (1, 15),
            (1, 16),
            (1, 17),
            (1, 18),
            (2, 11),
            (2, 12),
            (2, 13),
            (2, 14),
            (2, 15),
            (2, 16),
            (2, 17),
            (2, 19),
            (3, 11),
            (3, 12),
            (3, 13),
            (3, 14),
            (3, 15),
            (3, 16),
            (3, 17),
            (3, 20),
            (4, 11),
            (4, 12),
            (4, 13),
            (4, 14),
            (4, 15),
            (4, 16),
            (4, 17),
            (4, 18),
            (4, 19),
            (4, 20),
            (5, 11),
            (5, 12),
            (5, 13),
            (5, 14),
            (5, 15),
            (5, 16),
            (5, 17),
            (5, 18),
            (5, 19),
            (5, 20),
            (6, 11),
            (6, 12),
            (6, 13),
            (6, 14),
            (6, 15),
            (6, 16),
            (6, 17),
            (6, 18),
            (6, 19),
            (6, 20),
            (7, 11),
            (7, 12),
            (7, 13),
            (7, 14),
            (7, 15),
            (7, 16),
            (7, 17),
            (7, 18),
            (7, 19),
            (7, 20),
            (8, 11),
            (8, 12),
            (8, 13),
            (8, 14),
            (8, 15),
            (8, 16),
            (8, 17),
            (8, 18),
            (8, 19),
            (8, 20),
            (9, 11),
            (9, 12),
            (9, 13),
            (9, 14),
            (9, 15),
            (9, 16),
            (9, 17),
            (9, 18),
            (9, 19),
            (9, 20),
            (10, 11),
            (10, 12),
            (10, 13),
            (10, 14),
            (10, 15),
            (10, 16),
            (10, 17),
            (10, 18),
            (10, 19),
            (10, 20),
        ]
    )
    assert nx.bipartite.maximal_extendability(G) == 7