Coverage for local/lib/python2.7/site-packages/sage/knots/link.py : 88%

r""" 

Links 

A knot is defined as embedding of the circle `\mathbb{S}^1` in the 

3-dimensional sphere `\mathbb{S}^3`, considered up to ambient isotopy. 

They represent the physical idea of a knotted rope, but with the 

particularity that the rope is closed. That is, the ends of the 

rope are joined. 

A link is an embedding of one or more copies of `\mathbb{S}^1` in 

`\mathbb{S}^3`, considered up to ambient isotopy. That is, a link 

represents the idea of one or more tied ropes. Every knot is a link, 

but not every link is a knot. 

Generically, the projection of a link on `\RR^2` is a curve with 

crossings. The crossings are represented to show which strand goes 

over the other. This curve is called a planar diagram of the link. 

If we remove the crossings, the resulting connected components are 

segments. These segments are called the edges of the diagram. 

REFERENCES: 

- :wikipedia:`Knot_(mathematics)` 

- [Col2013]_ 

- [KnotAtlas]_ 

.. SEEALSO:: 

There are also tables of link and knot invariants at 

http://www.indiana.edu/~knotinfo/ 

and http://www.indiana.edu/~linkinfo/. 

AUTHORS: 

- Miguel Angel Marco Buzunariz 

- Amit Jamadagni 

""" 

#***************************************************************************** 

# Copyright (C) 2014 Miguel Angel Marco Buzunariz 

# Amit Jamadagni 

# 

# This program is free software: you can redistribute it and/or modify 

# it under the terms of the GNU General Public License as published by 

# the Free Software Foundation, either version 2 of the License, or 

# (at your option) any later version. 

# http://www.gnu.org/licenses/ 

#***************************************************************************** 

from __future__ import division 

from six.moves import range 

from sage.matrix.constructor import matrix 

from sage.rings.integer_ring import ZZ 

from sage.graphs.digraph import DiGraph 

from sage.graphs.graph import Graph 

from sage.rings.polynomial.laurent_polynomial_ring import LaurentPolynomialRing 

from sage.symbolic.ring import SR 

from sage.rings.integer import Integer 

from sage.numerical.mip import MixedIntegerLinearProgram 

from sage.functions.generalized import sign 

from sage.homology.chain_complex import ChainComplex 

from sage.misc.flatten import flatten 

from sage.misc.lazy_attribute import lazy_attribute 

from sage.misc.cachefunc import cached_method 

from copy import deepcopy, copy 

from itertools import combinations 

class Link(object): 

