Draw programme

Last modified 10th May, 2020

1. Introduction

The draw programme generates metapost code to draw diagrams from labelled peer codes. It is currently able to draw a variety of knots and links: classical, virtual, welded and flat, and (multi-)knotoids, which was the original motivation.

The programme can also draw a set of smoothed states for a given diagram, as used by various invariants based on state sums, or the convex triangulation of a disc determined by a peer code.

This page contains the following sections:

  1. Overall Description

    Controlling programme behaviour

    The draw programme software

  2. Drawing knots and knotoids

    Labelled peer codes for knotoids

  3. Draw programme command syntax

    Input file format

  4. Example diagrams

  5. Smoothed states

  6. References

2. Overall Description

The default drawing algorithm is one based on circle packing taken from the drawing routine in Knotscape, by Jim Hoste and Morwen Thistlethwaite, and in particular Ken Stephenson's implementation of Thurston's circle packing algrithm.

My code provides the environment to read peer codes from an input stream, then applies the algorithms of Knotscape to produce a sequence of coordinates at key points as we traverse the underlying immersion. Armed with these coordinates it is a simple matter to produce metapost output that can draw the immersion with the appropriate over, under and virtual crossings, knotoid shortcuts, and so on.

Specifically, the following key aspects have been taken from Knotscape. I am very grateful to the authors of Knotscape for making this code available in the public domain and fully acknowledge all rights they may have in that code and it's methods.

  1. triangulate.c - I have written code to produce the same triangulation as described in this Knotscape module starting from a labelled peer code. The output of my code is a file with the same file format as that produced by the Knotscape version. Starting with a labelled peer code allows my code to support links and non-prime diagrams, unlike Knotscape.
  2. ken.c - Initially, I simply integrated this Knotscape module into my code, having renamed it KS_circle_pack.c and added some comments and optional debug output. Later, I ported KS_circle_pack.c to C++, taking some ideas from another circle packing algorithm implemented in circle_pack.cpp but retaining Stephenson's algorithm. See the comments at the top of KS_circle_pack.cpp for more details.
  3. nodeseq.c - this module has been re-written to take into account the fact that the sequence of vertices I am interested in is determined by a labelled peer code; also, the use of metapost means I do not need all of the coordinates used by Knotscape. Thus, my nodeseq is a form of the corresponding Knotscape model optimized for peer codes, however, as with the other modules above, the algorithms (in particular the coordinate scaling algorithm) are all taken from Knotscape.
  4. badness - I have incorporated the same assessment of a set of coordinates as used by Knotscape via the badness function but have provided the option to control the location of the point at infinity explicitly.
In addition to the above, wherever the Knotscape original modules call auxiliary functions I have written corresponding functions in support of my versions. These are also acknowledged effectively to have been taken directly from Knotscape.

Various other drawing algorithms are available as options to the draw programme, these are largely experimental in nature and were produced in an effort to explore alternatives to circle packing in an attempt to draw aesthetic diagrams for those cases where circle packing creates a tightly knotted part of the diagram. There are options included for investigating the behaviour of the drawing algorithms, such as drawing the triangulation, tracing the progress of force directed placement algorithms etc. that may be ignored by most users.

Controlling programme behaviour

There are a number of command line options available to adjust things like the overall scale of the diagram (the u or unit option), the size of the discs added to create over and under crossings, or to designate virtual crossings (the d or disc-size option), or to designate the use of TeX's mathematics "script size" or "scriptscript size" font for semi-arc labels (the script-labels and scriptscript-labels options).

If the diagram results in metapost coordinates that are too large, the metapost_coordinate_scale_factor used by the programme may be adjusted using the M option. Simple help information is available by starting the programme with the command "draw -h", a full list of options may be seen by starting the programme with the command "draw -H!"

See the section Draw programme command syntax for more details.

The draw programme software

The file draw-release-10-5-20.tar contains the C++ source for the draw programme, together with a Makefile and a test input file.

