view env/lib/python3.9/site-packages/networkx/algorithms/components/tests/test_biconnected.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
line wrap: on
line source
```
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)
pts = set(nx.articulation_points(G))
assert pts == {7, 8, 9, 10, 11, 12, 20, 21, 22}

{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},
]

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)
pts = set(nx.articulation_points(G))
assert pts == {1}

def test_is_biconnected():
G = nx.cycle_graph(3)
assert nx.is_biconnected(G)
assert not nx.is_biconnected(G)

def test_empty_is_biconnected():
G = nx.empty_graph(5)
assert not nx.is_biconnected(G)
assert not nx.is_biconnected(G)

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

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))
[(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)],
]

def test_biconnected_components2():
G = nx.Graph()
comps = list(nx.biconnected_component_edges(G))
[
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")],
]

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()
{
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 set(nx.articulation_points(K)) == {0}

def test_biconnected_eppstein():
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))

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)
```