Home | History | Annotate | Download | only in tests 
      1 """
      2     Tests for VF2 isomorphism algorithm.
      3 """
      4 
      5 import os
      6 import struct
      7 import random
      8 
      9 from nose.tools import assert_true, assert_equal
     10 import networkx as nx
     11 from networkx.algorithms import isomorphism as iso
     12 
     13 class TestWikipediaExample(object):
     14     # Source: http://en.wikipedia.org/wiki/Graph_isomorphism
     15 
     16     # Nodes 'a', 'b', 'c' and 'd' form a column.
     17     # Nodes 'g', 'h', 'i' and 'j' form a column.
     18     g1edges = [['a','g'], ['a','h'], ['a','i'], 
     19                ['b','g'], ['b','h'], ['b','j'], 
     20                ['c','g'], ['c','i'], ['c','j'], 
     21                ['d','h'], ['d','i'], ['d','j']]
     22 
     23     # Nodes 1,2,3,4 form the clockwise corners of a large square.
     24     # Nodes 5,6,7,8 form the clockwise corners of a small square 
     25     g2edges = [[1,2], [2,3], [3,4], [4,1], 
     26                [5,6], [6,7], [7,8], [8,5], 
     27                [1,5], [2,6], [3,7], [4,8]]
     28 
     29     def test_graph(self):
     30         g1 = nx.Graph()
     31         g2 = nx.Graph()
     32         g1.add_edges_from(self.g1edges)
     33         g2.add_edges_from(self.g2edges)
     34         gm = iso.GraphMatcher(g1,g2)
     35         assert_true(gm.is_isomorphic())
     36 
     37         mapping = sorted(gm.mapping.items())
     38 # this mapping is only one of the possibilies 
     39 # so this test needs to be reconsidered 
     40 #        isomap = [('a', 1), ('b', 6), ('c', 3), ('d', 8), 
     41 #                  ('g', 2), ('h', 5), ('i', 4), ('j', 7)]
     42 #        assert_equal(mapping, isomap)
     43         
     44     def test_subgraph(self):
     45         g1 = nx.Graph()
     46         g2 = nx.Graph()
     47         g1.add_edges_from(self.g1edges)
     48         g2.add_edges_from(self.g2edges)
     49         g3 = g2.subgraph([1,2,3,4])
     50         gm = iso.GraphMatcher(g1,g3)
     51         assert_true(gm.subgraph_is_isomorphic())
     52 
     53 class TestVF2GraphDB(object):
     54     # http://amalfi.dis.unina.it/graph/db/
     55 
     56     @staticmethod
     57     def create_graph(filename):
     58         """Creates a Graph instance from the filename."""
     59 
     60         # The file is assumed to be in the format from the VF2 graph database.
     61         # Each file is composed of 16-bit numbers (unsigned short int).
     62         # So we will want to read 2 bytes at a time.
     63 
     64         # We can read the number as follows:
     65         #   number = struct.unpack('<H', file.read(2))
     66         # This says, expect the data in little-endian encoding
     67         # as an unsigned short int and unpack 2 bytes from the file.
     68 
     69         fh = open(filename, mode='rb')
     70 
     71         # Grab the number of nodes.
     72         # Node numeration is 0-based, so the first node has index 0.
     73         nodes = struct.unpack('<H', fh.read(2))[0]
     74 
     75         graph = nx.Graph()
     76         for from_node in range(nodes):
     77             # Get the number of edges.
     78             edges = struct.unpack('<H', fh.read(2))[0]
     79             for edge in range(edges):
     80                 # Get the terminal node.
     81                 to_node = struct.unpack('<H', fh.read(2))[0]
     82                 graph.add_edge(from_node, to_node)
     83 
     84         fh.close()
     85         return graph
     86 
     87     def test_graph(self):
     88         head,tail = os.path.split(__file__)
     89         g1 = self.create_graph(os.path.join(head,'iso_r01_s80.A99'))
     90         g2 = self.create_graph(os.path.join(head,'iso_r01_s80.B99'))
     91         gm = iso.GraphMatcher(g1,g2)
     92         assert_true(gm.is_isomorphic())
     93 
     94     def test_subgraph(self):
     95         # A is the subgraph
     96         # B is the full graph
     97         head,tail = os.path.split(__file__)
     98         subgraph = self.create_graph(os.path.join(head,'si2_b06_m200.A99'))
     99         graph = self.create_graph(os.path.join(head,'si2_b06_m200.B99'))
    100         gm = iso.GraphMatcher(graph, subgraph)
    101         assert_true(gm.subgraph_is_isomorphic())
    102 
    103 def test_graph_atlas():
    104     #Atlas = nx.graph_atlas_g()[0:208] # 208, 6 nodes or less
    105     Atlas = nx.graph_atlas_g()[0:100]
    106     alphabet = list(range(26))
    107     for graph in Atlas:
    108         nlist = graph.nodes()
    109         labels = alphabet[:len(nlist)]
    110         for s in range(10):
    111             random.shuffle(labels)
    112             d = dict(zip(nlist,labels))
    113             relabel = nx.relabel_nodes(graph, d)
    114             gm = iso.GraphMatcher(graph, relabel)
    115             assert_true(gm.is_isomorphic())
    116 
    117 def test_multiedge():
    118     # Simple test for multigraphs
    119     # Need something much more rigorous
    120     edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), 
    121              (5, 6), (6, 7), (7, 8), (8, 9), (9, 10), 
    122              (10, 11), (10, 11), (11, 12), (11, 12), 
    123              (12, 13), (12, 13), (13, 14), (13, 14), 
    124              (14, 15), (14, 15), (15, 16), (15, 16), 
    125              (16, 17), (16, 17), (17, 18), (17, 18), 
    126              (18, 19), (18, 19), (19, 0), (19, 0)]
    127     nodes = list(range(20))
    128 
    129     for g1 in [nx.MultiGraph(), nx.MultiDiGraph()]:
    130         g1.add_edges_from(edges)
    131         for _ in range(10):
    132             new_nodes = list(nodes)
    133             random.shuffle(new_nodes)
    134             d = dict(zip(nodes, new_nodes))
    135             g2 = nx.relabel_nodes(g1, d)
    136             if not g1.is_directed():
    137                 gm = iso.GraphMatcher(g1,g2)
    138             else:
    139                 gm = iso.DiGraphMatcher(g1,g2)
    140             assert_true(gm.is_isomorphic())
    141 
    142 def test_selfloop():
    143     # Simple test for graphs with selfloops
    144     edges = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 2), 
    145              (2, 4), (3, 1), (3, 2), (4, 2), (4, 5), (5, 4)]
    146     nodes = list(range(6))
    147 
    148     for g1 in [nx.Graph(), nx.DiGraph()]:
    149         g1.add_edges_from(edges)
    150         for _ in range(100):
    151             new_nodes = list(nodes)
    152             random.shuffle(new_nodes)
    153             d = dict(zip(nodes, new_nodes))
    154             g2 = nx.relabel_nodes(g1, d)
    155             if not g1.is_directed():
    156                 gm = iso.GraphMatcher(g1,g2)
    157             else:
    158                 gm = iso.DiGraphMatcher(g1,g2)
    159             assert_true(gm.is_isomorphic())
    160 
    161 def test_isomorphism_iter1():
    162     # As described in:
    163     # http://groups.google.com/group/networkx-discuss/browse_thread/thread/2ff65c67f5e3b99f/d674544ebea359bb?fwc=1
    164     g1 = nx.DiGraph()
    165     g2 = nx.DiGraph()
    166     g3 = nx.DiGraph()
    167     g1.add_edge('A','B')
    168     g1.add_edge('B','C')
    169     g2.add_edge('Y','Z')
    170     g3.add_edge('Z','Y')
    171     gm12 = iso.DiGraphMatcher(g1,g2)
    172     gm13 = iso.DiGraphMatcher(g1,g3)
    173     x = list(gm12.subgraph_isomorphisms_iter())
    174     y = list(gm13.subgraph_isomorphisms_iter())
    175     assert_true({'A':'Y','B':'Z'} in x)
    176     assert_true({'B':'Y','C':'Z'} in x)
    177     assert_true({'A':'Z','B':'Y'} in y)
    178     assert_true({'B':'Z','C':'Y'} in y)
    179     assert_equal(len(x),len(y))
    180     assert_equal(len(x),2)
    181 
    182 def test_isomorphism_iter2():
    183     # Path
    184     for L in range(2,10):
    185         g1 = nx.path_graph(L)
    186         gm = iso.GraphMatcher(g1,g1)
    187         s = len(list(gm.isomorphisms_iter()))
    188         assert_equal(s,2)
    189     # Cycle
    190     for L in range(3,10):
    191         g1 = nx.cycle_graph(L)
    192         gm = iso.GraphMatcher(g1,g1)
    193         s = len(list(gm.isomorphisms_iter()))
    194         assert_equal(s, 2*L)
    195 
    196 def test_multiple():
    197     # Verify that we can use the graph matcher multiple times
    198     edges = [('A','B'),('B','A'),('B','C')]
    199     for g1,g2 in [(nx.Graph(),nx.Graph()), (nx.DiGraph(),nx.DiGraph())]:
    200         g1.add_edges_from(edges)
    201         g2.add_edges_from(edges)
    202         g3 = nx.subgraph(g2, ['A','B'])
    203         if not g1.is_directed():
    204             gmA = iso.GraphMatcher(g1,g2)
    205             gmB = iso.GraphMatcher(g1,g3)
    206         else:
    207             gmA = iso.DiGraphMatcher(g1,g2)
    208             gmB = iso.DiGraphMatcher(g1,g3)
    209         assert_true(gmA.is_isomorphic())
    210         g2.remove_node('C')
    211         assert_true(gmA.subgraph_is_isomorphic())
    212         assert_true(gmB.subgraph_is_isomorphic())
    213 #        for m in [gmB.mapping, gmB.mapping]:
    214 #            assert_true(m['A'] == 'A')
    215 #            assert_true(m['B'] == 'B')
    216 #            assert_true('C' not in m)
    217 
    218