Revamped to work for links …

Hello everyone,
The last week we focused on extending the current functionality to links. That involved a lot of refactoring the code. The methods have become more general and work for links. Some of the issues like naming of the methods and storing once a form of representation is calculated are some of the few which remain to be worked upon. This has been a great learning curve for me. Many things were edited which includes addition of the method orientation which gives the signs of the crossings. That was really helpful in formulating the other structures. There was one other issue in the vogel move, this had a case where the pulling of the higher strand onto the lower one did not lead to a generalization on constructing the new crossings.  The issue was resolved as we looked upto the strands in the regions and decided how the crossings would be generated. If the strands were positive, one kind of crossing were obtained and if the strands were negative the other crossings were obtained. I had this thought but I was not sure whether it would work for all cases, Miguel chipped in and gave me the idea in a more concrete setting. So that set the method vogel move up. The rest was revamped and a lot of cleaning has been taking place in the code to remove the stuff which is not necessary. Hope we have most of the functionality by the end. That’s it from me. Thanks for reading through and here is the latest pull request.

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

Advertisements

Conversions, cleaning …

Hello everyone,
The last week we focused on the conversions. Some parts are ready for the knots, in sense the standard input conversion is done but there is lots more to add to it. We are returning the braid word as of now where we need to return the braid itself. That would give access to the other methods like the Seifert Matrix and Alexander polynomial. As of now we are thinking of conversions for the links. The braid to pd code has been edited. We no longer maintain the order the crossings, it is just that we encounter a crossing and we start numbering , previously we used to trace the braid out and then order the crossing accordingly. This week the focus is on converting pd code to braid for links, but it seems that we need to even consider the signs for the crossings,  this might affect the way we have been considering the pd code uptil now. There is one more way we can look at the pd code that is assign four new numbers at each crossing, that would completely change the way we have looked at the pd code and would also call for lot of re implementation. I guess considering the signs should be the possible way out for the pd code of the links. In knots we did not have this problem as it was a more structured structure. This is taking a lot of time than expected. Hopefully we have the implementation for links and all issues resolved by this week. Still there is the invariants which have to be implemented (the conway, homfly) but for now the focus is totally on the conversions. That’s it from me. Thanks for reading through. And here is the pull request for the week.

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

Jones Polynomial, Trip Matrix, documenting ….

Hello everyone,
This week we have made an attempt at implementing the Jones Polynomial. We have used the trip matrix of the knot to determine the Jones polynomial. The trip matrix of a knot is determined by the following process. We number the crossings randomly, and we start moving along the knot, let T be the matrix and T ij  be the elements. Now we start with the crossing i and see how many times we have encountered the crossing j until we return to the crossing i. We take mod2 of this value and fill that matrix element. So in this way we construct all the elements except the diagonal elements. For the diagonal elements we see whether i is a positive cross or negative cross. If it is a positive cross we fill it with zero and for the negative cross we fill it with 1. Now we have the initial trip matrix. To evaluate the Jones polynomial we smooth the crossings until we have a link for which we know the Kauffman’s bracket. So this decomposition here is looked by the matrix. So for the initial diagonal elements of the trip matrix we assign a certain type of smoothing and determine the number of seifert circles. Now we construct a new matrix by doing the following, we choose a crossing and smooth it in another way(different from the first), the only elements which are different from the initial matrix are the diagonal elements and the only element which changes when we do such kind of a smoothing is the crossing number element. In sense if we change the smoothing at crossing i we change the number at the matrix element T ii   (this is flipped from either one to zero or zero to one). Again we continue this until all the options are exhausted. Then for every matrix we have certain coefficients of the jones polynomial. Adding all these up gives the jones polynomial for the knot. I know it is tough to follow but that is the gist of the algorithm. I have followed the following material and I request the readers to have a look at them for greater understanding.

First Reference:
http://www.math.nus.edu.sg/~urops/Projects/knot.pdf

Second Reference :
A matrix for computing the Jones Polynomial of a Knot by Louis Zulli

We have dedicated some time for documenting the code that we coded till now. There have been some edge cases where the code showed some inconsistency. We are working on the edge cases as well as cleaning the code alongside continuing the implementation of the invariants.
Here is the pull request for the week:

https://github.com/miguelmarco/sage/pull/10
Here is the entire code uptil now:
https://github.com/amitjamadagni/sage/blob/b94bf8d9db77dd8ec52b92fe1da32f9bd9010e03/src/sage/knots/link.py

Braid word detection

Hello everyone,
The past week has been really on the thinking end. The task was to detect the braid word from the oriented gauss code. So I mentioned the dots were to be connected, but then I had problems implementing it. I was thinking more and more rather than a looking for the straight implementation. It took me a week to break through and then I had some consistent results.  So they were various ideas on how one could detect the braidword. One was to update the outgoing strands after each crossing has been looked into and then match it with were we have the incoming. I was working on various other ideas as well as I felt there was some kind of difficulty on the implementation end. Here are the gists of code on the ideas I worked upon.

The ones I attempted
https://gist.github.com/amitjamadagni/1ccad5ca91b96eac367b

The one which is working
https://gist.github.com/amitjamadagni/57b5de098efe11056efa

This was like I had all the answers yet I was missing something. There are some glitches still though, small condition on the seifert circles one is missing. I need to work on the documentation end as we are missing on that. And here is the pull request for the past two weeks.

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

Lot of work as to be done on the documenting and testing side of the code. Here are the results for the algorithm

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

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

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]]

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]]

We perform a move if they are bad regions
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]]

Final method gives the above information after all the moves are made
sage: L.final()
Seifert Circles
[[[4, 18, 4],
[15, 21, 15],
[1, 9, 3, 19, 11, 17, 5, 13, 7, 1],
[2, 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]]]

And finally we convert it to braid
sage: L.seifert_to_braid()
[-1, -2, -3, 2, 1, -2, -2, 3, 2, -2, -2]

One more example :

sage: from sage.knots import link

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.seifert_circles()
[[2, 10, 6, 12, 2], [4, 16, 8, 14, 4], [1, 13, 9, 3, 15, 5, 11, 7, 1]]

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.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.remove_regions()
‘No move required’

sage: L.final()
[[[2, 10, 6, 12, 2], [4, 16, 8, 14, 4], [1, 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()
[-1, 2, -1, -2, -2, 1, 1, -2]

So this week we are looking at jones polynomial implementation and lots of documentation and testing.Thanks for reading through.

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).