Opened 5 years ago

Closed 3 years ago

Last modified 16 months ago

#17030 closed enhancement (fixed)

Knot Theory as a part of GSoC 2014.

Reported by: amitjamadagni Owned by: amitjamadagni
Priority: major Milestone: sage-7.2
Component: algebraic topology Keywords:
Cc: mmarco, jhpalmieri, tscrim, fuglede Merged in:
Authors: Amit Jamadagni, Miguel Marco Reviewers: Miguel Marco, Karl-Dieter Crisman, Frédéric Chapoton, Travis Scrimshaw, Søren Fuglede Jørgensen, John Palmieri
Report Upstream: N/A Work issues:
Branch: 207d033 (Commits) Commit:
Dependencies: Stopgaps:

Description (last modified by tscrim)

We provide a basic implementation of knots and links such as the Seifert matrix, Jones and Alexander polynomials.

Change History (195)

comment:1 Changed 5 years ago by amitjamadagni

  • Branch set to u/amitjamadagni/knots

comment:2 Changed 5 years ago by amitjamadagni

  • Authors set to amitjamadagni, mmarco
  • Cc mmarco added
  • Commit set to 50abd9941bd9e4fa0c68fa26ff0b0beea643f26d
  • Milestone sage-6.4 deleted
  • Owner changed from (none) to amitjamadagni
  • Summary changed from knots to Knot Theory as a part of GSoC 2014.
  • Type changed from PLEASE CHANGE to task

comment:3 Changed 5 years ago by amitjamadagni

  • Status changed from new to needs_review

comment:4 Changed 5 years ago by amitjamadagni

  • Status changed from needs_review to needs_work

comment:5 Changed 5 years ago by amitjamadagni

Things to do:

  1. Plot method needs to be added.
  2. ncomponents needs to be worked upon.

comment:6 Changed 5 years ago by amitjamadagni

  • Reviewers set to mmarco

comment:7 Changed 5 years ago by jhpalmieri

  • Cc jhpalmieri added

comment:8 Changed 5 years ago by mmarco

I am not sure if it is a good idea that i would be the reviewer, since i have been involved in tge coding too. Besides, there is some polishing needed still and it would go faster if i directly work on it.

jhpamieri, do you feel able to do the revieweing? If yes, i will start working in the corrections. Otherwise, i will stay away from changing the code and just act as reviewer.

comment:9 follow-up: Changed 5 years ago by mmarco

  • Component changed from PLEASE CHANGE to algebraic topology

I get the following wrror when compiling:

running install_lib byte-compiling /home/mmarco/sage/local/lib/python2.7/site-packages/sage/all.py to all.pyc

File "/home/mmarco/sage/local/lib/python2.7/site-packages/sage/all.py", line 174

<<<<<<< HEAD

Is it a problem with the commit? Over which branch is it based?

comment:10 in reply to: ↑ 9 Changed 5 years ago by amitjamadagni

Replying to mmarco:

I get the following wrror when compiling:

running install_lib byte-compiling /home/mmarco/sage/local/lib/python2.7/site-packages/sage/all.py to all.pyc

File "/home/mmarco/sage/local/lib/python2.7/site-packages/sage/all.py", line 174

<<<<<<< HEAD

Is it a problem with the commit? Over which branch is it based?

I pushed the branch from github (the branch week15) onto the trac ticket. Let me try adding all.py and commit once again.

Last edited 5 years ago by amitjamadagni (previous) (diff)

comment:11 Changed 5 years ago by git

  • Commit changed from 50abd9941bd9e4fa0c68fa26ff0b0beea643f26d to e6e17c401b8b879cd041dafc120d3943b3f2dacb

Branch pushed to git repo; I updated commit sha1. New commits:

e6e17c4Removed the messages in all.py

comment:12 follow-up: Changed 5 years ago by tscrim

  • Authors changed from amitjamadagni, mmarco to Amit Jamadagni, Miguel Marco
  • Cc tscrim added
  • Milestone set to sage-6.4
  • Reviewers changed from mmarco to Miguel Marco

It looks like a bad resolution to a merge, but it's a simple enough fix. Also on a quick look through:

  • Doc formatting should follow:
    INPUT:
    
    - ``name`` -- some description that is very long and
      note the alignment
    
    OUTPUT:
    
    - these are not usually complete sentences but short descriptions
    
  • Move the nice documentation from the __init__ into the class-level doc so people can actually see it.
  • All methods must have doctests.
  • It's my pythonic to use isinstance(input_, list) instead of type(input_) == list.
  • input_ is a bad variable name (according to python standards), just use input (or perhaps the slightly more descriptive data)
  • Don't raise Exception, instead raise ValueError or TypeError (after killing with fire and holy water :P).
  • Change
    pd_error = _pd_check_(input_)
    if pd_error == True:
        pass
    elif pd_error == False:
        pass
    
    into (the pythonic)
    if _pd_check_(input_):
        pass
    else:
        pass
    
  • Use is not None instead of != None.
  • Make _dt_internal_ a proper method of the class.
  • Remove the trailing underscore of _pd_check_, ,_dt_internal_ etc. as methods with a leading and trailing underscore are usually Sage special functions (and naming conventions of python).
  • Is "dowker" a proper name (and hence, should be capitalized in the documentation)?
  • The method name Seifert_Matrix should be seifert_matrix (naming conventions again).
  • Could you change the name of ncomponents to number_of_components (although you can keep it as a shorthand alias)?
  • This needs to be added to the documentation (probably as a new component).

I'll make a more detailed pass through the code after these are addressed. I also don't know how much of the math I'll be able to review as I've studied a little knot theory, but possibly not enough to check everything. Although Miguel could count as the reviewer on that front.

I think this will be a great addition to Sage, all it needs a little polish.

Best,
Travis

Last edited 5 years ago by tscrim (previous) (diff)

comment:13 Changed 5 years ago by jdemeyer

Also please respect http://www.sagemath.org/doc/developer/coding_basics.html#headings-of-sage-library-code-files and add your new files to the reference manual (have a look at the files in src/doc/en/reference to see how that is done).

Even better, change

pd_error = _pd_check_(input_)
if pd_error == True:
    raise Exception("...")
elif pd_error == False:
    foo

to

if not _pd_check(input):
    raise ValueError("...")

foo

and change the last line of def _pd_check_(pd): to return not pd_error, since I would expect a "check" function to return True if the checking was successful. Also drop the trailing underscores.

comment:14 follow-up: Changed 5 years ago by jdemeyer

Instead of returning a string in _vogel_move_(), you should return None in case of failure. That would be more efficient and one wouldn't need to remember a magic string (which is by the way wrong in the doc of that method, further proving my point).

comment:15 in reply to: ↑ 14 Changed 5 years ago by amitjamadagni

Replying to jdemeyer:

Instead of returning a string in _vogel_move_(), you should return None in case of failure. That would be more efficient and one wouldn't need to remember a magic string (which is by the way wrong in the doc of that method, further proving my point).

I am currently having few issues with pushing commits onto trac, once I am done with the setup I will be sending in the commits. Thanks for guiding me and sorry for missing on the rules.

Last edited 5 years ago by amitjamadagni (previous) (diff)

comment:16 in reply to: ↑ 12 ; follow-up: Changed 5 years ago by kcrisman

I'll make a more detailed pass through the code after these are addressed. I also don't know how much of the math I'll be able to review as I've studied a little knot theory, but possibly not enough to check everything. Although Miguel could count as the reviewer on that front.

Yeah, I think it would be really wise for such a new component and with a lot of technicalities for determining e.g. whether a given link is a knot to have a couple actual knot theorists review it, at least by checking the output in lots of cases. That may take some cold-calling, though perhaps a sage-devel email will turn up some all by itself, and there are Sage-friendly knot folks out there - though I don't know if they know how to review a branch.

comment:17 follow-ups: Changed 5 years ago by mmarco

I was planning on making a package with the database from the knot atlas, and use it to run automated tests, computing the invariants for the knots and links there.

The problem with that approach is that a) It needs some nontrivial work to be implemented, and b) it restricts to knots and links presented im spcially "nice" ways, so we could miss some bugs if they show up only when some strange representations are used.

Anyways, it would be a nice addition by itself, so i will try to work on it in the following weeks.

In the meantime, and since there are several other reviewers in the coding style part, i will just focus on checking the mathematical correctness of the methods.

comment:18 follow-up: Changed 5 years ago by mmarco

There is something working wrong in the following case:

sage: L=Link([[1, 4, 2, 5], [7, 10, 8, 11], [3, 9, 4, 8], [9, 3, 10, 2], [5, 12, 6, 1], [11, 6, 12, 7]])
sage: L
<repr(<sage.knots.link.Link at 0x7f41771c8a28>) failed: Exception: Invalid Input>

It gets an error when trying to get the connected components, which in turn tries to convert it to braid (which is probably not a good idea, it would be wiser to compute the components directly from the PD_code, since we might me loosing something in the conversion PD<->braid).

In any case, this example fails in the conversion to braid:

sage: L.braid()
...
Exception: Invalid Input

Please go through it and debug. }}}

comment:19 in reply to: ↑ 17 ; follow-up: Changed 5 years ago by kcrisman

I was planning on making a package with the database from the knot atlas, and use it to run automated tests, computing the invariants for the knots and links there.

The problem with that approach is that a) It needs some nontrivial work to be implemented, and b) it restricts to knots and links presented im spcially "nice" ways, so we could miss some bugs if they show up only when some strange representations are used.

Anyways, it would be a nice addition by itself, so i will try to work on it in the following weeks.

That's a really excellent idea. It's always good to have two ways to check information anyway. Ideally one could have a prototype of that available in time to help test this ticket as well.

comment:20 in reply to: ↑ 16 ; follow-up: Changed 5 years ago by tscrim

Replying to kcrisman:

Yeah, I think it would be really wise for such a new component and with a lot of technicalities for determining e.g. whether a given link is a knot to have a couple actual knot theorists review it, at least by checking the output in lots of cases. That may take some cold-calling, though perhaps a sage-devel email will turn up some all by itself, and there are Sage-friendly knot folks out there - though I don't know if they know how to review a branch.

FTR - I might be able to pull a few of the knot theorists at Davis to do the review in a month or two.


Also here's some things that I'd like to see (although they don't have to be done here):

  • Make the monoid of all knots (and/or links) under connect sum (and disjoint union).
  • Implement a latex and/or a plotting method (although perhaps this would need specialized class for PL knots?).
  • Handle input in Dowker notation (if I understand it correctly, it completely determines a knot), and subsequently make _dowker_notation_ public (i.e. name it dowker_notation).

comment:21 in reply to: ↑ 19 Changed 5 years ago by mmarco

That's a really excellent idea. It's always good to have two ways to check information anyway. Ideally one could have a prototype of that available in time to help test this ticket as well.

I am already running some of those tests. That's how i found the error in the conversion to braid.

I have been working on a cleaner rewrite of the code used to convert from knot to braid, but i am not sure if it is a better idea that i stay as a reviewer. If i commit some code, someone else should review it.

comment:22 Changed 5 years ago by git

  • Commit changed from e6e17c401b8b879cd041dafc120d3943b3f2dacb to 4fb0409d0f89d75b01a9b4f7ef330b05ca80bae4

Branch pushed to git repo; I updated commit sha1. New commits:

4fb0409Few changes.

comment:23 in reply to: ↑ 20 Changed 5 years ago by amitjamadagni

Also here's some things that I'd like to see (although they don't have to be done here):

  • Make the monoid of all knots (and/or links) under connect sum (and disjoint union).
  • Implement a latex and/or a plotting method (although perhaps this would need specialized class for PL knots?).
  • Handle input in Dowker notation (if I understand it correctly, it completely determines a knot), and subsequently make _dowker_notation_ public (i.e. name it dowker_notation).

I am working on the plot method. Miguel has sent me the outline and I am on it.

The purpose of including the dowker notation was to implement the HOMFLY Polynomial which is in progress. The dowker notation as I understand is the incoming pair at each crossing. It completely determines the link but PD code is more complete. I guess we can include it but as PD is more complete I think we can exclude it. Anyways let me know your thoughts on this.

Sorry for the previous comment which mentioned the DT which is different from the dowker code.

Last edited 5 years ago by amitjamadagni (previous) (diff)

comment:24 in reply to: ↑ 17 Changed 5 years ago by amitjamadagni

Replying to mmarco:

I was planning on making a package with the database from the knot atlas, and use it to run automated tests, computing the invariants for the knots and links there.

The problem with that approach is that a) It needs some nontrivial work to be implemented, and b) it restricts to knots and links presented im spcially "nice" ways, so we could miss some bugs if they show up only when some strange representations are used.

Anyways, it would be a nice addition by itself, so i will try to work on it in the following weeks.

In the meantime, and since there are several other reviewers in the coding style part, i will just focus on checking the mathematical correctness of the methods.

Just to mention knot altas has other kind of representation of PD Code, they start on the under crossing and move in the anti clockwise direction around the cross while we move in the clockwise direction in the construction of the PD code.

comment:25 Changed 5 years ago by git

  • Commit changed from 4fb0409d0f89d75b01a9b4f7ef330b05ca80bae4 to 3dac5c06f4592c081fe52f5126b28dd612b2df97

Branch pushed to git repo; I updated commit sha1. New commits:

3dac5c0Changes.

comment:27 Changed 5 years ago by mmarco

  • Branch changed from u/amitjamadagni/knots to u/mmarco/ticket/17030
  • Created changed from 09/23/14 14:33:27 to 09/23/14 14:33:27
  • Modified changed from 09/25/14 20:58:11 to 09/25/14 20:58:11

comment:28 Changed 5 years ago by mmarco

  • Commit changed from 3dac5c06f4592c081fe52f5126b28dd612b2df97 to 29be8b00dd778425bd16cb3064dba381b8015672

I have done some changes cleaning up the conversion to braid.

I have also run a script to check the results of .alexander_polynomial against the ones available in the knot atlas (taking into account the notation differences that Amit noted), and so far they match. Although my script is only checking 838 cases. There are some oddities, for example, in some knots, the knot atlas states that the Alexander polynomial is "ComplexInfinity?", although our implementation returns an actual polynomial.

In other cases, the knot atlas shows no PD code, so i am not checking those.


New commits:

b58f492Cleanup of the braid conversion.
071683aMerge branch 'u/amitjamadagni/knots' of git://trac.sagemath.org/sage into ticket/17030
29be8b0Merge conflict resolution

comment:29 Changed 5 years ago by mmarco

I have also checked the jones polynomial (in this case in 1064 cases). Almost all match, with the following exceptions:

