Regina Calculation Engine
Public Types | Public Member Functions | Static Public Member Functions | List of all members
regina::ModelLinkGraph Class Reference

Represents an undirected 4-valent planar graph with a specific planar embedding. More...

#include <link/modellinkgraph.h>

Inheritance diagram for regina::ModelLinkGraph:
regina::Output< ModelLinkGraph >

Public Types

typedef void(* Use) (Link *, void *)
 A routine that can do arbitrary processing upon a knot or link. More...
 

Public Member Functions

 ModelLinkGraph ()
 Constructs an empty graph. More...
 
 ModelLinkGraph (const ModelLinkGraph &copy)
 Constructs a new copy of the given graph. More...
 
 ~ModelLinkGraph ()
 Destroys this graph. More...
 
size_t size () const
 Returns the number of nodes in this graph. More...
 
ModelLinkGraphNodenode (size_t index) const
 Returns the node at the given index within this graph. More...
 
void swapContents (ModelLinkGraph &other)
 Swaps the contents of this and the given graph. More...
 
void reflect ()
 Converts this graph into its reflection. More...
 
const ModelLinkGraphCellscells () const
 Returns details of the cellular decomposition of the sphere that is induced by this graph. More...
 
std::pair< ModelLinkGraphArc, ModelLinkGraphArcfindFlype (const ModelLinkGraphArc &from) const
 
TODO: Flype is between arc– and arc, i.e., over the region defined by cell(arc). More...
 
ModelLinkGraphflype (const ModelLinkGraphArc &from, const ModelLinkGraphArc &left, const ModelLinkGraphArc &right) const
 TODO: Document. More...
 
ModelLinkGraphflype (const ModelLinkGraphArc &from) const
 TODO: Document. More...
 
void generateMinimalLinks (Use use, void *useArgs=0) const
 TODO: Document. More...
 
std::string plantri () const
 Outputs this graph in the ASCII text format used by plantri. More...
 
std::string canonicalPlantri (bool useReflection=true, bool tight=false) const
 Outputs a text representation of this graph in the plantri ASCII format, using a canonical relabelling of nodes and arcs, and with optional compression. More...
 
void writeTextShort (std::ostream &out) const
 
Writes a short text representation of this graph to the given output stream. More...
 
void writeTextLong (std::ostream &out) const
 
Writes a detailed text representation of this graph to the given output stream. More...
 
ModelLinkGraphoperator= (const ModelLinkGraph &)=delete
 
std::string str () const
 
Returns a short text representation of this object. More...
 
std::string utf8 () const
 Returns a short text representation of this object using unicode characters. More...
 
std::string detail () const
 Returns a detailed text representation of this object. More...
 

Static Public Member Functions

static ModelLinkGraphfromPlantri (const std::string &plantri)
 Builds a graph from a line of plantri output. More...
 

Detailed Description

Represents an undirected 4-valent planar graph with a specific planar embedding.

This can be used as the model graph for a knot or link diagram, where each node of the graph becomes a crossing.

Current this class does not support circular graph components (which, in a link diagram, would correspond to zero-crossing unknot components of the link).

This class is primarily designed for enumerating knots and links. If you wish to study the underlying graph of an existing link, you do not need to create a ModelLinkGraph - instead the Link class already gives you direct access to the graph structure. In particular, if you include link/graph.h, you can use a Link directly as a directed graph type with the Boost Graph Library.

Member Typedef Documentation

◆ Use

typedef void(* regina::ModelLinkGraph::Use) (Link *, void *)

A routine that can do arbitrary processing upon a knot or link.

Such routines are used to process links that are found when running generateMinimalLinks().

The first parameter passed should be a link, which must be deallocated by this routine. The second parameter may contain arbitrary data as passed to generateMinimalLinks().

Note that the first parameter might be null to signal that link generation has finished.

Warning
The API for this class has not yet been finalised. This means that the class interface may change in new versions of Regina, without maintaining backward compatibility. If you use this class directly in your own code, please watch the detailed changelogs upon new releases to see if you need to make changes to your code.

Constructor & Destructor Documentation

◆ ModelLinkGraph() [1/2]

regina::ModelLinkGraph::ModelLinkGraph ( )
inline

