← Back to branch summary

~ubuntu-branches/ubuntu/saucy/python-igraph/saucy

« back to all changes in this revision

Viewing changes to igraph/test/isomorphism.py

  • Committer: Package Import Robot
  • Author(s): TANIGUCHI Takaki, Jakub Wilk, TANIGUCHI Takaki
  • Date: 2013-06-06 10:57:53 UTC
  • mfrom: (1.1.1)
  • Revision ID: package-import@ubuntu.com-20130606105753-0j44jjvqd3z9tirw
Tags: 0.6.5-1
[ Jakub Wilk ]
* Use canonical URIs for Vcs-* fields.

[ TANIGUCHI Takaki ]
* New upstream release
* Bump Standards-Version to 3.9.4. 

Show diffs side-by-side

added added

removed removed

Lines of Context:
igraph/test/isomorphism.py
1
1
import unittest
2
2
from igraph import *
3
3
 
 
4
def node_compat(g1, g2, v1, v2):
 
5
    """Node compatibility function for isomorphism tests"""
 
6
    return g1.vs[v1]["color"] == g2.vs[v2]["color"]
 
7
 
 
8
def edge_compat(g1, g2, e1, e2):
 
9
    """Edge compatibility function for isomorphism tests"""
 
10
    return g1.es[e1]["color"] == g2.es[e2]["color"]
 
11
 
4
12
class IsomorphismTests(unittest.TestCase):
5
13
    def testIsomorphic(self):
6
14
        g1 = Graph(8, [(0, 4), (0, 5), (0, 6), \
11
19
                       (2, 3), (2, 1), (2, 6), \
12
20
                       (5, 1), (5, 4), (5, 6), \
13
21
                       (7, 3), (7, 6), (7, 4)])
 
22
 
 
23
        # Test the isomorphy of g1 and g2
14
24
        self.failUnless(g1.isomorphic(g2))
15
25
        self.failUnless(g2.isomorphic_vf2(g1, return_mapping_21=True) \
16
26
          == (True, None, [0, 2, 5, 7, 1, 3, 4, 6]))
18
28
          == (True, None, [0, 2, 5, 7, 1, 3, 4, 6]))
19
29
        self.assertRaises(ValueError, g2.isomorphic_bliss, g1, sh2="nonexistent")
20
30
 
 
31
        # Test the automorphy of g1
 
32
        self.failUnless(g1.isomorphic())
 
33
        self.failUnless(g1.isomorphic_vf2(return_mapping_21=True) \
 
34
          == (True, None, [0, 1, 2, 3, 4, 5, 6, 7]))
 
35
 
 
36
        # Test VF2 with colors
 
37
        self.failUnless(g1.isomorphic_vf2(g2,
 
38
            color1=[0,1,0,1,0,1,0,1],
 
39
            color2=[0,0,1,1,0,0,1,1]))
 
40
        g1.vs["color"] = [0,1,0,1,0,1,0,1]
 
41
        g2.vs["color"] = [0,0,1,1,0,1,1,0]
 
42
        self.failUnless(not g1.isomorphic_vf2(g2, "color", "color"))
 
43
 
 
44
        # Test VF2 with vertex and edge colors
 
45
        self.failUnless(g1.isomorphic_vf2(g2,
 
46
            color1=[0,1,0,1,0,1,0,1],
 
47
            color2=[0,0,1,1,0,0,1,1]))
 
48
        g1.es["color"] = range(12)
 
49
        g2.es["color"] = [0]*6 + [1]*6
 
50
        self.failUnless(not g1.isomorphic_vf2(g2, "color", "color", "color", "color"))
 
51
 
 
52
        # Test VF2 with node compatibility function
 
53
        g2.vs["color"] = [0,0,1,1,0,0,1,1]
 
54
        self.failUnless(g1.isomorphic_vf2(g2, node_compat_fn=node_compat))
 
55
        g2.vs["color"] = [0,0,1,1,0,1,1,0]
 
56
        self.failUnless(not g1.isomorphic_vf2(g2, node_compat_fn=node_compat))
 
57
 
 
58
        # Test VF2 with node edge compatibility function
 
59
        g2.vs["color"] = [0,0,1,1,0,0,1,1]
 
60
        g1.es["color"] = range(12)
 
61
        g2.es["color"] = [0]*6 + [1]*6
 
62
        self.failUnless(not g1.isomorphic_vf2(g2, node_compat_fn=node_compat,
 
63
            edge_compat_fn=edge_compat))
 
64
 
 
65
    def testIsomorphicCallback(self):
 
66
        maps = []
 
67
        def callback(g1, g2, map1, map2):
 
68
            maps.append(map1)
 
69
            return True
 
70
 
 
71
        # Test VF2 callback
 
72
        g = Graph(6, [(0,1), (2,3), (4,5), (0,2), (2,4), (1,3), (3,5)])
 
73
        g.isomorphic_vf2(g, callback=callback)
 
74
        expected_maps = [[0,1,2,3,4,5], [1,0,3,2,5,4], [4,5,2,3,0,1], [5,4,3,2,1,0]]
 
75
        self.failUnless(sorted(maps) == expected_maps)
 
76
 
 
77
        maps[:] = []
 
78
        g3 = Graph.Full(4)
 
79
        g3.vs["color"] = [0,1,1,0]
 
80
        g3.isomorphic_vf2(callback=callback, color1="color", color2="color")
 
81
        expected_maps = [[0,1,2,3], [0,2,1,3], [3,1,2,0], [3,2,1,0]]
 
