## Maptrackers

### 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: 7, 4: 3, 5: 4, 6: 5, 7: 6}

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!