From graphs to maps
A *Maptracker* is a special backtracking algorithm used to check the equivalence of certain maps which can be represented as connected, directed graphs or finite state machines. It shall be described in this article.
The original motivation was to find an algorithm for reconstruction of grammars from finite state-machines with the following property: suppose you have a state-machine `M0` and a function P which turns `M0` into a grammar rule: `G = P(M0)`. When we translate G back again into a state-machine we get `M1 = T(P(M0))`. Generally `T o P != Id` and `M0 != M1`. But how different are `M0` and `M1` actually?
Watch the two graphs GR1 and GR2 above. When we abstract from their particular drawings and focus on the nodes and edges only we can describe them using the following dictionaries:
GR1 = {0: set([1, 3, 4, -1, 7]), 1: set([2]), 2: set([1, 3, 4, -1, 7]), 3: set([-1]), 4: set([6, 4, 5, -1, 7]), 5: set([5, 6]), 6: set([4, -1, 7]), 7: set([-1])} |
GR2 = {0: set([1, 3, 6, -1, 7]), 1: set([2]), 2: set([1, 3, 6, -1, 7]), 3: set([6, 3, 4, 5, -1]), 4: set([4, 5]), 5: set([3, 6, -1]), 6: set([-1]), 7: set([-1])} |
A pair `i: [j1, j2, … jn]` describes the set of edges i -> j1, i -> j2, …, i -> jn.
Checking for equivalence
We say that GR1 and GR2 are *equivalent* if there is a permutation `P` of `{-1, 0, 1, …, 7}` and
GR2 == dict( (P(key), set(map(P, value))) for (key, value) in GR1.items() ) |
`Maptracker` is merely a cute name for an algorithm which constructs the permutation `P` from map representations of the kind `GR1` and `GR2`. `P` itself will be described as a dictionary. Since the value `-1` is a fixed point it will be omitted:
class Maptracker(object): def __init__(self, gr1, gr2): self.gr1 = gr1 self.gr2 = gr2 def accept(self, value, stack): e1, e2 = value # e1 -> e2 V1 = self.gr1[e1] V2 = self.gr2[e2] # # e1 -> e2 => v1 -> v2 # # check consistency of the choice of the mapping if len(V1)!=len(V2): return False m = dict(p for (p,q) in stack) if e2 in m.values(): return False for v1 in V1: if v1 == e1: if e2 not in V2: return False if v1 in m: if m[v1] not in V2: return False for s in m: if e1 in self.gr1[s]: if e2 not in self.gr2[m[s]]: return False return True def run(self): stack = [] if len(self.gr1) != len(self.gr2): return {} sig1 = sorted(len(v) for v in self.gr1.values()) sig2 = sorted(len(v) for v in self.gr2.values()) if sig1!=sig2: return {} L1 = self.gr1.keys() L2 = self.gr2.keys() i = j = 0 while i<len(L1): e1 = L1[i] while j<len(L2): e2 = L2[j] if self.accept((e1,e2),stack): stack.append(((e1,e2),(i,j))) j = 0 break j+=1 else: if stack: _, (i,j) = stack.pop() if j == -1: return {} j+=1 continue else: return {} i+=1 return dict(elem[0] for elem in stack) |
If no permutation could be constructed an empty dictionary `{}` is returned.
Let’s watch the dict which is computed by the Maptracker for `GR1` and `GR2`:
>>> M = Maptracker(GR1, GR2).run() >>> M {0: 0, 1: 1, 2: 2, 3: 4, 4: 5, 5: 6, 6: 7, 7: 3} |
We can check the correctness of `M` manually or by setting
P = lambda k: (-1 if k == -1 else M[k] ) |
and check the equality we have defined above.
I think the dictionary definitions GR1 and GR2 are interchanged. GR1 corresponds to the bottom diagram and GR2 corresponds to the top diagram, was that the intention ?
@sateesh, you are right. I’ve updated the article accordingly. Thanks!