r""" 

A link. 

A link is an embedding of one or more copies of `\mathbb{S}^1` in 

`\mathbb{S}^3`, considered up to ambient isotopy. That is, a link 

represents the idea of one or more tied ropes. Every knot is a link, 

but not every link is a knot. 

A link can be created by using one of the conventions mentioned below: 

Braid: 

- The closure of a braid is a link:: 

sage: B = BraidGroup(8) 

sage: L = Link(B([-1, -1, -1, -2, 1, -2, 3, -2, 3])) 

sage: L 

Link with 1 component represented by 9 crossings 

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

sage: L 

Link with 2 components represented by 5 crossings 

.. NOTE:: 

The strands of the braid that have no crossings at all 

are removed. 

- Oriented Gauss Code: 

Label the crossings from `1` to `n` (where `n` is the number of 

crossings) and start moving along the link. Trace every component of 

the link, by starting at a particular point on one component of the 

link and writing down each of the crossings that you encounter until 

returning to the starting point. The crossings are written with sign 

depending on whether we cross them as over or undercrossing. Each 

component is then represented as a list whose elements are the 

crossing numbers. A second list of `+1` and `-1`'s keeps track of 

the orientation of each crossing:: 

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

....: [-1, -1, -1, -1, 1, 1, -1, 1]]) 

sage: L 

Link with 1 component represented by 8 crossings 

For links there may be more than one component and the input is 

as follows:: 

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

sage: L 

Link with 3 components represented by 4 crossings 

- Planar Diagram (PD) Code: 

The diagram of the link is formed by segments that are adjacent to 

the crossings. Label each one of this segments with a positive number, 

and for each crossing, write down the four incident segments. The 

order of these segments is clockwise, starting with the incoming 

undercrossing. 

There is no particular distinction between knots and links for 

this input. 

EXAMPLES: 

One of the representations of the trefoil knot:: 

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

sage: L 

Link with 1 component represented by 3 crossings 

.. PLOT:: 

:width: 300 px 

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

sphinx_plot(L.plot()) 

One of the representations of the Hopf link:: 

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

sage: L 

Link with 2 components represented by 2 crossings 

.. PLOT:: 

:width: 300 px 

L = Link([[1, 4, 2, 3], [4, 1, 3, 2]]) 

sphinx_plot(L.plot()) 

We can construct links from the braid group:: 

sage: B = BraidGroup(4) 

sage: L = Link(B([-1, -1, -1, -2, 1, -2, 3, -2])) 

sage: L 

Link with 2 components represented by 8 crossings 

.. PLOT:: 

:width: 300 px 

B = BraidGroup(4) 

L = Link(B([-1, -1, -1, -2, 1, -2, 3, -2])) 

sphinx_plot(L.plot()) 

:: 

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

sage: L 

Link with 2 components represented by 4 crossings 

.. PLOT:: 

:width: 300 px 

B = BraidGroup(4) 

L = Link(B([1, 2, 1, 3])) 

sphinx_plot(L.plot()) 

We construct the "monster" unknot using a planar code, and 

then construct the oriented Gauss code and braid representation:: 

sage: L = Link([[3,1,2,4], [8,9,1,7], [5,6,7,3], [4,18,6,5], 

....: [17,19,8,18], [9,10,11,14], [10,12,13,11], 

....: [12,19,15,13], [20,16,14,15], [16,20,17,2]]) 

sage: L.oriented_gauss_code() 

[[[1, -4, 3, -1, 10, -9, 6, -7, 8, 5, 4, -3, 2, -6, 7, -8, 9, -10, -5, -2]], 

[1, -1, 1, 1, 1, -1, -1, -1, -1, -1]] 

sage: L.braid() 

s0*s1^-1*s2^-1*s3^-1*s2*s1^-1*s0^-1*s1*s2^2*s1^-1*s3*s2*s1^-3 

.. PLOT:: 

:width: 300 px 

L = Link([[3,1,2,4],[8,9,1,7],[5,6,7,3],[4,18,6,5], 

[17,19,8,18],[9,10,11,14],[10,12,13,11], 

[12,19,15,13],[20,16,14,15],[16,20,17,2]]) 

sphinx_plot(L.plot()) 

We construct the Ochiai unknot by using an oriented Gauss code:: 

sage: L = Link([[[1,-2,-3,-8,-12,13,-14,15,-7,-1,2,-4,10,11,-13,12, 

....: -11,-16,4,3,-5,6,-9,7,-15,14,16,-10,8,9,-6,5]], 

....: [-1,-1,1,1,1,1,-1,1,1,-1,1,-1,-1,-1,-1,-1]]) 

sage: L.pd_code() 

[[10, 2, 11, 1], [2, 12, 3, 11], [3, 20, 4, 21], [12, 19, 13, 20], 

[21, 32, 22, 1], [31, 22, 32, 23], [9, 25, 10, 24], [4, 29, 5, 30], 

[23, 30, 24, 31], [28, 14, 29, 13], [17, 14, 18, 15], [5, 17, 6, 16], 

[15, 7, 16, 6], [7, 27, 8, 26], [25, 9, 26, 8], [18, 28, 19, 27]] 

.. PLOT:: 

:width: 300 px 

L = Link([[[1,-2,-3,-8,-12,13,-14,15,-7,-1,2,-4,10,11,-13,12, 

-11,-16,4,3,-5,6,-9,7,-15,14,16,-10,8,9,-6,5]], 

[-1,-1,1,1,1,1,-1,1,1,-1,1,-1,-1,-1,-1,-1]]) 

sphinx_plot(L.plot()) 

We construct the knot `7_1` and compute some invariants:: 

sage: B = BraidGroup(2) 

sage: L = Link(B([1]*7)) 

.. PLOT:: 

:width: 300 px 

B = BraidGroup(2) 

L = Link(B([1]*7)) 

sphinx_plot(L.plot()) 

:: 

sage: L.alexander_polynomial() 

t^-3 - t^-2 + t^-1 - 1 + t - t^2 + t^3 

sage: L.jones_polynomial() 

-t^10 + t^9 - t^8 + t^7 - t^6 + t^5 + t^3 

sage: L.determinant() 

7 

sage: L.signature() 

-6 

The links here have removed components in which no strand is used:: 

sage: B = BraidGroup(8) 

sage: b = B([1]) 

sage: L = Link(b) 

sage: b.components_in_closure() 

7 

sage: L.number_of_components() 

1 

sage: L.braid().components_in_closure() 

1 

sage: L.braid().parent() 

Braid group on 2 strands 

.. WARNING:: 

Equality of knots is done by comparing the corresponding braids, 

which may give false negatives. 

.. NOTE:: 

The behavior of removing unused strands from an element of a 

braid group may change without notice in the future. Do not 

rely on this feature. 

.. TODO:: 

Implement methods to creating new links from previously created links. 

""" 

def __init__(self, data): 

