/usr/lib/python2.7/dist-packages/networkx/algorithms/isomorphism/tests/test_vf2userfunc.py is in python-networkx 1.8.1-0ubuntu3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 | """
Tests for VF2 isomorphism algorithm for weighted graphs.
"""
from nose.tools import assert_true, assert_false
from operator import eq
import networkx as nx
import networkx.algorithms.isomorphism as iso
def test_simple():
# 16 simple tests
w = 'weight'
edges = [(0,0,1),(0,0,1.5),(0,1,2),(1,0,3)]
for g1 in [nx.Graph(),
nx.DiGraph(),
nx.MultiGraph(),
nx.MultiDiGraph(),
]:
g1.add_weighted_edges_from(edges)
g2 = g1.subgraph(g1.nodes())
if g1.is_multigraph():
em = iso.numerical_multiedge_match('weight', 1)
else:
em = iso.numerical_edge_match('weight', 1)
assert_true( nx.is_isomorphic(g1,g2,edge_match=em) )
for mod1, mod2 in [(False, True), (True, False), (True, True)]:
# mod1 tests a regular edge
# mod2 tests a selfloop
if g2.is_multigraph():
if mod1:
data1 = {0:{'weight':10}}
if mod2:
data2 = {0:{'weight':1},1:{'weight':2.5}}
else:
if mod1:
data1 = {'weight':10}
if mod2:
data2 = {'weight':2.5}
g2 = g1.subgraph(g1.nodes())
if mod1:
if not g1.is_directed():
g2.adj[1][0] = data1
g2.adj[0][1] = data1
else:
g2.succ[1][0] = data1
g2.pred[0][1] = data1
if mod2:
if not g1.is_directed():
g2.adj[0][0] = data2
else:
g2.succ[0][0] = data2
g2.pred[0][0] = data2
assert_false(nx.is_isomorphic(g1,g2,edge_match=em))
def test_weightkey():
g1 = nx.DiGraph()
g2 = nx.DiGraph()
g1.add_edge('A','B', weight=1)
g2.add_edge('C','D', weight=0)
assert_true( nx.is_isomorphic(g1, g2) )
em = iso.numerical_edge_match('nonexistent attribute', 1)
assert_true( nx.is_isomorphic(g1, g2, edge_match=em) )
em = iso.numerical_edge_match('weight', 1)
assert_false( nx.is_isomorphic(g1, g2, edge_match=em) )
g2 = nx.DiGraph()
g2.add_edge('C','D')
assert_true( nx.is_isomorphic(g1, g2, edge_match=em) )
class TestNodeMatch_Graph(object):
def setUp(self):
self.g1 = nx.Graph()
self.g2 = nx.Graph()
self.build()
def build(self):
self.nm = iso.categorical_node_match('color', '')
self.em = iso.numerical_edge_match('weight', 1)
self.g1.add_node('A', color='red')
self.g2.add_node('C', color='blue')
self.g1.add_edge('A','B', weight=1)
self.g2.add_edge('C','D', weight=1)
def test_noweight_nocolor(self):
assert_true( nx.is_isomorphic(self.g1, self.g2) )
def test_color1(self):
assert_false( nx.is_isomorphic(self.g1, self.g2, node_match=self.nm) )
def test_color2(self):
self.g1.node['A']['color'] = 'blue'
assert_true( nx.is_isomorphic(self.g1, self.g2, node_match=self.nm) )
def test_weight1(self):
assert_true( nx.is_isomorphic(self.g1, self.g2, edge_match=self.em) )
def test_weight2(self):
self.g1.add_edge('A', 'B', weight=2)
assert_false( nx.is_isomorphic(self.g1, self.g2, edge_match=self.em) )
def test_colorsandweights1(self):
iso = nx.is_isomorphic(self.g1, self.g2,
node_match=self.nm, edge_match=self.em)
assert_false(iso)
def test_colorsandweights2(self):
self.g1.node['A']['color'] = 'blue'
iso = nx.is_isomorphic(self.g1, self.g2,
node_match=self.nm, edge_match=self.em)
assert_true(iso)
def test_colorsandweights3(self):
# make the weights disagree
self.g1.add_edge('A', 'B', weight=2)
assert_false( nx.is_isomorphic(self.g1, self.g2,
node_match=self.nm, edge_match=self.em) )
class TestEdgeMatch_MultiGraph(object):
def setUp(self):
self.g1 = nx.MultiGraph()
self.g2 = nx.MultiGraph()
self.GM = iso.MultiGraphMatcher
self.build()
def build(self):
g1 = self.g1
g2 = self.g2
# We will assume integer weights only.
g1.add_edge('A', 'B', color='green', weight=0, size=.5)
g1.add_edge('A', 'B', color='red', weight=1, size=.35)
g1.add_edge('A', 'B', color='red', weight=2, size=.65)
g2.add_edge('C', 'D', color='green', weight=1, size=.5)
g2.add_edge('C', 'D', color='red', weight=0, size=.45)
g2.add_edge('C', 'D', color='red', weight=2, size=.65)
if g1.is_multigraph():
self.em = iso.numerical_multiedge_match('weight', 1)
self.emc = iso.categorical_multiedge_match('color', '')
self.emcm = iso.categorical_multiedge_match(['color', 'weight'], ['', 1])
self.emg1 = iso.generic_multiedge_match('color', 'red', eq)
self.emg2 = iso.generic_multiedge_match(['color', 'weight', 'size'], ['red', 1, .5], [eq, eq, iso.matchhelpers.close])
else:
self.em = iso.numerical_edge_match('weight', 1)
self.emc = iso.categorical_edge_match('color', '')
self.emcm = iso.categorical_edge_match(['color', 'weight'], ['', 1])
self.emg1 = iso.generic_multiedge_match('color', 'red', eq)
self.emg2 = iso.generic_edge_match(['color', 'weight', 'size'], ['red', 1, .5], [eq, eq, iso.matchhelpers.close])
def test_weights_only(self):
assert_true( nx.is_isomorphic(self.g1, self.g2, edge_match=self.em) )
def test_colors_only(self):
gm = self.GM(self.g1, self.g2, edge_match=self.emc)
assert_true( gm.is_isomorphic() )
def test_colorsandweights(self):
gm = self.GM(self.g1, self.g2, edge_match=self.emcm)
assert_false( gm.is_isomorphic() )
def test_generic1(self):
gm = self.GM(self.g1, self.g2, edge_match=self.emg1)
assert_true( gm.is_isomorphic() )
def test_generic2(self):
gm = self.GM(self.g1, self.g2, edge_match=self.emg2)
assert_false( gm.is_isomorphic() )
class TestEdgeMatch_DiGraph(TestNodeMatch_Graph):
def setUp(self):
self.g1 = nx.DiGraph()
self.g2 = nx.DiGraph()
self.build()
class TestEdgeMatch_MultiDiGraph(TestEdgeMatch_MultiGraph):
def setUp(self):
self.g1 = nx.MultiDiGraph()
self.g2 = nx.MultiDiGraph()
self.GM = iso.MultiDiGraphMatcher
self.build()
|