![\"\"](\"http:\/\/www.fiber-space.de\/misc\/MaptrackGraphs.PNG\" "\\"MaptrackGraphs\\"")
<\/p>\nA *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.<\/p>\n
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?<\/p>\n
<\/p>\n
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:<\/p>\n
GR1 = {0: set([1, 3, 4, -1, 7]),\r\n 1: set([2]),\r\n 2: set([1, 3, 4, -1, 7]),\r\n 3: set([-1]),\r\n 4: set([6, 4, 5, -1, 7]),\r\n 5: set([5, 6]),\r\n 6: set([4, -1, 7]),\r\n 7: set([-1])}<\/pre>\nGR2 = {0: set([1, 3, 6, -1, 7]),\r\n 1: set([2]),\r\n 2: set([1, 3, 6, -1, 7]),\r\n 3: set([6, 3, 4, 5, -1]),\r\n 4: set([4, 5]),\r\n 5: set([3, 6, -1]),\r\n 6: set([-1]),\r\n 7: set([-1])}<\/pre>\nA pair `i: [j1, j2, … jn]` describes the set of edges i -> j1,\u00a0 i -> j2, …, i -> jn.<\/p>\n
Checking for equivalence<\/h3>\n
We say that GR1 and GR2 are *equivalent* if there is a permutation `P` of\u00a0 `{-1, 0, 1, …, 7}` and<\/p>\n
GR2 == dict( (P(key), set(map(P, value))) for (key, value) in GR1.items() )<\/pre>\n`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:<\/p>\n
class Maptracker(object):\r\n def __init__(self, gr1, gr2):\r\n self.gr1 = gr1\r\n self.gr2 = gr2\r\n\r\n def accept(self, value, stack):\r\n e1, e2 = value # e1 -> e2\r\n V1 = self.gr1[e1]\r\n V2 = self.gr2[e2]\r\n #\r\n # e1 -> e2 => v1 -> v2\r\n #\r\n # check consistency of the choice of the mapping\r\n if len(V1)!=len(V2):\r\n return False\r\n m = dict(p for (p,q) in stack)\r\n if e2 in m.values():\r\n return False\r\n for v1 in V1:\r\n if v1 == e1:\r\n if e2 not in V2:\r\n return False\r\n if v1 in m:\r\n if m[v1] not in V2:\r\n return False\r\n for s in m:\r\n if e1 in self.gr1[s]:\r\n if e2 not in self.gr2[m[s]]:\r\n return False\r\n return True\r\n\r\n def run(self):\r\n stack = []\r\n if len(self.gr1) != len(self.gr2):\r\n return {}\r\n sig1 = sorted(len(v) for v in self.gr1.values())\r\n sig2 = sorted(len(v) for v in self.gr2.values())\r\n if sig1!=sig2:\r\n return {}\r\n\r\n L1 = self.gr1.keys()\r\n L2 = self.gr2.keys()\r\n i = j = 0\r\n while i\nIf no permutation could be constructed an empty dictionary `{}` is returned.<\/p>\n
Let's watch the dict which is computed by the Maptracker for `GR1` and `GR2`:<\/p>\n
>>> M = Maptracker(GR1, GR2).run()\r\n>>> M\r\n{0: 0, 1: 1, 2: 2, 3: 4, 4: 5, 5: 6, 6: 7, 7: 3}<\/pre>\nWe can check the correctness of `M` manually or by setting<\/p>\n
P = lambda k: (-1 if k == -1 else M[k] )<\/pre>\nand check the equality we have defined above.<\/p>\n","protected":false},"excerpt":{"rendered":"
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 … Continue reading