Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / approximation / tests / test_kcomponents.py @ 5cef0f13

History | View | Annotate | Download (9.14 KB)

1
# Test for approximation to k-components algorithm
2
from nose.tools import assert_equal, assert_true, assert_false, assert_in
3
from nose.tools import assert_raises, raises, assert_greater_equal
4
import networkx as nx
5
from networkx.algorithms.approximation import k_components
6
from networkx.algorithms.approximation.kcomponents import _AntiGraph, _same
7

    
8

    
9
def build_k_number_dict(k_components):
10
    k_num = {}
11
    for k, comps in sorted(k_components.items()):
12
        for comp in comps:
13
            for node in comp:
14
                k_num[node] = k
15
    return k_num
16

    
17
##
18
# Some nice synthetic graphs
19
##
20

    
21

    
22
def graph_example_1():
23
    G = nx.convert_node_labels_to_integers(nx.grid_graph([5, 5]),
24
                                           label_attribute='labels')
25
    rlabels = nx.get_node_attributes(G, 'labels')
26
    labels = {v: k for k, v in rlabels.items()}
27

    
28
    for nodes in [(labels[(0, 0)], labels[(1, 0)]),
29
                  (labels[(0, 4)], labels[(1, 4)]),
30
                  (labels[(3, 0)], labels[(4, 0)]),
31
                  (labels[(3, 4)], labels[(4, 4)])]:
32
        new_node = G.order() + 1
33
        # Petersen graph is triconnected
34
        P = nx.petersen_graph()
35
        G = nx.disjoint_union(G, P)
36
        # Add two edges between the grid and P
37
        G.add_edge(new_node + 1, nodes[0])
38
        G.add_edge(new_node, nodes[1])
39
        # K5 is 4-connected
40
        K = nx.complete_graph(5)
41
        G = nx.disjoint_union(G, K)
42
        # Add three edges between P and K5
43
        G.add_edge(new_node + 2, new_node + 11)
44
        G.add_edge(new_node + 3, new_node + 12)
45
        G.add_edge(new_node + 4, new_node + 13)
46
        # Add another K5 sharing a node
47
        G = nx.disjoint_union(G, K)
48
        nbrs = G[new_node + 10]
49
        G.remove_node(new_node + 10)
50
        for nbr in nbrs:
51
            G.add_edge(new_node + 17, nbr)
52
        G.add_edge(new_node + 16, new_node + 5)
53
    return G
54

    
55

    
56
def torrents_and_ferraro_graph():
57
    G = nx.convert_node_labels_to_integers(nx.grid_graph([5, 5]),
58
                                           label_attribute='labels')
59
    rlabels = nx.get_node_attributes(G, 'labels')
60
    labels = {v: k for k, v in rlabels.items()}
61

    
62
    for nodes in [(labels[(0, 4)], labels[(1, 4)]),
63
                  (labels[(3, 4)], labels[(4, 4)])]:
64
        new_node = G.order() + 1
65
        # Petersen graph is triconnected
66
        P = nx.petersen_graph()
67
        G = nx.disjoint_union(G, P)
68
        # Add two edges between the grid and P
69
        G.add_edge(new_node + 1, nodes[0])
70
        G.add_edge(new_node, nodes[1])
71
        # K5 is 4-connected
72
        K = nx.complete_graph(5)
73
        G = nx.disjoint_union(G, K)
74
        # Add three edges between P and K5
75
        G.add_edge(new_node + 2, new_node + 11)
76
        G.add_edge(new_node + 3, new_node + 12)
77
        G.add_edge(new_node + 4, new_node + 13)
78
        # Add another K5 sharing a node
79
        G = nx.disjoint_union(G, K)
80
        nbrs = G[new_node + 10]
81
        G.remove_node(new_node + 10)
82
        for nbr in nbrs:
83
            G.add_edge(new_node + 17, nbr)
84
        # Commenting this makes the graph not biconnected !!
85
        # This stupid mistake make one reviewer very angry :P
