Vogel’s algorithm continued …

Hello everyone,
Last week we implemented the Vogel’s algorithm Part – 1, which would check for the bad regions and remove them. This week started off  tweaking the last week’s code. I was thinking that instead of performing a move and then looking for the bad regions, why not perform all the moves necessary to correct the bad regions in a single go. But this turned out to be a wrong approach as the seifert circles expected were not matching with the results we got. So we choose a bad region, perform a move and again see if there are bad regions, basically a while loop which captures this was implemented. If there are no bad regions we move onto the next part which is detecting the braidword of the knot. In the part 2, we use the following information from part 1 of the algorithm, the PD Code, seifert circles, regions with respect to the final knot after we have removed the necessary regions by performing the moves.  Now there are exactly two seifert circles which match with the regions, we select one of them and see with what seifert circle it shares a crossing and number the second seifert circle as 2 and so on and so forth.
For example here are the results we get :
sage: L = link.Link(oriented_gauss_code = [[-1, +2, -3, 4, +5, +1, -2, +6, +7, 3, -4, -7, -6,-5],[‘-‘,’-‘,’-‘,’-‘,’+’,’-‘,’+’]])

Final method gives out the final seifert circles, regions and the planar code of the modified knot. We see exactly two regions coincide with the seifert circles.
sage: L.final()

seifert circles
[[[18, 4],
[21, 15],
[9, 3, 19, 11, 17, 5, 13, 7, 1],
[10, 20, 16, 12, 6, 14, 22, 8, 2]]

regions,
[[-15, -21],
[6, -13],
[2, -9],
[8, -1],
[18, 4],
[-3, 10, -19],
[12, -5, -17],
[20, 16, -11],
[14, 22, -7],
[19, 11, 17, -4],
[21, -14, -6, -12, -16],
[15, -20, -10, -2, -8, -22],
[5, 13, 7, 1, 9, 3, -18]]

PD_code,
[[1, 9, 2, 8],
[9, 3, 10, 2],
[5, 13, 6, 12],
[13, 7, 14, 6],
[22, 7, 1, 8],
[19, 11, 20, 10],
[16, 11, 17, 12],
[18, 4, 19, 3],
[17, 4, 18, 5],
[21, 14, 22, 15],
[20, 16, 21, 15]]]

#this is still a method in development
sage: L.seifert_to_braid()
here we have numbered the seifert circles which form the strands in the braidword
{1: [18, 4], 2: [9, 3, 19, 11, 17, 5, 13, 7, 1], 3: [10, 20, 16, 12, 6, 14, 22, 8, 2], 4: [21, 15]}

#this is other information required for the ordering of the crossings
{1: [[18, 4, 19, 3], [17, 4, 18, 5]], 2: [[1, 9, 2, 8], [9, 3, 10, 2], [5, 13, 6, 12], [13, 7, 14, 6], [22, 7, 1, 8], [19, 11, 20, 10], [16, 11, 17, 12], [18, 4, 19, 3], [17, 4, 18, 5]], 3: [[1, 9, 2, 8], [9, 3, 10, 2], [5, 13, 6, 12], [13, 7, 14, 6], [22, 7, 1, 8], [19, 11, 20, 10], [16, 11, 17, 12], [21, 14, 22, 15], [20, 16, 21, 15]], 4: [[21, 14, 22, 15], [20, 16, 21, 15]]}
{1: [‘-‘, ‘+’], 2: [‘-‘, ‘-‘, ‘-‘, ‘-‘, ‘+’, ‘-‘, ‘+’, ‘-‘, ‘+’], 3: [‘-‘, ‘-‘, ‘-‘, ‘-‘, ‘+’, ‘-‘, ‘+’, ‘+’, ‘-‘], 4: [‘+’, ‘-‘]}
{1: [[4, 19], [18, 5]], 2: [[9, 2], [3, 10], [13, 6], [7, 14], [1, 8], [11, 20], [17, 12], [4, 19], [18, 5]], 3: [[9, 2], [3, 10], [13, 6], [7, 14], [1, 8], [11, 20], [17, 12], [22, 15], [16, 21]], 4: [[22, 15], [16, 21]]}
{1: [[18, 3], [17, 4]], 2: [[1, 8], [9, 2], [5, 12], [13, 6], [22, 7], [19, 10], [16, 11], [18, 3], [17, 4]], 3: [[1, 8], [9, 2], [5, 12], [13, 6], [22, 7], [19, 10], [16, 11], [21, 14], [20, 15]], 4: [[21, 14], [20, 15]]}