3. Drawing knots and knotoids

The draw programme takes as input a labelled peer code description of a knot, link or knotoid, either from the command line or from an input file. Full details of labelled peer codes are provided in the paper labelled-peer-code.pdf. Here we provide only a brief description.

A labelled peer code for a virtual (or classical) link (knot) diagram is obtained from the underlying immersion by choosing an arbitary starting component and semi-arc and numbering each semi-arc of that component consecutively from zero as we trace around the component. When we return to the starting semi-arc we move onto another component and continue the numbering. We require that each time we start a new component we choose one that has a crossing involving a strand belonging to a component that has already been numbered. We also require that we start the numbering of the new component on a semi-arc that ensures that the first crossing we encounter involving a previously numbered strand has both an odd and an even numbered incoming semi-arc, with respect to the orientation induced by the numbering. It is always possible to construct such a numbering, as described in the document referenced above. We view the immersion as a 4-regular plane graph. The numbering results in every vertex having an even and odd numbered terminating edge and an even and odd numbered originating edge with respect to the induced orientation. The two edges terminating at a common vertex are called peer edges.

If the immersion has n vertices, the graph has 2n edges and the peer edges are of the form 2i, 2j-1 (taken mod 2n) for some integers i and j in the range 0,...n-1. The value of i determines a numbering for the vertex (and corresponding crossing) at which edge 2i terminates. We therefore refer to the even edge as the naming edge for the corresponding crossing.

Further, the peer edges will be oriented around the vertex so that the odd edge is located adjacent to the even edge in a clockwise or anticlockwise direction. We call crossings of the first type Type 1 crossings and of the second type Type 2 crossings.

The first part of a labelled peer code is comprised of a list of the odd-numbered peers in the order determined by the vertex numbering. The list is separated by commas into the peers of naming edges that are associated with the same component of the link.

For example, for the immersion and edge numbering shown in the figure above, the list of odd peers is

11 9, 3 1 13 5 7

The list of odd peers may be supplemented to record the type of each crossing by writing each odd peer associated with a Type I crossing as a negative number. Thus, for the diagram above we get

-11 9, -3 1 -13 5 -7

we refer to this code as a peer code.

The second part of a labelled peer code provides information about the original link diagram. For classical crossings we assign the label + if the naming edge forms part of the over-arc of the crossing and the label - if it forms part of the under-arc. For virtual or welded crossings we assign the label * and for flat crossings we assign the label #.

These labels are writen after the list of odd peers separated by a / character. They are written in the order determined by the vertex numbering. Thus continuing the above example if the original link diagram is as follows:

then the full labelled peer code is

-11 9, -3 1 -13 5 -7 / + - - + - + -

For the purposes of distinguishing labelled peer codes from other codes when using a computer the peer code will be enclosed in square brackets, as follows:.

[-11 9, -3 1 -13 5 -7] / + - - + - + -

Labelled peer codes for knotoids

To represent a knotoid we draw a shortcut from the head to the leg comprised of under-crossings, whereupon we may obtain an immersion as before. We then determine the peer code by starting with the edge containing the leg of the knotoid and proceed along the knotoid to the head and then along the shortcut. We identify the first crossing created by adding the shortcut by writing the ^ character after the odd peer at that crossing in the first part of the peer code. We attach labels to a knotoid's peer code in the same manner as we do with links.

The following is an example of a labelled peer code for a knotoid.

[-7 13 -11 -1 3 -5 9^ ]/+ + - + + - -

Note that the ^ character uniquely identifies the head since there is a unique edge entering each crossing as part of the under-arc.

4. Draw programme command syntax

The command syntax for the programme draw is as follows:

Usage draw [--<programme-option>][-<metapost-control>][<infile>[<outfile>]]

The programme reads labelled peer codes from the <infile>, or from a command prompt if no <infile> is provided, and then evaluates a triangulation of the disc determined by the immersion underlying the peer code.

