Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (5.73 KB)

1
import itertools
2
from nose.tools import assert_true, assert_equal, assert_raises
3

    
4
import networkx as nx
5
from networkx.algorithms import approximation as approx
6

    
7

    
8
def test_global_node_connectivity():
9
    # Figure 1 chapter on Connectivity
10
    G = nx.Graph()
11
    G.add_edges_from([(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 6), (3, 4),
12
                      (3, 6), (4, 6), (4, 7), (5, 7), (6, 8), (6, 9), (7, 8),
13
                      (7, 10), (8, 11), (9, 10), (9, 11), (10, 11)])
14
    assert_equal(2, approx.local_node_connectivity(G, 1, 11))
15
    assert_equal(2, approx.node_connectivity(G))
16
    assert_equal(2, approx.node_connectivity(G, 1, 11))
17

    
18

    
19
def test_white_harary1():
20
    # Figure 1b white and harary (2001)
21
    # A graph with high adhesion (edge connectivity) and low cohesion
22
    # (node connectivity)
23
    G = nx.disjoint_union(nx.complete_graph(4), nx.complete_graph(4))
24
    G.remove_node(7)
25
    for i in range(4, 7):
26
        G.add_edge(0, i)
27
    G = nx.disjoint_union(G, nx.complete_graph(4))
28
    G.remove_node(G.order() - 1)
29
    for i in range(7, 10):
30
        G.add_edge(0, i)
31
    assert_equal(1, approx.node_connectivity(G))
32

    
33

    
34
def test_complete_graphs():
35
    for n in range(5, 25, 5):
36
        G = nx.complete_graph(n)
37
        assert_equal(n - 1, approx.node_connectivity(G))
38
        assert_equal(n - 1, approx.node_connectivity(G, 0, 3))
39

    
40

    
41
def test_empty_graphs():
42
    for k in range(5, 25, 5):
43
        G = nx.empty_graph(k)
44
        assert_equal(0, approx.node_connectivity(G))
45
        assert_equal(0, approx.node_connectivity(G, 0, 3))
46

    
47

    
48
def test_petersen():
49
    G = nx.petersen_graph()
50
    assert_equal(3, approx.node_connectivity(G))
51
    assert_equal(3, approx.node_connectivity(G, 0, 5))
52

    
53
# Approximation fails with tutte graph
54
# def test_tutte():
55
#    G = nx.tutte_graph()
56
#    assert_equal(3, approx.node_connectivity(G))
57

    
58

    
59
def test_dodecahedral():
60
    G = nx.dodecahedral_graph()
61
    assert_equal(3, approx.node_connectivity(G))
62
    assert_equal(3, approx.node_connectivity(G, 0, 5))
63

    
64

    
65
def test_octahedral():
66
    G = nx.octahedral_graph()
67
    assert_equal(4, approx.node_connectivity(G))
68
    assert_equal(4, approx.node_connectivity(G, 0, 5))
69

    
70
# Approximation can fail with icosahedral graph depending
71
# on iteration order.
72
# def test_icosahedral():
73
#    G=nx.icosahedral_graph()
74
#    assert_equal(5, approx.node_connectivity(G))
75
#    assert_equal(5, approx.node_connectivity(G, 0, 5))
76

    
77

    
78
def test_only_source():
79
    G = nx.complete_graph(5)
80
    assert_raises(nx.NetworkXError, approx.node_connectivity, G, s=0)
81

    
82

    
83
def test_only_target():
84
    G = nx.complete_graph(5)
85
    assert_raises(nx.NetworkXError, approx.node_connectivity, G, t=0)
86

    
87

    
88
def test_missing_source():
89
    G = nx.path_graph(4)
90
    assert_raises(nx.NetworkXError, approx.node_connectivity, G, 10, 1)
91

    
92

    
93
def test_missing_target():
94
    G = nx.path_graph(4)
95
    assert_raises(nx.NetworkXError, approx.node_connectivity, G, 1, 10)
96

    
97

    
98
def test_source_equals_target():
99
    G = nx.complete_graph(5)
100
    assert_raises(nx.NetworkXError, approx.local_node_connectivity, G, 0, 0)
101

    
102

    
103
def test_directed_node_connectivity():
104
    G = nx.cycle_graph(10, create_using=nx.DiGraph())  # only one direction
105
    D = nx.cycle_graph(10).to_directed()  # 2 reciprocal edges
106
    assert_equal(1, approx.node_connectivity(G))
107
    assert_equal(1, approx.node_connectivity(G, 1, 4))
108
    assert_equal(2,  approx.node_connectivity(D))
109
    assert_equal(2,  approx.node_connectivity(D, 1, 4))
110

    
111

    
112
class TestAllPairsNodeConnectivityApprox:
113

    
114
    def setUp(self):
115
        self.path = nx.path_graph(7)
116
        self.directed_path = nx.path_graph(7, create_using=nx.DiGraph())
117
        self.cycle = nx.cycle_graph(7)
118
        self.directed_cycle = nx.cycle_graph(7, create_using=nx.DiGraph())
119
        self.gnp = nx.gnp_random_graph(30, 0.1)
120
        self.directed_gnp = nx.gnp_random_graph(30, 0.1, directed=True)
121
        self.K20 = nx.complete_graph(20)
122
        self.K10 = nx.complete_graph(10)
123
        self.K5 = nx.complete_graph(5)
124
        self.G_list = [self.path, self.directed_path, self.cycle,
125
                       self.directed_cycle, self.gnp, self.directed_gnp, self.K10,
126
                       self.K5, self.K20]
127

    
128
    def test_cycles(self):
129
        K_undir = approx.all_pairs_node_connectivity(self.cycle)
130
        for source in K_undir:
131
            for target, k in K_undir[source].items():
132
                assert_true(k == 2)
133
        K_dir = approx.all_pairs_node_connectivity(self.directed_cycle)
134
        for source in K_dir:
135
            for target, k in K_dir[source].items():
136
                assert_true(k == 1)
137

    
138
    def test_complete(self):
139
        for G in [self.K10, self.K5, self.K20]:
140
            K = approx.all_pairs_node_connectivity(G)
141
            for source in K:
142
                for target, k in K[source].items():
143
                    assert_true(k == len(G) - 1)
144

    
145
    def test_paths(self):
146
        K_undir = approx.all_pairs_node_connectivity(self.path)
147
        for source in K_undir:
148
            for target, k in K_undir[source].items():
149
                assert_true(k == 1)
150
        K_dir = approx.all_pairs_node_connectivity(self.directed_path)
151
        for source in K_dir:
152
            for target, k in K_dir[source].items():
153
                if source < target:
154
                    assert_true(k == 1)
155
                else:
156
                    assert_true(k == 0)
157

    
158
    def test_cutoff(self):
159
        for G in [self.K10, self.K5, self.K20]:
160
            for mp in [2, 3, 4]:
161
                paths = approx.all_pairs_node_connectivity(G, cutoff=mp)
162
                for source in paths:
163
                    for target, K in paths[source].items():
164
                        assert_true(K == mp)
165

    
166
    def test_all_pairs_connectivity_nbunch(self):
167
        G = nx.complete_graph(5)
168
        nbunch = [0, 2, 3]
169
        C = approx.all_pairs_node_connectivity(G, nbunch=nbunch)
170
        assert_equal(len(C), len(nbunch))