Vehicle-cpp/hkpc/software/networkx/algorithms/components/tests/test_biconnected.py

import pytest

import networkx as nx
from networkx import NetworkXNotImplemented


def assert_components_edges_equal(x, y):
    sx = {frozenset(frozenset(e) for e in c) for c in x}
    sy = {frozenset(frozenset(e) for e in c) for c in y}
    assert sx == sy


def assert_components_equal(x, y):
    sx = {frozenset(c) for c in x}
    sy = {frozenset(c) for c in y}
    assert sx == sy


def test_barbell():
    G = nx.barbell_graph(8, 4)
    nx.add_path(G, [7, 20, 21, 22])
    nx.add_cycle(G, [22, 23, 24, 25])
    pts = set(nx.articulation_points(G))
    assert pts == {7, 8, 9, 10, 11, 12, 20, 21, 22}

    answer = [
        {12, 13, 14, 15, 16, 17, 18, 19},
        {0, 1, 2, 3, 4, 5, 6, 7},
        {22, 23, 24, 25},
        {11, 12},
        {10, 11},
        {9, 10},
        {8, 9},
        {7, 8},
        {21, 22},
        {20, 21},
        {7, 20},
    ]
    assert_components_equal(list(nx.biconnected_components(G)), answer)

    G.add_edge(2, 17)
    pts = set(nx.articulation_points(G))
    assert pts == {7, 20, 21, 22}


def test_articulation_points_repetitions():
    G = nx.Graph()
    G.add_edges_from([(0, 1), (1, 2), (1, 3)])
    assert list(nx.articulation_points(G)) == [1]


def test_articulation_points_cycle():
    G = nx.cycle_graph(3)
    nx.add_cycle(G, [1, 3, 4])
    pts = set(nx.articulation_points(G))
    assert pts == {1}


def test_is_biconnected():
    G = nx.cycle_graph(3)
    assert nx.is_biconnected(G)
    nx.add_cycle(G, [1, 3, 4])
    assert not nx.is_biconnected(G)


def test_empty_is_biconnected():
    G = nx.empty_graph(5)
    assert not nx.is_biconnected(G)
    G.add_edge(0, 1)
    assert not nx.is_biconnected(G)


def test_biconnected_components_cycle():
    G = nx.cycle_graph(3)
    nx.add_cycle(G, [1, 3, 4])
    answer = [{0, 1, 2}, {1, 3, 4}]
    assert_components_equal(list(nx.biconnected_components(G)), answer)


def test_biconnected_components1():
    # graph example from
    # https://web.archive.org/web/20121229123447/http://www.ibluemojo.com/school/articul_algorithm.html
    edges = [
        (0, 1),
        (0, 5),
        (0, 6),
        (0, 14),
        (1, 5),
        (1, 6),
        (1, 14),
        (2, 4),
        (2, 10),
        (3, 4),
        (3, 15),
        (4, 6),
        (4, 7),
        (4, 10),
        (5, 14),
        (6, 14),
        (7, 9),
        (8, 9),
        (8, 12),
        (8, 13),
        (10, 15),
        (11, 12),
        (11, 13),
        (12, 13),
    ]
    G = nx.Graph(edges)
    pts = set(nx.articulation_points(G))
    assert pts == {4, 6, 7, 8, 9}
    comps = list(nx.biconnected_component_edges(G))
    answer = [
        [(3, 4), (15, 3), (10, 15), (10, 4), (2, 10), (4, 2)],
        [(13, 12), (13, 8), (11, 13), (12, 11), (8, 12)],
        [(9, 8)],
        [(7, 9)],
        [(4, 7)],
        [(6, 4)],
        [(14, 0), (5, 1), (5, 0), (14, 5), (14, 1), (6, 14), (6, 0), (1, 6), (0, 1)],
    ]
    assert_components_edges_equal(comps, answer)


def test_biconnected_components2():
    G = nx.Graph()
    nx.add_cycle(G, "ABC")
    nx.add_cycle(G, "CDE")
    nx.add_cycle(G, "FIJHG")
    nx.add_cycle(G, "GIJ")
    G.add_edge("E", "G")
    comps = list(nx.biconnected_component_edges(G))
    answer = [
        [
            tuple("GF"),
            tuple("FI"),
            tuple("IG"),
            tuple("IJ"),
            tuple("JG"),
            tuple("JH"),
            tuple("HG"),
        ],
        [tuple("EG")],
        [tuple("CD"), tuple("DE"), tuple("CE")],
        [tuple("AB"), tuple("BC"), tuple("AC")],
    ]
    assert_components_edges_equal(comps, answer)


def test_biconnected_davis():
    D = nx.davis_southern_women_graph()
    bcc = list(nx.biconnected_components(D))[0]
    assert set(D) == bcc  # All nodes in a giant bicomponent
    # So no articulation points
    assert len(list(nx.articulation_points(D))) == 0


def test_biconnected_karate():
    K = nx.karate_club_graph()
    answer = [
        {
            0,
            1,
            2,
            3,
            7,
            8,
            9,
            12,
            13,
            14,
            15,
            17,
            18,
            19,
            20,
            21,
            22,
            23,
            24,
            25,
            26,
            27,
            28,
            29,
            30,
            31,
            32,
            33,
        },
        {0, 4, 5, 6, 10, 16},
        {0, 11},
    ]
    bcc = list(nx.biconnected_components(K))
    assert_components_equal(bcc, answer)
    assert set(nx.articulation_points(K)) == {0}


def test_biconnected_eppstein():
    # tests from http://www.ics.uci.edu/~eppstein/PADS/Biconnectivity.py
    G1 = nx.Graph(
        {
            0: [1, 2, 5],
            1: [0, 5],
            2: [0, 3, 4],
            3: [2, 4, 5, 6],
            4: [2, 3, 5, 6],
            5: [0, 1, 3, 4],
            6: [3, 4],
        }
    )
    G2 = nx.Graph(
        {
            0: [2, 5],
            1: [3, 8],
            2: [0, 3, 5],
            3: [1, 2, 6, 8],
            4: [7],
            5: [0, 2],
            6: [3, 8],
            7: [4],
            8: [1, 3, 6],
        }
    )
    assert nx.is_biconnected(G1)
    assert not nx.is_biconnected(G2)
    answer_G2 = [{1, 3, 6, 8}, {0, 2, 5}, {2, 3}, {4, 7}]
    bcc = list(nx.biconnected_components(G2))
    assert_components_equal(bcc, answer_G2)


def test_null_graph():
    G = nx.Graph()
    assert not nx.is_biconnected(G)
    assert list(nx.biconnected_components(G)) == []
    assert list(nx.biconnected_component_edges(G)) == []
    assert list(nx.articulation_points(G)) == []


def test_connected_raise():
    DG = nx.DiGraph()
    with pytest.raises(NetworkXNotImplemented):
        next(nx.biconnected_components(DG))
    with pytest.raises(NetworkXNotImplemented):
        next(nx.biconnected_component_edges(DG))
    with pytest.raises(NetworkXNotImplemented):
        next(nx.articulation_points(DG))
    pytest.raises(NetworkXNotImplemented, nx.is_biconnected, DG)