""" 

Initialize ``self``. 

TESTS:: 

sage: B = BraidGroup(8) 

sage: L = Link(B([-1, -1, -1, -2,1, -2, 3, -2])) 

sage: TestSuite(L).run() 

sage: L = Link(B([1, 2, 1])) 

sage: TestSuite(L).run() 

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

sage: TestSuite(L).run() 

sage: L = Link(B.one()) 

sage: L = Link([]) 

sage: L = Link([[], []]) 

sage: Link([[[-1, 2, -1, 2]], [1, 1, 1, 1]]) 

Traceback (most recent call last): 

... 

ValueError: invalid input: data is not a valid oriented Gauss code 

sage: Link([[[-1, 2, 3, 4]]]) 

Traceback (most recent call last): 

... 

ValueError: invalid PD code: crossings must be represented by four segments 

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

Traceback (most recent call last): 

... 

ValueError: invalid PD code: each segment must appear twice 

sage: L = Link(5) 

Traceback (most recent call last): 

... 

ValueError: invalid input: data must be either a list or a braid 

""" 

if isinstance(data, list): 

if len(data) != 2 or not all(isinstance(i, list) for i in data[0]): 

for i in data: 

if len(i) != 4: 

raise ValueError("invalid PD code: crossings must be represented by four segments") 

else: 

flat = flatten(data) 

if any(flat.count(i) != 2 for i in set(flat)): 

raise ValueError("invalid PD code: each segment must appear twice") 

self._pd_code = data 

self._oriented_gauss_code = None 

self._braid = None 

else: 

flat = flatten(data[0]) 

if flat: 

a, b = max(flat), min(flat) 

if 2 * len(data[1]) != len(flat) or set(range(b, a + 1)) - set([0]) != set(flat): 

raise ValueError("invalid input: data is not a valid oriented Gauss code") 

self._oriented_gauss_code = data 

self._pd_code = None 

self._braid = None 

else: 

from sage.groups.braid import Braid, BraidGroup 

if isinstance(data, Braid): 

# Remove all unused strands 

support = sorted(set(abs(x) for x in data.Tietze())) 

i = 0 

cur = 1 

while i < len(support): 

if support[i] == cur: 

cur += 1 

i += 1 

elif support[i] == cur + 1: 

support.insert(i, cur+1) 

cur += 2 

i += 2 

else: 

cur = support[i] 

i += 1 

d = {} 

for i,s in enumerate(support): 

d[s] = i+1 

d[-s] = -i-1 

if not support: 

B = BraidGroup(2) 

else: 

B = BraidGroup(len(support)+1) 

self._braid = B([d[x] for x in data.Tietze()]) 

self._oriented_gauss_code = None 

self._pd_code = None 

else: 

raise ValueError("invalid input: data must be either a list or a braid") 

def arcs(self, presentation='pd'): 

r""" 

Return the arcs of ``self``. 

Arcs are the connected components of the planar diagram. 

INPUT: 

- ``presentation`` -- one of the following: 

* ``'pd'`` - the arcs are returned as lists of parts in the PD code 

* ``'gauss_code'`` - the arcs are returned as pieces of the Gauss 

code that start with a negative number, and end with the 

following negative one; of there exist a closed arc, 

it is returned as a list of positive numbers only 

OUTPUT: 

A list of lists representing the arcs based upon ``presentation``. 

EXAMPLES:: 

sage: K = Knot([[[1,-2,3,-1,2,-3]],[1,1,1]]) 

sage: K.arcs() 

[[1, 2], [3, 4], [5, 6]] 

sage: K.arcs(presentation='gauss_code') 

[[-3, 1, -2], [-2, 3, -1], [-1, 2, -3]] 

:: 

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

sage: L.arcs() 

[[2, 4], [1], [3]] 

sage: L.arcs(presentation='gauss_code') 

[[-2, -1], [-1, -2], [2, 1]] 

sage: L.gauss_code() 

[[-1, -2], [2, 1]] 

""" 

if presentation == 'pd': 

G = DiGraph() 

for e in set(flatten(self.pd_code())): 

G.add_vertex(e) 

for cr in zip(self.pd_code(), self.orientation()): 

if cr[1] == 1: 

G.add_edge(cr[0][1], cr[0][3]) 

else: 

G.add_edge(cr[0][3], cr[0][1]) 

res = [] 

for S in G.connected_components_subgraphs(): 

check = S.is_directed_acyclic(certificate=True) 

if check[0]: 

source = S.sources()[0] 

sink = S.sinks()[0] 

res.append(S.shortest_path(source, sink)) 

else: 

res.append(check[1]) 

return res 

elif presentation == 'gauss_code': 

res = [] 

for comp in self.gauss_code(): 

if not any(i<0 for i in comp): 

res.append(comp) 

else: 

rescom = [] 

par = [] 

for i in comp: 

par.append(i) 

if i<0: 

rescom.append(copy(par)) 

par = [i] 

rescom[0] = par + rescom[0]