diff env/lib/python3.9/site-packages/networkx/algorithms/components/tests/test_biconnected.py @ 0:4f3585e2f14b draft default tip

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author shellac
date Mon, 22 Mar 2021 18:12:50 +0000
parents
children
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/env/lib/python3.9/site-packages/networkx/algorithms/components/tests/test_biconnected.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,244 @@
+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
+    # 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()
+    pytest.raises(NetworkXNotImplemented, nx.biconnected_components, DG)
+    pytest.raises(NetworkXNotImplemented, nx.biconnected_component_edges, DG)
+    pytest.raises(NetworkXNotImplemented, nx.articulation_points, DG)
+    pytest.raises(NetworkXNotImplemented, nx.is_biconnected, DG)