<knot:L11n307>
-q^10 + 3*q^9 - 6*q^8 + 8*q^7 - 9*q^6 + 11*q^5 - 8*q^4 + 8*q^3 - 4*q^2 + 2*q
-q^10 + 3*q^9 - 6*q^8 + 8*q^7 - 9*q^6 + 11*q^5 - 8*q^4 + 8*q^3 - 4*q^2 + 2

<knot:K11n162>
-q^10 + 3*q^9 - 5*q^8 + 7*q^7 - 9*q^6 + 9*q^5 - 8*q^4 + 7*q^3 - 4*q^2 + 2*q
-q^10 + 3*q^9 - 5*q^8 + 7*q^7 - 9*q^6 + 9*q^5 - 8*q^4 + 7*q^3 - 4*q^2 + 2


<knot:L11n271>
-q^10 + 2*q^9 - 5*q^8 + 7*q^7 - 9*q^6 + 11*q^5 - 8*q^4 + 9*q^3 - 5*q^2 + 3*q
-q^10 + 2*q^9 - 5*q^8 + 7*q^7 - 9*q^6 + 11*q^5 - 8*q^4 + 9*q^3 - 5*q^2 + 3


<knot:L10n112>
q^9 - q^8 + 6*q^7 - 5*q^6 + 11*q^5 - 5*q^4 + 10*q^3 - 5*q^2 + 4*q
q^9 - q^8 + 6*q^7 - 5*q^6 + 11*q^5 - 5*q^4 + 10*q^3 - 5*q^2 + 4


<knot:K11n63>
-q^10 + 2*q^9 - 3*q^8 + 5*q^7 - 6*q^6 + 6*q^5 - 6*q^4 + 5*q^3 - 3*q^2 + 2*q
-q^10 + 2*q^9 - 3*q^8 + 5*q^7 - 6*q^6 + 6*q^5 - 6*q^4 + 5*q^3 - 3*q^2 + 2


<knot:10_165>
q^9 - 3*q^8 + 4*q^7 - 6*q^6 + 7*q^5 - 6*q^4 + 6*q^3 - 4*q^2 + 2*q
q^9 - 3*q^8 + 4*q^7 - 6*q^6 + 7*q^5 - 6*q^4 + 6*q^3 - 4*q^2 + 2


<knot:L11n316>
q^9 - 3*q^8 + 5*q^7 - 6*q^6 + 8*q^5 - 7*q^4 + 7*q^3 - 4*q^2 + 3*q
q^9 - 3*q^8 + 5*q^7 - 6*q^6 + 8*q^5 - 7*q^4 + 7*q^3 - 4*q^2 + 3


<knot:L9n20>
-q^8 + 2*q^7 - 4*q^6 + 5*q^5 - 4*q^4 + 6*q^3 - 3*q^2 + 3*q
-q^8 + 2*q^7 - 4*q^6 + 5*q^5 - 4*q^4 + 6*q^3 - 3*q^2 + 3

In each case, the first polynomial is the one given by our implementation, and the second the one given by the knot atlas.

Can someone confirm if the knot atlas results are correct?

comment:30 in reply to: ↑ 18 Changed 5 years ago by amitjamadagni

Replying to mmarco:

There is something working wrong in the following case:

sage: L=Link([[1, 4, 2, 5], [7, 10, 8, 11], [3, 9, 4, 8], [9, 3, 10, 2], [5, 12, 6, 1], [11, 6, 12, 7]])
sage: L
<repr(<sage.knots.link.Link at 0x7f41771c8a28>) failed: Exception: Invalid Input>

It gets an error when trying to get the connected components, which in turn tries to convert it to braid (which is probably not a good idea, it would be wiser to compute the components directly from the PD_code, since we might me loosing something in the conversion PD<->braid).

In any case, this example fails in the conversion to braid:

sage: L.braid()
...
Exception: Invalid Input

Please go through it and debug. }}}

I have worked along on the debug and here are the results :

sage: L = Link([[1,5,2,4],[7,11,8,10],[3,8,4,9],[9,2,10,3],[5,1,6,12],[11,7,12,6]])  
sage: L.braid()
s0*s1^-1*s2*s1^-1*s0^-1*s1^-1*s2^-1*s3^-1*s2*s1^-1*s0*s2*s1^-1

Last edited 5 years ago by amitjamadagni (previous) (diff)

comment:31 Changed 5 years ago by amitjamadagni

  • Branch changed from u/mmarco/ticket/17030 to u/amitjamadagni/ticket/17030

comment:32 Changed 5 years ago by mmarco

  • Commit changed from 29be8b00dd778425bd16cb3064dba381b8015672 to c020d916536244a736c6a2feb6665f49f31e0c6a

Please take a look at my previous commit, i have rewriten part of the braid conversion.


New commits:

c020d91Edits in Vogel Move. Correction in the previous after the RM has been made.

comment:33 follow-up: Changed 5 years ago by mmarco

My bad, the discrepancies with the knot atlas where due to my script not parsing correctly the file given by the knot atlas. So we can say that so far our implementation coincides with the knot atlas.

comment:34 in reply to: ↑ 33 Changed 5 years ago by amitjamadagni

Replying to mmarco:

My bad, the discrepancies with the knot atlas where due to my script not parsing correctly the file given by the knot atlas. So we can say that so far our implementation coincides with the knot atlas.

That's good to hear. :) Sorry for the previous commit, but I have found out the bug in my code. I will go through the rewritten parts. Could you please let me know the way you are testing things so that I can do it as well. Thanks.

comment:35 follow-up: Changed 5 years ago by vdelecroix

Hello,

The logic of every if/else is completely crazy. Rewriting the __init__ properly takes only half of the preceding implementation: see my commit at u/vdelecroix/17030. The code needs a lot of polishing. I did not dig in the details but it is clearly hard to read!

Vincent

comment:36 in reply to: ↑ 35 ; follow-up: Changed 5 years ago by amitjamadagni

Replying to vdelecroix:

Hello,

The logic of every if/else is completely crazy. Rewriting the __init__ properly takes only half of the preceding implementation: see my commit at u/vdelecroix/17030. The code needs a lot of polishing. I did not dig in the details but it is clearly hard to read!

Vincent

I have browsed through the commit, data can also be a PD code when its length is 2 it is not always oriented gauss code.

comment:37 in reply to: ↑ 36 ; follow-up: Changed 5 years ago by vdelecroix

Replying to amitjamadagni:

Replying to vdelecroix:

Hello,

The logic of every if/else is completely crazy. Rewriting the __init__ properly takes only half of the preceding implementation: see my commit at u/vdelecroix/17030. The code needs a lot of polishing. I did not dig in the details but it is clearly hard to read!

Vincent

I have browsed through the commit, data can also be a PD code when its length is 2 it is not always oriented gauss code.

Yes and this is fine. From my commit:

+            if len(data) != 2 or not all(isinstance(i,list) for i in data[0]):
+                # here we expect a PD code

Which mean that you expect a PD code if either len(data) != 2 or if any element of data[0] is not a list.

Vincent

comment:38 in reply to: ↑ 37 Changed 5 years ago by amitjamadagni

Replying to vdelecroix:

Replying to amitjamadagni:

Replying to vdelecroix:

Hello,

The logic of every if/else is completely crazy. Rewriting the __init__ properly takes only half of the preceding implementation: see my commit at u/vdelecroix/17030. The code needs a lot of polishing. I did not dig in the details but it is clearly hard to read!

Vincent

I have browsed through the commit, data can also be a PD code when its length is 2 it is not always oriented gauss code.

Yes and this is fine. From my commit:

+            if len(data) != 2 or not all(isinstance(i,list) for i in data[0]):
+                # here we expect a PD code

Which mean that you expect a PD code if either len(data) != 2 or if any element of data[0] is not a list.

Vincent

Yeah ! I get it.

comment:39 Changed 5 years ago by mmarco

Actually, i think that tuples should be allowed too. What do you think about storing the attributes as tuples ? (so they would be immutable)

comment:40 Changed 5 years ago by git

  • Commit changed from c020d916536244a736c6a2feb6665f49f31e0c6a to 013330510468c160af37fb3048c2e5a8cc1aa0eb

Branch pushed to git repo; I updated commit sha1. New commits:

0133305Edits in the __init__ method.

comment:41 Changed 5 years ago by jhpalmieri

You should add this to the reference manual using changes like these:

  • src/doc/en/reference/index.rst

    diff --git a/src/doc/en/reference/index.rst b/src/doc/en/reference/index.rst
    index 662a079..c5e2211 100644
    a b Geometry and Topology 
    6969* :doc:`Cell Complexes and their Homology <homology/index>`
    7070* :doc:`Differential Forms <tensor/index>`
    7171* :doc:`Parametrized Surfaces <riemannian_geometry/index>`
     72* :doc:`Knot Theory <knots/index>`
    7273
    7374Number Theory, Algebraic Geometry
    7475---------------------------------
  • new file src/doc/en/reference/knots/conf.py

    diff --git a/src/doc/en/reference/knots/conf.py b/src/doc/en/reference/knots/conf.py
    new file mode 120000
    index 0000000..2bdf7e6
    - +  
     1../conf_sub.py
     2 No newline at end of file
  • new file src/doc/en/reference/knots/index.rst

    diff --git a/src/doc/en/reference/knots/index.rst b/src/doc/en/reference/knots/index.rst
    new file mode 100644
    index 0000000..229ccac
    - +  
     1Knot theory
     2===========
     3
     4.. toctree::
     5   :maxdepth: 2
     6
     7   sage/knots/link
     8
     9.. include:: ../footer.txt

(It may not be clear from this, but src/doc/en/reference/knots/conf.py is a symlink pointing to src/doc/en/reference/conf_sub.py.) Once you do this, you will find that the documentation is a mess: indentations are wrong, etc. For example, here are some changes I found by looking at the first few methods:

  • src/sage/knots/link.py

    diff --git a/src/sage/knots/link.py b/src/sage/knots/link.py
    index 6259df0..3ed2dd6 100644
    a b class Link: 
    4444      2. Oriented Gauss Code
    4545      3. Planar Diagram Code
    4646
    47       EXAMPLES::
    48 
    49           sage: B = BraidGroup(8)
    50           sage: L = Link(B([1, 2, 1, -2,-1]))
    51           sage: L
    52           Link with 2 components represented by 5 crossings
    53           sage: L = Link([[[-1, +2, -3, 4, +5, +1, -2, +6, +7, 3, -4, -7, -6,-5]],[-1, -1, -1, -1, 1, -1, 1]])
    54           sage: L
    55           Knot represented by 7 crossings
    56           sage: L = Link([[1,8,2,7],[8,4,9,5],[3,9,4,10],[10,1,7,6],[5,3,6,2]])
    57           sage: L
    58           Link with 2 components represented by 5 crossings
     47    EXAMPLES::
     48
     49        sage: B = BraidGroup(8)
     50        sage: L = Link(B([1, 2, 1, -2,-1]))
     51        sage: L
     52        Link with 2 components represented by 5 crossings
     53        sage: L = Link([[[-1, +2, -3, 4, +5, +1, -2, +6, +7, 3, -4, -7, -6,-5]],[-1, -1, -1, -1, 1, -1, 1]])
     54        sage: L
     55        Knot represented by 7 crossings
     56        sage: L = Link([[1,8,2,7],[8,4,9,5],[3,9,4,10],[10,1,7,6],[5,3,6,2]])
     57        sage: L
     58        Link with 2 components represented by 5 crossings
    5959    """
    6060
    6161    def __init__(self, data):
    class Link: 
    7070
    7171        Generators of the braid group are used to generate the link.
    7272
     73        EXAMPLES::
     74
    7375            sage: B = BraidGroup(8)
    7476            sage: L = Link(B([-1, -1, -1, -2,1, -2,3,-2,3]))
    7577            sage: L
    class Link: 
    9294        anti-clockwise, -1 if the direction from the leaving over-cross to the
    9395        leaving under-cross is clockwise.
    9496
     97        EXAMPLES::
     98
    9599            # for knots there is only a single component so the input is as follows
    96100            sage: L = Link([[[-1, +2, 3, -4, 5, -6, 7, 8, -2, -5, +6, +1, -8, -3, 4, -7]],[-1,-1,-
    97101            sage: L
    class Link: 
    240244        r"""
    241245        Return the oriented gauss code of the link. The oriented gauss
    242246        code has two parts
     247
    243248        a. The gauss code
    244249        b. The orientation of each crossing
     250
    245251        The following orientation was taken into consideration for consturction
    246252        of knots:

(And now I just saw that "construction" is misspelled in the last sentence.)

Doctest coverage is not yet 100%:

$ sage --coverage src/sage/knots/link.py
------------------------------------------------------------------------
SCORE src/sage/knots/link.py: 85.3% (29 of 34)

Missing documentation:
     * line 1686: def _rule_1_(over)
     * line 1701: def _rule_2_(over)
     * line 1714: def _pd_error_(pd)
     * line 1728: def _bracket_(pd_code)
     * line 1768: def _rule_4_(rest, c_1, c_2)
------------------------------------------------------------------------

comment:42 Changed 5 years ago by git

  • Commit changed from 013330510468c160af37fb3048c2e5a8cc1aa0eb to c3bedaa8d0ac5a819612acb881b2fe86aa1c46ea

Branch pushed to git repo; I updated commit sha1. New commits:

c3bedaaFlatten used. WIP: docs and other methods.

comment:43 Changed 5 years ago by git

  • Commit changed from c3bedaa8d0ac5a819612acb881b2fe86aa1c46ea to 1613a3282029a8234bad39707afe2b4a71d1d5c5

Branch pushed to git repo; I updated commit sha1. New commits:

1613a32Changes.

comment:44 Changed 5 years ago by mmarco

Documentation does not build:

...
[knots    ] loading cross citations...
[knots    ] /home/mmarco/sage/local/lib/python2.7/site-packages/sage/knots/link.py:docstring of sage.knots.link:2: ERROR: Unexpected indentation.
[knots    ] /home/mmarco/sage/local/lib/python2.7/site-packages/sage/knots/link.py:docstring of sage.knots.link:4: WARNING: Block quote ends without a blank line; unexpected unindent.
[knots    ] <autodoc>:0: ERROR: Unexpected indentation.
[interface] reading sources... [ 25%] sage/interfaces/gap
[categorie] reading sources... [ 92%] sage/categories/semirings
Error building the documentation.
Traceback (most recent call last):
  File "/home/mmarco/sage/src/doc/common/builder.py", line 1491, in <module>
    getattr(get_builder(name), type)()
  File "/home/mmarco/sage/src/doc/common/builder.py", line 292, in _wrapper
    getattr(get_builder(document), 'inventory')(*args, **kwds)
  File "/home/mmarco/sage/src/doc/common/builder.py", line 503, in _wrapper
    x.get(99999)
  File "/home/mmarco/sage/local/lib/python/multiprocessing/pool.py", line 558, in get
    raise self._value