By default, the programme uses Ken Stephenson's circle packing algorithm to place the vertices of the triangulation. Alternatively one of the following long programme options may be used to select a different vertex placement technique.

Once the vertices have been positioned, the programme creates a metapost script describing the diagram in <outfile>, or in the file draw.out if no <outfile> is provided.

The supported programme-option and metapost-control options are:

  convex: draw the convex, straight line triangulation of a disc
  edge[=<max-iterations>] default 200: use edge distribution placement
  force[=<max-iterations>] default 200: use Plestenjak force directed placement
  gravity[=<max-iterations>] default 200: use centre of gravity placement
  magnify[=<percentage>] default 0: magnify small circles in circle packing by specified percentage
  shrink[=<max-iterations>] default 200: use region shrinking placement after circle packing
  small-shrink[=<max-iterations>]: use small region shrinking placement after circle packing
  smoothed: draw all of the smoothed states for the given diagram

  c=<centre>: specify the centre of rotation <centre> = (<x>,<y>)|z<n>
  C=<cycle>: specify the turning cycle to bound the infinite region
  D: set the smoothed state disc size multiplier to determine the size of smoothed crossings n*d (default n=6)
  d: set the unit multiplier to determine the crossing disc diameter (default 30)
  F: do not draw the crossing features
  h: help screen
  I: do not draw the immersion (consider using F option also)
  k: draw knotoids with the leg in the unbounded component of the immersion's complement
  l: add edge labels to the diagram
  o: draw orientation for knots (orientation always shown for knotoids)
  p: set the pen multiplier n to determine the pencircle scale n*0.5pt (default n=1)
  P: draw the underlying circle packing that determines the diagram
  r=<degrees>: rotate the diagram anti-clockwise by the specified number of degrees
  S: draw the shortcut if the code describes a knotoid
  t: draw the triangulation of the unit disc
  u: set the unit dimension nn to determine u=0.nn points (default 20)
  v: label the vertices and draw coordinate axes

The short <metapost-control> options have corresponding long options, useful for including in input files as global options or as qualifiers (see the section Input file format):

  centre=<centre>: specify the centre of rotation <centre> = (<x>,<y>)|z<n>
  cycle=<cycle>: specify the turning cycle to bound the infinite region
  dots: draw knotoid shortcuts dashed with dots rather than dashed evenly
  disc-size: set the unit multiplier to determine the crossing disc diameter (default 30)
  knotoid-leg-unbounded: draw knotoids with the leg in the unbounded component of the immersion's complement
  labels: add edge labels to the diagram
  no-crossings: do not draw the crossing features
  no-immersion: do not draw the immersion
  oriented: draw orientation for knots (orientation always shown for knotoids)
  packing: draw the underlying circle packing that determines the diagram
  pen-size: set the pen multiplier n to determine the pencircle scale n*0.5pt (default n=1)
  rotate=<degrees>: rotate the diagram anti-clockwise by the specified number of degrees
  shortcut: draw the shortcut if the code describes a knotoid
  triangulation: draw the triangulation of the unit disc
  unit: set the unit dimension nn to determine u=0.nn points (default 20)
  vertices: label the vertices and draw coordinate axes

additional long options:

  edge-factor=<float> default 0.5: amount by which vertices are moved towards the COG in edge distribution placement
  first-gap: always use the first gap as the active gap in edge distribution placement
  frame-corners: show frame corners when tracking placement iteration
  hyperbolic: drawing diagram in the hyperbolic plane
  no-vertex-axes: do not show the axes when labelling the vertices of a diagram
  no-show-displacement: do not show the triangulation displacement when tracking placement iteration
  plot=<divisions>: set the number of divisions for the histogram in edge distribution placement (default 20)
  script-labels: label vertices using TeX's script size font
  scriptscript-labels: label vertices using TeX's scriptscript size font
  show-shrink: draw the effect of shrinking the triangulation when using region shrinking placement
  show-small: highlight the small edges of the triangulation when using edge_distribution placement
  shrink-factor=<float> default 0.75: amount by which region shrinking placement retracts trianglulation
                                      vertices towards the barycentre
  shrink-area-factor=<float> default 1.618034: region shrinking placement converges if all compact regions
                                               have an area within this factor of their average area
  smoothed-disc-size: set the smoothed state disc size multiplier to determine the size of smoothed crossings n*disc-size (default n=6)  
  tension: set the metapost path tension, default value 1.0, i.e. the metapost ".." default