So the next and the final part is to trace through the ordering of the crossings and assign them with a braid generator and that generates the braidword.
The last part of ordering has been a tough part to generalize and code. It is like we have all the information but the dots are yet to be connected to get the final picture. I would like to leave you with two examples which we start from the first.

#so we start with the oriented gauss code
sage: L = link.Link(oriented_gauss_code = [[-1, +2, -3, 4, +5, +1, -2, +6, +7, 3, -4, -7, -6,-5],[‘-‘,’-‘,’-‘,’-‘,’+’,’-‘,’+’]])
#get the pd_code
sage: L.PD_code()
[[1, 7, 2, 6],
[7, 3, 8, 2],
[3, 11, 4, 10],
[11, 5, 12, 4],
[14, 5, 1, 6],
[13, 9, 14, 8],
[12, 9, 13, 10]]
#compute the regions
sage: L.regions()
[[4, -11],
[2, -7],
[6, -1],
[13, 9],
[-4, -10, -12],
[-8, -2, -6, -14],
[10, -3, 8, -13],
[14, -5, 12, -9],
[7, 3, 11, 5, 1]]
#compute the seifert circles
sage: L.seifert_circles()
[[13, 9], [12, 10, 4], [8, 14, 6, 2], [7, 3, 11, 5, 1]]
#remove the bad regions … this is just a method showing how the remove_regions works
#it returns a pd_code after the move has been made
sage: L.remove_regions()
[[1, 9, 2, 8],
[9, 3, 10, 2],
[5, 13, 6, 12],
[13, 7, 14, 6],
[18, 7, 1, 8],
[17, 11, 18, 10],
[14, 11, 15, 12],
[16, 4, 17, 3],
[15, 4, 16, 5]]

#the below method returns the seifert circles, regions and pd_code after the correction (we run the above method until we end up with these results)
sage: L.final()
[[[18, 4],
[21, 15],
[9, 3, 19, 11, 17, 5, 13, 7, 1],
[10, 20, 16, 12, 6, 14, 22, 8, 2]],
[[-15, -21],
[6, -13],
[2, -9],
[8, -1],
[18, 4],
[-3, 10, -19],
[12, -5, -17],
[20, 16, -11],
[14, 22, -7],
[19, 11, 17, -4],
[21, -14, -6, -12, -16],
[15, -20, -10, -2, -8, -22],
[5, 13, 7, 1, 9, 3, -18]],
[[1, 9, 2, 8],
[9, 3, 10, 2],
[5, 13, 6, 12],
[13, 7, 14, 6],
[22, 7, 1, 8],
[19, 11, 20, 10],
[16, 11, 17, 12],
[18, 4, 19, 3],
[17, 4, 18, 5],
[21, 14, 22, 15],
[20, 16, 21, 15]]]

#here we have numbered the seifert circles which form the strands in the braidword
sage: L.seifert_to_braid()
{1: [18, 4], 2: [9, 3, 19, 11, 17, 5, 13, 7, 1], 3: [10, 20, 16, 12, 6, 14, 22, 8, 2], 4: [21, 15]}

The ordering of the crossing remain …. which would complete the algorithm

Another example :

sage: L = link.Link(oriented_gauss_code = [[-1, +2, 3, -4, 5, -6, 7, 8, -2, -5, +6, +1, -8, -3, -4, -7],[‘-‘,’-‘,’-‘,’-‘,’+’,’+’,’-‘,’+’]])

sage: L.PD_code()
[[1, 13, 2, 12],
[9, 3, 10, 2],
[14, 4, 15, 3],
[4, 16, 5, 15],
[10, 5, 11, 6],
[6, 11, 7, 12],
[16, 8, 1, 7],
[13, 8, 14, 9]]
sage: L.regions()
[[6, -11],
[15, -4],
[9, 3, -14],
[2, -9, -13],
[1, 13, -8],
[12, -1, -7],
[5, 11, 7, -16],
[-3, 10, -5, -15],
[-6, -10, -2, -12],
[16, 8, 14, 4]]

sage: L.seifert_circles()
[[10, 6, 12, 2], [16, 8, 14, 4], [13, 9, 3, 15, 5, 11, 7, 1]]

