Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / components / tests / test_biconnected.py @ 5cef0f13

History | View | Annotate | Download (5.96 KB)

1
#!/usr/bin/env python
2
from nose.tools import *
3
import networkx as nx
4
from networkx.algorithms.components import biconnected
5
from networkx import NetworkXNotImplemented
6

    
7

    
8
def assert_components_edges_equal(x, y):
9
    sx = {frozenset([frozenset(e) for e in c]) for c in x}
10
    sy = {frozenset([frozenset(e) for e in c]) for c in y}
11
    assert_equal(sx, sy)
12

    
13

    
14
def assert_components_equal(x, y):
15
    sx = {frozenset(c) for c in x}
16
    sy = {frozenset(c) for c in y}
17
    assert_equal(sx, sy)
18

    
19

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

    
27
    answer = [
28
        {12, 13, 14, 15, 16, 17, 18, 19},
29
        {0, 1, 2, 3, 4, 5, 6, 7},
30
        {22, 23, 24, 25},
31
        {11, 12},
32
        {10, 11},
33
        {9, 10},
34
        {8, 9},
35
        {7, 8},
36
        {21, 22},
37
        {20, 21},
38
        {7, 20},
39
    ]
40
    assert_components_equal(list(nx.biconnected_components(G)), answer)
41

    
42
    G.add_edge(2, 17)
43
    pts = set(nx.articulation_points(G))
44
    assert_equal(pts, {7, 20, 21, 22})
45

    
46

    
47
def test_articulation_points_repetitions():
48
    G = nx.Graph()
49
    G.add_edges_from([(0, 1), (1, 2), (1, 3)])
50
    assert_equal(list(nx.articulation_points(G)), [1])
51

    
52

    
53
def test_articulation_points_cycle():
54
    G = nx.cycle_graph(3)
55
    nx.add_cycle(G, [1, 3, 4])
56
    pts = set(nx.articulation_points(G))
57
    assert_equal(pts, {1})
58

    
59

    
60
def test_is_biconnected():
61
    G = nx.cycle_graph(3)
62
    assert_true(nx.is_biconnected(G))
63
    nx.add_cycle(G, [1, 3, 4])
64
    assert_false(nx.is_biconnected(G))
65

    
66

    
67
def test_empty_is_biconnected():
68
    G = nx.empty_graph(5)
69
    assert_false(nx.is_biconnected(G))
70
    G.add_edge(0, 1)
71
    assert_false(nx.is_biconnected(G))
72

    
73

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

    
80
# deprecated
81

    
82

    
83
def test_biconnected_component_subgraphs_cycle():
84
    G = nx.cycle_graph(3)
85
    nx.add_cycle(G, [1, 3, 4, 5])
86
    Gc = set(nx.biconnected_component_subgraphs(G))
87
    assert_equal(len(Gc), 2)
88
    g1, g2 = Gc
89
    if 0 in g1:
90
        assert_true(nx.is_isomorphic(g1, nx.Graph([(0, 1), (0, 2), (1, 2)])))
91
        assert_true(nx.is_isomorphic(g2, nx.Graph([(1, 3), (1, 5), (3, 4), (4, 5)])))
92
    else:
93
        assert_true(nx.is_isomorphic(g1, nx.Graph([(1, 3), (1, 5), (3, 4), (4, 5)])))
94
        assert_true(nx.is_isomorphic(g2, nx.Graph([(0, 1), (0, 2), (1, 2)])))
95

    
96

    
97
def test_biconnected_components1():
98
    # graph example from
99
    # http://www.ibluemojo.com/school/articul_algorithm.html
100
    edges = [
101
        (0, 1), (0, 5), (0, 6), (0, 14), (1, 5), (1, 6), (1, 14), (2, 4),
102
        (2, 10), (3, 4), (3, 15), (4, 6), (4, 7), (4, 10), (5, 14), (6, 14),
103
        (7, 9), (8, 9), (8, 12), (8, 13), (10, 15), (11, 12), (11, 13), (12, 13)
104
    ]
105
    G = nx.Graph(edges)