additional short options:

  #: debug
  a=<float> default 1.0: average triangulation edge length factor
     used to magnify edge vertices closer than a*average_triangulation_edge_length
  A: adjust the angle of diagram arcs at crossings to be right angles
  b: do not use badness optimization
  B: include boundary vertices; may be used with f, g, P, or t.
     Boundary vertices are alway included in force directed placement,
     in which case this option only has an efect if the t option is also used.
  E: use edge repulsion rather than Plestenjak force directed placement
  i[=<max-iterations>] default 1000: set maximum circle packing iterations
  H!: additional help screen
  #H!: display debug help screen
  K: use Fenn's circle packing algorithm rather than Ken Stephenson's
  L: start from one when labelling edges
  M=<scale_factor> : set metapost_coordinate_scale_factor: default 2500 with the circle packing
     option, 1000 with force or gravity placement, 600 with the convex-disc option, 25 otherwise
  O: create metapost with one cycled path for each component
  P: draw circle packing
  R=<float>: retract boundary vertices radially towards their centroid by a factor <float> < 1
  T[=<track-step>] default 1: track placement iteration (force, gravity, shrink)
  V[=<vertex>] default 0: check inner hull calculation of <vertex>
  x=[0|1|2|3] default 0: set debug level for Stephenson circle packing

The overlap between long options and short options is designed to provide a convenient mechanism for setting programme defaults from the command line as well as an intuitive approach to creating input files (see below)

By default the draw programme produces metapost code based on the following metapost parameters

Input file format

Multiple peer codes may be included in the inputfile, written on different lines. Default options to be applied to all the codes in the file may be specified from the command line using long or short options. Alternatively, defaults may be included within the file by specifying one or more long options within square brackets, separated by commas, as in [unit=30,labels]. It is possible to override the defaults on a per-code basis by including qualifiers after a peer code. Qualifiers are long options, separated by commas, included within braces {}

The input file may contain comments by inserting the ; character anywhere on a line. Titles may be included by starting a line with -- to allow names to be given to peer codes. An example input file is:

; here is an example input file

[oriented, unit=30] ; set the defaults for these codes

-- an example of a flat knot; this is a comment on a title line
[-5 -7 -1 -9 -3]/#####
-- a rotated knotoid
[-7 13 -11 -1 3 -5 9^ ]/+ + - + + - - {rotated=45, centre=z4}

In the above example a diagram is rotated by 45 degrees about z4. The default centre of rotation is determined from the minumum and maximum x-coordinates and y-coordinades, the midpoint of each being used to determine the centre of rotation. In the above example an explicit centre of rotation is given as one of the vertices used to draw the diagram. The metapost path created for each diagram has a vertex at each crossing and a vertex at the midpoint of each semi-arc. A diagram with the vertices labelled may be drawn using the long option vertices or the short option v (see below for an example). Alternatively, an explicit centre of roatation may be specified by giving the exact x and y coordinates.

5. Example diagrams

Some examples of the diagrams that the programme can produce are shown below, these pictures are png format files that have been produced, and scaled, using Ghostscript for presentation on this page.

The following is an example of the diagram resulting from the metapost code produced by the draw programme for the virtual knot

[-5 7 9 -11 3 1 ]/+ + * + + +

A more complex example is the link l11n455, which has peer code

[-7 39 -53 27 15 35 -47, 13 -43 37 -45, 49 -33 -21 -41 5 19 11 -23 -51 -29 1, -31 25 -9 -17 -3]/- + - + - + + - + + + + + + + - - - - + - - + - - + -

