[docs]def isomorph(G, H, Ga, Ha, f):
'''f is a list, which is a mapping of a subset of G that is isomorphic to a subset of H.
This function will try to expand f. If successful, it will call isomorph recursively
with this expanded f. If not successful, it will return False, which
signals to the caller that its proposed f is no good, and it should propose another.
If isomorph matches the entire graph, then it returns True. This signals to the
caller that it should also return True.
In the function, the vertices of G will be traversed in order.
The potential vertices to expand f are chosen from H which are not already in f.
Caller should guarantee number of vertices are the same. (Caller should also check
that number of bonds are the same.) Any application should call isomorph with
f = []. f should be ignored if isomorph returns False.
Input graphs are lists of lists with 0-based indexing, without self-edges and
with both forward and backward edges (for undirected graphs). Ga and Ha are
additional lists that contain vertex attributes to be matched.
Possible optimizations: order of traversing G; candidates chosen as neighbors of
existing vertex in f
'''
k = len(f) # we are considering vertex k in G
neigh = G[k] # neighbors of k in G
deg = len(neigh)
# candidates are unselected vertices with same degree as k
# this is the only place that Ha and Ga are used
candidates = [
j for j in range(len(H))
if (j not in f) and (len(H[j]) == deg) and (Ha[j] == Ga[k])
]
for j in candidates:
# loop over i, neighbors of k in G and check that they are neighbors of j in H
match = True
for i in neigh:
if i >= k:
continue
if f[i] not in H[j]: # f[i] must be connected to candidate j in H
match = False
break
# loop over neighbors of j in H and check they are neighbors of k in G
if match:
for h in H[j]:
if h not in f:
continue
i = f.index(h) # could be optimized with inverse array
if i not in neigh:
match = False
break
if match:
f.append(j)
if len(f) == len(G):
return True # isomorphism found
ret = isomorph(G, H, Ga, Ha, f)
if ret:
return ret # we are rewinding
# else try next candidate; pop off bad entry
j = f.pop()
return False # no candidates could expand f
if __name__ == '__main__':
G = [[]]
H = [[]]
G = [[1], [0, 2], [1]] # not isomorphic
H = [[2], [0, 1], [2]]
G = [[1], [0]]
H = [[1], [0]]
G = [[1], [0, 2], [1]] # isomorphic
H = [[2], [2], [0, 1]]
G = [[1, 4, 5], [0, 2], [1, 3], [2, 5], [0, 5], [0, 3, 4]]
H = [[1, 4, 5], [0, 2], [1, 3], [2, 5], [0, 5], [0, 3, 4]]
G = [[1], [0, 2], [1, 3], [2]]
H = [[1], [0, 2], [1, 3], [2]]
Ga = ['a', 'a', 'a', 'b']
Ha = ['a', 'a', 'a', 'a']
f = []
ret = isomorph(G, H, Ga, Ha, f)
if ret:
print('Isomorphic', f)
else:
print('Not isomorphic')