OSError: [knots    ] /home/mmarco/sage/local/lib/python2.7/site-packages/sage/knots/link.py:docstring of sage.knots.link:2: ERROR: Unexpected indentation.

Makefile:60: recipe for target 'doc-html' failed
make: *** [doc-html] Error 1

comment:45 Changed 5 years ago by mmarco

The conversion to braid gives wrong answer, which causes several other errors:

sage: L=Link([[1, 5, 2, 4], [7, 11, 8, 10], [3, 8, 4, 9], [9, 2, 10, 3], [5, 1, 6, 12], [11, 7, 12, 6]])
sage: L.braid()
s0*s1^-1*s2*s1^-1*s0^-1*s1^-1*s2^-1*s3^-1*s2*s1^-1*s0*s2*s1^-1
sage: L
Link with 2 components represented by 6 crossings

comment:46 Changed 5 years ago by git

  • Commit changed from 1613a3282029a8234bad39707afe2b4a71d1d5c5 to 61bec349e5c6da529bcd1de0ac46f2b3de38d1d5

Branch pushed to git repo; I updated commit sha1. New commits:

61bec34Corrections.

comment:47 Changed 5 years ago by amitjamadagni

I guess its fixed.Here are the results

sage: L=Link([[1, 5, 2, 4], [7, 11, 8, 10], [3, 8, 4, 9], [9, 2, 10, 3], [5, 1, 6, 12], [11, 7, 12, 6]])
sage: L
Knot represented by 6 crossings
sage: L.braid()
s0*s1^-1*s2*s1^-1*s0^-1*s1^-1*s2^-1*s3^-1*s2*s1^-1*s2*s3  
sage: L.braidword()
(1, -2, 3, -2, -1, -2, -3, -4, 3, -2, 3, 4)

New commits:

61bec34Corrections.

comment:48 Changed 5 years ago by mmarco

Still broken:

sage: L=Link([[1, 9, 2, 8], [7, 15, 8, 14], [5, 17, 6, 16], [9, 1, 10, 18], [15, 7, 16, 6], [17, 11, 18, 10], [13, 3, 14, 2], [3, 13, 4, 12], [11, 5, 12, 4]])
sage: L.bra
L.braid      L.braidword  
sage: L.braidword()

(does not finish the computation).

comment:49 Changed 5 years ago by amitjamadagni

I am getting into an infinite loop with the _info_all_moves_ method.With this approach there seems that the regions with same sign never are in the same seifert circles there by the above method keeps on giving out the edited pd_code. Could you please let me know the knot reference ??

comment:50 Changed 5 years ago by git

  • Commit changed from 61bec349e5c6da529bcd1de0ac46f2b3de38d1d5 to a5cb90cefc254c3ad055b6050717ff204f83b717

Branch pushed to git repo; I updated commit sha1. New commits:

a5cb90cDocumentation. WIP : Other methods.

comment:51 Changed 5 years ago by amitjamadagni

The above commit aims to fix the documentation. The documentation builds both pdf and html.

comment:52 Changed 5 years ago by tscrim

I think the bulk of the documentation should be at the class level, rather than the module level. That way when a user does Link?, the user sees all of that documentation. Also this way the doc is better associated with what it's documenting.

