1 from nose.tools import assert_equal, assert_true, assert_false, assert_raises 2 import networkx as nx 3 4 # Tests for node and edge cutsets 5 def _generate_no_biconnected(max_attempts=50): 6 attempts = 0 7 while True: 8 G = nx.fast_gnp_random_graph(100,0.0575) 9 if nx.is_connected(G) and not nx.is_biconnected(G): 10 attempts = 0 11 yield G 12 else: 13 if attempts >= max_attempts: 14 msg = "Tried %d times: no suitable Graph."%attempts 15 raise Exception(msg % max_attempts) 16 else: 17 attempts += 1 18 19 def test_articulation_points(): 20 Ggen = _generate_no_biconnected() 21 for i in range(5): 22 G = next(Ggen) 23 cut = nx.minimum_node_cut(G) 24 assert_true(len(cut) == 1) 25 assert_true(cut.pop() in set(nx.articulation_points(G))) 26 27 def test_brandes_erlebach_book(): 28 # Figure 1 chapter 7: Connectivity 29 # http://www.informatik.uni-augsburg.de/thi/personen/kammer/Graph_Connectivity.pdf 30 G = nx.Graph() 31 G.add_edges_from([(1,2),(1,3),(1,4),(1,5),(2,3),(2,6),(3,4), 32 (3,6),(4,6),(4,7),(5,7),(6,8),(6,9),(7,8), 33 (7,10),(8,11),(9,10),(9,11),(10,11)]) 34 # edge cutsets 35 assert_equal(3, len(nx.minimum_edge_cut(G,1,11))) 36 edge_cut = nx.minimum_edge_cut(G) 37 assert_equal(2, len(edge_cut)) # Node 5 has only two edges 38 H = G.copy() 39 H.remove_edges_from(edge_cut) 40 assert_false(nx.is_connected(H)) 41 # node cuts 42 assert_equal(set([6,7]), nx.minimum_st_node_cut(G,1,11)) 43 assert_equal(set([6,7]), nx.minimum_node_cut(G,1,11)) 44 node_cut = nx.minimum_node_cut(G) 45 assert_equal(2,len(node_cut)) 46 H = G.copy() 47 H.remove_nodes_from(node_cut) 48 assert_false(nx.is_connected(H)) 49 50 def test_white_harary_paper(): 51 # Figure 1b white and harary (2001) 52 # http://eclectic.ss.uci.edu/~drwhite/sm-w23.PDF 53 # A graph with high adhesion (edge connectivity) and low cohesion 54 # (node connectivity) 55 G = nx.disjoint_union(nx.complete_graph(4), nx.complete_graph(4)) 56 G.remove_node(7) 57 for i in range(4,7): 58 G.add_edge(0,i) 59 G = nx.disjoint_union(G, nx.complete_graph(4)) 60 G.remove_node(G.order()-1) 61 for i in range(7,10): 62 G.add_edge(0,i) 63 # edge cuts 64 edge_cut = nx.minimum_edge_cut(G) 65 assert_equal(3, len(edge_cut)) 66 H = G.copy() 67 H.remove_edges_from(edge_cut) 68 assert_false(nx.is_connected(H)) 69 # node cuts 70 node_cut = nx.minimum_node_cut(G) 71 assert_equal(set([0]), node_cut) 72 H = G.copy() 73 H.remove_nodes_from(node_cut) 74 assert_false(nx.is_connected(H)) 75 76 def test_petersen_cutset(): 77 G = nx.petersen_graph() 78 # edge cuts 79 edge_cut = nx.minimum_edge_cut(G) 80 assert_equal(3, len(edge_cut)) 81 H = G.copy() 82 H.remove_edges_from(edge_cut) 83 assert_false(nx.is_connected(H)) 84 # node cuts 85 node_cut = nx.minimum_node_cut(G) 86 assert_equal(3,len(node_cut)) 87 H = G.copy() 88 H.remove_nodes_from(node_cut) 89 assert_false(nx.is_connected(H)) 90 91 def test_octahedral_cutset(): 92 G=nx.octahedral_graph() 93 # edge cuts 94 edge_cut = nx.minimum_edge_cut(G) 95 assert_equal(4, len(edge_cut)) 96 H = G.copy() 97 H.remove_edges_from(edge_cut) 98 assert_false(nx.is_connected(H)) 99 # node cuts 100 node_cut = nx.minimum_node_cut(G) 101 assert_equal(4,len(node_cut)) 102 H = G.copy() 103 H.remove_nodes_from(node_cut) 104 assert_false(nx.is_connected(H)) 105 106 def test_icosahedral_cutset(): 107 G=nx.icosahedral_graph() 108 # edge cuts 109 edge_cut = nx.minimum_edge_cut(G) 110 assert_equal(5, len(edge_cut)) 111 H = G.copy() 112 H.remove_edges_from(edge_cut) 113 assert_false(nx.is_connected(H)) 114 # node cuts 115 node_cut = nx.minimum_node_cut(G) 116 assert_equal(5,len(node_cut)) 117 H = G.copy() 118 H.remove_nodes_from(node_cut) 119 assert_false(nx.is_connected(H)) 120 121 def test_node_cutset_exception(): 122 G=nx.Graph() 123 G.add_edges_from([(1,2),(3,4)]) 124 assert_raises(nx.NetworkXError, nx.minimum_node_cut,G) 125 126 def test_node_cutset_random_graphs(): 127 for i in range(5): 128 G = nx.fast_gnp_random_graph(50,0.2) 129 if not nx.is_connected(G): 130 ccs = iter(nx.connected_components(G)) 131 start = next(ccs)[0] 132 G.add_edges_from( (start,c[0]) for c in ccs ) 133 cutset = nx.minimum_node_cut(G) 134 assert_equal(nx.node_connectivity(G), len(cutset)) 135 G.remove_nodes_from(cutset) 136 assert_false(nx.is_connected(G)) 137 138 def test_edge_cutset_random_graphs(): 139 for i in range(5): 140 G = nx.fast_gnp_random_graph(50,0.2) 141 if not nx.is_connected(G): 142 ccs = iter(nx.connected_components(G)) 143 start = next(ccs)[0] 144 G.add_edges_from( (start,c[0]) for c in ccs ) 145 cutset = nx.minimum_edge_cut(G) 146 assert_equal(nx.edge_connectivity(G), len(cutset)) 147 G.remove_edges_from(cutset) 148 assert_false(nx.is_connected(G)) 149 150 # Test empty graphs 151 def test_empty_graphs(): 152 G = nx.Graph() 153 D = nx.DiGraph() 154 assert_raises(nx.NetworkXPointlessConcept, nx.minimum_node_cut, G) 155 assert_raises(nx.NetworkXPointlessConcept, nx.minimum_node_cut, D) 156 assert_raises(nx.NetworkXPointlessConcept, nx.minimum_edge_cut, G) 157 assert_raises(nx.NetworkXPointlessConcept, nx.minimum_edge_cut, D) 158