sage: L.remove_regions()
‘No move required’
sage: L.final()
[[[10, 6, 12, 2], [16, 8, 14, 4], [13, 9, 3, 15, 5, 11, 7, 1]],
[[6, -11],
[15, -4],
[9, 3, -14],
[2, -9, -13],
[1, 13, -8],
[12, -1, -7],
[5, 11, 7, -16],
[-3, 10, -5, -15],
[-6, -10, -2, -12],
[16, 8, 14, 4]],

[[1, 13, 2, 12],

[9, 3, 10, 2],
[14, 4, 15, 3],
[4, 16, 5, 15],
[10, 5, 11, 6],
[6, 11, 7, 12],
[16, 8, 1, 7],
[13, 8, 14, 9]]]

sage: L.seifert_to_braid()
#we number the strands
{1: [10, 6, 12, 2], 2: [13, 9, 3, 15, 5, 11, 7, 1], 3: [16, 8, 14, 4]}

Other information for extracting the braidword
{1: [[1, 13, 2, 12], [9, 3, 10, 2], [10, 5, 11, 6], [6, 11, 7, 12]], 2: [[1, 13, 2, 12], [9, 3, 10, 2], [14, 4, 15, 3], [4, 16, 5, 15], [10, 5, 11, 6], [6, 11, 7, 12], [16, 8, 1, 7], [13, 8, 14, 9]], 3: [[14, 4, 15, 3], [4, 16, 5, 15], [16, 8, 1, 7], [13, 8, 14, 9]]}
{1: [‘-‘, ‘-‘, ‘+’, ‘+’], 2: [‘-‘, ‘-‘, ‘-‘, ‘-‘, ‘+’, ‘+’, ‘-‘, ‘+’], 3: [‘-‘, ‘-‘, ‘-‘, ‘+’]}
{1: [[13, 2], [3, 10], [11, 6], [7, 12]], 2: [[13, 2], [3, 10], [4, 15], [16, 5], [11, 6], [7, 12], [8, 1], [14, 9]], 3: [[4, 15], [16, 5], [8, 1], [14, 9]]}
{1: [[1, 12], [9, 2], [10, 5], [6, 11]], 2: [[1, 12], [9, 2], [14, 3], [4, 15], [10, 5], [6, 11], [16, 7], [13, 8]], 3: [[14, 3], [4, 15], [16, 7], [13, 8]]}
{1: [[9, 3, 10, 2], [10, 5, 11, 6], [6, 11, 7, 12]], 2: [[1, 13, 2, 12], [9, 3, 10, 2], [14, 4, 15, 3], [4, 16, 5, 15], [10, 5, 11, 6], [6, 11, 7, 12], [16, 8, 1, 7], [13, 8, 14, 9]], 3: [[14, 4, 15, 3], [4, 16, 5, 15], [16, 8, 1, 7], [13, 8, 14, 9]]}
[[13, 2], [3, 10], None]

So to conclude, I hope I can say we are almost able to see the result and almost there but as said the dots are yet to be connected. The implementation of the last part remains.

Everything to PD ….

Hello everyone,
This week we focused on the implementation details of the Vogel’s algorithm. I will get back to this algorithm at a later stage. To start off, last week we had a problem in generating the planar diagram code. But that was resolved using the braid as input. It seems braid word has all the information to generate the planar diagram (unique). The problem with other inputs like the gauss code or the dt code is we get a planar diagram but which component of the over-crossing comes first when we move in the clockwise direction is what is the problem. But in braidword we have this information in the form of -1 and +1, which happens to provide this information. This was achieved at the very beginning of the last week. Ever since it has been the implementation of Vogel’s algorithm, which takes in the oriented gauss code and converts it to the braid word. We have had to work on the oriented gauss code as the parameter to the method, it is not in a great shape but still the main idea has been achieved. (The minor problem is we have to pass the oriented gauss code as a parameter for the method). The difference here is, for every crossing we take how the crossing is oriented, so the name oriented gauss code. So this allows us to convert from oriented gauss code to planar diagram. The next thing was to determine the regions and then the Seifert circles. There are two parts to the algorithm of which one is to identify the unoriented Seifert circles and then perform a Reidmester move. Once this move is done then look for other unoriented Seifert circles. Once we end up with no unoriented circles we get the braidword which forms the second part. So in the first part we are able to convert the oriented gauss code to Planar Diagram, we are working on looking into how we can get regions which are bounded by the components. Next step is to identify the Seifert circles and then detect the unoriented pair. We have used different approaches for detecting the regions, like the Directed graphs where the crossings form the vertices and they have an edge if they have a component or two in common. But this made things a bit complicated as directed graphs cycles (g._show_all_cycles() ) returned more data and it was a bit difficult to get the exact regions. We are working on this as of now. Miguel has sent in his ideas on this matter and I am looking into it. The idea now is to move around the crossings in a given fashion and then work out the regions and then move on. I had another approach which I took time to read, this was the approach of Andrew who has implemented a version of Vogel’s algorithm in the Braid programme. It is somewhat on the similar lines but we choose to re think as it had some huge information to calculate after each step. I have sent in a pull request with the work

