Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / isomorphism / tests / test_vf2userfunc.py @ 5cef0f13

History | View | Annotate | Download (6.62 KB)

1
"""
2
    Tests for VF2 isomorphism algorithm for weighted graphs.
3
"""
4

    
5
from nose.tools import assert_true, assert_false
6
from operator import eq
7

    
8
import networkx as nx
9
import networkx.algorithms.isomorphism as iso
10

    
11

    
12
def test_simple():
13
    # 16 simple tests
14
    w = 'weight'
15
    edges = [(0, 0, 1), (0, 0, 1.5), (0, 1, 2), (1, 0, 3)]
16
    for g1 in [nx.Graph(),
17
               nx.DiGraph(),
18
               nx.MultiGraph(),
19
               nx.MultiDiGraph(),
20
               ]:
21

    
22
        g1.add_weighted_edges_from(edges)
23
        g2 = g1.subgraph(g1.nodes())
24
        if g1.is_multigraph():
25
            em = iso.numerical_multiedge_match('weight', 1)
26
        else:
27
            em = iso.numerical_edge_match('weight', 1)
28
        assert_true(nx.is_isomorphic(g1, g2, edge_match=em))
29

    
30
        for mod1, mod2 in [(False, True), (True, False), (True, True)]:
31
            # mod1 tests a regular edge
32
            # mod2 tests a selfloop
33
            if g2.is_multigraph():
34
                if mod1:
35
                    data1 = {0: {'weight': 10}}
36
                if mod2:
37
                    data2 = {0: {'weight': 1}, 1: {'weight': 2.5}}
38
            else:
39
                if mod1:
40
                    data1 = {'weight': 10}
41
                if mod2:
42
                    data2 = {'weight': 2.5}
43

    
44
            g2 = g1.subgraph(g1.nodes()).copy()
45
            if mod1:
46
                if not g1.is_directed():
47
                    g2._adj[1][0] = data1
48
                    g2._adj[0][1] = data1
49
                else:
50
                    g2._succ[1][0] = data1
51
                    g2._pred[0][1] = data1
52
            if mod2:
53
                if not g1.is_directed():
54
                    g2._adj[0][0] = data2
55
                else:
56
                    g2._succ[0][0] = data2
57
                    g2._pred[0][0] = data2
58

    
59
            assert_false(nx.is_isomorphic(g1, g2, edge_match=em))
60

    
61

    
62
def test_weightkey():
63
    g1 = nx.DiGraph()
64
    g2 = nx.DiGraph()
65

    
66
    g1.add_edge('A', 'B', weight=1)
67
    g2.add_edge('C', 'D', weight=0)
68

    
69
    assert_true(nx.is_isomorphic(g1, g2))
70
    em = iso.numerical_edge_match('nonexistent attribute', 1)
71
    assert_true(nx.is_isomorphic(g1, g2, edge_match=em))
72
    em = iso.numerical_edge_match('weight', 1)
73
    assert_false(nx.is_isomorphic(g1, g2, edge_match=em))
74

    
75
    g2 = nx.DiGraph()
76
    g2.add_edge('C', 'D')
77
    assert_true(nx.is_isomorphic(g1, g2, edge_match=em))
78

    
79

    
80
class TestNodeMatch_Graph(object):
81
    def setUp(self):
82
        self.g1 = nx.Graph()
83
        self.g2 = nx.Graph()
84
        self.build()
85

    
86
    def build(self):
87

    
88
        self.nm = iso.categorical_node_match('color', '')
89
        self.em = iso.numerical_edge_match('weight', 1)
90

    
91
        self.g1.add_node('A', color='red')
92
        self.g2.add_node('C', color='blue')
93

    
94
        self.g1.add_edge('A', 'B', weight=1)
95
        self.g2.add_edge('C', 'D', weight=1)
96

    
97
    def test_noweight_nocolor(self):
98
        assert_true(nx.is_isomorphic(self.g1, self.g2))
99

    
100
    def test_color1(self):
101
        assert_false(nx.is_isomorphic(self.g1, self.g2, node_match=self.nm))
102

    
103
    def test_color2(self):
104
        self.g1.nodes['A']['color'] = 'blue'
105
        assert_true(nx.is_isomorphic(self.g1, self.g2, node_match=self.nm))
106

    
107
    def test_weight1(self):
108
        assert_true(nx.is_isomorphic(self.g1, self.g2, edge_match=self.em))
