Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Vogel implementation along with PD Code
#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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment