main page

The Planar Enumerator

1 Introduction

The Planar Enumerator is designed to enumerate objects that have a planar presentation, such as knots, links, tangles, and 2D surfaces in .  It does this by first generating all the planar diagrams of a given complexity (the number of crossings for knots) and then finding out which of them are isomorphic to each other by finding relations between them (Reidemeister moves for knots).  The final result is hopefully just one diagram from each isomorphism class.

At this point, however, the program is fairly slow and requires a lot of memory to run for higher complexities.  It still accomplishes its task though.

2 Installation

The Planar Enumerator is written primarily in C, but requires Mathematica as well.  The front end is done in Mathematica.

To install, obtain the tar archive planarenumerator.tar.gz and extract it to some directory.  You then need to put the files "mathlink.h" and "libML.a" from your Mathematica installation into this directory.  For my setup, they can be found in the directory "/usr/local/Wolfram/Mathematica/4.2/AddOns/MathLink/DeveloperKit/Linux/CompilerAdditions", but that could certainly be different for your installation.

Once you have the files, simply type "make" at the command prompt, and the Planar Enumerator should compile.  You may want to edit the Makefile first to optimize it for your system.  Also, depending on the speed and memory of your computer, you might want to increase "MAXPDS", found in the file "planarenumerator.h".  That variable decides how much memory to allocate the for the planar diagrams.  I have it set to 2000000 diagrams by default because my computer can't handle any more.

The following command loads the Planar Enumerator into Mathematica, as long as the file "PlanarEnumerator.m" is in your path.

Minor changes may be needed for your particular system in the Makefile or "PlanarEnumerator.m".  I have it configured for Linux, but if you wanted to run it in Windows, for example, you would need to change the name of the C executable from "pe" to "pe.exe".

3 "PD notation"

This section explains the notation used by the Planar Enumerator to represent planar diagrams.  We will use the example of knots.

The following represents the trefoil:

Each represents one of the vertices.  The numbers number the edges.  The first vertex represents the bottom left vertex in the diagram below.  For knots, the numbers go counterclockwise starting at an edge that goes 'under' at a crossing.

Of course, you could use any type of vertex you want (except that there is a maximum of 7 characters allowed).  But for this example of knots, we are using 's.

For each type of vertex you must specify three additional numbers: the complexity, the degree, and the symmetry.

•Complexity

The complexity for a knot vertex is the number of crossings that it represents.  So for an vertex, the complexity is 1.  Most vertices will have complexity 1.  It's when you come to relations, that complexities can be higher.

•Degree

The degree of a vertex is the number of edges that go out from it.  It's the same as the valency.  For an vertex the degree is 4.

•Symmetry

The symmetry of a vertex is a number that specifies how many times the vertex's list of numbers must be rotated before arriving at an equivalent vertex.  The symmetry must divide the degree.  For an vertex, the symmetry is 2.  This means that both and represent the same vertex.  However, represents a different vertex.

•Setting the values

To set the complexity, degree, and symmetry input the following:

•The 'p' vertex

There is a built-in vertex type called , for 'point'.  It has complexity 0, degree 2, and symmetry 1.  It is used to connect together two edges that have different edge numbers, and the Planar Enumerator will often eliminate it from your planar diagram and renumber the edges.

4 Canonical Form

The function CanonicalForm[] takes a planar diagram in 'PD notation' as input and it returns a canonical form of that planar diagram, where the edges have been renumbered and the vertices have been reordered.  The purpose is to be able to tell if two PDs are actually the same or not.  Here are some examples:

Notice that CanonicalForm[] removes vertices from PDs:

Lets add vertices to our types:

The previous PD was a cube.

5 Diagrams

The function Diagrams[complexity, vertices] produces all the non-isomorphic planar diagrams of a given total complexity and with vertices of a given type(s).  They are all returned in canonical form.

Instead of specifying , you can write 'Several X', to allow zero or more 's, such that the total complexity is still the first argument to Diagrams[].

'Several' is more useful when you want to combine 2 or more types of vertices, with some total complexity.

•Loops

There is the option to turn off loops for any vertex type.  Just set to turn them off, and to turn them back on.  By default they are on.  Turning them off saves a lot of time and greatly reduces the number of PDs produced.

6 Relations

Relations are the moves that are allowed to be performed on parts of planar diagrams, and give you planar diagrams that are different from what you started with, but that represent the same object.  For example, with knots and links, the relations are the Reidemeister moves: R1, R2, and R3.

Continuing with the knots and links example, here's how to specify R1, R2, and R3.

We need to specify both the left hand side and the right hand side of this relation.

Notice that in the first line, we have .  The 'c' is so that the program can give a number to the new edge.  The second and fourth lines of the statement specify how many new edges each side has.

For each relation, you must also specify the complexity, degree, and symmetry as with ordinary vertices.  The complexity should be set to the complexity of the higher complexity side.

Here's the other two Reidemeister moves along with their descriptions to Mathematica.  Notice that for sides consisting of more than one vertex, we enclose multiple vertices in a 'PD'.

•Mirror Images

Note that some relations have mirror images.  For knots, R1 and R3 both have them.  It can be advantageous to use these because they can improve the results from the Enumerate[] function discussed in the next section.

We shall call these mirror images 'R1P' and 'R3P':

7 Enumerate

Enumerate[complexity, complexitybound, vertices, relations] will find all of the PDs made up of 'vertices' with complexity 'complexity' that cannot be reduced to a lower complexity by any of the 'relations'.  Also, if more than one of the PDs can be linked through relations (going up to PDs with complexity 'complexitybound') to other PDs, then only one PD from the list of linked PDs is returned.

Essentially, Enumerate[] attempts to find all the PDs that represent objects that are not isomorphic to eachother.  By specifying a higher 'complexitybound', results will be improved, but more computer resources will be required.

The result given here is the Hopf Link, which is the only complexity 2 knot or link.  In this case, 'complexitybound' did not need to be increased.

Note that the relations must be enclosed in a List for the program to work.

Enumerate[] also prints out the status of what task it is performing, while the C program prints to a stderr window information such as how many PDs are produced.

We drew the result using Emily Redelmeier's program at http://www.math.toronto.edu/~drorbn/KAtlas/Manual/DrawPD.html.

With complexity 3, we get the two mirror images of the trefoil.

Here we see the importance of using 'Several' instead of specific numbers in describing the vertices for the Enumerate[] function.  As you can see from the printout, it generated PDs with 'R1 + Several X' vertices and 'R3 + Several X' vertices, both with complexity 3.  R1 and R3 have different complexities themselves, so really 'R1 + Several X' was like calling 'R1 + 2X', and 'R3 + Several X' was like calling 'R3'.  So if a specific number was put in place of 'Several', the program wouldn't work.

In this case, the first 2 links represent the same object.  This can be fixed by increasing the 'complexitybound' to 5.

Now, all these 4 results represent different knots or links.  However, it took much longer to run.

•Loops

Something that might be worth looking into is turning off loops before calling Enumerate[].  This would mean that not as many PDs would be produced at each level, saving time.  However, not as many relations would be found between PDs, requiring a higher 'complexitybound' to achieve the same results.

8 How The Planar Enumerator Works

In this section, a rough outline of how the program works is given.  For more details, consult the comments in the code.

•Diagrams

The Diagrams[] function is written mainly in C, but the C function is called by a Mathematica function that formats the input a bit.  Most of the code for the Diagrams[] function is found in the file "PDgenerator.c".

First, all of the adjacency matrices that could represent diagrams with some degree sequence are produced.  In each entry of an adjacency matrix we find the number of edges between the vertex represented by the column and the vertex represented by the row.  For example for the Hopf Link, we would get the adjacency matrix , since each vertex makes 4 connections with the other vertex.  If you swap row i with row j and column i with column j in an adjacency matrix, you obtain a new adjacency matrix which represents the same object.  A few checks are done to try to reduce the number of isomorphic adjacency matrices produced, but still, many isomorphic ones are produced at the higher complexities.  Finding a canonical form for adjacency matrices would speed up the program greatly.

Turning loops on or off is implented as the adjacency matrices are generated, by allowing or disallowing non-zero entries along the diagonals of the matrices.

Next, from each adjacency matrix, we produce all the diagrams (planar and non-planar) that the matrix could represent.  At this stage, we treat all vertices of the same degree as equivalent, and assign each vertex symmetry 1.  We then filter out the non-planar ones by using Euler's Formula which says that:



The planar ones are put into canonical form, and the duplicates removed.  These planar diagrams are called 'basic PDs' since all vertices of the same degree are equivalent, and symmetry is always 1.

For each basic PD, we then assign types to each of its vertices and rotate their edge lists according to their symmetry in order to obtain all the PDs it could represent.  Each PD is put into canonical form and duplicates are again removed.  When this is done for every basic PD, we have the final result.

With this technique, we generate all the planar and non-planar graphs, even though we never use the non-planar graphs.  Since the non-planar graphs greatly outnumber the planar ones, it would be worthwhile to find a new method that somehow only finds the planar graphs.

•Enumerate

Enumerate[] is also primarily implemented in C, but the C function makes calls to Mathematica through MathLink to access the RightHS[] and LeftHS[] functions that the user must define for the relations.  Also, the Mathematica function Enumerate[] calls the C functions to get things started.  Most of the C code is found in the file "PDhashtable.c".  Also, this makes use of a hash table available at http://burtleburtle.net/bob/hash/hashtab.html.

First, all of the PDs with the desired vertices with complexities ranging from 'complexity' to 'complexitybound' are produced.  Each one is then put into a hash table as the key, with an associated value which consists of a number.  These numbers are just assigned sequentially starting with 1.

Then the program generates two int arrays, each of the same length as the total number of PDs already produced.  One of them, called 'eliminateablePDs' contains all zeros.  The other, called 'relations', contains an int in each element which is equal to the element number.

The program then finds all the PDs containing a relation which have one side with complexity within the range we're looking at and the other side with complexity below 'complexity'.  The upper side of each of these can then be reduced by a single move to a PD of complexity less than we want.  We then change the value of the element in 'eliminateablePDs' corresponding to the upper complexity side to 1 from 0.

We then find all the PDs containing a relation which have both sides within the range we're looking at.  We take the LeftHS and RightHS of the relation to get the two PDs, which we put into canonical form.  Then using the hash table we find their indices.  To finish off, we change the value of the element of 'relations' which corresponds to the upper complexity PD to the index of the lower complexity PD.  Also, if the element of 'eliminateablePDs' corresponding to the upper complexity side is 1, then we change the value of 'eliminateablePDs' corresponding to the lower complexity side to 1 as well.  If the value of the upper complexity element in 'relations' is something other than the element number, then it already points somewhere else so we do some more changes.

Finally, we return all of the PDs of complexity 'complexity' that have 'eliminateablePDs' set to 0 and that have 'relations' point to themselves.

9 Future Improvements

At this point, the program is too slow and requires too much memory.  The number 7 seems to be the limit for the complexity with knots (loops turned on) on my machine (Athlon 1.2 GHz with 512 MB of RAM) due to the memory usage.  The number of PDs produced increases very rapidly as the complexity increases, so storing them all becomes a problem.  Solutions to the memory problem could include using some sort of disk-based database instead of that hash table stored in memory, and finding a more compact way of storing the PDs.

Although the memory is the first bottleneck I encounter, if this can be fixed, speed will become an issue.  In the generation of PDs, a large improvement could be found if we either found a canonical form for the adjacency matrices, or found a way to generate only the planar graphs, as discussed above.  In the enumeration part of the program, a lot of speed was gained by moving away from Mathematica into C (the Mathematica Dispatch tables were way to slow), but we still must make many calls through MathLink in order to access the LeftHS and RightHS functions defined by the user.  If a method was found to move these functions into C and still make them easy for the user to define, then things would be greatly sped up.  However, the first priority when it comes to speed is probably improving the planar diagram generation.

A new feature that would be fairly easy to implement is an option in the Enumerate function to apply a filter to all the PDs as they are generated, before they are put into the hash table.  This could be used to filter out knots from all the diagrams with vertices.  Later on, functions to "relax" diagrams and tell if two diagrams represent the same object or not, with a list of moves to show how they are the same would be useful.

Converted by Mathematica  (September 2, 2003)