sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.45k stars 481 forks source link

Knot Theory as a part of GSoC 2014. #17030

Closed amitjamadagni closed 8 years ago

amitjamadagni commented 10 years ago

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

CC: @miguelmarco @jhpalmieri @tscrim @fuglede

Component: algebraic topology

Author: Amit Jamadagni, Miguel Marco

Branch: 207d033

Reviewer: Miguel Marco, Karl-Dieter Crisman, Frédéric Chapoton, Travis Scrimshaw, Søren Fuglede Jørgensen, John Palmieri

Issue created by migration from https://trac.sagemath.org/ticket/17030

amitjamadagni commented 10 years ago

Branch: u/amitjamadagni/knots

amitjamadagni commented 10 years ago

Commit: 50abd99

amitjamadagni commented 10 years ago

Author: amitjamadagni, mmarco

amitjamadagni commented 10 years ago
comment:5

Things to do:

  1. Plot method needs to be added.
  2. ncomponents needs to be worked upon.
amitjamadagni commented 10 years ago

Reviewer: mmarco

miguelmarco commented 10 years ago
comment:8

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.

miguelmarco commented 10 years ago
comment:9

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?

amitjamadagni commented 10 years ago
comment:10

Replying to @miguelmarco:

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

e6e17c4Removed the messages in all.py
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 50abd99 to e6e17c4

tscrim commented 10 years ago

Changed reviewer from mmarco to Miguel Marco

tscrim commented 10 years ago

Changed author from amitjamadagni, mmarco to Amit Jamadagni, Miguel Marco

tscrim commented 10 years ago
comment:12

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

INPUT:

- ``name`` -- some description that is very long and
  note the alignment

OUTPUT:

- these are not usually complete sentences but short descriptions
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

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

jdemeyer commented 10 years ago
comment:13

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.

jdemeyer commented 10 years ago
comment:14

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

amitjamadagni commented 10 years ago
comment:15

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.

kcrisman commented 10 years ago
comment:16

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.

miguelmarco commented 10 years ago
comment:17

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.

miguelmarco commented 10 years ago
comment:18

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

kcrisman commented 10 years ago
comment:19

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.

tscrim commented 10 years ago
comment:20

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

miguelmarco commented 10 years ago
comment:21

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

4fb0409Few changes.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from e6e17c4 to 4fb0409

amitjamadagni commented 10 years ago
comment:23

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.

amitjamadagni commented 10 years ago
comment:24

Replying to @miguelmarco:

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

3dac5c0Changes.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 4fb0409 to 3dac5c0

jhpalmieri commented 10 years ago
comment:26

Regarding LaTeX, the following links (heh) might be helpful, although it doesn't look like they completely solve the problem:

miguelmarco commented 10 years ago

Changed branch from u/amitjamadagni/knots to u/mmarco/ticket/17030

miguelmarco commented 10 years ago

Changed commit from 3dac5c0 to 29be8b0

miguelmarco commented 10 years ago
comment:28

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
miguelmarco commented 10 years ago
comment:29

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?

amitjamadagni commented 10 years ago
comment:30

Replying to @miguelmarco:

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
amitjamadagni commented 10 years ago

Changed branch from u/mmarco/ticket/17030 to u/amitjamadagni/ticket/17030

miguelmarco commented 10 years ago

Changed commit from 29be8b0 to c020d91

miguelmarco commented 10 years ago
comment:32

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.
miguelmarco commented 10 years ago
comment:33

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.

amitjamadagni commented 10 years ago
comment:34

Replying to @miguelmarco:

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.

videlec commented 10 years ago
comment:35

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

amitjamadagni commented 10 years ago
comment:36

Replying to @videlec:

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.

videlec commented 10 years ago
comment:37

Replying to @amitjamadagni:

Replying to @videlec:

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

amitjamadagni commented 10 years ago
comment:38

Replying to @videlec:

Replying to @amitjamadagni:

Replying to @videlec:

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.

miguelmarco commented 10 years ago
comment:39

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from c020d91 to 0133305

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