86
        G.add_edge(new_node + 16, new_node + 8)
87

    
88
    for nodes in [(labels[(0, 0)], labels[(1, 0)]),
89
                  (labels[(3, 0)], labels[(4, 0)])]:
90
        new_node = G.order() + 1
91
        # Petersen graph is triconnected
92
        P = nx.petersen_graph()
93
        G = nx.disjoint_union(G, P)
94
        # Add two edges between the grid and P
95
        G.add_edge(new_node + 1, nodes[0])
96
        G.add_edge(new_node, nodes[1])
97
        # K5 is 4-connected
98
        K = nx.complete_graph(5)
99
        G = nx.disjoint_union(G, K)
100
        # Add three edges between P and K5
101
        G.add_edge(new_node + 2, new_node + 11)
102
        G.add_edge(new_node + 3, new_node + 12)
103
        G.add_edge(new_node + 4, new_node + 13)
104
        # Add another K5 sharing two nodes
105
        G = nx.disjoint_union(G, K)
106
        nbrs = G[new_node + 10]
107
        G.remove_node(new_node + 10)
108
        for nbr in nbrs:
109
            G.add_edge(new_node + 17, nbr)
110
        nbrs2 = G[new_node + 9]
111
        G.remove_node(new_node + 9)
112
        for nbr in nbrs2:
113
            G.add_edge(new_node + 18, nbr)
114
    return G
115

    
116
# Helper function
117

    
118

    
119
def _check_connectivity(G):
120
    result = k_components(G)
121
    for k, components in result.items():
122
        if k < 3:
123
            continue
124
        for component in components:
125
            C = G.subgraph(component)
126
            K = nx.node_connectivity(C)
127
            assert_greater_equal(K, k)
128

    
129

    
130
def test_torrents_and_ferraro_graph():
131
    G = torrents_and_ferraro_graph()
132
    _check_connectivity(G)
133

    
134

    
135
def test_example_1():
136
    G = graph_example_1()
137
    _check_connectivity(G)
138

    
139

    
140
def test_karate_0():
141
    G = nx.karate_club_graph()
142
    _check_connectivity(G)
143

    
144

    
145
def test_karate_1():
146
    karate_k_num = {0: 4, 1: 4, 2: 4, 3: 4, 4: 3, 5: 3, 6: 3, 7: 4, 8: 4, 9: 2,
147
                    10: 3, 11: 1, 12: 2, 13: 4, 14: 2, 15: 2, 16: 2, 17: 2, 18: 2,
148
                    19: 3, 20: 2, 21: 2, 22: 2, 23: 3, 24: 3, 25: 3, 26: 2, 27: 3,
149
                    28: 3, 29: 3, 30: 4, 31: 3, 32: 4, 33: 4}
150
    approx_karate_k_num = karate_k_num.copy()
151
    approx_karate_k_num[24] = 2
152
    approx_karate_k_num[25] = 2
153
    G = nx.karate_club_graph()
154
    k_comps = k_components(G)
155
    k_num = build_k_number_dict(k_comps)
156
    assert_in(k_num, (karate_k_num, approx_karate_k_num))
157

    
158

    
159
def test_example_1_detail_3_and_4():
160
    G = graph_example_1()
161
    result = k_components(G)
162
    # In this example graph there are 8 3-components, 4 with 15 nodes
163
    # and 4 with 5 nodes.
164
    assert_equal(len(result[3]), 8)
165
    assert_equal(len([c for c in result[3] if len(c) == 15]), 4)
166
    assert_equal(len([c for c in result[3] if len(c) == 5]), 4)
167
    # There are also 8 4-components all with 5 nodes.
168
    assert_equal(len(result[4]), 8)
169
    assert_true(all(len(c) == 5 for c in result[4]))
170
    # Finally check that the k-components detected have actually node
171
    # connectivity >= k.
172
    for k, components in result.items():
173
        if k < 3:
174
            continue
175
        for component in components:
176
            K = nx.node_connectivity(G.subgraph(component))