Constructs an empty graph.

◆ ModelLinkGraph() [2/2]

regina::ModelLinkGraph::ModelLinkGraph ( const ModelLinkGraph copy)

Constructs a new copy of the given graph.

Parameters
copythe graph to copy.

◆ ~ModelLinkGraph()

regina::ModelLinkGraph::~ModelLinkGraph ( )
inline

Destroys this graph.

The ModelLinkGraphNode objects contained in this graph will also be destroyed.

Member Function Documentation

◆ canonicalPlantri()

std::string regina::ModelLinkGraph::canonicalPlantri ( bool  useReflection = true,
bool  tight = false 
) const

Outputs a text representation of this graph in the plantri ASCII format, using a canonical relabelling of nodes and arcs, and with optional compression.

This routine is similar to plantri(), but with two significant differences:

  • This routine does not preserve the labelling of nodes and the order of arcs around each node. Instead it reorders the nodes and arcs so that any two relabellings of the "same" planar embedding will produce the same canonicalPlantri() output. By "same" we allow for relabelling and isotopy (sliding the graph around the sphere); if the argument useReflection is true then we allow for reflection also.
  • If the argument tight is true, then this routine uses an abbreviated output format. The resulting compression is only trivial (it reduces the length by roughly 40%), but the resulting string is still human-parseable (though with a little more effort required). This compression will simply remove the commas, and for each node it will suppress the destination of the first arc (since this can be deduced from the canonical labelling).

Regardless of whether tight is true or false, the resulting string can be parsed by fromPlantri() to reconstruct the original graph. Note however that, due to the canonical labelling, the resulting graph might be a relabelling of the original (and might even be a reflection of the original, if useReflection was passed as true).

See plantri() for further details on the ASCII format itself.

The running time for this routine is quadratic in the size of the graph.

Precondition
This graph is connected.
This graph has between 1 and 26 nodes inclusive.
The dual to this graph is a simple quadrangulation of the sphere. In particular, the dual must not have any parallel edges. Note that any graph that fails this condition will the model graph for a link diagram that is an "obvious" connected sum.
Parameters
useReflectiontrue if a graph and its reflection should be considered the same (i.e., produce the same canonical output), or false if they should be considered different. Of course, if a graph is symmetric under reflection then the graph and its reflection will produce the same canonical output regardless of this parameter.
tightfalse if the usual plantri ASCII format should be used (as described by plantri() and fromPlantri()), or true if the abbreviated format should be used as described above.
Returns
an optionally compressed plantri ASCII representation of this graph.

◆ cells()

const ModelLinkGraphCells & regina::ModelLinkGraph::cells ( ) const
inline

Returns details of the cellular decomposition of the sphere that is induced by this graph.

This cellular decomposition will only be computed on demand. This means that the first call to this function will take linear time (as the decomposition is computed), but subsequent calls will be constant time (since the decomposition is cached).

Precondition
This graph is connected.
Returns
the induced cellular decomposition of the sphere.

◆ detail()

std::string regina::Output< ModelLinkGraph , false >::detail ( ) const
inherited

Returns a detailed text representation of this object.

This text may span many lines, and should provide the user with all the information they could want. It should be human-readable, should not contain extremely long lines (which cause problems for users reading the output in a terminal), and should end with a final newline. There are no restrictions on the underlying character set.

Returns
a detailed text representation of this object.

◆ findFlype()

std::pair<ModelLinkGraphArc, ModelLinkGraphArc> regina::ModelLinkGraph::findFlype ( const ModelLinkGraphArc from) const


TODO: Flype is between arc– and arc, i.e., over the region defined by cell(arc).

Returns (null, null) iff flype() will refuse to work with this. Otherwise returns (left outgoing arc, right outgoing arc).

Conditions that explicitly return null:

  • The upper and lower cells are the same.
  • The common cell is the inside cell at from.node().
Precondition
This graph is connected and TODO: valid.
Python
Instead of a C++ pair, this routine returns a Python tuple containing two ModelLinkGraphArc objects.

◆ flype() [1/2]

ModelLinkGraph* regina::ModelLinkGraph::flype ( const ModelLinkGraphArc from,
const ModelLinkGraphArc left,
const ModelLinkGraphArc right 
) const

TODO: Document.

       Cell A

    __   __
      \ /                    ----> left
       X         Cell B
    __/ \__from              ----> right

       Cell C

Conditions that explicitly return 0:

  • Neither left nor right ends at from.node().
  • The upper and lower bounding cells are distinct,
  • The cell between left and right is not the inside cell where the flype begins from from.node().

◆ flype() [2/2]

ModelLinkGraph * regina::ModelLinkGraph::flype ( const ModelLinkGraphArc from) const
inline

TODO: Document.

◆ fromPlantri()

static ModelLinkGraph* regina::ModelLinkGraph::fromPlantri ( const std::string &  plantri)
static

Builds a graph from a line of plantri output.

The software plantri, by Gunnar Brinkmann and Brendan McKay, can be used to enumerate 4-valent planar graphs (amongst many other things). This routine converts a piece of output from plantri into a ModelLinkGraph object that Regina can work with directly.

The output from plantri must be in ASCII format, and must be the dual graph of a simple quadrangulation of the sphere. The corresponding flags that must be passed to plantri to obtain such output are -adq (although you will may wish to pass additional flags to expand or restrict the classes of graphs that plantri builds).

When run with these flags, plantri produces output in the following form:

6 bbcd,adca,abee,affb,cffc,deed
6 bcdd,aeec,abfd,acfa,bffb,ceed
6 bcde,affc,abfd,acee,addf,becb

Each line consists of an integer (the number of nodes in the graph), followed by a comma-separated sequence of alphabetical strings that encode the edges leaving each node.

This function only takes the comma-separated sequence of alphabetical strings. So, for example, to construct the graph correpsonding to the second line of output above, you could call:

fromPlantri("bcdd,aeec,abfd,acfa,bffb,ceed");

Regina can only recognise graphs in this format with up to 26 nodes. If the graph contains more than 27 nodes then the plantri output will contain punctuation, Regina will not be able to parse it, and this function will return null.

The given string does not need to be come from the program plantri itself. Whereas plantri always outputs graphs with a particular canonical labelling, this function can accept an arbitrary ordering of nodes and arcs - in particular, it can accept the string g.plantri() for any graph g that meets the preconditions below. Nevertheless, the graph must still meet these preconditions, since otherwise the plantri format might not be enough to uniquely reconstruct the graph and its planar embedding.

This routine can also interpret the "tight" format that is output by the member function canonicalPlantri() (even though such output would certainly not be produced by the program plantri).

Warning
While this routine does some error checking on the input, it does not test for planarity of the graph. Of course plantri does not output non-planar graphs, but if a user constructs one by hand and passes it to this routine then the resulting behaviour is undefined.
Precondition
The graph being described is connected.
The graph being described has between 1 and 26 nodes inclusive.
The graph being described is dual to a simple quadrangulation of the sphere. In particular, the dual must not have any parallel edges. Note that any graph that fails this condition will the model graph for a link diagram that is an "obvious" connected sum.
Parameters
plantria string containing the comma-separated sequence of alphabetical strings output by plantri, as described above.
Returns
a newly constructed graph, or null if the input was found to be invalid.

◆ generateMinimalLinks()

void regina::ModelLinkGraph::generateMinimalLinks ( Use  use,
void *  useArgs = 0 
) const

TODO: Document.

Only aims for minimal, ignores reflections.

Node n will become crossing n.

Arc (0,0) will always be forwards, and crossing 0 will always be positive.

TODO: PRE: Knot, not link.

Warning
The API for this class has not yet been finalised. This means that the class interface may change in new versions of Regina, without maintaining backward compatibility. If you use this class directly in your own code, please watch the detailed changelogs upon new releases to see if you need to make changes to your code.

◆ node()

ModelLinkGraphNode * regina::ModelLinkGraph::node ( size_t  index) const
inline

Returns the node at the given index within this graph.

For a graph with n nodes, the nodes are numbered from 0 to n-1 inclusive.

Warning
If some nodes are added or removed then the indices of other nodes might change. If you wish to track a particular node through such operations then you should use the pointer to the relevant ModelLinkGraphNode object instead.
Parameters
indexthe index of the requested node. This must be between 0 and size()-1 inclusive.
Returns
the node at the given index.

