Statistics
| Branch: | Revision:

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

 1 ```import itertools ``` ```from nose.tools import assert_true, assert_equal, assert_raises ``` ```import networkx as nx ``` ```from networkx.algorithms import approximation as approx ``` ```def test_global_node_connectivity(): ``` ``` # Figure 1 chapter on Connectivity ``` ``` G = nx.Graph() ``` ``` G.add_edges_from([(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 6), (3, 4), ``` ``` (3, 6), (4, 6), (4, 7), (5, 7), (6, 8), (6, 9), (7, 8), ``` ``` (7, 10), (8, 11), (9, 10), (9, 11), (10, 11)]) ``` ``` assert_equal(2, approx.local_node_connectivity(G, 1, 11)) ``` ``` assert_equal(2, approx.node_connectivity(G)) ``` ``` assert_equal(2, approx.node_connectivity(G, 1, 11)) ``` ```def test_white_harary1(): ``` ``` # Figure 1b white and harary (2001) ``` ``` # A graph with high adhesion (edge connectivity) and low cohesion ``` ``` # (node connectivity) ``` ``` G = nx.disjoint_union(nx.complete_graph(4), nx.complete_graph(4)) ``` ``` G.remove_node(7) ``` ``` for i in range(4, 7): ``` ``` G.add_edge(0, i) ``` ``` G = nx.disjoint_union(G, nx.complete_graph(4)) ``` ``` G.remove_node(G.order() - 1) ``` ``` for i in range(7, 10): ``` ``` G.add_edge(0, i) ``` ``` assert_equal(1, approx.node_connectivity(G)) ``` ```def test_complete_graphs(): ``` ``` for n in range(5, 25, 5): ``` ``` G = nx.complete_graph(n) ``` ``` assert_equal(n - 1, approx.node_connectivity(G)) ``` ``` assert_equal(n - 1, approx.node_connectivity(G, 0, 3)) ``` ```def test_empty_graphs(): ``` ``` for k in range(5, 25, 5): ``` ``` G = nx.empty_graph(k) ``` ``` assert_equal(0, approx.node_connectivity(G)) ``` ``` assert_equal(0, approx.node_connectivity(G, 0, 3)) ``` ```def test_petersen(): ``` ``` G = nx.petersen_graph() ``` ``` assert_equal(3, approx.node_connectivity(G)) ``` ``` assert_equal(3, approx.node_connectivity(G, 0, 5)) ``` ```# Approximation fails with tutte graph ``` ```# def test_tutte(): ``` ```# G = nx.tutte_graph() ``` ```# assert_equal(3, approx.node_connectivity(G)) ``` ```def test_dodecahedral(): ``` ``` G = nx.dodecahedral_graph() ``` ``` assert_equal(3, approx.node_connectivity(G)) ``` ``` assert_equal(3, approx.node_connectivity(G, 0, 5)) ``` ```def test_octahedral(): ``` ``` G = nx.octahedral_graph() ``` ``` assert_equal(4, approx.node_connectivity(G)) ``` ``` assert_equal(4, approx.node_connectivity(G, 0, 5)) ``` ```# Approximation can fail with icosahedral graph depending ``` ```# on iteration order. ``` ```# def test_icosahedral(): ``` ```# G=nx.icosahedral_graph() ``` ```# assert_equal(5, approx.node_connectivity(G)) ``` ```# assert_equal(5, approx.node_connectivity(G, 0, 5)) ``` ```def test_only_source(): ``` ``` G = nx.complete_graph(5) ``` ``` assert_raises(nx.NetworkXError, approx.node_connectivity, G, s=0) ``` ```def test_only_target(): ``` ``` G = nx.complete_graph(5) ``` ``` assert_raises(nx.NetworkXError, approx.node_connectivity, G, t=0) ``` ```def test_missing_source(): ``` ``` G = nx.path_graph(4) ``` ``` assert_raises(nx.NetworkXError, approx.node_connectivity, G, 10, 1) ``` ```def test_missing_target(): ``` ``` G = nx.path_graph(4) ``` ``` assert_raises(nx.NetworkXError, approx.node_connectivity, G, 1, 10) ``` ```def test_source_equals_target(): ``` ``` G = nx.complete_graph(5) ``` ``` assert_raises(nx.NetworkXError, approx.local_node_connectivity, G, 0, 0) ``` ```def test_directed_node_connectivity(): ``` ``` G = nx.cycle_graph(10, create_using=nx.DiGraph()) # only one direction ``` ``` D = nx.cycle_graph(10).to_directed() # 2 reciprocal edges ``` ``` assert_equal(1, approx.node_connectivity(G)) ``` ``` assert_equal(1, approx.node_connectivity(G, 1, 4)) ``` ``` assert_equal(2, approx.node_connectivity(D)) ``` ``` assert_equal(2, approx.node_connectivity(D, 1, 4)) ``` ```class TestAllPairsNodeConnectivityApprox: ``` ``` def setUp(self): ``` ``` self.path = nx.path_graph(7) ``` ``` self.directed_path = nx.path_graph(7, create_using=nx.DiGraph()) ``` ``` self.cycle = nx.cycle_graph(7) ``` ``` self.directed_cycle = nx.cycle_graph(7, create_using=nx.DiGraph()) ``` ``` self.gnp = nx.gnp_random_graph(30, 0.1) ``` ``` self.directed_gnp = nx.gnp_random_graph(30, 0.1, directed=True) ``` ``` self.K20 = nx.complete_graph(20) ``` ``` self.K10 = nx.complete_graph(10) ``` ``` self.K5 = nx.complete_graph(5) ``` ``` self.G_list = [self.path, self.directed_path, self.cycle, ``` ``` self.directed_cycle, self.gnp, self.directed_gnp, self.K10, ``` ``` self.K5, self.K20] ``` ``` def test_cycles(self): ``` ``` K_undir = approx.all_pairs_node_connectivity(self.cycle) ``` ``` for source in K_undir: ``` ``` for target, k in K_undir[source].items(): ``` ``` assert_true(k == 2) ``` ``` K_dir = approx.all_pairs_node_connectivity(self.directed_cycle) ``` ``` for source in K_dir: ``` ``` for target, k in K_dir[source].items(): ``` ``` assert_true(k == 1) ``` ``` def test_complete(self): ``` ``` for G in [self.K10, self.K5, self.K20]: ``` ``` K = approx.all_pairs_node_connectivity(G) ``` ``` for source in K: ``` ``` for target, k in K[source].items(): ``` ``` assert_true(k == len(G) - 1) ``` ``` def test_paths(self): ``` ``` K_undir = approx.all_pairs_node_connectivity(self.path) ``` ``` for source in K_undir: ``` ``` for target, k in K_undir[source].items(): ``` ``` assert_true(k == 1) ``` ``` K_dir = approx.all_pairs_node_connectivity(self.directed_path) ``` ``` for source in K_dir: ``` ``` for target, k in K_dir[source].items(): ``` ``` if source < target: ``` ``` assert_true(k == 1) ``` ``` else: ``` ``` assert_true(k == 0) ``` ``` def test_cutoff(self): ``` ``` for G in [self.K10, self.K5, self.K20]: ``` ``` for mp in [2, 3, 4]: ``` ``` paths = approx.all_pairs_node_connectivity(G, cutoff=mp) ``` ``` for source in paths: ``` ``` for target, K in paths[source].items(): ``` ``` assert_true(K == mp) ``` ``` def test_all_pairs_connectivity_nbunch(self): ``` ``` G = nx.complete_graph(5) ``` ``` nbunch = [0, 2, 3] ``` ``` C = approx.all_pairs_node_connectivity(G, nbunch=nbunch) ``` ``` assert_equal(len(C), len(nbunch)) ```