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
|