109

    
110
    def test_weight2(self):
111
        self.g1.add_edge('A', 'B', weight=2)
112
        assert_false(nx.is_isomorphic(self.g1, self.g2, edge_match=self.em))
113

    
114
    def test_colorsandweights1(self):
115
        iso = nx.is_isomorphic(self.g1, self.g2,
116
                               node_match=self.nm, edge_match=self.em)
117
        assert_false(iso)
118

    
119
    def test_colorsandweights2(self):
120
        self.g1.nodes['A']['color'] = 'blue'
121
        iso = nx.is_isomorphic(self.g1, self.g2,
122
                               node_match=self.nm, edge_match=self.em)
123
        assert_true(iso)
124

    
125
    def test_colorsandweights3(self):
126
        # make the weights disagree
127
        self.g1.add_edge('A', 'B', weight=2)
128
        assert_false(nx.is_isomorphic(self.g1, self.g2,
129
                                      node_match=self.nm, edge_match=self.em))
130

    
131

    
132
class TestEdgeMatch_MultiGraph(object):
133
    def setUp(self):
134
        self.g1 = nx.MultiGraph()
135
        self.g2 = nx.MultiGraph()
136
        self.GM = iso.MultiGraphMatcher
137
        self.build()
138

    
139
    def build(self):
140
        g1 = self.g1
141
        g2 = self.g2
142

    
143
        # We will assume integer weights only.
144
        g1.add_edge('A', 'B', color='green', weight=0, size=.5)
145
        g1.add_edge('A', 'B', color='red', weight=1, size=.35)
146
        g1.add_edge('A', 'B', color='red', weight=2, size=.65)
147

    
148
        g2.add_edge('C', 'D', color='green', weight=1, size=.5)
149
        g2.add_edge('C', 'D', color='red', weight=0, size=.45)
150
        g2.add_edge('C', 'D', color='red', weight=2, size=.65)
151

    
152
        if g1.is_multigraph():
153
            self.em = iso.numerical_multiedge_match('weight', 1)
154
            self.emc = iso.categorical_multiedge_match('color', '')
155
            self.emcm = iso.categorical_multiedge_match(['color', 'weight'], ['', 1])
156
            self.emg1 = iso.generic_multiedge_match('color', 'red', eq)
157
            self.emg2 = iso.generic_multiedge_match(['color', 'weight', 'size'], ['red', 1, .5], [
158
                                                    eq, eq, iso.matchhelpers.close])
159
        else:
160
            self.em = iso.numerical_edge_match('weight', 1)
161
            self.emc = iso.categorical_edge_match('color', '')
162
            self.emcm = iso.categorical_edge_match(['color', 'weight'], ['', 1])
163
            self.emg1 = iso.generic_multiedge_match('color', 'red', eq)
164
            self.emg2 = iso.generic_edge_match(['color', 'weight', 'size'], ['red', 1, .5], [
165
                                               eq, eq, iso.matchhelpers.close])
166

    
167
    def test_weights_only(self):
168
        assert_true(nx.is_isomorphic(self.g1, self.g2, edge_match=self.em))
169

    
170
    def test_colors_only(self):
171
        gm = self.GM(self.g1, self.g2, edge_match=self.emc)
172
        assert_true(gm.is_isomorphic())
173

    
174
    def test_colorsandweights(self):
175
        gm = self.GM(self.g1, self.g2, edge_match=self.emcm)
176
        assert_false(gm.is_isomorphic())
177

    
178
    def test_generic1(self):
179
        gm = self.GM(self.g1, self.g2, edge_match=self.emg1)
180
        assert_true(gm.is_isomorphic())
181

    
182
    def test_generic2(self):
183
        gm = self.GM(self.g1, self.g2, edge_match=self.emg2)
184
        assert_false(gm.is_isomorphic())
185

    
186

    
187
class TestEdgeMatch_DiGraph(TestNodeMatch_Graph):
188
    def setUp(self):
189
        self.g1 = nx.DiGraph()
190
        self.g2 = nx.DiGraph()
191
        self.build()
192

    
193

    
194
class TestEdgeMatch_MultiDiGraph(TestEdgeMatch_MultiGraph):
195
    def setUp(self):
196
        self.g1 = nx.MultiDiGraph()
197
        self.g2 = nx.MultiDiGraph()
198
        self.GM = iso.MultiDiGraphMatcher
199
        self.build()