106
    pts = set(nx.articulation_points(G))
107
    assert_equal(pts, {4, 6, 7, 8, 9})
108
    comps = list(nx.biconnected_component_edges(G))
109
    answer = [
110
        [(3, 4), (15, 3), (10, 15), (10, 4), (2, 10), (4, 2)],
111
        [(13, 12), (13, 8), (11, 13), (12, 11), (8, 12)],
112
        [(9, 8)],
113
        [(7, 9)],
114
        [(4, 7)],
115
        [(6, 4)],
116
        [(14, 0), (5, 1), (5, 0), (14, 5), (14, 1), (6, 14), (6, 0), (1, 6), (0, 1)],
117
    ]
118
    assert_components_edges_equal(comps, answer)
119

    
120

    
121
def test_biconnected_components2():
122
    G = nx.Graph()
123
    nx.add_cycle(G, 'ABC')
124
    nx.add_cycle(G, 'CDE')
125
    nx.add_cycle(G, 'FIJHG')
126
    nx.add_cycle(G, 'GIJ')
127
    G.add_edge('E', 'G')
128
    comps = list(nx.biconnected_component_edges(G))
129
    answer = [
130
        [tuple('GF'), tuple('FI'), tuple('IG'), tuple('IJ'),
131
         tuple('JG'), tuple('JH'), tuple('HG')],
132
        [tuple('EG')],
133
        [tuple('CD'), tuple('DE'), tuple('CE')],
134
        [tuple('AB'), tuple('BC'), tuple('AC')]
135
    ]
136
    assert_components_edges_equal(comps, answer)
137

    
138

    
139
def test_biconnected_davis():
140
    D = nx.davis_southern_women_graph()
141
    bcc = list(nx.biconnected_components(D))[0]
142
    assert_true(set(D) == bcc)  # All nodes in a giant bicomponent
143
    # So no articulation points
144
    assert_equal(len(list(nx.articulation_points(D))), 0)
145

    
146

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

    
157

    
158
def test_biconnected_eppstein():
159
    # tests from http://www.ics.uci.edu/~eppstein/PADS/Biconnectivity.py
160
    G1 = nx.Graph({
161
        0: [1, 2, 5],
162
        1: [0, 5],
163
        2: [0, 3, 4],
164
        3: [2, 4, 5, 6],
165
        4: [2, 3, 5, 6],
166
        5: [0, 1, 3, 4],
167
        6: [3, 4],
168
    })
169
    G2 = nx.Graph({
170
        0: [2, 5],
171
        1: [3, 8],
172
        2: [0, 3, 5],
173
        3: [1, 2, 6, 8],
174
        4: [7],
175
        5: [0, 2],
176
        6: [3, 8],
177
        7: [4],
178
        8: [1, 3, 6],
179
    })
180
    assert_true(nx.is_biconnected(G1))
181
    assert_false(nx.is_biconnected(G2))
182
    answer_G2 = [{1, 3, 6, 8}, {0, 2, 5}, {2, 3}, {4, 7}]
183
    bcc = list(nx.biconnected_components(G2))
184
    assert_components_equal(bcc, answer_G2)
185

    
186

    
187
def test_null_graph():
188
    G = nx.Graph()
189
    assert_false(nx.is_biconnected(G))
190
    assert_equal(list(nx.biconnected_components(G)), [])
191
    assert_equal(list(nx.biconnected_component_edges(G)), [])
192
    assert_equal(list(nx.articulation_points(G)), [])
193

    
194

    
195
def test_connected_raise():
196
    DG = nx.DiGraph()
197
    assert_raises(NetworkXNotImplemented, nx.biconnected_components, DG)
198
    assert_raises(NetworkXNotImplemented, nx.biconnected_component_edges, DG)
199
    assert_raises(NetworkXNotImplemented, nx.articulation_points, DG)
200
    assert_raises(NetworkXNotImplemented, nx.is_biconnected, DG)
201
    # deprecated
202
    assert_raises(NetworkXNotImplemented, nx.biconnected_component_subgraphs, DG)