Vogel implementation along with PD Code

vogel

#whatever is the crossing one should give the sign for that first
    #the order of the sign is as per the ordering of the crossings as in the gauss code
    #so for example if the gauss code is 1 -3 2 -1 3 -2 then the order of the sign of the crossings is
    #sign of crossing 1 then 3 then at 2 and so on and so forth.
    def PD_code_ogc(self, oriented_gauss_code):
        self.oriented_gauss_code = oriented_gauss_code
        gc = self.oriented_gauss_code[0]
        gc_sign = self.oriented_gauss_code[1]
        l = [0 for i in range(len(gc))]
        for i in range(len(gc)):
            k = abs(gc[i])
            if l[2*(k-1)] == 0:
                l[2*(k-1)] = (i + 1)*(cmp(gc[i],0))
            else:
                l[2*k-1] = (i + 1)*(cmp(gc[i],0))
        y = [None for i in range(2*len(gc_sign))]
        for i in range(0,2*len(gc_sign),2):
            if l[i] < 0:
                y[i] = 'under'
                y[i+1] = 'over'
            elif l[i] > 0:
                y[i] = 'over'
                y[i+1] = 'under'
        l1 = [abs(x) for x in l]
        r = []
        p = [[None for i in range(4)] for i in range(len(gc_sign))]
        for i in range(len(gc_sign)):
            if gc_sign[i] == '-':
                if y[2*i] == 'under':
                    p[i][0] = l1[2*i]
                    p[i][2] = p[i][0] + 1
                    p[i][3] = l1[2*i+1]
                    p[i][1] = p[i][3] + 1
                elif y[2*i+1] == 'under':
                    p[i][0] = l1[2*i+1]
                    p[i][3] = l1[2*i]
                    p[i][2] = p[i][0] + 1
                    p[i][1] = p[i][3] + 1
            elif gc_sign[i] == '+':
                if y[2*i] == 'under':
                    p[i][0] = l1[2*i]
                    p[i][2] = p[i][0] + 1
                    p[i][1] = l1[2*i+1]
                    p[i][3] = p[i][1] + 1
                elif y[2*i+1] == 'under':
                    p[i][0] = l1[2*i+1]
                    p[i][1] = l1[2*i]
                    p[i][2] = p[i][0] + 1
                    p[i][3] = p[i][1] + 1
        for i in range(len(p)):
            for j in range(4):
                if p[i][j] == max(l1) + 1:
                    p[i][j] = 1
        return p

    def seifert_circles(self, oriented_gauss_code):
        self.oriented_gauss_code = oriented_gauss_code
        x = self.PD_code_ogc(self.oriented_gauss_code)
        s = [[None for i in range(4)] for i in range(len(x))]
        for i in range(len(x)):
            s[i][0] = 'entering'
            s[i][2] = 'leaving'
            if self.oriented_gauss_code[1][i] == '-':
                s[i][1] = 'leaving'
                s[i][3] = 'entering'
            elif self.oriented_gauss_code[1][i] == '+':
                s[i][1] = 'entering'
                s[i][3] = 'leaving'
        x1 = x #the arrays are being copied, just a tag
        s1 = s
        r = [[[None,None],[None,None]] for i in range(len(x))]
        for i in range(len(x)):
            for j in [1,3]:
                if s[i][j] == 'leaving':
                    r[i][0][0] = x1[i][0]
                    r[i][0][1] = x1[i][j]
                    del x1[i][j]
                    del x1[i][0]
                    del s1[i][j]
                    del s1[i][0]
                    break
        for i in range(len(x)):
            for j in [0,1]:
                if s1[i][0] == "entering":
                    r[i][1][0] = x1[i][0]
                    r[i][1][1] = x1[i][1]
                elif s1[i][0] == "leaving":
                    r[i][1][0] = x1[i][1]
                    r[i][1][1] = x1[i][0]
        r1 = [a for b in r for a in b]
        dic = dict(sorted(r1))
        for i in dic:
            dic[i] = [dic[i]]
        D = DiGraph(dic)
        d = D.all_simple_cycles()
        for i in d:
            del i[0]
        return d

    def regions(self, oriented_gauss_code):
        self.oriented_gauss_code = oriented_gauss_code
        x = self.PD_code_ogc(self.oriented_gauss_code)
        s = [[None for i in range(4)] for i in range(len(x))]
        for i in range(len(x)):
            s[i][0] = 'entering'
            s[i][2] = 'leaving'
            if self.oriented_gauss_code[1][i] == '-':
                s[i][1] = 'leaving'
                s[i][3] = 'entering'
            elif self.oriented_gauss_code[1][i] == '+':
                s[i][1] = 'entering'
                s[i][3] = 'leaving'
        ou = [["under","over","under","over"] for i in range(len(x))]
        r = [[[None,None],[None,None]] for i in range(len(x))]
        r1 = [[[None,None],[None,None]] for i in range(len(x))]
        for i in range(len(x)):
            r[i][0][0] = x[i][0]
            r1[i][0][0] = "under"
            for j in range(1,4):
                if s[i][j] == "entering":
                    r[i][0][1] = x[i][j]
                    r1[i][0][1] = ou[i][j]
                    del x[i][j]
                    del ou[i][j]
                    s[i][j] = 0
                    del ou[i][0]
                    s[i][0] = 0
                    del x[i][0]
        for i in range(len(x)):
            r[i][1][0] = x[i][0]
            r[i][1][1] = x[i][1]
            r1[i][1][0] = ou[i][0]
            r1[i][1][1] = ou[i][1]
            del x[i][1]
            del x[i][0]
            del ou[i][1]
            del ou[i][0]
        gc_sign = self.oriented_gauss_code[1]
        r = [a for b in r for a in b]
        r1 = [a for b in r1 for a in b]
        r3 = deepcopy(r)
        lc = [[None,None] for i in range(len(x))]
        for i in range(len(x)):
            if gc_sign[i] == '-':
                if r1[2*i+1][0] == 'over':
                    lc[i][0] = r[2*i+1][0]
                lc[i][1] = (-1)*r[2*i][0]
            elif gc_sign[i] == '+':
                if r1[2*i+1][0] == 'under':
                    lc[i][1] = r[2*i+1][0]
                lc[i][0] = (-1)*r[2*i][1]
        r2 = []
        for i in reversed(range(len(x))):
            r2.append(r[2*i])
            del r[2*i]
        entering = r2[::-1]
        left_component_entering = lc
        leaving = r
        r4 = deepcopy(r)
        for i in r4:
            i[0] = (-1)*i[0]
            i[1] = (-1)*i[1]
        lc1 = [[None,None] for i in range(len(x))]
        for i in range(len(x)):
            if gc_sign[i] == '-':
                if r1[2*i+1][0] == 'over':
                    lc1[i][0] = r3[2*i+1][1]
                    if r1[2*i][0] == 'over':
                        lc1[i][1] = (-1)*r3[2*i][0]
                    elif r1[2*i][1] == 'over':
                        lc1[i][1] = (-1)*r3[2*i][1]
            elif gc_sign[i] == '+':
                if r1[2*i+1][1] == 'over':
                    lc1[i][0] = r3[2*i+1][1]
                    if r1[2*i][0] == 'under':
                        lc1[i][1] = (-1)*r3[2*i][0]
                    elif r1[2*i][1] == 'under':
                        lc1[i][1] = (-1)*r3[2*i][1]
        left_component_leaving = lc1
        w = {}
        w1 = {}
        for i in range(len(x)):
            w.update({entering[i][0] : left_component_entering[i][0]})
            w.update({entering[i][1] : left_component_entering[i][1]})
            w1.update({r4[i][0] : left_component_leaving[i][0]})
            w1.update({r4[i][1] : left_component_leaving[i][1]})
        for i in range(1,len(w)+1):
            w[i] = [w[i]]
        for i in range(-len(w),0):
            w1[i] = [w1[i]]
        w2 = dict(w.items() + w1.items())
        d = DiGraph(w2)
        regions = d.all_simple_cycles()
        for i in regions:
            del i[0]
        check = [i for i in range(-len(w), len(w)+1)]
        del check[len(w)]
        regions1 = [a for b in regions for a in b]
        r5 = sorted(regions1)
        if r5 == check:
            return regions
        else:
            raise Exception("Incorrect Input")

    def _is_move_required(self, oriented_gauss_code):
        self.oriented_gauss_code = oriented_gauss_code
        x = self.PD_code_ogc(self.oriented_gauss_code)
        sc = self.seifert_circles(self.oriented_gauss_code)
        regions = self.regions(self.oriented_gauss_code)
        q1 = deepcopy(regions)
        q = [[[],[]] for i in range(len(regions))]
        for i in range(len(regions)):
            for j in range(len(regions[i])):
                if regions[i][j] < 0:
                    q[i][0].append(regions[i][j])
                elif regions[i][j] > 0:
                    q[i][1].append(regions[i][j])
        r = [[] for i in range(len(q))]
        for i in range(len(q)):
            for j in range(len(q[i])):
                r[i].append(None)
                for k in range(len(q[i][j])):
                    if q[i][j][k] < 0:
                        q[i][j][k] = (-1)*q[i][j][k]
        for i in range(len(q)):
            for j in range(len(q[i])):
                for k in sc:
                    if set(q[i][j]).intersection(set(k)) == set(q[i][j]):
                        r[i][j] = None
                        break
                else:
                    r[i][j] = q[i][j]
        for i in reversed(range(len(r))):
            for j in reversed(range(len(r[i]))):
                if r[i][j] == None:
                    del r[i][j]
         #we see whether they belong to the same region if it is so we remove the other.
        for i in reversed(range(len(r))):
            if len(r[i]) > 1:
                del r[i][1]
            if len(r[i]) == 0:
                del r[i]
        # r has the components together
        r = [a for b in r for a in b]
        # we flat r to get r1
        r1 = deepcopy(r)
        r1 = sum(r1,[])
        # we sort r1 to get r2 this is in order to computer c
        r2 = sorted(r1)
        # c has the new components after the move has been made
        c = [[None for i in range(3)] for i in range(len(r2))]
        for i in range(len(c)):
            c[i][0] = r2[i] + 2*i
            c[i][1] = c[i][0] + 1
            c[i][2] = c[i][1] + 1
        #here we update c1 after comparing r1 & r2
        c1 = []
        for i in range(len(r1)):
            for j in range(len(r2)):
                if r1[i] == r2[j]:
                    c1.append(c[j])
                    break
        #now using the above data in c1 compute the PD info at the new crossings
        #we always pull the component numbered higher onto the component numbered lower
        npd = [[None for i in range(4)] for i in range(len(r1))]
        for i in range(len(r)):
            if max(r[i]) == r1[2*i]:
                npd[2*i+1][0] = c1[2*i][0]
                npd[2*i+1][2] = npd[2*i][0] + 1
                npd[2*i][0] = npd[2*i][2]
                npd[2*i][2] = npd[2*i][0] + 1
            elif max(r[i]) == r1[2*i+1]:
                npd[2*i+1][0] = c1[2*i+1][0]
                npd[2*i+1][2] = npd[2*i+1][0] + 1
                npd[2*i][0] = npd[2*i+1][2]
                npd[2*i][2] = npd[2*i][0] + 1
        #now we need to decide the over crossings, for this we need to find which crossing has
        #the highest component leaving since that has the new lowest component entering
        for i in range(len(r)):
            if max(r[i]) == r1[2*i+1]:
                if max(c1[2*i+1]) == max(npd[2*i]):
                    npd[2*i][1] = c1[2*i][1]
                    npd[2*i][3] = c1[2*i][0]
                    npd[2*i+1][1] = c1[2*i][1]
                    npd[2*i+1][3] = c1[2*i][2]
                elif max(c1[2*i+1]) == max(npd[2*i+1]):
                    npd[2*i+1][1] = c1[2*i][1]
                    npd[2*i+1][3] = c1[2*i][0]
                    npd[2*i][1] = c1[2*i][1]
                    npd[2*i][3] = c1[2*i][2]
            elif max(r[i]) == r1[2*i]:
                if max(c1[2*i]) == max(npd[2*i]):
                    npd[2*i][1] = c1[2*i][1]
                    npd[2*i][3] = c1[2*i][0]
                    npd[2*i+1][1] = c1[2*i][1]
                    npd[2*i+1][3] = c1[2*i][2]
                elif max(c1[2*i]) == max(npd[2*i+1]):
                    npd[2*i+1][1] = c1[2*i][1]
                    npd[2*i+1][3] = c1[2*i][0]
                    npd[2*i][1] = c1[2*i][1]
                    npd[2*i][3] = c1[2*i][2]
        #here we compute the planar diagram and store it in y with the new components
        #the npd has the PD Code for new crossings, now we need to modify the previous 
        #crossings.
        y = [[None for i in range(4)] for i in range(len(x))]
        for i in range(len(r2)):
            if i+1  < len(r2):
                for j in range(len(x)):
                    for k in range(4):
                        if x[j][k] < r2[0]:
                            y[j][k] = x[j][k]
                        elif x[j][k] > r2[i] and x[j][k] < r2[i+1]:
                            y[j][k] = x[j][k] + 2*(i+1)
                        elif x[j][k] > r2[len(r2)-1]:
                            y[j][k] = x[j][k] + 2*(i+2)
        #the above PD code has only few elements and not all, as we are updating the 
        #previous crossings we can use the sign information from the input.
        gc_sign = self.oriented_gauss_code[1]
        for i in range(len(x)):
            if gc_sign[i] == '-':
                if y[i][0] == None:
                    y[i][0] = y[i][2] - 1
                if y[i][2] == None:
                    y[i][2] = y[i][0] + 1 
                if y[i][3] == None:
                    y[i][3] = y[i][1] - 1
                if y[i][1] == None:
                    y[i][1] = y[i][3] + 1
            elif gc_sign[i] == '+':
                if y[i][0] == None:
                    y[i][0] = y[i][2] - 1
                if y[i][2] == None:
                    y[i][2] = y[i][0] + 1
                if y[i][3] == None:
                    y[i][3] = y[i][1] + 1
                if y[i][1] == None:
                    y[i][1] = y[i][3] - 1
        y = y + npd
        return y