1 import networkx as nx 2 from networkx import tensor_product,cartesian_product,lexicographic_product,strong_product 3 from nose.tools import assert_raises, assert_true, assert_equal, raises 4 5 @raises(nx.NetworkXError) 6 def test_tensor_product_raises(): 7 P = tensor_product(nx.DiGraph(),nx.Graph()) 8 9 def test_tensor_product_null(): 10 null=nx.null_graph() 11 empty10=nx.empty_graph(10) 12 K3=nx.complete_graph(3) 13 K10=nx.complete_graph(10) 14 P3=nx.path_graph(3) 15 P10=nx.path_graph(10) 16 # null graph 17 G=tensor_product(null,null) 18 assert_true(nx.is_isomorphic(G,null)) 19 # null_graph X anything = null_graph and v.v. 20 G=tensor_product(null,empty10) 21 assert_true(nx.is_isomorphic(G,null)) 22 G=tensor_product(null,K3) 23 assert_true(nx.is_isomorphic(G,null)) 24 G=tensor_product(null,K10) 25 assert_true(nx.is_isomorphic(G,null)) 26 G=tensor_product(null,P3) 27 assert_true(nx.is_isomorphic(G,null)) 28 G=tensor_product(null,P10) 29 assert_true(nx.is_isomorphic(G,null)) 30 G=tensor_product(empty10,null) 31 assert_true(nx.is_isomorphic(G,null)) 32 G=tensor_product(K3,null) 33 assert_true(nx.is_isomorphic(G,null)) 34 G=tensor_product(K10,null) 35 assert_true(nx.is_isomorphic(G,null)) 36 G=tensor_product(P3,null) 37 assert_true(nx.is_isomorphic(G,null)) 38 G=tensor_product(P10,null) 39 assert_true(nx.is_isomorphic(G,null)) 40 41 def test_tensor_product_size(): 42 P5 = nx.path_graph(5) 43 K3 = nx.complete_graph(3) 44 K5 = nx.complete_graph(5) 45 46 G=tensor_product(P5,K3) 47 assert_equal(nx.number_of_nodes(G),5*3) 48 G=tensor_product(K3,K5) 49 assert_equal(nx.number_of_nodes(G),3*5) 50 51 52 def test_tensor_product_combinations(): 53 # basic smoke test, more realistic tests would be usefule 54 P5 = nx.path_graph(5) 55 K3 = nx.complete_graph(3) 56 G=tensor_product(P5,K3) 57 assert_equal(nx.number_of_nodes(G),5*3) 58 G=tensor_product(P5,nx.MultiGraph(K3)) 59 assert_equal(nx.number_of_nodes(G),5*3) 60 G=tensor_product(nx.MultiGraph(P5),K3) 61 assert_equal(nx.number_of_nodes(G),5*3) 62 G=tensor_product(nx.MultiGraph(P5),nx.MultiGraph(K3)) 63 assert_equal(nx.number_of_nodes(G),5*3) 64 65 G=tensor_product(nx.DiGraph(P5),nx.DiGraph(K3)) 66 assert_equal(nx.number_of_nodes(G),5*3) 67 68 69 def test_tensor_product_classic_result(): 70 K2 = nx.complete_graph(2) 71 G = nx.petersen_graph() 72 G = tensor_product(G,K2) 73 assert_true(nx.is_isomorphic(G,nx.desargues_graph())) 74 75 G = nx.cycle_graph(5) 76 G = tensor_product(G,K2) 77 assert_true(nx.is_isomorphic(G,nx.cycle_graph(10))) 78 79 G = nx.tetrahedral_graph() 80 G = tensor_product(G,K2) 81 assert_true(nx.is_isomorphic(G,nx.cubical_graph())) 82 83 def test_tensor_product_random(): 84 G = nx.erdos_renyi_graph(10,2/10.) 85 H = nx.erdos_renyi_graph(10,2/10.) 86 GH = tensor_product(G,H) 87 88 for (u_G,u_H) in GH.nodes_iter(): 89 for (v_G,v_H) in GH.nodes_iter(): 90 if H.has_edge(u_H,v_H) and G.has_edge(u_G,v_G): 91 assert_true(GH.has_edge((u_G,u_H),(v_G,v_H))) 92 else: 93 assert_true(not GH.has_edge((u_G,u_H),(v_G,v_H))) 94 95 96 def test_cartesian_product_multigraph(): 97 G=nx.MultiGraph() 98 G.add_edge(1,2,key=0) 99 G.add_edge(1,2,key=1) 100 H=nx.MultiGraph() 101 H.add_edge(3,4,key=0) 102 H.add_edge(3,4,key=1) 103 GH=cartesian_product(G,H) 104 assert_equal( set(GH) , set([(1, 3), (2, 3), (2, 4), (1, 4)])) 105 assert_equal( set(GH.edges(keys=True)) , 106 set([((1, 3), (2, 3), 0), ((1, 3), (2, 3), 1), 107 ((1, 3), (1, 4), 0), ((1, 3), (1, 4), 1), 108 ((2, 3), (2, 4), 0), ((2, 3), (2, 4), 1), 109 ((2, 4), (1, 4), 0), ((2, 4), (1, 4), 1)])) 110 111 @raises(nx.NetworkXError) 112 def test_cartesian_product_raises(): 113 P = cartesian_product(nx.DiGraph(),nx.Graph()) 114 115 def test_cartesian_product_null(): 116 null=nx.null_graph() 117 empty10=nx.empty_graph(10) 118 K3=nx.complete_graph(3) 119 K10=nx.complete_graph(10) 120 P3=nx.path_graph(3) 121 P10=nx.path_graph(10) 122 # null graph 123 G=cartesian_product(null,null) 124 assert_true(nx.is_isomorphic(G,null)) 125 # null_graph X anything = null_graph and v.v. 126 G=cartesian_product(null,empty10) 127 assert_true(nx.is_isomorphic(G,null)) 128 G=cartesian_product(null,K3) 129 assert_true(nx.is_isomorphic(G,null)) 130 G=cartesian_product(null,K10) 131 assert_true(nx.is_isomorphic(G,null)) 132 G=cartesian_product(null,P3) 133 assert_true(nx.is_isomorphic(G,null)) 134 G=cartesian_product(null,P10) 135 assert_true(nx.is_isomorphic(G,null)) 136 G=cartesian_product(empty10,null) 137 assert_true(nx.is_isomorphic(G,null)) 138 G=cartesian_product(K3,null) 139 assert_true(nx.is_isomorphic(G,null)) 140 G=cartesian_product(K10,null) 141 assert_true(nx.is_isomorphic(G,null)) 142 G=cartesian_product(P3,null) 143 assert_true(nx.is_isomorphic(G,null)) 144 G=cartesian_product(P10,null) 145 assert_true(nx.is_isomorphic(G,null)) 146 147 def test_cartesian_product_size(): 148 # order(GXH)=order(G)*order(H) 149 K5=nx.complete_graph(5) 150 P5=nx.path_graph(5) 151 K3=nx.complete_graph(3) 152 G=cartesian_product(P5,K3) 153 assert_equal(nx.number_of_nodes(G),5*3) 154 assert_equal(nx.number_of_edges(G), 155 nx.number_of_edges(P5)*nx.number_of_nodes(K3)+ 156 nx.number_of_edges(K3)*nx.number_of_nodes(P5)) 157 G=cartesian_product(K3,K5) 158 assert_equal(nx.number_of_nodes(G),3*5) 159 assert_equal(nx.number_of_edges(G), 160 nx.number_of_edges(K5)*nx.number_of_nodes(K3)+ 161 nx.number_of_edges(K3)*nx.number_of_nodes(K5)) 162 163 def test_cartesian_product_classic(): 164 # test some classic product graphs 165 P2 = nx.path_graph(2) 166 P3 = nx.path_graph(3) 167 # cube = 2-path X 2-path 168 G=cartesian_product(P2,P2) 169 G=cartesian_product(P2,G) 170 assert_true(nx.is_isomorphic(G,nx.cubical_graph())) 171 172 # 3x3 grid 173 G=cartesian_product(P3,P3) 174 assert_true(nx.is_isomorphic(G,nx.grid_2d_graph(3,3))) 175 176 def test_cartesian_product_random(): 177 G = nx.erdos_renyi_graph(10,2/10.) 178 H = nx.erdos_renyi_graph(10,2/10.) 179 GH = cartesian_product(G,H) 180 181 for (u_G,u_H) in GH.nodes_iter(): 182 for (v_G,v_H) in GH.nodes_iter(): 183 if (u_G==v_G and H.has_edge(u_H,v_H)) or \ 184 (u_H==v_H and G.has_edge(u_G,v_G)): 185 assert_true(GH.has_edge((u_G,u_H),(v_G,v_H))) 186 else: 187 assert_true(not GH.has_edge((u_G,u_H),(v_G,v_H))) 188 189 @raises(nx.NetworkXError) 190 def test_lexicographic_product_raises(): 191 P=lexicographic_product(nx.DiGraph(),nx.Graph()) 192 193 def test_lexicographic_product_null(): 194 null=nx.null_graph() 195 empty10=nx.empty_graph(10) 196 K3=nx.complete_graph(3) 197 K10=nx.complete_graph(10) 198 P3=nx.path_graph(3) 199 P10=nx.path_graph(10) 200 # null graph 201 G=lexicographic_product(null,null) 202 assert_true(nx.is_isomorphic(G,null)) 203 # null_graph X anything = null_graph and v.v. 204 G=lexicographic_product(null,empty10) 205 assert_true(nx.is_isomorphic(G,null)) 206 G=lexicographic_product(null,K3) 207 assert_true(nx.is_isomorphic(G,null)) 208 G=lexicographic_product(null,K10) 209 assert_true(nx.is_isomorphic(G,null)) 210 G=lexicographic_product(null,P3) 211 assert_true(nx.is_isomorphic(G,null)) 212 G=lexicographic_product(null,P10) 213 assert_true(nx.is_isomorphic(G,null)) 214 G=lexicographic_product(empty10,null) 215 assert_true(nx.is_isomorphic(G,null)) 216 G=lexicographic_product(K3,null) 217 assert_true(nx.is_isomorphic(G,null)) 218 G=lexicographic_product(K10,null) 219 assert_true(nx.is_isomorphic(G,null)) 220 G=lexicographic_product(P3,null) 221 assert_true(nx.is_isomorphic(G,null)) 222 G=lexicographic_product(P10,null) 223 assert_true(nx.is_isomorphic(G,null)) 224 225 def test_lexicographic_product_size(): 226 K5=nx.complete_graph(5) 227 P5=nx.path_graph(5) 228 K3=nx.complete_graph(3) 229 G=lexicographic_product(P5,K3) 230 assert_equal(nx.number_of_nodes(G),5*3) 231 G=lexicographic_product(K3,K5) 232 assert_equal(nx.number_of_nodes(G),3*5) 233 234 def test_lexicographic_product_combinations(): 235 P5=nx.path_graph(5) 236 K3=nx.complete_graph(3) 237 G=lexicographic_product(P5,K3) 238 assert_equal(nx.number_of_nodes(G),5*3) 239 G=lexicographic_product(nx.MultiGraph(P5),K3) 240 assert_equal(nx.number_of_nodes(G),5*3) 241 G=lexicographic_product(P5,nx.MultiGraph(K3)) 242 assert_equal(nx.number_of_nodes(G),5*3) 243 G=lexicographic_product(nx.MultiGraph(P5),nx.MultiGraph(K3)) 244 assert_equal(nx.number_of_nodes(G),5*3) 245 246 247 248 249 #No classic easily found classic results for lexicographic product 250 def test_lexicographic_product_random(): 251 G = nx.erdos_renyi_graph(10,2/10.) 252 H = nx.erdos_renyi_graph(10,2/10.) 253 GH = lexicographic_product(G,H) 254 255 for (u_G,u_H) in GH.nodes_iter(): 256 for (v_G,v_H) in GH.nodes_iter(): 257 if G.has_edge(u_G,v_G) or (u_G==v_G and H.has_edge(u_H,v_H)): 258 assert_true(GH.has_edge((u_G,u_H),(v_G,v_H))) 259 else: 260 assert_true(not GH.has_edge((u_G,u_H),(v_G,v_H))) 261 262 @raises(nx.NetworkXError) 263 def test_strong_product_raises(): 264 P = strong_product(nx.DiGraph(),nx.Graph()) 265 266 def test_strong_product_null(): 267 null=nx.null_graph() 268 empty10=nx.empty_graph(10) 269 K3=nx.complete_graph(3) 270 K10=nx.complete_graph(10) 271 P3=nx.path_graph(3) 272 P10=nx.path_graph(10) 273 # null graph 274 G=strong_product(null,null) 275 assert_true(nx.is_isomorphic(G,null)) 276 # null_graph X anything = null_graph and v.v. 277 G=strong_product(null,empty10) 278 assert_true(nx.is_isomorphic(G,null)) 279 G=strong_product(null,K3) 280 assert_true(nx.is_isomorphic(G,null)) 281 G=strong_product(null,K10) 282 assert_true(nx.is_isomorphic(G,null)) 283 G=strong_product(null,P3) 284 assert_true(nx.is_isomorphic(G,null)) 285 G=strong_product(null,P10) 286 assert_true(nx.is_isomorphic(G,null)) 287 G=strong_product(empty10,null) 288 assert_true(nx.is_isomorphic(G,null)) 289 G=strong_product(K3,null) 290 assert_true(nx.is_isomorphic(G,null)) 291 G=strong_product(K10,null) 292 assert_true(nx.is_isomorphic(G,null)) 293 G=strong_product(P3,null) 294 assert_true(nx.is_isomorphic(G,null)) 295 G=strong_product(P10,null) 296 assert_true(nx.is_isomorphic(G,null)) 297 298 def test_strong_product_size(): 299 K5=nx.complete_graph(5) 300 P5=nx.path_graph(5) 301 K3 = nx.complete_graph(3) 302 G=strong_product(P5,K3) 303 assert_equal(nx.number_of_nodes(G),5*3) 304 G=strong_product(K3,K5) 305 assert_equal(nx.number_of_nodes(G),3*5) 306 307 def test_strong_product_combinations(): 308 P5=nx.path_graph(5) 309 K3 = nx.complete_graph(3) 310 G=strong_product(P5,K3) 311 assert_equal(nx.number_of_nodes(G),5*3) 312 G=strong_product(nx.MultiGraph(P5),K3) 313 assert_equal(nx.number_of_nodes(G),5*3) 314 G=strong_product(P5,nx.MultiGraph(K3)) 315 assert_equal(nx.number_of_nodes(G),5*3) 316 G=strong_product(nx.MultiGraph(P5),nx.MultiGraph(K3)) 317 assert_equal(nx.number_of_nodes(G),5*3) 318 319 320 321 #No classic easily found classic results for strong product 322 def test_strong_product_random(): 323 G = nx.erdos_renyi_graph(10,2/10.) 324 H = nx.erdos_renyi_graph(10,2/10.) 325 GH = strong_product(G,H) 326 327 for (u_G,u_H) in GH.nodes_iter(): 328 for (v_G,v_H) in GH.nodes_iter(): 329 if (u_G==v_G and H.has_edge(u_H,v_H)) or \ 330 (u_H==v_H and G.has_edge(u_G,v_G)) or \ 331 (G.has_edge(u_G,v_G) and H.has_edge(u_H,v_H)): 332 assert_true(GH.has_edge((u_G,u_H),(v_G,v_H))) 333 else: 334 assert_true(not GH.has_edge((u_G,u_H),(v_G,v_H))) 335