Side note, making things raw strings, the r""", is usually safer, in particular when you have latex commands.

comment:53 Changed 5 years ago by git

  • Commit changed from a5cb90cefc254c3ad055b6050717ff204f83b717 to e2f61ed659f7e35053ec4198720fb290df651c41

Branch pushed to git repo; I updated commit sha1. New commits:

e2f61edCheck in the documentation.

comment:54 Changed 5 years ago by git

  • Commit changed from e2f61ed659f7e35053ec4198720fb290df651c41 to 2b36cda5875a5e0a1d49b1c60d1c4976c15b5a84

Branch pushed to git repo; I updated commit sha1. New commits:

2b36cdaIdea of plot method added. Some failing cases. WIP : ncomponents

comment:55 Changed 5 years ago by amitjamadagni

The idea of plot by Miguel has been added. I am trying on the refinement as it raises an error for the cases like :

sage: B = BraidGroup(8)
sage: L = Link(B([-1,3,1,5,1,7,1,6]))
sage: L.linkplot()
 
MIPSolverException: 'GLPK : Solution is undefined' 

The errors like this and the work on documentation for the plot remain.

comment:56 follow-up: Changed 5 years ago by mmarco

I would dsy thast this fasils because the diagram has more than one connected component. It could be useful to have a method to list the different "completely unlinked" components, as they should be treated separatedly in several places.

comment:57 in reply to: ↑ 56 Changed 5 years ago by amitjamadagni

Replying to mmarco:

I would dsy thast this fasils because the diagram has more than one connected component. It could be useful to have a method to list the different "completely unlinked" components, as they should be treated separatedly in several places.

Okay then I guess a combination of braidwordcomponents which gives

sage: L._braidwordcomponents_()
[[-1, 1, 1, 1], [3], [5, 7, 6]]

ncomponents could be used. I will try to set this up.

Last edited 5 years ago by amitjamadagni (previous) (diff)

comment:58 Changed 5 years ago by mmarco

No, it is not the same as ncomponents. ncomponents counts how many different pieces of rope are in the link. What i am talking about is about pieces of the diagram that don't cross at all.

That is, the braid [1,1] has two connected components (that is, two pieces of rope), but they have crossings between them, so they are in the same part of the diagram.

Whereas the braid [1,3] has also two connected components (two pieces of rope), but there is no crossing at all between them. The planar diagram is just two separated planar diagrams.

This situation of "completely independent" pieces needs to be treated separatedly in several methods. For instance, try to check how many methods fail for things like Link(1,1,2,2],[3,3,4,4?)

comment:59 Changed 5 years ago by amitjamadagni

So are we looking at something like the _braidwordcomponents_() which acts like :

sage: L._braidwordcomponents_()
[[-1, 1, 1, 1], [3], [5, 7, 6]]

comment:60 Changed 5 years ago by mmarco

Yes, that is the idea.

But be careful: thinkig only in terms of braids might lead to errors that appear when we deal with other representations.

comment:61 Changed 5 years ago by mmarco

  • Branch changed from u/amitjamadagni/ticket/17030 to u/mmarco/ticket/17030
  • Modified changed from 11/04/14 18:33:54 to 11/04/14 18:33:54

comment:62 Changed 5 years ago by mmarco

  • Commit changed from 2b36cda5875a5e0a1d49b1c60d1c4976c15b5a84 to 37bd26ba2e6ccd45e886fd7fdcbcdfa4d0ba0d03
  • Reviewers Miguel Marco deleted
  • Status changed from needs_work to needs_review
  • Type changed from task to enhancement

Since Amit did not answer lately, i decided to step up and do some cleanup and polishing of the code. Maybe documentation can be improved, but i think besides that it is pretty much ready for review.

Bad news is that, since i am now an author, somebody else should do the reviewing instead of me.


New commits:

7f382baCleanup of code
17a982eSome further polishing.
b58f492Cleanup of the braid conversion.
071683aMerge branch 'u/amitjamadagni/knots' of git://trac.sagemath.org/sage into ticket/17030
29be8b0Merge conflict resolution
37bd26bMerge old branch.

comment:63 Changed 5 years ago by kcrisman

Bad news is that, since i am now an author, somebody else should do the reviewing instead of me.

Not all bad news, because you can specify exactly which files/commits/contributions remain "yet to be reviewed". You can also suggest ways for people (even non-knot theorists) to test things out, and which things need some outside eyes.

comment:64 Changed 5 years ago by kcrisman

By the way, once this has positive review, it might be worth making a new branch that just adds in all these new files at one fell swoop. Or that might be a bad idea, depending on how you want the history to go in Sage. Just pointing it out.

comment:65 Changed 5 years ago by amitjamadagni

In the case of testing, the polynomial invariants have been compared with Knot Atlas as mentioned by Miguel. The other major part that need to be tested are the conversions, I guess it is easy for anyone to have a go at this by reading the documentation.

comment:66 Changed 5 years ago by kcrisman

Alternately, if there is a good "core" of functionality you (mmarco) as reviewer approve of that is a coherent whole, then other stuff could be moved to a new ticket. Especially if the stuff that still needs review is more peripheral, such as plotting...

comment:67 follow-up: Changed 5 years ago by mmarco

Inthe case of git history, i like it to reflect the process that actually took place, in case that someone in the future wants to do some archeology.

But it is just a matter of personal taste. I understand why other people prefear to avoid haveing too many commits in the history.

My last changes touch most of the relevant methods, so it would be difficult to stablish a clear separation from my work and Amit's.

Here some ideas of things that non specialists in knot theory can do towards reviewing:

  • Check the documentation. In fact, it is better if they are not specialist: the documentation should be clear for everybody. So if there is something that someone does not understand, please point it out.
  • Test some results that are known in other sources. For instance go to the knot atlas, pick any knot or link there, create it in Sage, compute the different invariants and compare. (Note, here we follow a different convention than in the knot atlas for the PD code, Xa,b,c,d in the knot atlas corresponds here to [a,d,b,c]).
  • Check out also the plotting of knots (no deep knowledge of knot theory is needed, although it is a complicated method, so it is hard to review... but it is really cool ;) ).

Regarding the idea of separting it into smaller tickets, we could do that, but besides the plotting, all the methods that can be separated into other tickets (i.e. the computation of the different invariants), are pretty trivial, since they are almost direct aplications of the conversion to braid).

comment:68 Changed 5 years ago by mmarco

I forgot to mention: the conversion to braid is one of the methods that i have rewriten. And it is really essential (i.e. it makes little sense to have a link class without it).

comment:69 Changed 5 years ago by amitjamadagni

I observe there is some problem with the regions method, I end up getting a build error.

comment:70 Changed 5 years ago by mmarco

Oops, i see there was some problem while merging different branches.

The actual branch is a mess. Let me try to solve it tonight.

comment:71 Changed 5 years ago by mmarco

How can i force the branch to go back to commit ​17a982e? If i try to push it i get the message:

Not pushing your changes because they would discard some of the commits on the remote branch

comment:72 Changed 5 years ago by kcrisman

There is a lot of discussion out there about this. Git has the philosophy that once something is pushed to a public repo, it really shouldn't be changed. See this SO question and this answer for some points of view, though an internet search will yield a LOT more opinions on this, such as this one which seems more nuanced.

Basic is that you can "force" a push (and this happens on occasion on Sage Trac) or "revert" some commits.

Last edited 5 years ago by kcrisman (previous) (diff)

comment:73 Changed 5 years ago by vdelecroix

I would be happy to participate in the review. But first, you have to read my two cents about git history. I think that the git history must be helpful to newcomers and not for archaeologists (for them, we have trac and sage-devel. Moreover, they do not necessarily want to know that in the first n commits you were just trying to understand how to use git).

More precisely:

  • keep the history simple
  • always have the following sentence in mind: "what is the most helpful for the reviewer?"

More concretely

  • merge as less as possible
  • if you modify a lot on an already existing file, try to have one commit that deletes and an other one that adds
  • if you are only providing new functionalities in independent file, try to minimize the number of commits (or at least make them coherent for the reader)

Git history could be really helpful to reviewer. For example, if you simply move a file, the commit will only be "mv old_file -> new_file". Hence, as a reviewer, I know that there is nothing to check in that file.

Vincent

comment:74 Changed 5 years ago by git

  • Commit changed from 37bd26ba2e6ccd45e886fd7fdcbcdfa4d0ba0d03 to 17a982e3e8b5ad28ba82ced6b4effe8962fe459b

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

comment:75 Changed 5 years ago by mmarco

Ok, i forced a push that should simplify the history, and return to a sane state.

comment:76 Changed 5 years ago by tscrim

I'd have just merged the remote branch (from the message, it seems like your local branch was behind the one on trac). I'll try to take a look at this soon too.

Vincent and I disagree on the following git stuff. The general git philosophy, as far as I have seen, is to favor more commits into small logical chunks and to keep history that you can go back and see (or retrieve) code formats that you've tried before. The important thing is to have commit messages which describe what is done in the commit.

comment:77 in reply to: ↑ 67 Changed 5 years ago by kcrisman

My last changes touch most of the relevant methods, so it would be difficult to stablish a clear separation from my work and Amit's.

Well, not exactly; in fact, you only did the last two commits, so in principle someone else could review just those commits (and the very last commit seems very straightforward). What I was hoping to elicit from you is the answer to the following question:

In your opinion, is everything not touched by your commits okay (even if fairly trivial), and do you feel there is any additional work needed beyond reviewing the pieces (many, granted) you did work on?

comment:78 Changed 5 years ago by kcrisman

  • Reviewers set to Miguel Marco

comment:79 Changed 5 years ago by kcrisman

  • Reviewers changed from Miguel Marco to Miguel Marco, Karl-Dieter Crisman

Some minor things, just on a first glance:

  • Various minor English misspellings.
  • There should probably be an "intro" module-level section telling people what links and knots are (in particular, the difference, since lots of people have heard of knots but not so many of links). See e.g. the cooperative game theory doc though this is quite comprehensive.
  • Sometimes there are sort-of-bullet lists that aren't formatted that way, such as for how to create a link.
  • The plot example doesn't show how to make a plot.

comment:80 Changed 5 years ago by mmarco

Thank you for the review. You are totally right. I will work on that.

comment:81 Changed 5 years ago by kcrisman

Another random question. So say I look at a random knot page at the atlas, say K11a142. We only seem to have a few of the invariants (which is fine) but what about the non-polynomial invariants? Also, I think we have braid diagrams (?) so maybe we should have some of those in the examples.

comment:82 Changed 5 years ago by mmarco

Sorry, i don't really understand your question. Can you be more explicit about what you propose?

comment:83 Changed 5 years ago by kcrisman

What I mean is, are any of the non-polynomial invariants like "3-genus" available yet? Just asking.

Secondly, I think that we have a way to plot braids, and this is in the atlas, so we should probably at least mention this in the documentation along with an example or two.

Sorry for any confusion.

comment:84 Changed 5 years ago by amitjamadagni

Yeah we have genus, signature, determinant, arf invariant (only for knots) which can be seen as invariants as they distinguish between different links. Coming to the plotting of braids, the closure of braids gives a link but the plotting of braids would be not sufficient here as we have to close the braids to get the corresponding link, so we did not consider it as an option.

Last edited 5 years ago by amitjamadagni (previous) (diff)

comment:85 Changed 5 years ago by kcrisman

I wasn't suggesting plotting the braids as something in knots, just that the knot atlas picks some random braid rep of the link and shows a plot, so since that is such a standard reference we could include that in (perhaps the module-level) documentation.

comment:86 Changed 5 years ago by git

  • Commit changed from 17a982e3e8b5ad28ba82ced6b4effe8962fe459b to 884d1416e0486c114e16b8606c525b51972c9281

Branch pushed to git repo; I updated commit sha1. New commits:

884d141Added module documentation, corrected some minor issues with documentation

comment:87 Changed 5 years ago by mmarco

I have writen a module documentation (i think it still needs work), and solved some misspellings and the plot documentation.

We don't have implemented the 3-genus, as many other invariants.

comment:88 Changed 5 years ago by kcrisman

Thanks for this commit.

I have writen a module documentation (i think it still needs work)

Perhaps, but at least now it is sufficient for people coming in with a reasonable mathematical background. Often things are implemented in Sage for research first, then stuff making it more useful for pedagogy comes later.

Hopefully someone might be able to look at the remaining code, of course! I won't have time for this in the immediate future.

comment:89 Changed 4 years ago by mmarco

There is a bug with the .regions method that shows up when there are edges with both ends in the same crossing:

sage: L=Link([[1,2,2,1]])
sage: L.regions()
[]
sage: L=Link([[1,1,2,2]])
sage: L.regions()
[[-2], [1], [2, -1]]

I don't have much time right now, but can try to solve it when i find some time. In the meantime, can Amit or someone else take a look?

comment:90 Changed 4 years ago by amitjamadagni

The problem with the first case is with the orientation of the knot. It seems the orientation of the knot is coming out as -1 which should be +1

sage: L = Link([[1, 2, 2, 1]])  
sage: L.orientation()
[-1]

I will try looking into the construction of orientation.

As for the second input, single negative entry does not make sense and I have added a bit of code (not optimal yet works). Here are the results :

sage: L = Link([[1, 1, 2, 2]])
sage: L.orientation()
[-1]
sage: L.regions()
[[1], [2, -1]]

I will try working on the orientation to see where it is going wrong.

comment:91 Changed 4 years ago by amitjamadagni

  • Branch changed from u/mmarco/ticket/17030 to u/amitjamadagni/ticket/17030

comment:92 Changed 4 years ago by mmarco

  • Commit changed from 884d1416e0486c114e16b8606c525b51972c9281 to 7c09ce6f279cabfbd4073b1abbb63052d13127f4

Wait, this part:

sage: L=Link([[1,1,2,2]])
sage: L.regions()
[[-2], [1], [2, -1]]

was correct. There is one region whose boundary is just the edge 2 in the negative direction.


New commits:

7c09ce6Change in method regions

comment:93 Changed 4 years ago by amitjamadagni

As far as I remember we had to select an edge and turn left until we arrived at the edge where we started. I guess we do not consider the edges reversed which are the negative ones, in this case -2, so I thought we should not include -2. Please do correct me if I am missing something.

comment:94 Changed 4 years ago by mmarco

The regions with only one edge are regions like the others, and we have to describe them using the same convention as the others.

If you draw that knot diagram, you will see three regions: two "inside" (the [1] and the [-2]) and the exterior one (the [2, -1]).

comment:95 Changed 4 years ago by mmarco

Somebody else is getting an error message when building the documentation? I am unable to point the problem.

comment:96 Changed 4 years ago by jhpalmieri

The documentation builds for me if I make this change:

  • src/sage/knots/link.py

    diff --git a/src/sage/knots/link.py b/src/sage/knots/link.py
    index c15484f..72c9ce4 100644
    a b class Link: 
    13521352        OUTPUT:
    13531353
    13541354        - Jones Polynomial of the link. It is a polynomial in var, as an element
    1355         of the symbolic ring.
     1355          of the symbolic ring.
    13561356
    13571357        EXAMPLES::

comment:97 Changed 4 years ago by mmarco

  • Branch changed from u/amitjamadagni/ticket/17030 to u/mmarco/ticket/17030
  • Modified changed from 03/11/15 17:27:46 to 03/11/15 17:27:46

comment:98 Changed 4 years ago by mmarco

  • Commit changed from 7c09ce6f279cabfbd4073b1abbb63052d13127f4 to b45bf7c113249f5ad8bd52a28ec99cc76890677a

I have corrected the regions method, with some ad-hoc code for degenerated cases with two loops in the same crossing.

The plot method needs some work to handle too these kind of loops properly.


New commits:

5f137c6Handled issue with regions method. Minor documentation fix.
88a80d6Merge branch 'u/amitjamadagni/ticket/17030' of git://trac.sagemath.org/sage into ticket/17030
b45bf7cMerge conflict resolution

comment:99 Changed 4 years ago by kcrisman

See also http://www.math.uic.edu/t3m/SnapPy/spherogram.html#the-link-class for how SnapPy deals with knots when inside of Sage.

comment:100 Changed 4 years ago by chapoton

  • Status changed from needs_review to needs_work

One doctest failing

File "src/sage/knots/link.py", line 1475, in sage.knots.link.Link.plot
Failed example:
    L.plot()
Expected nothing
Got:
    Graphics object consisting of 28 graphics primitives

comment:101 Changed 4 years ago by chapoton

and also not yet at 100% coverage

Missing doctests  knots/link.py 27 / 29 = 93%

comment:102 Changed 4 years ago by git

  • Commit changed from b45bf7c113249f5ad8bd52a28ec99cc76890677a to 5828c77131e39cd941a349edffbccfc546c4281a

Branch pushed to git repo; I updated commit sha1. New commits:

5828c77Correct and add doctests.

comment:103 Changed 4 years ago by mmarco

Fixed the minor issues woth doctests.

I am also woriking on a method to compute the homfly polynomial, but it deppends on #18047 and #18057. Since this ticket is already quite big, and taking a lot to be reviewed, i prefear to wait for it in another ticket (unless somebody is willing to review this whole ticket plus the new functionality).

comment:104 Changed 4 years ago by chapoton

  • Branch changed from u/mmarco/ticket/17030 to public/ticket/17030
  • Commit changed from 5828c77131e39cd941a349edffbccfc546c4281a to d4ede52a281e79a4b280bbb9bc9873978f0fa998

fixed the failing "plot" doctest


New commits:

0477a34Merge branch 'u/mmarco/ticket/17030' into 6.6.rc2
d4ede52trac #17030 fixing plot doctest

comment:105 Changed 4 years ago by kcrisman

  • Reviewers changed from Miguel Marco, Karl-Dieter Crisman to Miguel Marco, Karl-Dieter Crisman, Frédéric Chapoton

comment:106 Changed 4 years ago by chapoton

  • Milestone changed from sage-6.4 to sage-6.8

comment:107 Changed 4 years ago by chapoton

  • Milestone changed from sage-6.8 to sage-6.9

+Missing doctests knots/link.py 28 / 29 = 96%

comment:108 Changed 4 years ago by mmarco

Since this seems to be too big for a proper review, i am planning to split it in several smaller tickets. Does that sound like a good idea?

comment:109 Changed 4 years ago by chapoton

oh, well.. If it passes all tests, and has 100% doc, one could has well get it inside as a block.. Maybe ask on sage-devel (once 100% doctest has been reached !)

comment:110 Changed 4 years ago by tscrim

I don't think we necessarily need to split this into multiple tickets (in fact, that seems kind of hard). If someone can review the mathematics side of things, I'd be happy to do the code review.

comment:111 Changed 4 years ago by mmarco

Ok then, i will try to work in improving the doctest coverage.

comment:112 Changed 4 years ago by git

  • Commit changed from d4ede52a281e79a4b280bbb9bc9873978f0fa998 to cb84cec88f012844ac65d102296644a77f89818c

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

e2bea16Cleanup of code
dc5143aSome further polishing.
dda740cAdded module documentation, corrected some minor issues with documentation
782b3c1Change in method regions
bfc184dHandled issue with regions method. Minor documentation fix.
b21c42aCorrect and add doctests.
8c911c1trac #17030 fixing plot doctest
171b94bAdded missing doctest
19b41d1Solved bug in orientation
cb84cecMerge branch 'public/ticket/17030' of git://trac.sagemath.org/sage into ticket/17030

comment:113 Changed 4 years ago by mmarco

Ok, i added the misisng doctest. I also solved a bug in the orientation method, and while i were at it, i rebased the whole thing to the last development version.

If you feel able to review it, then please go for it. Otherwise i will try to tho de the splitting into smaller parts for easier review.

comment:114 Changed 4 years ago by kcrisman

I agree that in this particular case it could be useful to keep it in one piece. However, if mmarco is willing to do the work to split this into coherent separate tickets that could be easily reviewed by people other than the authors, that is certainly not a bad idea. For one thing, it might be possible for him to create a few tickets of material that he did not write and could just give positive review to. I'm sorry I haven't been able to help figure this out better although I think it should be very high priority, but I had a very busy year and couldn't learn enough knot theory algorithms to do this yet, nor to convince any knot theorist friends to take the time to learn Sage yet.

comment:115 Changed 4 years ago by jhpalmieri

One quick comment: the file reference/knots/conf.py should be a symlink to ../conf_sub.py, not a copy of that file.

comment:116 follow-up: Changed 4 years ago by tscrim

If Miguel thinks it is (now) mathematically solid, then I will do the final parts of the review over the next day or so.

Some things from a quick lookthrough:

  • Is the definition of the writhe valid for links? Right now the documentation just says "of the knot".
  • Methods like alexander_polynomial could use elaboration in their documentation, such as their definition and/or references.
  • I want to create a separate class Knot inheriting from Link to make it easier for people expanding on this in the future (and there is already a method specifically for knots). Any objections to me doing this?

(John just outposted me on the symlink :P ).

comment:117 follow-up: Changed 4 years ago by jhpalmieri

Hi Travis,

Please go ahead with a full review. I think a new Knot class would be good. For future work, it would also be nice to have a catalog of links and knots (e.g., knots.Trefoil()) and also ways of producing new links from old. Could you add a .. todo list?

I agree that more documentation would be great, with definitions, references, and (for plot at least) algorithms.

How is equality determined? How should it be? Should the oriented Gauss code be good enough?

sage: trefoil = Link([[1, 5, 2, 4], [5, 3, 6, 2], [3, 1, 4, 6]])
sage: trefoil == Link([[1, 5, 2, 4], [5, 3, 6, 2], [3, 1, 4, 6]])
False

I haven't actually looked at the code, and I don't know if I ever will. Some suggestions for miscellaneous minor cleanup:

  • src/sage/knots/link.py

    diff --git a/src/sage/knots/link.py b/src/sage/knots/link.py
    index 04facf8..89f9624 100644
    a b A link is an embedding of one or more copies of `\\mathbb{S}^1` in `\\mathbb{S}^ 
    1010considered up to ambient isotopy. That is, a link represents the idea of one or more
    1111tied ropes. Every knot is a link, but not every link is a knot.
    1212
    13 Generically, the projection of a link on `\\mathbb{R}^2`
     13Generically, the projection of a link to `\\Bold{R}^2`
    1414is a curve with crossings. The crossings are represented to show which strand goes
    1515over the other. This curve is called a planar diagram of the link. If we remove the
    1616crossings, the resulting connected components are segments. These segments are
    AUTHORS: 
    4040
    4141from sage.matrix.constructor import matrix
    4242from sage.rings.integer_ring import ZZ
    43 from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
    4443from sage.rings.finite_rings.integer_mod import Mod
    4544from sage.graphs.digraph import DiGraph
    4645from sage.graphs.graph import Graph
    4746from copy import deepcopy, copy
    4847from sage.rings.polynomial.laurent_polynomial_ring import LaurentPolynomialRing
    49 from sage.rings.integer_ring import IntegerRing
    50 from sage.combinat.permutation import Permutations
    51 from sage.rings.finite_rings.integer_mod_ring import IntegerModRing
    52 from sage.symbolic.ring import SR, var
     48from sage.symbolic.ring import SR
    5349from sage.rings.integer import Integer
    5450from sage.numerical.mip import MixedIntegerLinearProgram
    5551from sage.functions.generalized import sign
    class Link: 
    7470        sage: L
    7571        Link with 2 components represented by 5 crossings
    7672
    77     Note that the strands of the braid that have no crossings at all are ignored.
     73      Note that the strands of the braid that have no crossings at all are ignored.
    7874
    7975    - Oriented Gauss Code:
    8076
    class Link: 
    8278      crossings) and start moving along the link. Trace every component of
    8379      the link, by starting at a particular point on one component of the link and
    8480      writing down each of the crossings that you encounter until returning to the starting
    85       point. The crossings are written with sign depending on wheter we cross them
     81      point. The crossings are written with sign depending on whether we cross them
    8682      as over or undercrossing. Each component is then represented as a list whose
    8783      elements are the crossing numbers. A second list of +1 and -1's keeps track of
    8884      the orientation of each crossing::
    class Link: 
    9187        sage: L
    9288        Knot represented by 8 crossings
    9389
    94       For links there is more than one component and the input is as follows::
     90      For links there may be more than one component and the input is as follows::
    9591
    9692        sage: L = Link([[[-1, 2], [-3, 4], [1, 3, -4, -2]], [-1, -1, 1, 1]])
    9793        sage: L
    class Link: 
    177173                self._PD_code = None
    178174
    179175            else:
    180                 raise Exception("Invalid Input: Data must be either a list or a Braid")
     176                raise ValueError("Invalid Input: Data must be either a list or a Braid")
    181177
    182178    def __repr__(self):
    183179        """
    184180        Return a string representation.
    185181
    186         OUTPUT:
    187 
    188         - A string.
     182        OUTPUT: string representation
    189183
    190184        EXAMPLES::
    191185
    class Link: 
    211205        """
    212206        Return the braid representation of the link.
    213207
    214         OUTPUT:
    215 
    216         - Braid representation of the link.
     208        OUTPUT: braid representation of the link
    217209
    218210        EXAMPLES::
    219211
    class Link: 
    397389
    398390        b. The orientation of each crossing
    399391
    400         The following orientation was taken into consideration for consturction
     392        The following orientation was taken into consideration for construction
    401393        of knots:
    402394
    403395        From the outgoing of the overcrossing if we move in the clockwise direction
    class Link: 
    411403        The order of the orientation is same as the ordering of the crossings in the
    412404        gauss code.
    413405
    414         Convention : under is denoted by -1, and over by +1 in the crossing info.
     406        Convention: under is denoted by -1, and over by +1 in the crossing info.
    415407
    416         OUTPUT:
    417 
    418         - Oriented gauss code of the link
     408        OUTPUT: Oriented gauss code of the link
    419409
    420410        EXAMPLES::
    421411
    class Link: 
    469459
    470460    def PD_code(self):
    471461        """
    472         Return the Planar Diagram code of the link. The Planar Diagram is returned
     462        Return the planar diagram code of the link. The planar diagram is returned
    473463        in the following format.
    474464
    475465        We construct the crossing by starting with the entering component of the
    476466        undercrossing, move in the clockwise direction and then generate the list.
    477         Suppose if the crossing is given by [a, b, c, d], then we interpret this
    478         information as :
     467        If the crossing is given by [a, b, c, d], then we interpret this
     468        information as:
    479469
    480470        1. a is the entering component of the undercrossing
    481471        2. b, d are the components of the overcrossing
    482472        3. c is the leaving component of the undercrossing
    483473
    484         OUTPUT:
    485 
    486         - Planar Diagram representation of the link.
     474        OUTPUT: planar diagram representation of the link.
    487475
    488476        EXAMPLES::
    489477
    class Link: 
    564552
    565553    def gauss_code(self):
    566554        """
    567         Return the gauss_code of the link. Gauss code is generated by the
     555        Return the Gauss code of the link. Gauss code is generated by the
    568556        following procedure:
    569557
    570558        a. Number the crossings from 1 to n.
    571559        b. Select a point on the knot and start moving along the component.
    572560        c. At each crossing, take the number of the crossing, along with
    573            sign, which is '-' if it is a undercrossing and '+' if it is a
     561           sign, which is '-' if it is an undercrossing and '+' if it is an
    574562           overcrossing.
    575563
    576         OUTPUT:
    577 
    578         - Gauss code representation of the link.
     564        OUTPUT: Gauss code representation of the link
    579565
    580566        EXAMPLES::
    581567
    class Link: 
    594580
    595581    def dt_code(self):
    596582        """
    597         Return the dt_code of the knot. DT code is generated by the following way.
     583        Return the DT code of the knot. DT code is generated as follows.
    598584
    599585        Start moving along the knot, as we encounter the crossings we
    600586        start numbering them, so every crossing has two numbers assigned to
    class Link: 
    605591        Take the even number with a negative sign if it is an overcrossing
    606592        that we are encountering.
    607593
    608         OUTPUT:
    609 
    610         - DT Code representation of the knot. This is implemented only
    611           for knots.
     594        OUTPUT: DT Code representation of the knot. This is implemented only for knots.
    612595
    613596        EXAMPLES::
    614597
    class Link: 
    644627                        crossing = i
    645628                        break
    646629            if(label[2 * crossing + next_label % 2] == 1):
    647                 raise Exception("Implemented only for knots")
     630                raise ValueError("Implemented only for knots")
    648631            else:
    649632                label[2 * crossing + next_label % 2] = next_label
    650633                next_label = next_label + 1
    class Link: 
    674657    def _dowker_notation_(self):
    675658        """
    676659        Return the dowker notation of the link. Similar to the PD Code we number the
    677         components. So every crossing is represented by four numbers. We focus on
    678         the incoming entites of the under and the over crossing. It is the pair of incoming
    679         under cross and the incoming over cross. This information at every cross
     660        components, so every crossing is represented by four numbers. We focus on
     661        the incoming entities of the under and the overcrossing. It is the pair of incoming
     662        undercross and the incoming overcross. This information at every cross
    680663        gives the dowker notation.
    681664
    682         OUTPUT:
    683 
    684         - List containing the pair of incoming under cross and the incoming
    685           over cross.
     665        OUTPUT: List containing the pair of incoming undercross and the incoming overcross.
    686666
    687667        EXAMPLES::
    688668
    class Link: 
    705685
    706686    def _braidwordcomponents_(self):
    707687        """
    708         Return the disjoint braid components, if any, else returns the braid itself.
    709         For example consider the braid [-1, 3, 1, 3] this can be viewed as a braid
     688        Return the disjoint braid components, if any, else return the braid itself.
     689        For example consider the braid [-1, 3, 1, 3]. This can be viewed as a braid
    710690        with components as [-1, 1] and [3, 3]. There is no common crossing to these
    711691        two (in sense there is a crossing between strand 1 and 2, crossing between
    712692        3 and 4 but no crossing between strand 2 and 3,so these can be viewed as
    713693        independent components in the braid).
    714694
    715         OUTPUT:
    716 
    717         - List containing the components is returned
     695        OUTPUT: List containing the components is returned
    718696
    719697        EXAMPLES::
    720698
    class Link: 
    733711        b = self.braid()
    734712        ml = list(b.Tietze())
    735713        if ml == []:
    736             raise Exception("The braid remains the same with no components")
     714            raise ValueError("The braid remains the same with no components")
    737715        else:
    738716            l = list(set([abs(k) for k in ml]))
    739717            missing1 = list(set(range(min(l), max(l) + 1)) - set(l))
    class Link: 
    755733
    756734    def _braidwordcomponentsvector_(self):
    757735        """
    758         The list from the braidwordcomponents is flattened to give out the vector form.
     736        The list from :meth:`_braidwordcomponents_` is flattened to give the vector form.
    759737
    760         OUTPUT:
    761 
    762         - Vector containing braidwordcomponents
     738        OUTPUT: Vector containing :meth:`_braidwordcomponents_`
    763739
    764740        EXAMPLES::
    765741
    class Link: 
    780756
    781757    def _homology_generators_(self):
    782758        """
    783         The set of generators for the first homology group of the connected Seifert surface of the given link.
    784         This method uses the braidwordcomponentsvector to generate the homology generators.
    785         The position of the repeated element w.r.t the braidwordcomponentvector list is
    786         compiled into a list.
    787 
    788         OUTPUT:
     759        The set of generators for the first homology group of the
     760        connected Seifert surface of the given link.  This method uses
     761        :meth:`_braidwordcomponentsvector_` to generate the homology
     762        generators.  The position of the repeated element w.r.t.
     763        :meth:`_braidwordcomponentsvector_` is compiled into a list.
    789764
    790         - The homology generators relating to the braid word representation
     765        OUTPUT: The homology generators relating to the braid word representation
    791766
    792767        EXAMPLES::
    793768
    class Link: 
    802777            sage: L = Link(B([-2, 4, 1, 6, 1, 4]))
    803778            sage: L._homology_generators_()
    804779            [0, 2, 0, 4, 0]
     780
    805781        """
    806782        x4 = self._braidwordcomponentsvector_()
    807783        hom_gen = []
    class Link: 
    819795        """
    820796        Return the Seifert Matrix associated with the link.
    821797
    822         OUTPUT:
    823 
    824         - The intersection matrix of a (not necessarily minimal) Seifert surface of the
    825           link.
     798        OUTPUT: The intersection matrix of a (not necessarily minimal) Seifert
     799        surface of the link.
    826800
    827801        EXAMPLES::
    828802
    class Link: 
    892866        """
    893867        Return the number of connected components of the link.
    894868
    895         OUTPUT:
    896 
    897         - Connected components of the link
     869        OUTPUT: Connected components of the link
    898870
    899871        EXAMPLES::
    900872
    class Link: 
    919891
    920892    def is_knot(self):
    921893        """
    922         Return True if the link is knot.
     894        Return True if the link is a knot.
    923895        Every knot is a link but the converse is not true.
    924896
    925         OUTPUT:
    926 
    927         - True if knot else False
     897        OUTPUT: True if knot else False
    928898
    929899        EXAMPLES::
    930900
    class Link: 
    946916        """
    947917        Return the genus of the link
    948918
    949         OUTPUT:
    950 
    951         - Genus of the Link
     919        OUTPUT: genus of the link
    952920
    953921        EXAMPLES::
    954922
    class Link: 
    1004972        """
    1005973        Return the signature of the link
    1006974
    1007         OUTPUT:
    1008 
    1009         - Signature of the Link
     975        OUTPUT: signature of the link
    1010976
    1011977        EXAMPLES::
    1012978
    class Link: 
    10391005
    10401006        - ``var`` -- (default: ``'t'``); the variable in the polynomial.
    10411007
    1042         OUTPUT:
    1043 
    1044         - Alexander Polynomial of the Link
     1008        OUTPUT: Alexander Polynomial of the Link
    10451009
    10461010        EXAMPLES::
    10471011
    class Link: 
    10671031        """
    10681032        Return the determinant of the knot
    10691033
    1070         OUTPUT:
    1071 
    1072         - Determinant of the Knot
     1034        OUTPUT: determinant of the knot
    10731035
    10741036        EXAMPLES::
    10751037
    class Link: 
    10891051            a = self.alexander_polynomial()
    10901052            return Integer(abs(a(-1)))
    10911053        else:
    1092             raise Exception("Determinant implmented only for knots")
     1054            raise ValueError("Determinant implemented only for knots")
    10931055
    10941056    def arf_invariant(self):
    10951057        """
    10961058        Return the arf invariant. Arf invariant is defined only for knots.
    10971059
    1098         OUTPUT:
    1099 
    1100         - Arf invariant of knot
     1060        OUTPUT: Arf invariant of the knot
    11011061
    11021062        EXAMPLES::
    11031063
    class Link: 
    11201080            else:
    11211081                return 1
    11221082        else:
    1123             raise Exception("Arf invariant is defined only for knots")
     1083            raise ValueError("Arf invariant is defined only for knots")
    11241084
    11251085    def is_alternating(self):
    11261086        """
    1127         Return True if the given knot diagram is alternating else returns False.
    1128         Alternating diagram implies every over cross is followed by an under cross
     1087        Return True if the given knot diagram is alternating else return False.
     1088        Alternating diagram means that every over cross is followed by an under cross
    11291089        or the vice-versa.
    11301090
    1131         We look at the gauss code if the sign is alternating, True is returned else
    1132         the knot is not alternating False is returned.
    1133 
    1134         OUTPUT:
    1135 
    1136         - True if the knot diagram is alternating else False
     1091        In the gauss code, if the sign is alternating, True is returned, else
     1092        the knot is not alternating so False is returned.
    11371093
    11381094        EXAMPLES::
    11391095
    class Link: 
    11691125        """
    11701126        Return the orientation of the crossings of the link diagram.
    11711127
    1172         OUTPUT:
    1173 
    1174         - Orientation  of the crossings.
    1175 
    11761128        EXAMPLES::
    11771129
    11781130            sage: L = Link([[1, 4, 5, 2], [3, 5, 6, 7], [4, 8, 9, 6], [7, 9, 10, 11], [8, 1, 13, 10], [11, 13, 2, 3]])
    class Link: 
    12011153
    12021154    def seifert_circles(self):
    12031155        """
    1204         Return the seifert circles from the link diagram. Seifert circles are the circles
     1156        Return the Seifert circles from the link diagram. Seifert circles are the circles
    12051157        obtained by smoothing all crossings respecting the orientation of the segments.
    12061158
    12071159        Each Seifert circle is represented as a list of the segments that form it.
    12081160
    1209         OUTPUT:
    1210 
    1211         - Seifert circles of the given link diagram.
    1212 
    12131161        EXAMPLES::
    12141162
    12151163            sage: L = Link([[[1, -2, 3, -4, 2, -1, 4, -3]],[1, 1, -1, -1]])
    class Link: 
    12631211        its boundary, with a sign deppending on the orientation of the segment
    12641212        as part of the boundary.
    12651213
    1266         OUTPUT:
    1267 
    1268         - Regions of the knot.
     1214        OUTPUT: regions of the knot
    12691215
    12701216        EXAMPLES::
    12711217
    class Link: 
    13441290        """
    13451291        Return the writhe of the knot.
    13461292
    1347         OUTPUT:
    1348 
    1349         - Writhe of the knot.
     1293        OUTPUT: writhe of the knot
    13501294
    13511295        EXAMPLES::
    13521296
    class Link: 
    13671311
    13681312    def jones_polynomial(self, var='q'):
    13691313        """
    1370         Return the jones polynomial of the link.
     1314        Return the Jones polynomial of the link.
    13711315
    13721316        INPUT:
    13731317
    13741318        - ``var`` -- (default: ``'q'``); the variable in the polynomial.
    13751319
    1376         OUTPUT:
    1377 
    1378         - Jones Polynomial of the link. It is a polynomial in var, as an element
    1379           of the symbolic ring.
     1320        OUTPUT: Jones polynomial of the link. It is a polynomial in
     1321        ``var``, as an element of the symbolic ring.
    13801322
    13811323        EXAMPLES::
    13821324
    class Link: 
    13941336            sage: L = Link(l5)
    13951337            sage: L.jones_polynomial()
    13961338            -q^(3/2) + sqrt(q) - 2/sqrt(q) + 1/q^(3/2) - 2/q^(5/2) + 1/q^(7/2)
     1339
    13971340        """
    13981341        t = SR(var)
    13991342        poly = self._bracket_(t)
    class Link: 
    14201363            sage: L = Link([[2, 1, 3, 4], [4, 3, 1, 2]])
    14211364            sage: L._bracket_()
    14221365            -q^4 - 1/q^4
    1423 
    1424 
    14251366        """
    14261367        t = SR(variable)
    14271368        if len(self.PD_code()) == 1:
    class Link: 
    14821423            sage: L = Link([[1, 1, 2, 2], [3, 3, 4, 4]])
    14831424            sage: L._isolated_components_()
    14841425            [[[1, 1, 2, 2]], [[3, 3, 4, 4]]]
    1485 
    14861426        """
    14871427        G = Graph()
    14881428        for c in self.PD_code():