◆ plantri()

std::string regina::ModelLinkGraph::plantri ( ) const

Outputs this graph in the ASCII text format used by plantri.

The software plantri, by Gunnar Brinkmann and Brendan McKay, can be used to enumerate 4-valent planar graphs (amongst many other things). This routine outputs this graph in a format that mimics plantri's own dual ASCII format (i.e., the format that plantri outputs when run with the flags -adq).

Specifically, the output will be a comma-separated sequence of alphabetical strings. The ith such string will consist of four lower-case letters, encoding the endpoints of the four edges in clockwise order that leave node i. The letters a,b,c,... represent nodes 0,1,2,... respectively. An example of such a string is:

bcdd,aeec,abfd,acfa,bffb,ceed

This routine is an inverse to fromPlantri(): for any graph g that satisfies the preconditions below, fromPlantri(g.plantri()) is identical to g. Likewise, for any string s that satisfies the preconditions for fromPlantri(), calling fromPlantri(s).plantri() will recover the original string s.

It is important to note the preconditions below: in particular, that this graph must be dual to a simple quadrangulation of the sphere. This is because the planar embeddings for more general graphs (i.e., the duals of non-simple quadrangulations) cannot always be uniquely reconstructed from their plantri output.

Note
The output of this function might not correspond to any possible output from the program plantri itself. This is because plantri only outputs graphs with a certain canonical labelling. In contrast, plantri() can be called on any graph that satisfies the preconditions below, and it will preserve the labels of the nodes and the order of the arcs around each node.
Precondition
This graph is connected.
This graph has between 1 and 26 nodes inclusive.
The dual to this graph is a simple quadrangulation of the sphere. In particular, the dual must not have any parallel edges. Note that any graph that fails this condition will the model graph for a link diagram that is an "obvious" connected sum.
Returns
a plantri format ASCII representation of this graph.

◆ reflect()

void regina::ModelLinkGraph::reflect ( )

Converts this graph into its reflection.

This routine simply reverses (and also cycles) the order of outgoing arcs around every node.

◆ size()

size_t regina::ModelLinkGraph::size ( ) const
inline

Returns the number of nodes in this graph.

Returns
the number of nodes.

◆ str()

std::string regina::Output< ModelLinkGraph , false >::str ( ) const
inherited


Returns a short text representation of this object.

This text should be human-readable, should fit on a single line, and should not end with a newline. Where possible, it should use plain ASCII characters.

Python
In addition to str(), this is also used as the Python "stringification" function __str__().
Returns
a short text representation of this object.

◆ swapContents()

void regina::ModelLinkGraph::swapContents ( ModelLinkGraph other)
inline

Swaps the contents of this and the given graph.

All nodes that belong to this graph will be moved to other, and all nodes that belong to other will be moved to this graph.

In particular, any ModelLinkGraphNode pointers or references and any ModelLinkGraphArc objects will remain valid.

This routine will behave correctly if other is in fact this graph.

Parameters
otherthe graph whose contents should be swapped with this.

◆ utf8()

std::string regina::Output< ModelLinkGraph , false >::utf8 ( ) const
inherited

Returns a short text representation of this object using unicode characters.

Like str(), this text should be human-readable, should fit on a single line, and should not end with a newline. In addition, it may use unicode characters to make the output more pleasant to read. This string will be encoded in UTF-8.

Returns
a short text representation of this object.

◆ writeTextLong()

void regina::ModelLinkGraph::writeTextLong ( std::ostream &  out) const


Writes a detailed text representation of this graph to the given output stream.

Python
Not present.
Parameters
outthe output stream to which to write.

◆ writeTextShort()

void regina::ModelLinkGraph::writeTextShort ( std::ostream &  out) const


Writes a short text representation of this graph to the given output stream.

Python
Not present.
Parameters
outthe output stream to which to write.

The documentation for this class was generated from the following file:

Copyright © 1999-2021, The Regina development team
This software is released under the GNU General Public License, with some additional permissions; see the source code for details.
For further information, or to submit a bug or other problem, please contact Ben Burton (bab@maths.uq.edu.au).