https://github.com/miguelmarco/sage/pull/7.

Documentation work still remains of the newly implemented methods and we just got these methods working we still need to re think on the design, two to three things that we are lacking as of now:
1. Documentation
2. Redesigning the currently implemented methods.
3. Setting the minor issues which have been already identified from the previous pull requests. (in-line comments on the previous pull requests have to be worked upon).

 

Gauss to DT, DT to Planar Code, Plot ….

Hello everyone,
This week has been a bit on the slower side. I had to think hard on few problems I faced. First of all, last week I started with Gauss to DT implementation and I sent in the pull request with not the full implementation (The DT was being generated but not the sign related to the crossings). This week started off with generating signs for the DT Code. This was cross checked using the already implemented methods. Then I started to implement the planar code, there was this input which made me think I was on the wrong path i.e., 4 -6 8 -2, I saw the results of this in a wrong way, then started to focus more on what was going wrong in the computation process. But later I realized that it was a valid input and the output also made complete sense. Next there was this ambiguity in considering which component number on the over cross would come first. The algorithm said move clockwise around the crossing noting down the component numbers surrounding it. It seems there is no solution for this problem as neither the gauss code nor the dt code captures this information. If the user could provide with the information on how the crossings are oriented (this code is the oriented gauss code), then the planar diagram could be generated as we now know which component on the over cross comes first as we move clockwise around the crossing. On this issue me and Miguel decided to use the braid word as input (I guess this has all the information encoded) and have thought of including planar code as one of the standard inputs. Next there was this implementation whether the given knot is an alternating diagram or not. That was start forward from the gauss code implementation. Then I tried to plot the knot using various plot methods, but I must say the results on this are not that great. This week our focus is on generating the planar diagram code from the braidword (this requires a lot of thinking on how one can move on the braid, although braid to DT has the required pointers for the same). Generate the PD code from the oriented gauss code and then move onto implementation of Vogel’s algorithm. The last task has been on the todo list for a long time and I hope I can pull that off this week. So that concludes the third week, which had nothing great on the implementation side but was more of thinking, and lot of fun playing around with the diagram stuff. It was fun, but costed me a lot of time :P. Thanks for reading through.

PS: Braidword to PD code has been achieved (There is a small technical glitch, the component one gets numbered twice 1 as well as the last component plus one, anyways I wanted to share it). The gist of the code

https://gist.github.com/amitjamadagni/ac2298557b5b28277356

DT to Gauss, Braid to DT …

Hello everyone,
As the title says, the main focus of the previous week was to work on the conversions. This has been achieved and this allows the conversion from braidword to any other presentation. Coming to the algorithms used, the one used for DT to Gauss uses the following method, insert odds between the evens which form the DT notation, then give each of the pair a number, then move from one crossing to the other and note down the number to which pair it belongs to. The sign of the crossing are taken along with the numbers which we have assigned to the pairs. The following has been taken as the reference http://katlas.org/wiki/DT_(Dowker-Thistlethwaite)_Codes . The gist of the code, which has the gauss method
https://gist.github.com/amitjamadagni/aabd7b4b116df1186151.
The second algorithm which converts Braid to DT moves around the braid giving each crossing three things a crossing number, label and type1 (I still have some doubt about the consistency in the sign we are taking in, which is looked into by the type1 variable). The program has been inspired from the braid program.  The gist of the code,

https://gist.github.com/amitjamadagni/d039dd95b8e9733d66bb.

An additional method that is the knot determinant has been implemented, which is the modulus of alexander polynomial at value -1.

So the summary, above conversion would allow the following conversions  :

braid      (missing)    Gauss < ==  DT  <==|

|_____________________________|

So the missing part is the Vogel algorithm implementation, which would be the focus of the next week (It was on the list last week as well, but I wanted to complete the conversions related to braid word and then move onto this). I have also looked into how to generate the Link/Knot diagrams. I was thinking of using the already implemented braid representation and closing them to form the necessary link or knot.  There are other ways like using TikZ or the xy package which uses LaTeX for generation. That’s all from me for this week. Thanks for reading through.