comment:118 in reply to: ↑ 116 Changed 4 years ago by mmarco

  • Is the definition of the writhe valid for links? Right now the documentation just says "of the knot".

It is as valid for link diagrams. The only difference with the knot case is that a change of orientation in a knot diagram does not change the writhe. However, in the case of link diagrams, a change of the orientation on a component might change the writhe. However, we are always internally considering an orientation in the diagrams, so it does make sense.

  • Methods like alexander_polynomial could use elaboration in their documentation, such as their definition and/or references.

Ok, i will try to work on that, in the following days.

  • I want to create a separate class Knot inheriting from Link to make it easier for people expanding on this in the future (and there is already a method specifically for knots). Any objections to me doing this?

I had thought of keeping the same class (since they would be two almost identical classes), but have two different funcions to create the general links and the knots. The knot function would then just check that the given diagram corresponds to a knot and then create the corresponding link object.

comment:119 in reply to: ↑ 117 Changed 4 years ago by mmarco

Please go ahead with a full review. I think a new Knot class would be good. For future work, it would also be nice to have a catalog of links and knots (e.g., knots.Trefoil()) and also ways of producing new links from old. Could you add a .. todo list?

I am working on a package that would provide a knot/link database taken from the knot atlas (http://katlas.org).

Once done that, i would also like to have an "identify" method that, given a knot/link, computes its invariants and compares them with the ones in the database, giving then a list of possibilities from the database for the given knot/link.

I agree that more documentation would be great, with definitions, references, and (for plot at least) algorithms.

Agree on all. I defintely need to document better the plot method. That was one of the reasons for my proposal of splitting: right now the plot code is specially hard to review.

How is equality determined? How should it be? Should the oriented Gauss code be good enough?

sage: trefoil = Link([[1, 5, 2, 4], [5, 3, 6, 2], [3, 1, 4, 6]])
sage: trefoil == Link([[1, 5, 2, 4], [5, 3, 6, 2], [3, 1, 4, 6]])
False

We can't realistically determine equality. Even determining if a given diagram corresponds to the unknot is a really hard problem. Oriented Gauss code is not even a knot invariant.

Now that you mention it, i think that equality checking should raise "not implemented error".

Thanks for the suggestions. I will work on them.

comment:120 Changed 4 years ago by tscrim

I'm working on them right now. Give me a day to finish what I'm working on and after I push you can take over at that point.

comment:121 Changed 4 years ago by git

  • Commit changed from cb84cec88f012844ac65d102296644a77f89818c to 06aad784cdd03604d77f9f9c7e6c9332a4982fc6

Branch pushed to git repo; I updated commit sha1. New commits:

06aad78Initial pass of code review.

comment:122 follow-up: Changed 4 years ago by tscrim

Okay, I've done my initial pass. There's still a lot more work to be done with respect to the documentation, in particular, the class level doc for the respective Link and Knot classes. (This needs to be cleaned up before a positive review; the other doc is not so important to me but it would be nice to have.)

I couldn't get one of the doctests to pass with cb84cec:

sage -t link.py
**********************************************************************
File "link.py", line 1185, in sage.knots.link.Link.orientation
Failed example:
    L.orientation()
Expected:
    [-1, -1, 1]
Got:
    [-1, -1, -1]

I believe this was a typo of a missing minus sign (if I understand the knot correctly from the plot).

I made a lot of minor to micro optimizations and code cleanup. I created a Knot class as Miguel suggested (and was what I had in mind initially). I created an equality check by looking at the braids (is that a link invariant?) and put a warning message about false negatives (but if it is a link invariant, then we should be able to remove the warning message).

There shouldn't be any more large refactoring of the code after this point I think.

I think for the catalog, we should open up a followup ticket rather than put an explicit todo in the file. However a big +1 on doing this.

comment:123 in reply to: ↑ 122 Changed 4 years ago by mmarco

I will look at it more carefully tomorrow.

In the meantime, the failing doctest is indeed a typo. The knot should be defined as

sage: L = Link([[1, 2, 3, 3], [2, 4, 5, 5], [7, 4, 1, 7]])

I made a lot of minor to micro optimizations and code cleanup. I created a Knot class as Miguel suggested (and was what I had in mind initially). I created an equality check by looking at the braids (is that a link invariant?) and put a warning message about false negatives (but if it is a link invariant, then we should be able to remove the warning message).

The braid is not a link invariant. Actually we should be careful about what equality means. If it means equality of diagrams (that is, the planar diagrams are actually the same, although maybe the elements are enumerated in a different order), we could write some method to check if there exists a different choice of labels that makes the presentations identical. If by equality we mean isotopy invariants, then we are definitely out of luck, since as far as a i know there is no effective method for that.

There shouldn't be any more large refactoring of the code after this point I think.

I think for the catalog, we should open up a followup ticket rather than put an explicit todo in the file. However a big +1 on doing this.

comment:124 Changed 4 years ago by fuglede

Carbon-copying a few remarks from a sage-devel thread: Link.jones_polynomial() has some issues for sufficiently trivial links.

In the following example -- which should be covered -- the method throws an exception:

sage: B = BraidGroup(2)
sage: b = B([])
sage: L = Link(b)
sage: L.jones_polynomial()
...
IndexError: list index out of range

And here's an example where it returns an incorrect value:

sage: B = BraidGroup(8)
sage: b = B([1])
sage: L = Link(b)
sage: L.jones_polynomial()
1
Last edited 4 years ago by fuglede (previous) (diff)

comment:125 follow-up: Changed 4 years ago by mmarco

In the sacond case, the class documentation states that the strands of the braid that have no crossings are ignored. Considering that, the result is correct.

Maybe we should change that anyways. But would involve some redeisgn of the internal data structures.

comment:126 in reply to: ↑ 125 Changed 4 years ago by fuglede

Replying to mmarco:

In the sacond case, the class documentation states that the strands of the braid that have no crossings are ignored. Considering that, the result is correct.

Ah, sorry, you're right, I missed that.

Maybe we should change that anyways. But would involve some redeisgn of the internal data structures.

Personally, I would find that more natural.

comment:127 Changed 4 years ago by mmarco

I get tthe following errors:

Running doctests with ID 2015-08-10-14-07-03-076dea73.
Git branch: ticket/17030
Using --optional=gdb,mpir,python2,sage,scons,tides
Doctesting 1 file.
sage -t --warn-long 59.0 src/sage/knots/link.py
**********************************************************************
File "src/sage/knots/link.py", line 1309, in sage.knots.link.Link.jones_polynomial
Failed example:
    L.jones_polynomial()
Exception raised:
    Traceback (most recent call last):
      File "/home/mmarco/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/mmarco/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.knots.link.Link.jones_polynomial[1]>", line 1, in <module>
        L.jones_polynomial()
      File "/home/mmarco/sage/local/lib/python2.7/site-packages/sage/knots/link.py", line 1323, in jones_polynomial
        poly = self._bracket_()
      File "sage/misc/cachefunc.pyx", line 1888, in sage.misc.cachefunc.CachedMethodCaller.__call__ (/home/mmarco/sage/src/build/cythonized/sage/misc/cachefunc.c:11438)
        w = self._cachedmethod._instance_call(self._instance, *args, **kwds)
      File "sage/misc/cachefunc.pyx", line 2544, in sage.misc.cachefunc.CachedMethod._instance_call (/home/mmarco/sage/src/build/cythonized/sage/misc/cachefunc.c:14884)
        return self._cachedfunc.f(inst, *args, **kwds)
    TypeError: _bracket_() takes exactly 2 arguments (1 given)
**********************************************************************
File "src/sage/knots/link.py", line 1312, in sage.knots.link.Link.jones_polynomial
Failed example:
    L.jones_polynomial()
Exception raised:
    Traceback (most recent call last):
      File "/home/mmarco/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/mmarco/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.knots.link.Link.jones_polynomial[3]>", line 1, in <module>
        L.jones_polynomial()
      File "/home/mmarco/sage/local/lib/python2.7/site-packages/sage/knots/link.py", line 1323, in jones_polynomial
        poly = self._bracket_()
      File "sage/misc/cachefunc.pyx", line 1888, in sage.misc.cachefunc.CachedMethodCaller.__call__ (/home/mmarco/sage/src/build/cythonized/sage/misc/cachefunc.c:11438)
        w = self._cachedmethod._instance_call(self._instance, *args, **kwds)
      File "sage/misc/cachefunc.pyx", line 2544, in sage.misc.cachefunc.CachedMethod._instance_call (/home/mmarco/sage/src/build/cythonized/sage/misc/cachefunc.c:14884)
        return self._cachedfunc.f(inst, *args, **kwds)
    TypeError: _bracket_() takes exactly 2 arguments (1 given)
**********************************************************************
File "src/sage/knots/link.py", line 1316, in sage.knots.link.Link.jones_polynomial
Failed example:
    L.jones_polynomial()
Exception raised:
    Traceback (most recent call last):
      File "/home/mmarco/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/mmarco/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.knots.link.Link.jones_polynomial[6]>", line 1, in <module>
        L.jones_polynomial()
      File "/home/mmarco/sage/local/lib/python2.7/site-packages/sage/knots/link.py", line 1323, in jones_polynomial
        poly = self._bracket_()
      File "sage/misc/cachefunc.pyx", line 1888, in sage.misc.cachefunc.CachedMethodCaller.__call__ (/home/mmarco/sage/src/build/cythonized/sage/misc/cachefunc.c:11438)
        w = self._cachedmethod._instance_call(self._instance, *args, **kwds)
      File "sage/misc/cachefunc.pyx", line 2544, in sage.misc.cachefunc.CachedMethod._instance_call (/home/mmarco/sage/src/build/cythonized/sage/misc/cachefunc.c:14884)
        return self._cachedfunc.f(inst, *args, **kwds)
    TypeError: _bracket_() takes exactly 2 arguments (1 given)
**********************************************************************
File "src/sage/knots/link.py", line 1320, in sage.knots.link.Link.jones_polynomial
Failed example:
    L.jones_polynomial()
Exception raised:
    Traceback (most recent call last):
      File "/home/mmarco/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/mmarco/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.knots.link.Link.jones_polynomial[9]>", line 1, in <module>
        L.jones_polynomial()
      File "/home/mmarco/sage/local/lib/python2.7/site-packages/sage/knots/link.py", line 1323, in jones_polynomial
        poly = self._bracket_()
      File "sage/misc/cachefunc.pyx", line 1888, in sage.misc.cachefunc.CachedMethodCaller.__call__ (/home/mmarco/sage/src/build/cythonized/sage/misc/cachefunc.c:11438)
        w = self._cachedmethod._instance_call(self._instance, *args, **kwds)
      File "sage/misc/cachefunc.pyx", line 2544, in sage.misc.cachefunc.CachedMethod._instance_call (/home/mmarco/sage/src/build/cythonized/sage/misc/cachefunc.c:14884)
        return self._cachedfunc.f(inst, *args, **kwds)
    TypeError: _bracket_() takes exactly 2 arguments (1 given)
**********************************************************************
File "src/sage/knots/link.py", line 1342, in sage.knots.link.Link._bracket_
Failed example:
    L._bracket_()
Exception raised:
    Traceback (most recent call last):
      File "/home/mmarco/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/mmarco/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.knots.link.Link._bracket_[1]>", line 1, in <module>
        L._bracket_()
      File "sage/misc/cachefunc.pyx", line 1888, in sage.misc.cachefunc.CachedMethodCaller.__call__ (/home/mmarco/sage/src/build/cythonized/sage/misc/cachefunc.c:11438)
        w = self._cachedmethod._instance_call(self._instance, *args, **kwds)
      File "sage/misc/cachefunc.pyx", line 2544, in sage.misc.cachefunc.CachedMethod._instance_call (/home/mmarco/sage/src/build/cythonized/sage/misc/cachefunc.c:14884)
        return self._cachedfunc.f(inst, *args, **kwds)
    TypeError: _bracket_() takes exactly 2 arguments (1 given)
**********************************************************************
File "src/sage/knots/link.py", line 1345, in sage.knots.link.Link._bracket_
Failed example:
    L._bracket_()
Exception raised:
    Traceback (most recent call last):
      File "/home/mmarco/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/mmarco/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.knots.link.Link._bracket_[3]>", line 1, in <module>
        L._bracket_()
      File "sage/misc/cachefunc.pyx", line 1888, in sage.misc.cachefunc.CachedMethodCaller.__call__ (/home/mmarco/sage/src/build/cythonized/sage/misc/cachefunc.c:11438)
        w = self._cachedmethod._instance_call(self._instance, *args, **kwds)
      File "sage/misc/cachefunc.pyx", line 2544, in sage.misc.cachefunc.CachedMethod._instance_call (/home/mmarco/sage/src/build/cythonized/sage/misc/cachefunc.c:14884)
        return self._cachedfunc.f(inst, *args, **kwds)
    TypeError: _bracket_() takes exactly 2 arguments (1 given)
**********************************************************************
2 items had failures:
   2 of   5 in sage.knots.link.Link._bracket_
   4 of  11 in sage.knots.link.Link.jones_polynomial
    [221 tests, 6 failures, 1.63 s]
----------------------------------------------------------------------
sage -t --warn-long 59.0 src/sage/knots/link.py  # 6 doctests failed
----------------------------------------------------------------------
Total time for all tests: 1.7 seconds
    cpu time: 1.6 seconds
    cumulative wall time: 1.6 seconds

Also, doctest coverage is not complete:

mmarco@mountain ~/sage $ ./sage -coverage src/sage/knots/link.py
------------------------------------------------------------------------
SCORE src/sage/knots/link.py: 93.1% (27 of 29)

Missing doctests:
     * line 219: def __eq__(self, other)
     * line 233: def __ne__(self, other)

About the splitting of the classes, i think that what should be exposed to the user, is a function that creates a Link or a Knot deppending of the input. That is: if the user wants to create a Link that happens to be a knot, why shouldn't it have a arf_invariantmethod?

comment:128 Changed 4 years ago by git

  • Commit changed from 06aad784cdd03604d77f9f9c7e6c9332a4982fc6 to 8f4ec1977612c42da767931683dae92ba17e4bb0

Branch pushed to git repo; I updated commit sha1. New commits:

8f4ec19Commiting some additional fixes.

comment:129 Changed 4 years ago by tscrim

Hmm...weird, somehow some of my changes didn't get committed previously (most likely I forgot).

I don't like always doing an expensive check of the input with Link, even with a check. If the user think it's a knot or wants a knot, then they should create a Knot instance. Otherwise they are probably looking a links. We could put an example about this. IMO we do the same thing across Sage. The most direct comparison is with posets/lattices, but it also is similar to fraction fields, if you create elements that are of the proper base ring (say polynomials instead of rational functions).

PS - With high probability, knot theorists wanting to create knots are going to tab-complete find Knot before Link (if they even discover it).

Last edited 4 years ago by tscrim (previous) (diff)

comment:130 Changed 4 years ago by mmarco

Well, the check doesn't need to be expensive at all. What do other people think?

In any case, at a very minumum, we should have conversions from knot to link and vice-versa.

comment:131 follow-up: Changed 4 years ago by tscrim

Getting the number of (connected) components seems very expensive from the code, but I haven't done any profiling. To compute it, we have to get the PD code (this looks like the most expensive part), construct a graph, and check the number of connected components on that. Is there a faster/better way to check?

I don't think we need a conversion from a knot to a link because of subclassing, however I'm not opposed to handling a Link as input to Knot/Link.

comment:132 in reply to: ↑ 131 ; follow-up: Changed 4 years ago by fuglede

Replying to tscrim:

Getting the number of (connected) components seems very expensive from the code, but I haven't done any profiling. To compute it, we have to get the PD code (this looks like the most expensive part), construct a graph, and check the number of connected components on that. Is there a faster/better way to check?

I don't think we need a conversion from a knot to a link because of subclassing, however I'm not opposed to handling a Link as input to Knot/Link.

Sorry for coming in a bit from the sideline here, but if the link is given as a trace closure of a braid, the number of components is straightforward to compute: https://github.com/fuglede/jones-representation/blob/9305852913b9092f4ef18e547400fb8b66f33079/curverep.sage#L394

comment:133 Changed 4 years ago by mmarco

It deppends on the input. If the input is the oriented Gauss code, you have the number of components for free. If it is a braid, it is just the cycle representation of the corresponding permutation. If it is a PD code, then essentially it is a matter of computing the connected components of a graph.

comment:134 in reply to: ↑ 132 Changed 4 years ago by fuglede

Replying to fuglede:

Sorry for coming in a bit from the sideline here, but if the link is given as a trace closure of a braid, the number of components is straightforward to compute: https://github.com/fuglede/jones-representation/blob/9305852913b9092f4ef18e547400fb8b66f33079/curverep.sage#L394

As a bit of an aside for those interested, I included the methods from the link above in #19011.

comment:135 Changed 4 years ago by mmarco

Travis's latest changes look good to me.

comment:136 Changed 4 years ago by fuglede

With #19011 merged, I ran a number of different tests to compare the run times of the two algorithms for Jones polynomial computation (the one from #19011 and one from here). See this gist for the results. Depending on the exact use case, there is a huge difference in performance, and optimally we would include some logic to figure out which algorithm sage should use.

Last edited 4 years ago by fuglede (previous) (diff)

comment:137 follow-up: Changed 4 years ago by tscrim

From your data, it looks like the implementation on #19011 is the better one to use (except for perhaps small cases). My recommendation would be to add an algorithm argument for the Jones polynomial which dispatches to the correct algorithm (with the default being #19011). That way we can use both as extra verification of the result and the user can choose the other algorithm if the default happens to be slower.

comment:138 in reply to: ↑ 137 Changed 4 years ago by fuglede

Sounds reasonable enough. One thing I didn't consider by the way, is how long it actually takes to make the relevant conversions between the planar diagram and braid presentations of links.

And by the way, one could of course ask the same question about Alexander polynomials. Here, the algorithms are much more comparable and the difference might boil down to micro-optimisations(?):

https://gist.githubusercontent.com/fuglede/da35ac110ee17dc06beb/raw/c8f80d6f3d10d917a099d9559c58674b59cf686e/alexandercombined.png

On a related note, I think it would make sense to take the closure-related methods from Braid and refactor into Link, just because they logically fit there.

Last edited 4 years ago by fuglede (previous) (diff)

comment:139 Changed 4 years ago by tscrim

@fuglede Are you planning to make that change?

@everyone What else needs to be done to get this merged in? Is the Jones polynomial issue something that needs a serious fix? I think this ticket has been hanging around far too long and otherwise is in good enough shape to get a positive review.

comment:140 Changed 4 years ago by mmarco

It is not as polished as i would like, but i don't see it improving much anytime soon.

I think it is good enough to get it rolling. It would be better if we merge it now and then slowly do the small improvements that it needs, than to keep waiting for a complete exhaustive review process leading to a polished ticket that might never happen.

comment:141 Changed 4 years ago by fuglede

I pushed those changes to u/fuglede/17030 (GH mirror of the commit if you just want to have a quick look). One obvious pain is that the two algorithms give different results when the link is not the trace closure of the braid used to initialize it, which happens when one has crossing-less strands, as the following example illustrates:

sage: B = BraidGroup(3)
sage: b = B([1])
sage: L = Link(b)
sage: b.components_in_closure()
2
sage: L.number_of_components()
1
sage: L.jones_polynomial(algorithm='jonesrep')
-sqrt(t) - 1/sqrt(t)
sage: L.jones_polynomial(algorithm='statesum')
1

Of course, this is not specific to Jones related stuff:

sage: B = BraidGroup(3)
sage: b = B([1])
sage: b.alexander_polynomial()
0
sage: Link(b).alexander_polynomial()
1

The branch also corrects a couple of typos.

comment:142 Changed 4 years ago by fuglede

Actually, I just noticed that the alexander_polynomial method currently gives incorrect results, even when no braid strands are ignored:

sage: B = BraidGroup(4)
sage: b = B([1,3])  # A braid where all strands play a role
sage: L = Link(b)   # Two disjoint unknots
sage: b.alexander_polynomial()
0
sage: L.alexander_polynomial()
1

In this case, 0 is the correct result as the link bounds a disconnected oriented surface (two disjoint disks).

To debug it, it would be helpful to document what _homology_generators_ actually returns: according to the current docs, it returns 'homology generators' but it currently outputs a list of integers. Perhaps the constructed Seifert surface is not connected, or something like that? This would explain why seifert_matrix gives the following output:

sage: L.seifert_matrix()
[]

In this particular case, the simplest Seifert surface is probably the cylinder whose corresponding Seifert matrix is the 1x1 zero matrix.

Something else that seems weird is the following:

sage: L.genus()
-2
Last edited 4 years ago by fuglede (previous) (diff)

comment:143 Changed 4 years ago by chapoton

  • Milestone changed from sage-6.9 to sage-6.10

comment:144 Changed 4 years ago by chapoton

  • Milestone changed from sage-6.10 to sage-7.0

comment:145 Changed 3 years ago by mmarco

  • Cc fuglede added
  • Description modified (diff)

comment:146 follow-up: Changed 3 years ago by kcrisman

I have some people (actual knot theorists) I've recruited to just try it out in a shared SMC instance (nothing necessary for them other than to try it and verify it performs as advertised) but I just haven't had time yet, was hoping for March :( but of course if you can finish this before that it would stupendous.

comment:147 Changed 3 years ago by mmarco

Can you add me to the SMC project? Aslo, take a look at

https://groups.google.com/forum/#!topic/sage-devel/4hp4SvCfEP0

If some time in March is good for you, it is ok for me too.

comment:148 Changed 3 years ago by tscrim

The biggest issue is fixing the discrepancy in alexander_polynomial noted in comment:142. I also took a look at homology_generators, but I had no idea what they were suppose to do either.

comment:149 Changed 3 years ago by kcrisman

Can you add me to the SMC project? Aslo, take a look at

Well, I haven't created it yet :) but will do so if I am indeed able to get around to it.

comment:150 Changed 3 years ago by amitjamadagni

The reference to the seifert_matrix construction is the following by Julia Collins :

http://www.maths.ed.ac.uk/~jcollins/SeifertMatrix/

The results from the site are as follows :

You entered the braid [1,3] (Alphabetical notation: AC) This has 2 component(s), i.e. it is a link. The Seifert matrix is: [[]] The genus of the Seifert surface is 0, and it has 2 connected component(s). The braid is a disjoint union of unrelated subbraids: { [1], [3] }.

Also the reference to homology_generators, genus is the same. Though the results of the genus are different to what is reflected.

comment:151 in reply to: ↑ 146 Changed 3 years ago by mmarco

Replying to kcrisman:

I have some people (actual knot theorists) I've recruited to just try it out in a shared SMC instance (nothing necessary for them other than to try it and verify it performs as advertised) but I just haven't had time yet, was hoping for March :( but of course if you can finish this before that it would stupendous.

any news about it?

comment:152 follow-up: Changed 3 years ago by kcrisman

No, but hope springs eternal... I do notice that the branch is red for some reason now.

comment:153 Changed 3 years ago by git

  • Commit changed from 8f4ec1977612c42da767931683dae92ba17e4bb0 to 79d175ab20b41008e74ab0895b4781d7358b6dd5

Branch pushed to git repo; I updated commit sha1. New commits:

79d175aMerge branch 'public/ticket/17030' of trac.sagemath.org:sage into public/ticket/17030

comment:154 in reply to: ↑ 152 Changed 3 years ago by tscrim

Replying to kcrisman: I do notice that the branch is red for some reason now.

This was a trivial merge conflict in all.py.

comment:155 Changed 3 years ago by tscrim

Linear algebra question: What is the determinant of a 0x0 matrix? FYI - The Sage answer:

sage: mat = matrix(ZZ, 0, 0)
sage: mat.det()
1

This is why the Alexander polynomial is returning 1 for the example in comment:142. IMO, I think it should be 0 because the sum in the definition of the determinant is vacuous. (A related question, is a 0x0 matrix invertible?)

I get the genus is 0 for the example in comment:142 with the current version.

I'm starting to understand what is going on with the code. The homology generators is setting a value of 0 if a particular pair (L[i], L[i+1]) in the braid word component vector does not contribute to a homology generator. The braid word components are a nice reduced expression to compute these generators. See Lemma 3.1 in http://www.maths.ed.ac.uk/~jcollins/SeifertMatrix/SeifertMatrix.pdf.

I'm going through right now and doing some code improvements, seeing if I can simplify things, and working around the issue noted above.

comment:156 Changed 3 years ago by git

  • Commit changed from 79d175ab20b41008e74ab0895b4781d7358b6dd5 to b50b8bde559c63cc794b8702efe280bff1674ce7

Branch pushed to git repo; I updated commit sha1. New commits:

1fd6028Code improvements and fixes.
b50b8bdSome additional documentation additions and code tweaks.

comment:157 Changed 3 years ago by git

  • Commit changed from b50b8bde559c63cc794b8702efe280bff1674ce7 to f3c26992fa3186a7ee1e4bf324e7863b5bff40bf

Branch pushed to git repo; I updated commit sha1. New commits:

020dcfbMerge commit '37ca1e8c73a60aa9cc3243331047cd5febe6b57a' of git://trac.sagemath.org/sage into u/fuglede/17030
72bb738Move Jones polynomial related methods from braid.py to link.py
e18058fMinor fixes to documentation
9f6f626Merge branch 'u/fuglede/17030' of trac.sagemath.org:sage into u/fuglede/17030
f3c2699Changing around the Jones polynomial code.

comment:158 Changed 3 years ago by git

  • Commit changed from f3c26992fa3186a7ee1e4bf324e7863b5bff40bf to fb2d6c5f7f89525bd9150c4097e43bebc0489fe0

Branch pushed to git repo; I updated commit sha1. New commits:

fb2d6c5Have the link code actually remove unused strands.

comment:159 Changed 3 years ago by tscrim

  • Milestone changed from sage-7.0 to sage-7.2
  • Reviewers changed from Miguel Marco, Karl-Dieter Crisman, Frédéric Chapoton to Miguel Marco, Karl-Dieter Crisman, Frédéric Chapoton, Travis Scrimshaw
  • Status changed from needs_work to needs_review

Okay, I have fixed the code issues I came across, merged in u/fuglede/17030 but changed how the Jones polynomial was called (in particular, it should be available for the braid group elements), added a hack around the 0x0 matrix determinant issue noted in comment:155, and made it so the link actually removed unused strands from an input as a braid group element. So back to needing review.

comment:160 Changed 3 years ago by tscrim

  • Description modified (diff)

Also, should we put a remark somewhere that we might be changing the behavior of how we handle input from the braid group to include unused strands?

One last remark, there are some oddities with plotting multiple links, but I think we can just put a warning about that for now (unless someone wants to delve into that code). We should also add a few pictures to that doc with the .. PLOT:: directive...

comment:161 Changed 3 years ago by mmarco

Thanks a lot ofr the work Travis!

I wrote the code for the plotting, and I am aware that it needs some work, but I think it is good enough for now. +1 to the warning and the pics in the doc.

I hope to have some time in the next week to do a deep review.

comment:162 Changed 3 years ago by git

  • Commit changed from fb2d6c5f7f89525bd9150c4097e43bebc0489fe0 to 1a30f4b419d9ff18b490ad029ac11b4d9041ea33

Branch pushed to git repo; I updated commit sha1. New commits:

09b7b7bAdded some more complex examples, plots, and warnings.
a1e168eMaking the conf.py in the doc a symlink.
1a30f4bA few more documentation additions and tweaks.

comment:163 Changed 3 years ago by git

  • Commit changed from 1a30f4b419d9ff18b490ad029ac11b4d9041ea33 to 25393da7cc5d43ed39160436b7b2be117711771b

Branch pushed to git repo; I updated commit sha1. New commits:

25393daA little bit more doc changes.

comment:164 Changed 3 years ago by tscrim

The issue with plotting seems to be a problem when there are multiple components that can be completely separated, but otherwise it seems to work very well.

I've added a bunch of pictures, the notes/warnings mentioned above, and did a little bit more cleanup. Hopefully this go-around we can get this finished and into Sage.

comment:165 Changed 3 years ago by tscrim

I created this sage-devel thread asking about the determinant of a 0x0 matrix. There are good reasons for having it be 1, so we just have to work around that here.

comment:166 Changed 3 years ago by git

  • Commit changed from 25393da7cc5d43ed39160436b7b2be117711771b to 075d7b74a5e4c1026f06c9f03f63c993e646e5d4

Branch pushed to git repo; I updated commit sha1. New commits:

075d7b7Change message about 0x0 matrices.

comment:167 Changed 3 years ago by fuglede

The determinant should definitely be 1; it's the Seifert matrix that doesn't really make sense to me (because as mentioned above, for the case of interest, one Seifert surface is the cylinder, but again, I have not understood what the algorithm actually does).

By treating only the symptoms, the algorithm now (in 7711771b) produces the incorrect result for the unknot:

sage: B = BraidGroup(2)
sage: b = B([1])
sage: b.alexander_polynomial()
1
sage: Link(b).alexander_polynomial()
0

comment:168 Changed 3 years ago by git

  • Commit changed from 075d7b74a5e4c1026f06c9f03f63c993e646e5d4 to 0cce5891b429ea267c45bd89adacff6ebb12e453

Branch pushed to git repo; I updated commit sha1. New commits:

0cce589Fixing issues with the Alexander polynomial.

comment:169 Changed 3 years ago by tscrim

I see what the problem is now (after treating enough symptoms). In Definition 2.11, there is this: "For a link with a disconnected Seifert surface we define the Alexander polynomial to be zero." So we just need to check to see if the links can be separated, which means the braid representation can be broken into 2 disjoint components.

However, I believe the Seifert matrix is correct as it encodes the H1 information of the Seifert surface. Since the unlink is a disjoint union of 2 disks, the positive homology groups are all trivial, so the Seifert matrix should be a 0x0 matrix. (If you want to think of it as a [empty] cylinder, H1 is also trivial in that case as well. However, I don't think this is the correct construction of the Seifert surface from the reading I've done, but I'm not an expert.)

comment:170 follow-up: Changed 3 years ago by fuglede

Cool, that's also what I suspected back then. Where I come from, Seifert surfaces are connected by definition; that can make life a bit easier -- in particular in this situation where you can just use the same definition for the Alexander polynomial regardless of the chosen surface.

In any case, by "cylinder", I meant something homeomorphic to S1 × [0, 1] which has boundary two separated unknots, and which has non-trivial H1. In that case, a Seifert matrix is the 1x1 zero matrix. Likewise in the case of the unknot, you can avoid having to ponder about 0x0 matrices, since H1(D2 × R, Z) may be presented by the 1x1 unit matrix.

For the case at hand, the algorithm still produces incorrect results for links which bound disconnected oriented surfaces (I would not call such links "disjoint", since link components are always disjoint);

sage: B3 = BraidGroup(3)
sage: b = B3([1, 2, -2])
sage: b.alexander_polynomial()
0
sage: Link(b).alexander_polynomial()
1

And a weirder example:

sage: B2 = BraidGroup(2)
sage: b = B2([1, -1])
sage: b.alexander_polynomial()
0
sage: Link(b).alexander_polynomial()
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-14-c27fd62b3305> in <module>()
----> 1 Link(b).alexander_polynomial()

/home/fuglede/repos/sage/local/lib/python2.7/site-packages/sage/knots/link.pyc in alexander_polynomial(self, var)
   1244         R = LaurentPolynomialRing(ZZ, var)
   1245         # The Alexander polynomial of disjoint links are defined to be 0
-> 1246         if len(self._braid_word_components()) > 1:
   1247             return R.zero()
   1248         t = R.gen()

/home/fuglede/repos/sage/local/lib/python2.7/site-packages/sage/knots/link.pyc in _braid_word_components(self)
    899         ml = list(self.braid().Tietze())
    900         if not ml:
--> 901             raise ValueError("the braid remains the same with no components")
    902 
    903         l = set(abs(k) for k in ml)

ValueError: the braid remains the same with no components

Edit: Ah, it looks like for the first one of those examples, the library throws away one of the components (is that intended? According to the docs, only "The strands of the braid that have no crossings at all are removed", and in this case, all of them have crossings; they just happen to be pretty trivial).

Last edited 3 years ago by fuglede (previous) (diff)

comment:171 in reply to: ↑ 170 ; follow-up: Changed 3 years ago by tscrim

Replying to fuglede:

Cool, that's also what I suspected back then. Where I come from, Seifert surfaces are connected by definition; that can make life a bit easier -- in particular in this situation where you can just use the same definition for the Alexander polynomial regardless of the chosen surface.

Yes, definitely.

In any case, by "cylinder", I meant something homeomorphic to S1 × [0, 1] which has boundary two separated unknots, and which has non-trivial H1.

In that case, I agree. Although this doesn't agree with Seifert's construction AFAIK, and for 4+ components, at least by my understanding of how you are constructing things, wouldn't give a surface.

In that case, a Seifert matrix is the 1x1 zero matrix. Likewise in the case of the unknot, you can avoid having to ponder about 0x0 matrices, since H1(D2 × R, Z) may be presented by the 1x1 unit matrix.

For the case at hand, the algorithm still produces incorrect results for links which bound disconnected oriented surfaces (I would not call such links "disjoint", since link components are always disjoint);

sage: B3 = BraidGroup(3)
sage: b = B3([1, 2, -2])
sage: b.alexander_polynomial()
0
sage: Link(b).alexander_polynomial()
1

In that case the 2 -2 are canceled automatically by the braid group:

sage: B = BraidGroup(4)
sage: B([1,2,-2])
s0

So it becomes just 1 unknot as far as the code currently works. Which is why we get an Alexander polynomial of 1.

And a weirder example:

sage: B2 = BraidGroup(2)
sage: b = B2([1, -1])
sage: b.alexander_polynomial()
0
sage: Link(b).alexander_polynomial()
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-14-c27fd62b3305> in <module>()
----> 1 Link(b).alexander_polynomial()

/home/fuglede/repos/sage/local/lib/python2.7/site-packages/sage/knots/link.pyc in alexander_polynomial(self, var)
   1244         R = LaurentPolynomialRing(ZZ, var)
   1245         # The Alexander polynomial of disjoint links are defined to be 0
-> 1246         if len(self._braid_word_components()) > 1:
   1247             return R.zero()
   1248         t = R.gen()

/home/fuglede/repos/sage/local/lib/python2.7/site-packages/sage/knots/link.pyc in _braid_word_components(self)
    899         ml = list(self.braid().Tietze())
    900         if not ml:
--> 901             raise ValueError("the braid remains the same with no components")
    902 
    903         l = set(abs(k) for k in ml)

ValueError: the braid remains the same with no components

Edit: Ah, it looks like for the first one of those examples, the library throws away one of the components (is that intended? According to the docs, only "The strands of the braid that have no crossings at all are removed", and in this case, all of them have crossings; they just happen to be pretty trivial).

In both cases this is what is going on. Although we could special case the identity element of the braid group, but this wouldn't handle when the input is B([3, 1, -3, -1]). I'm somewhat unsure if we really should push this in as-is. I think it is a very good addition, but not dealing with these lingering braid group issues seems to cause confusion... I can try to fix things up a little bit to handle all of these issues, but I'm not sure I will be successful with out a substantial rewrite (which I am not sure I have the mathematical knowledge to do).

comment:172 Changed 3 years ago by tscrim

PS - I agree, "disjoint" is not a good word. Perhaps "separable" is a better? Also, maybe we use _isolated_components to check for the Alexander polynomial instead of my current approach?

comment:173 in reply to: ↑ 171 ; follow-up: Changed 3 years ago by fuglede

Replying to tscrim:

In that case, I agree. Although this doesn't agree with Seifert's construction AFAIK, and for 4+ components, at least by my understanding of how you are constructing things, wouldn't give a surface.

I'm not really constructing anything at all, so I'm not quite sure what it is that would not be a surface.

In that case the 2 -2 are canceled automatically by the braid group:

sage: B = BraidGroup(4)
sage: B([1,2,-2])
s0

Yeah, that makes sense. Isn't it a bit unfortunate that one would need to understand the BraidGroup internals in order to use the knot theory module, though? If I just read the documentation in Link, then I might assume that [1, -2, -2] contains knots on all three strands (that's what I did anyway).

PS - I agree, "disjoint" is not a good word. Perhaps "separable" is a better?

Yes, I believe I've heard "separable" being used in this context as well, although I can't seem to find a written source at the moment. The word of course already has another meaning in the context of topological spaces, but that's not really an issue. In any case, you could always just go with "bounds and oriented disconnected surface".

comment:174 in reply to: ↑ 173 Changed 3 years ago by tscrim

Replying to fuglede:

Replying to tscrim:

In that case, I agree. Although this doesn't agree with Seifert's construction AFAIK, and for 4+ components, at least by my understanding of how you are constructing things, wouldn't give a surface.

I'm not really constructing anything at all, so I'm not quite sure what it is that would not be a surface.

I thought you were taking S1 x S1 and then connecting up points inbetween. Now that I actually drew something, you were taking the two unknots and drawing them projected into the plane with overlap, where I did get a cylinder.

In that case the 2 -2 are canceled automatically by the braid group:

sage: B = BraidGroup(4)
sage: B([1,2,-2])
s0

Yeah, that makes sense. Isn't it a bit unfortunate that one would need to understand the BraidGroup internals in order to use the knot theory module, though? If I just read the documentation in Link, then I might assume that [1, -2, -2] contains knots on all three strands (that's what I did anyway).

I agree. Do you think a warning with an example would be sufficient (if it's not possible to quickly fix) to clarify things?

PS - I agree, "disjoint" is not a good word. Perhaps "separable" is a better?

Yes, I believe I've heard "separable" being used in this context as well, although I can't seem to find a written source at the moment. The word of course already has another meaning in the context of topological spaces, but that's not really an issue. In any case, you could always just go with "bounds and oriented disconnected surface".

True.

comment:175 Changed 3 years ago by mmarco

I propose to use the word "unlinked components" for the case you are talking about: they bound a disconnected surface, or, equivalently, they could be represented in a planar diagram where there are no crossings that involve two different components.

I chosed the word _isolated_components to reffer to that situation: where the planar representation that we are dealing with has no crossings that involve different components.

I considered other names, like "unlinked components", but I didin't like them because the concept I wanted to consider does not deppend on the 3-dimensional topology, but on the particular planar representation that we are using. If two components are shown as "isolated" in a planar diagram (which is the case that is troubling us here), they are clearly unlinked. But the converse is not true: we could have a very complicated diagram with crossings everywhere that actually represents 2 unlinked knots.

The implementation of the alexander polynomial assumes that the input doesn't have isolated components (that is why we need to treat that case separatedly), but is able to give the right output if there are several unlinked components that are not isolated. So i guess that the solution of detecting that case and giving a 0 output is the right one.

_isolated_components and _braid_word_components should do pretty much the same. The difference is that one computes it from the PD representation whereas the other uses the braid one.

So, can we give a positive review or are there still pending issues?

comment:176 Changed 3 years ago by git

  • Commit changed from 0cce5891b429ea267c45bd89adacff6ebb12e453 to 81cb543c6abca887e32128681c6c12fd0439f4b3

Branch pushed to git repo; I updated commit sha1. New commits:

81cb543Fixing plotting of isolated components and allowing trivial braid group element.

comment:177 Changed 3 years ago by tscrim

If you think my last set of changes are good, then yes, I believe we can. In this last commit, I added support for the unknot given as the identity element in the braid group. I also was able to fix the plotting of multiple isolated components (a + to a -) as far as I can tell.

@fuglede From your previous comments, I am assuming you are good overall with the current version. Is this correct? Also, could you add your real name to the reviewers field?

Last edited 3 years ago by tscrim (previous) (diff)

comment:178 Changed 3 years ago by fuglede

@tscrim Unless it is customary to do for the kind of small discussion we had here, I hesitate to do so: all I did here was really to try out the Jones and Alexander polynomial implementations (and I still barely understand the implementation of the latter), so that doesn't constitute much of a review. I wish I had time to devote to a full-fleshed review, but unfortunately that's far from the case.

comment:179 Changed 3 years ago by tscrim

You looked at and tested a part of the code. Furthermore, you also made some additions. You definitely qualify as a reviewer.

comment:180 Changed 3 years ago by mmarco

  • Status changed from needs_review to positive_review

I agree fuglede should be considered a reviewer. Maybe even an author.

Travis, do you want to add yourself to the authors list?

comment:181 Changed 3 years ago by kcrisman

mmarco: Do you think that this combined effort suffices for positive review? Just checking that whatever stuff hadn't been looked at before is now really ready for inclusion - it would be great to have knots in Sage but it would also be good to have as close to "all correct" as possible. Great teamwork, everybody!

comment:182 Changed 3 years ago by mmarco

Well, I think it is about as close to "all correct" as we can get before merging it. I am pretty sure that the base code is mostly correct (although there might be other bugs that show up in corner cases) .Unless there is a short term plan to make a substantial improvement (like the idea you mentioned to gather some specialists to work on a SMC project intensively), I would prefear to merge something that might have bugs (and solve them later in subsequent tickets), than risking it to bitrot again.

Of course, you might disagree. In that case, feel free to revert to needs_review.

comment:183 Changed 3 years ago by kcrisman

No disagreement, just checking in. In which case my plan for making a SMC project would be vastly simplified - I just make a SMC project with a standard Sage and invite them to it!

comment:184 Changed 3 years ago by jhpalmieri

  • Status changed from positive_review to needs_review

comment:185 Changed 3 years ago by git

  • Commit changed from 81cb543c6abca887e32128681c6c12fd0439f4b3 to 57c816f85bc99a192ac2ec85fe930f01e52d7b14

Branch pushed to git repo; I updated commit sha1. New commits:

57c816ftrac 17030: test error-raising

comment:186 Changed 3 years ago by jhpalmieri

I made a few small changes: added a little documentation and added some doctests for some previously untested parts of the code. We should probably add more doctests to get even better coverage – for example, I couldn't figure out how to create links with several isolated components in order to test the error-raising in the regions method – but we can do more clean-up on another ticket.

comment:187 Changed 3 years ago by git

  • Commit changed from 57c816f85bc99a192ac2ec85fe930f01e52d7b14 to 5e812450e03bb2561cd4cc641c0fae0e95158f37

Branch pushed to git repo; I updated commit sha1. New commits:

5e81245deleted some extraneous stuff

comment:188 Changed 3 years ago by tscrim

  • Reviewers changed from Miguel Marco, Karl-Dieter Crisman, Frédéric Chapoton, Travis Scrimshaw to Miguel Marco, Karl-Dieter Crisman, Frédéric Chapoton, Travis Scrimshaw, Søren Fuglede Jørgensen

I went through most of everything once I have the references to the algorithms. At this point, I do not have any plans to making any (significant) improvements. I also agree with the philosophy of get good, but maybe not perfect, code in and fix bugs as we come across them.

As a followup, we might want to consider adding in optional spkgs of those other knot/link projects listed on Collins' webpage (e.g., BraidProgramme).

John, your changes look good to me. You should be able create isolated components with something like this:

sage: B = BraidGroup(4)
sage: L = Link(B([1,3]))

There's also a more interesting example with two isolated trefoils in the plot() examples:

sage: L = Link([[[-1, 2, -3, 1, -2, 3], [4, -5, 6, -4, 5, -6]], [1, 1, 1, 1, 1, 1]])

@fudlege I got your name from your Github page; I hope that was okay. Thank you for working on this, and I hope you continue to contribute to Sage.

comment:189 Changed 3 years ago by git

  • Commit changed from 5e812450e03bb2561cd4cc641c0fae0e95158f37 to 207d033813994705e75a22ef73b5b637a2b93085

Branch pushed to git repo; I updated commit sha1. New commits:

207d033knots: one more doctest

comment:190 Changed 3 years ago by jhpalmieri

Should we set this back to "positive review"? I don't plan to make any more changes.

comment:191 Changed 3 years ago by tscrim

  • Reviewers changed from Miguel Marco, Karl-Dieter Crisman, Frédéric Chapoton, Travis Scrimshaw, Søren Fuglede Jørgensen to Miguel Marco, Karl-Dieter Crisman, Frédéric Chapoton, Travis Scrimshaw, Søren Fuglede Jørgensen, John Palmieri
  • Status changed from needs_review to positive_review

comment:192 Changed 3 years ago by vbraun

  • Branch changed from public/ticket/17030 to 207d033813994705e75a22ef73b5b637a2b93085
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:193 follow-up: Changed 3 years ago by jhpalmieri

  • Commit 207d033813994705e75a22ef73b5b637a2b93085 deleted

See #20315 for a followup.

comment:194 in reply to: ↑ 193 Changed 3 years ago by jhpalmieri

Replying to jhpalmieri:

See #20315 for a followup.

In more detail, whoever is familiar with the plotting code should review the changes there.

comment:195 Changed 16 months ago by slelievre

Follow-up ticket at #25050: allow braid computation for more links.

Note: See TracTickets for help on using tickets.