82
        self.failUnless(sorted(maps) == expected_maps)
 
83
 
21
84
    def testCountIsomorphisms(self):
22
85
        g = Graph.Full(4)
23
86
        self.failUnless(g.count_automorphisms_vf2() == 24)
24
87
        g = Graph(6, [(0,1), (2,3), (4,5), (0,2), (2,4), (1,3), (3,5)])
25
88
        self.failUnless(g.count_automorphisms_vf2() == 4)
26
89
 
 
90
        # Some more tests with colors
 
91
        g3 = Graph.Full(4)
 
92
        g3.vs["color"] = [0,1,1,0]
 
93
        self.failUnless(g3.count_isomorphisms_vf2() == 24)
 
94
        self.failUnless(g3.count_isomorphisms_vf2(color1="color", color2="color") == 4)
 
95
        self.failUnless(g3.count_isomorphisms_vf2(color1=[0,1,2,0], color2=(0,1,2,0)) == 2)
 
96
        self.failUnless(g3.count_isomorphisms_vf2(edge_color1=[0,1,0,0,0,1],
 
97
            edge_color2=[0,1,0,0,0,1]) == 2)
 
98
 
 
99
        # Test VF2 with node/edge compatibility function
 
100
        g3.vs["color"] = [0,1,1,0]
 
101
        self.failUnless(g3.count_isomorphisms_vf2(node_compat_fn=node_compat) == 4)
 
102
        g3.vs["color"] = [0,1,2,0]
 
103
        self.failUnless(g3.count_isomorphisms_vf2(node_compat_fn=node_compat) == 2)
 
104
        g3.es["color"] = [0,1,0,0,0,1]
 
105
        self.failUnless(g3.count_isomorphisms_vf2(edge_compat_fn=edge_compat) == 2)
 
106
 
27
107
    def testGetIsomorphisms(self):
28
108
        g = Graph(6, [(0,1), (2,3), (4,5), (0,2), (2,4), (1,3), (3,5)])
29
109
        maps = g.get_automorphisms_vf2()
30
110
        expected_maps = [[0,1,2,3,4,5], [1,0,3,2,5,4], [4,5,2,3,0,1], [5,4,3,2,1,0]]
31
111
        self.failUnless(maps == expected_maps)
32
112
 
 
113
        g3 = Graph.Full(4)
 
114
        g3.vs["color"] = [0,1,1,0]
 
115
        expected_maps = [[0,1,2,3], [0,2,1,3], [3,1,2,0], [3,2,1,0]]
 
116
        self.failUnless(sorted(g3.get_automorphisms_vf2(color="color")) == expected_maps)
 
117
 
33
118
    def testSubisomorphic(self):
34
119
        g = Graph.Lattice([3,3], circular=False)
35
120
        g2 = Graph([(0,1), (1,2), (1,3)])
36
121
        self.failUnless(g.subisomorphic_vf2(g2))
37
122
        self.failUnless(not g2.subisomorphic_vf2(g))
38
123
 
 
124
        # Test with vertex colors
 
125
        g.vs["color"] = [0,0,0,0,1,0,0,0,0]
 
126
        g2.vs["color"] = [1,0,0,0]
 
127
        self.failUnless(g.subisomorphic_vf2(g2, node_compat_fn=node_compat))
 
128
        g2.vs["color"] = [2,0,0,0]
 
129
        self.failUnless(not g.subisomorphic_vf2(g2, node_compat_fn=node_compat))
 
130
 
 
131
        # Test with edge colors
 
132
        g.es["color"] = [1] + [0]*(g.ecount()-1)
 
133
        g2.es["color"] = [1] + [0]*(g2.ecount()-1)
 
134
        self.failUnless(g.subisomorphic_vf2(g2, edge_compat_fn=edge_compat))
 
135
        g2.es[0]["color"] = [2]
 
136
        self.failUnless(not g.subisomorphic_vf2(g2, node_compat_fn=node_compat))
 
137
 
39
138
    def testCountSubisomorphisms(self):
40
139
        g = Graph.Lattice([3,3], circular=False)
41
140
        g2 = Graph.Lattice([2,2], circular=False)
42
141
        self.failUnless(g.count_subisomorphisms_vf2(g2) == 4*4*2)
43
142
        self.failUnless(g2.count_subisomorphisms_vf2(g) == 0)
44
143
 
 
144
        # Test with vertex colors
 
145
        g.vs["color"] = [0,0,0,0,1,0,0,0,0]
 
146
        g2.vs["color"] = [1,0,0,0]
 
147
        self.failUnless(g.count_subisomorphisms_vf2(g2, "color", "color") == 4*2)
 
148
        self.failUnless(g.count_subisomorphisms_vf2(g2, node_compat_fn=node_compat) == 4*2)
 
149
 
 
150
        # Test with edge colors
 
151
        g.es["color"] = [1] + [0]*(g.ecount()-1)
 
152
        g2.es["color"] = [1] + [0]*(g2.ecount()-1)
 
153
        self.failUnless(g.count_subisomorphisms_vf2(g2, edge_color1="color", edge_color2="color") == 2)
 
154
        self.failUnless(g.count_subisomorphisms_vf2(g2, edge_compat_fn=edge_compat) == 2)
 
155
 
45
156
    def testPermuteVertices(self):
46
157
        g1 = Graph(8, [(0, 4), (0, 5), (0, 6), \
47
158
                       (1, 4), (1, 5), (1, 7), \