177
            assert_greater_equal(K, k)
178

    
179

    
180
@raises(nx.NetworkXNotImplemented)
181
def test_directed():
182
    G = nx.gnp_random_graph(10, 0.4, directed=True)
183
    kc = k_components(G)
184

    
185

    
186
def test_same():
187
    equal = {'A': 2, 'B': 2, 'C': 2}
188
    slightly_different = {'A': 2, 'B': 1, 'C': 2}
189
    different = {'A': 2, 'B': 8, 'C': 18}
190
    assert_true(_same(equal))
191
    assert_false(_same(slightly_different))
192
    assert_true(_same(slightly_different, tol=1))
193
    assert_false(_same(different))
194
    assert_false(_same(different, tol=4))
195

    
196

    
197
class TestAntiGraph:
198
    def setUp(self):
199
        self.Gnp = nx.gnp_random_graph(20, 0.8)
200
        self.Anp = _AntiGraph(nx.complement(self.Gnp))
201
        self.Gd = nx.davis_southern_women_graph()
202
        self.Ad = _AntiGraph(nx.complement(self.Gd))
203
        self.Gk = nx.karate_club_graph()
204
        self.Ak = _AntiGraph(nx.complement(self.Gk))
205
        self.GA = [(self.Gnp, self.Anp),
206
                   (self.Gd, self.Ad),
207
                   (self.Gk, self.Ak)]
208

    
209
    def test_size(self):
210
        for G, A in self.GA:
211
            n = G.order()
212
            s = len(list(G.edges())) + len(list(A.edges()))
213
            assert_true(s == (n * (n - 1)) / 2)
214

    
215
    def test_degree(self):
216
        for G, A in self.GA:
217
            assert_equal(sorted(G.degree()), sorted(A.degree()))
218

    
219
    def test_core_number(self):
220
        for G, A in self.GA:
221
            assert_equal(nx.core_number(G), nx.core_number(A))
222

    
223
    def test_connected_components(self):
224
        for G, A in self.GA:
225
            gc = [set(c) for c in nx.connected_components(G)]
226
            ac = [set(c) for c in nx.connected_components(A)]
227
            for comp in ac:
228
                assert_true(comp in gc)
229

    
230
    def test_adj(self):
231
        for G, A in self.GA:
232
            for n, nbrs in G.adj.items():
233
                a_adj = sorted((n, sorted(ad)) for n, ad in A.adj.items())
234
                g_adj = sorted((n, sorted(ad)) for n, ad in G.adj.items())
235
                assert_equal(a_adj, g_adj)
236

    
237
    def test_adjacency(self):
238
        for G, A in self.GA:
239
            a_adj = list(A.adjacency())
240
            for n, nbrs in G.adjacency():
241
                assert_true((n, set(nbrs)) in a_adj)
242

    
243
    def test_neighbors(self):
244
        for G, A in self.GA:
245
            node = list(G.nodes())[0]
246
            assert_equal(set(G.neighbors(node)), set(A.neighbors(node)))
247

    
248
    def test_node_not_in_graph(self):
249
        for G, A in self.GA:
250
            node = 'non_existent_node'
251
            assert_raises(nx.NetworkXError, A.neighbors, node)
252
            assert_raises(nx.NetworkXError, G.neighbors, node)
253

    
254
    def test_degree_thingraph(self):
255
        for G, A in self.GA:
256
            node = list(G.nodes())[0]
257
            nodes = list(G.nodes())[1:4]
258
            assert_equal(G.degree(node), A.degree(node))
259
            assert_equal(sum(d for n, d in G.degree()), sum(d for n, d in A.degree()))
260
            # AntiGraph is a ThinGraph, so all the weights are 1
261
            assert_equal(sum(d for n, d in A.degree()),
262
                         sum(d for n, d in A.degree(weight='weight')))
263
            assert_equal(sum(d for n, d in G.degree(nodes)),
264
                         sum(d for n, d in A.degree(nodes)))