Using the --oriented/-o option adds the orientation determined by the immersion code:

Using the --label/-l option produces labels on the edges of the diagram:

Using the --vertices/-v option produces a diagram with coordinate axes and vertex labels, intended in case the Metapost code requires manual editing:

The following is an example of the diagram resulting from the metapost code produced by the draw programme for the knotoid

[-7 13 -11 -1 3 -5 9^ ]/+ + - + + - -

If the --knotoid/-k option is used the leg appears in the unbounded component of the knotoid complement, however, as in the following example this does not always produce an aesthetic result.

If the --shortcut/-s option is used the shortcut is drawn:

When deciding how to arrange the vertices in a diagram the draw programme must make a choice of where to place the unbounded component of the underlying immersions complement. Put another way, if we imagine the diagram drawn on a 2-sphere, the programme has to choose in which region to place the point at infinity. By default, the choice is made by selecting the region whose boundary contains the largest number of edges. As described above, for knotoids the knotoid or k option overrides this choice by choosing the region whose boundary includes the edge labelled zero (which contains the leg of the knotoid. For knots and links it is also possible to influence this choice using the cycle or C option. In the metapost file produced by the draw programme, each figure is prefixed by the title (if one has been provided), the peer code, and a list of left and right turning cycles. These list the semi-arcs in the boundary of the regions making up the diagram's complement. An example of this information is:

% -- Example immersion
% [4 8 0 2 6]/# # # # #
% left turning cycles:
% cycle 0: 0 6
% cycle 1: -1 -5
% cycle 2: 2 8 4
% cycle 3: -3 -7 -9
% right turning cycles:
% cycle 4: 0 -5 2 -7
% cycle 5: -1 6 -9 4
% cycle 6: -3 8

See labelled-peer-code.pdf for an explanation of the minus signs in this output.

From this information it is possible to select a particular turning cycle if required. For example, the peer code

[5 7 1 9 3]/##### {labels}

produces the following immersion diagram

and the turning cycle information shown above. If we select cycle 2 and use the qualifier:

[5 7 1 9 3]/##### {labels,cycle=2}

we produce the following diagram.

Note: sometimes the Metapost code produced by the draw programme results in Metapost producing postscript files with negative bounding box values. For some programmes it is therefore necessary to add the following line to these postscript files

<x-shift> <y-shift> translate

where <x-shift> and <y-shift> are chosen so the lower-left bounding box coordinates are non-negative.

6. Smoothed states

There are several invariants based on state sums for which it is sometimes useful to generate pictures of the smoothed states for an example diagram. By using the smoothed programme option, the draw programme will produce metapost code for all of the smoothed states of each input code.

Only non-virtual crossings are smoothed, and in the case of knotoids, shortcut crossings are not smoothed. For the remaining crossings, the states range over all combinations of Seifert-smoothed and non-Seifert-smoothed choices for each crossing. A Seifert smoothed crossing is one for which the smoothed state corresponds to tracing the Seifert circles of the underlying diagram at that crossing.

The smoothed option produces a diagram of the original knot or knotoid, with semi-arcs labelled from zero as determined by the labelled peer code. Then produces state diagrams, identifying each non-Seifert-smoothed crossing by marking the crossing with a small black dot on each smoothed strand. Furthermore it labels each crossing with a state label as follows:

For some diagrams, the default size of the smoothed crossing is too large and causes metapost to complain about paths not intersecting. In this case, reducing the size of the smoothed crossing using the smoothed-disc-size or D option, or if necessary additionally adjusting the crossing disc size with the disc-size or d should resolve the situation.

The following is an example of a smoothed state for a knotoid that closes to the Slvik knot:

The full set of smoothed states for this knotoid are as follows:

7. References

Knotoids, Vladimir Turaev, arXiv:1002.4133v4.

back to maths homepage