0133305Edits in the `__init__` method.
jhpalmieri commented 10 years ago
comment:41

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

diff --git a/src/doc/en/reference/index.rst b/src/doc/en/reference/index.rst
index 662a079..c5e2211 100644
--- a/src/doc/en/reference/index.rst
+++ b/src/doc/en/reference/index.rst
@@ -69,6 +69,7 @@ Geometry and Topology
 * :doc:`Cell Complexes and their Homology <homology/index>`
 * :doc:`Differential Forms <tensor/index>`
 * :doc:`Parametrized Surfaces <riemannian_geometry/index>`
+* :doc:`Knot Theory <knots/index>`

 Number Theory, Algebraic Geometry
 ---------------------------------
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
--- /dev/null
+++ b/src/doc/en/reference/knots/conf.py
@@ -0,0 +1 @@
+../conf_sub.py
\ No newline at end of file
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
--- /dev/null
+++ b/src/doc/en/reference/knots/index.rst
@@ -0,0 +1,9 @@
+Knot theory
+===========
+
+.. toctree::
+   :maxdepth: 2
+
+   sage/knots/link
+
+.. 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:

diff --git a/src/sage/knots/link.py b/src/sage/knots/link.py
index 6259df0..3ed2dd6 100644
--- a/src/sage/knots/link.py
+++ b/src/sage/knots/link.py
@@ -44,18 +44,18 @@ class Link:
       2. Oriented Gauss Code
       3. Planar Diagram Code

-      EXAMPLES::
-
-          sage: B = BraidGroup(8)
-          sage: L = Link(B([1, 2, 1, -2,-1]))
-          sage: L
-          Link with 2 components represented by 5 crossings
-          sage: L = Link([[[-1, +2, -3, 4, +5, +1, -2, +6, +7, 3, -4, -7, -6,-5]],[-1, -1, -1, -1, 1, -1, 1]])
-          sage: L
-          Knot represented by 7 crossings
-          sage: L = Link([[1,8,2,7],[8,4,9,5],[3,9,4,10],[10,1,7,6],[5,3,6,2]])
-          sage: L
-          Link with 2 components represented by 5 crossings
+    EXAMPLES::
+
+        sage: B = BraidGroup(8)
+        sage: L = Link(B([1, 2, 1, -2,-1]))
+        sage: L
+        Link with 2 components represented by 5 crossings
+        sage: L = Link([[[-1, +2, -3, 4, +5, +1, -2, +6, +7, 3, -4, -7, -6,-5]],[-1, -1, -1, -1, 1, -1, 1]])
+        sage: L
+        Knot represented by 7 crossings
+        sage: L = Link([[1,8,2,7],[8,4,9,5],[3,9,4,10],[10,1,7,6],[5,3,6,2]])
+        sage: L
+        Link with 2 components represented by 5 crossings
     """

     def __init__(self, data):
@@ -70,6 +70,8 @@ class Link:

         Generators of the braid group are used to generate the link.

+        EXAMPLES::
+
             sage: B = BraidGroup(8)
             sage: L = Link(B([-1, -1, -1, -2,1, -2,3,-2,3]))
             sage: L
@@ -92,6 +94,8 @@ class Link:
         anti-clockwise, -1 if the direction from the leaving over-cross to the
         leaving under-cross is clockwise.

+        EXAMPLES::
+
             # for knots there is only a single component so the input is as follows
             sage: L = Link([[[-1, +2, 3, -4, 5, -6, 7, 8, -2, -5, +6, +1, -8, -3, 4, -7]],[-1,-1,-
             sage: L
@@ -240,8 +244,10 @@ class Link:
         r"""
         Return the oriented gauss code of the link. The oriented gauss
         code has two parts
+
         a. The gauss code
         b. The orientation of each crossing
+
         The following orientation was taken into consideration for consturction
         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)
------------------------------------------------------------------------
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 0133305 to c3bedaa

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

c3bedaaFlatten used. WIP: docs and other methods.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from c3bedaa to 1613a32