Home | History | Annotate | Download | only in tests 
      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