Regina 7.4 Calculation Engine
regina::ModelLinkGraph Class Reference

Represents an undirected 4-valent graph with a specific embedding in some closed orientable surface. More...

#include <link/modellinkgraph.h>

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

Public Member Functions

 ModelLinkGraph ()
 Constructs an empty graph.
 
 ModelLinkGraph (const Link &link)
 Constructs the graph that models the given link.
 
 ModelLinkGraph (const ModelLinkGraph &copy)
 Constructs a new copy of the given graph.
 
 ModelLinkGraph (ModelLinkGraph &&src) noexcept
 Moves the given graph into this new graph.
 
 ModelLinkGraph (const std::string &description)
 "Magic" constructor that tries to find some way to interpret the given string as a 4-valent graph with embedding.
 
 ~ModelLinkGraph ()
 Destroys this graph.
 
size_t size () const
 Returns the number of nodes in this graph.
 
bool isEmpty () const
 Determines whether this graph is empty.
 
size_t countComponents () const
 Returns the number of connected components in this graph.
 
size_t countTraversals () const
 Returns the number of traversals in this graph.
 
ModelLinkGraphNodenode (size_t index) const
 Returns the node at the given index within this graph.
 
auto nodes () const
 Returns an object that allows iteration through and random access to all nodes in this graph.
 
ModelLinkGraphoperator= (const ModelLinkGraph &src)
 Sets this to be a (deep) copy of the given graph.
 
ModelLinkGraphoperator= (ModelLinkGraph &&src) noexcept
 Moves the contents of the given graph into this graph.
 
void swap (ModelLinkGraph &other) noexcept
 Swaps the contents of this and the given graph.
 
void insertGraph (const ModelLinkGraph &source)
 Inserts a copy of the given graph into this graph.
 
void insertGraph (ModelLinkGraph &&source)
 Moves the contents of the given graph into this graph.
 
void moveContentsTo (ModelLinkGraph &dest)
 Moves the contents of this graph into the given destination graph, leaving this graph empty but otherwise usable.
 
bool operator== (const ModelLinkGraph &other) const
 Determines if this graph is combinatorially identical to the given graph.
 
void reflect ()
 Converts this graph into its reflection.
 
const ModelLinkGraphCellscells () const
 Returns the cellular decomposition of the closed orientable surface in which this graph embeds.
 
bool isConnected () const
 Identifies whether this graph is connected.
 
bool isSimple () const
 Identifies whether this graph is simple; that is, has no loops or multiple edges.
 
size_t genus () const
 Returns the genus of the closed orientable surface in which this graph embeds.
 
std::pair< ModelLinkGraphArc, ModelLinkGraphArcfindFlype (const ModelLinkGraphArc &from) const
 Identifies the smallest flype that can be performed on this graph from the given starting location.
 
ModelLinkGraph flype (const ModelLinkGraphArc &from, const ModelLinkGraphArc &left, const ModelLinkGraphArc &right) const
 Performs a flype on this graph at the given location.
 
ModelLinkGraph flype (const ModelLinkGraphArc &from) const
 Performs the smallest possible flype on this graph from the given starting location.
 
Link generateAnyLink () const
 Generates an arbitrary link diagram that is modelled by this graph.
 
template<typename Action , typename... Args>
void generateMinimalLinks (Action &&action, Args &&... args) const
 Exhaustively generates potentially-minimal link diagrams that are modelled by this graph.
 
template<typename Action , typename... Args>
void generateAllLinks (Action &&action, Args &&... args) const
 Exhaustively generates all link diagrams that are modelled by this graph, up to reversal of individual link components.
 
ModelLinkGraph canonical (bool allowReflection=true) const
 Returns the canonical relabelling of this graph.
 
void randomise ()
 Randomly relabels this graph in an orientation-preserving manner.
 
std::string plantri () const
 Outputs this graph in a variant of the ASCII text format used by plantri.
 
std::string canonicalPlantri (bool allowReflection=true, bool tight=false) const
 Outputs a text representation of this graph in a variant of the plantri ASCII format, using a canonical relabelling of nodes and arcs, and with optional compression.
 
std::string extendedPlantri () const
 Outputs this graph using Regina's extended variant of the plantri text format, which is better suited for non-planar graphs.
 
void tightEncode (std::ostream &out) const
 Writes the tight encoding of this graph to the given output stream.
 
void writeTextShort (std::ostream &out) const
 Writes a short text representation of this graph to the given output stream.
 
void writeTextLong (std::ostream &out) const
 Writes a detailed text representation of this graph to the given output stream.
 
std::string str () const
 Returns a short text representation of this object.
 
std::string utf8 () const
 Returns a short text representation of this object using unicode characters.
 
std::string detail () const
 Returns a detailed text representation of this object.
 
std::string tightEncoding () const
 Returns the tight encoding of this object.
 
size_t hash () const
 Hashes this object to a non-negative integer, allowing it to be used for keys in hash tables.
 

Static Public Member Functions

template<typename Action , typename... Args>
static void generateAllEmbeddings (const FacetPairing< 3 > &pairing, bool allowReflection, Flags< GraphConstraint > constraints, Action &&action, Args &&... args)
 Generates all possible local embeddings of the given 4-valent graph into some closed orientable surface.
 
static ModelLinkGraph fromPlantri (const std::string &plantri)
 Builds a graph from a line of plantri output, using Regina's variant of the plantri ASCII format.
 
static ModelLinkGraph fromExtendedPlantri (const std::string &text)
 Builds a graph from a text representation using Regina's extended variant of the plantri format, which is better suited for non-planar graphs.
 
static ModelLinkGraph tightDecode (std::istream &input)
 Reconstructs a graph from its given tight encoding.
 
static ModelLinkGraph tightDecoding (const std::string &enc)
 Reconstructs an object of type T from its given tight encoding.
 

Detailed Description

Represents an undirected 4-valent graph with a specific embedding in some closed orientable surface.

This class only stores the graph and a local description of the embedding (i.e., a cyclic ordering of arcs around each node). It does not store the surface explicitly, though the surface is implied from the embedding - if you need it you can always access a full description of the surface by calling cells().

In particular, the surface is assumed to be the minimal genus surface in which the graph embeds. Each connected component of the graph is embedded in a separate connected component of the surface, and each component of the surface is formed from a collection of discs (or cells) whose boundaries follow the nodes and arcs of the graph according to the local embedding.

Regina uses graphs like these as model graphs for classical or virtual link diagrams, where each node of the graph becomes a classical crossing. If the surface is a collection of 2-spheres, then the graph is planar and models a classical link diagram. If the surface has genus, then the graph is non-planar and instead models a virtual link diagram.

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

For Boost users: if you wish to study the underlying graph of an existing link, you do not need to create a ModelLinkGraph - instead you can include link/graph.h and then use Link directly as a directed graph type with the Boost Graph Library.

This class implements C++ move semantics and adheres to the C++ Swappable requirement. It is designed to avoid deep copies wherever possible, even when passing or returning objects by value.

Constructor & Destructor Documentation

◆ ModelLinkGraph() [1/5]

regina::ModelLinkGraph::ModelLinkGraph ( )
inline

Constructs an empty graph.

◆ ModelLinkGraph() [2/5]

regina::ModelLinkGraph::ModelLinkGraph ( const Link & link)

Constructs the graph that models the given link.

Any zero-component unknot components of the link will be ignored.

The nodes of this graph will be numbered in the same way as the crossings of link. For each node, arc 0 will represent the outgoing lower strand of the corresponding crossing.

Using this constructor is identical to calling Link::graph().

Parameters
linkthe link that this new graph will model.

◆ ModelLinkGraph() [3/5]

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

Constructs a new copy of the given graph.

Parameters
copythe graph to copy.

◆ ModelLinkGraph() [4/5]

regina::ModelLinkGraph::ModelLinkGraph ( ModelLinkGraph && src)
inlinenoexcept

Moves the given graph into this new graph.

This is a fast (constant time) operation.

All nodes and cells that belong to src will be moved into this graph, and so any ModelLinkGraphNode or ModelLinkGraphCells pointers or references will remain valid.

The graph that is passed (src) will no longer be usable.

Parameters
srcthe graph to move.

◆ ModelLinkGraph() [5/5]

regina::ModelLinkGraph::ModelLinkGraph ( const std::string & description)

"Magic" constructor that tries to find some way to interpret the given string as a 4-valent graph with embedding.

At present, Regina understands the following types of strings (and attempts to parse them in the following order):

This list may grow in future versions of Regina.

Exceptions
InvalidArgumentRegina could not interpret the given string as representing a graph using any of the supported string types.
Parameters
descriptiona string that describes a 4-valent graph with embedding.

◆ ~ModelLinkGraph()

regina::ModelLinkGraph::~ModelLinkGraph ( )
inline

Destroys this graph.

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

Member Function Documentation

◆ canonical()

ModelLinkGraph regina::ModelLinkGraph::canonical ( bool allowReflection = true) const

Returns the canonical relabelling of this graph.

Here "relabelling" allows for any combination of:

  • a relabelling of the nodes;
  • a relabelling of the arcs around each node, whilst preserving the cyclic order;
  • if allowReflection is true, a reversal of the cyclic order of the arcs around every node (i.e., a reflection of the surface in which the graph embeds).

Two graphs are related under such a relabelling if and only if their canonical relabellings are identical.

There is no promise that this will be the same canonical labelling as used by canonicalPlantri().

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

Precondition
This graph is connected.
Parameters
allowReflectiontrue if we allow reflection of the surface in which the graph embeds; that is, a graph and its reflection should produce the same canonical relabelling.
Returns
the canonical relabelling of this graph.

◆ canonicalPlantri()

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

Outputs a text representation of this graph in a variant of 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 uses a canonical relabelling of the graph. Specifically, two graphs will have the same canonicalPlantri() output if and only if they are related under some combination of: (i) relabelling nodes; (ii) relabelling the arcs around each node whilst preserving their cyclic order; and (iii) if allowReflection is true, optionally reversing the cyclic order of the arcs around every node. This corresponds to a homeomorphism between the surfaces in which the graphs embed that maps one graph to the other; the argument allowReflection indicates whether this homeomorphism is allowed to reverse orientation. While this has a similar aim to canonical(), there is no promise that both routines will use the same "canonical relabelling".
  • 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 allowReflection was passed as true).

See plantri() for further details on the ASCII format itself, including how Regina's implementation differs from plantri's for graphs with more than 26 nodes.

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 52 nodes inclusive.
The dual to this graph is a simple quadrangulation of the surface in which it embeds; see plantri() for a discussion on why this condition is needed.
Exceptions
FailedPreconditionThis graph is empty or has more than 52 nodes.
Parameters
allowReflectiontrue 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 the cellular decomposition of the closed orientable surface in which this graph embeds.

This will be the decomposition induced by this graph; in particular, it will be formed from discs bounded by the nodes and arcs of 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).

Note that, as of Regina 7.4, you can call this routine even if the graph is non-planar and/or disconnected.

Warning
This routine is not thread-safe.
Exceptions
InvalidArgumentThis graph induces more cells than should ever be possible. This should never occur unless the graph is malformed in some way.
Returns
the induced cellular decomposition of the surface in which this graph embeds.

◆ countComponents()

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

Returns the number of connected components in this graph.

Warning
This routine is not thread-safe, since it caches the number of components after computing it for the first time.
Note
These are components in the graph theoretical sense, not link components. So, for example, the graph that models the Hopf link is considered to be connected with just one component.
Returns
the number of connected components.

◆ countTraversals()

size_t regina::ModelLinkGraph::countTraversals ( ) const

Returns the number of traversals in this graph.

A traversal is a closed path through the graph that always enters and exits a node through opposite arcs. If this graph models a diagram for some link L, then the number of traversals in this graph will be precisely the number of link components in L.

This routine runs in linear time (and the result is not cached).

Returns
the number of traversals.

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

◆ extendedPlantri()

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

Outputs this graph using Regina's extended variant of the plantri text format, which is better suited for non-planar graphs.

See plantri() for a discussion of the plantri text format. A limitation of the plantri format is that it requires the graph to be dual to a simple quadrangulation of the surface in which it embeds. This is a reasonable requirement for planar graphs, but not so for non-planar graphs (which, in particular, are used to model virtual link diagrams).

This routine extends the plantri format to more explicitly encode the embedding of the graph, which means we can remove the problematic requirement on the dual quadrangulation. The format is Regina's own (i.e., it is not compatible with the Brinkmann-McKay plantri software).

The output will be a comma-separated sequence of alphanumeric strings. The ith such string will consist of four letter-number pairs, encoding the endpoints of the four edges in clockwise order that leave node i. The letters represent nodes (with a..zA..Z representing nodes 0 to 51 respectively). The numbers represent arcs (with 0..3 representing the four arcs around each node in clockwise order). An example of such a string (describing a genus one graph that models the virtual trefoil) is:

b3b2b0b1,a2a3a1a0

This routine is an inverse to fromExtendedPlantri(). That is, for any graph g of a supported size, fromExtendedPlantri(g.extendedPlantri()) will be identical to g. Likewise, for any string s that satisfies the preconditions for fromExtendedPlantri(), calling fromExtendedPlantri(s).extendedPlantri() will recover the original string s.

Precondition
This graph has between 1 and 52 nodes inclusive.
Exceptions
FailedPreconditionThis graph is empty or has more than 52 nodes.
Returns
a representation of this graph in the extended plantri format.

◆ findFlype()

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

Identifies the smallest flype that can be performed on this graph from the given starting location.

Here we use the same notation as in the three-argument flype() function, where you perform a flype by passing three arcs from, left and right. Read the flype() documentation now if you have not done so already; this includes a full description of the flype operation as well as diagrams with the arcs from, left and right clearly marked.

The given arc from identifies the node to the left of the flype disc. The aim of this routine is to identify two suitable arcs left and right that exit through the right of the flype disc. Together, these three arcs uniquely identify the entire flype disc, and therefore prescribe the operation precisely.

Here, by "suitable arcs", we mean a pair of arcs (left, right) for which the three arcs (from, left, right) together satisfy the preconditions for the flype() routine.

There are several possible outcomes:

  • It is possible that there are no suitable arcs left and right. In this case, this routine returns a pair of null arcs.
  • It is possible that there is exactly one pair of suitable arcs (left, right). In this case, this pair will be returned.
  • It is possible that there are many pairs of suitable arcs. In this case, it can be shown that the suitable pairs have an ordering P_1, ..., P_k in which the flype disc for P_i is completely contained within the flype disc for P_j whenever i < j. In this case, this routine returns the smallest pair P_1; that is, the pair (left, right) that gives the smallest possible flype disc.

It should be noted that choosing only the smallest flype is not a serious restriction: assuming the graph does not model a composition of non-trivial knot diagrams, any suitable flype can be expressed as a composition of minimal flypes in this sense.

Precondition
This graph is planar.
Parameters
fromthe arc that indicates where the flype disc should begin. This is the arc labelled from in the diagrams for the three-argument flype() function: it is the lower of the two arcs that enter the flype disc from the node X to the left of the disc. This should be presented as an arc of the node X.
Returns
the pair (left, right) representing the smallest suitable flype beginning at from, or a pair of null arcs if there are no suitable pairs (left, right).

◆ flype() [1/2]

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

Performs the smallest possible flype on this graph from the given starting location.

This is a convenience routine that simply calls findFlype() to identify the smallest possible flype from the given starting location, and then calls the three-argument flype() to actually perform it. If there is no possible flype from the given starting location then this routine throws an exception.

See the documentation for the three-argument flype() for further details on the flype operation, and see findFlype() for a discussion on what is meant by "smallest possible".

Precondition
This graph is planar.
Exceptions
InvalidArgumentThere is no suitable flype on this graph from the given starting location (that is, findFlype() returns a pair of null arcs).
Parameters
fromthe arc that indicates where the flype disc should begin. This is the arc labelled from in the diagrams for the three-argument flype() function: it is the lower of the two arcs that enter the flype disc from the node X to the left of the disc. This should be presented as an arc of the node X.
Returns
the graph obtained by performing the flype.

◆ flype() [2/2]

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

Performs a flype on this graph at the given location.

A flype is an operation on a disc in the plane. The boundary of the disc must cut through four arcs of the graph (and otherwise must not meet the graph at all), as indicated in the diagram below. Moreover, the two arcs that exit the disc on the left must meet at a common node just outside the disc. (The punctuation symbols drawn inside the disc are just to help illustrate how the transformation works.)

         ______                       ______
        /      \                     /      \
__   __| ##  ** |_______     _______| ::  <> |__   __
  \ /  |        |                   |        |  \ /
   X   |  Disc  |        ==>        |        |   X
__/ \__|        |_______     _______|        |__/ \__
       | ::  <> |                   | ##  ** |
        \______/                     \______/

The operation involves:

  • reflecting this disc in a horizontal axis (so the two arcs on the left switch places, and the two arcs on the right switch places);
  • removing the node outside the disc on the left, where the two arcs meet;
  • introducing a new node on the right instead, where the two arcs on the right will now meet.

The equivalent operation on a knot diagram involves twisting the entire region inside the disc about a horizontal axis, in a way that undoes the crossing on the left but introduces a new crossing on the right instead.

You will need to pass arguments to indicate where the flype should take place. For this, we will label some of the features of the initial diagram (before the move takes place): see the diagram below. Here the labels from, left and right all refer to arcs. The labels A, B, C and D all refer to dual 2-cells in the plane; these are not passed as arguments, but they do appear in the list of preconditions for this routine.

                 ______
Cell A          /      \
__   __________|        |_________ left
  \ /          |        |
   X   Cell B  |        |  Cell D
__/ \__________|        |_________ right
         from  |        |
Cell C          \______/

The arc from must be given as an arc of the node outside the disc (i.e., the node to the left of cell B). The arcs left and right must be given as arcs of their respective nodes inside the disc.

Precondition
This graph is planar.
The arcs from, left and right are laid out as in the diagram above. In particular: from and right have the same cell to their right (cell C); left and the arc to the left of from have the same cell to their left (cell A); and left and right have the same cell between them (cell D).
Neither of the arcs left or right, when followed in the direction away from the disc, end back at the node on the left of the diagram. That is, neither left.traverse().node() nor right.traverse().node() is equal to from.node(). (If this fails, then either the flype simply reflects the entire graph, or else the graph models a composition of two non-trivial knot diagrams.)
Cells A and C are distinct (that is, the node on the left of the diagram is not a cut-vertex of the graph).
Cells B and D are distinct (that is, the disc actually contains one or more nodes, and the graph does not model a composition of two non-trivial knot diagrams).
Exceptions
InvalidArgumentOne or more of the preconditions above fails to hold. Be warned that the connectivity and planarity preconditions will not be checked - these are the user's responsibility - but all other preconditions will be checked, and an exception will be thrown if any of them fails.
Parameters
fromthe first arc that indicates where the flype should take place, as labelled on the diagram above. This should be presented as an arc of the node outside the disc, to the left.
leftthe second arc that indicates where the flype should take place, as labelled on the diagram above. This should be presented as an arc of the node that it meets inside the disc.
rightthe third arc that indicates where the flype should take place, as labelled on the diagram above. This should be presented as an arc of the node that it meets inside the disc.
Returns
the graph obtained by performing the flype.

◆ fromExtendedPlantri()

static ModelLinkGraph regina::ModelLinkGraph::fromExtendedPlantri ( const std::string & text)
static

Builds a graph from a text representation using Regina's extended variant of the plantri format, which is better suited for non-planar graphs.

See extendedPlantri() for a detailed description of Regina's extended plantri text format. In essence, this extends the original Brinkmann-McKay plantri format to more explicitly encode the embedding of the graph, thereby removing the original plantri requirement that the graph be dual to a simple quadrangulation of the surface in which it embeds. Removing this requirement is important for non-planar graphs (which are used to model virtual link diagrams).

As an example, the string below is the extended plantri representation of a genus one graph that models the virtual trefoil:

b3b2b0b1,a2a3a1a0
Exceptions
InvalidArgumentThe input was not a valid representation of a graph using Regina's extended plantri format.
Parameters
textthe representation of a graph using Regina's extended plantri format, as described in extendedPlantri().
Returns
the resulting graph.

◆ fromPlantri()

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

Builds a graph from a line of plantri output, using Regina's variant of the plantri ASCII format.

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, or the encoding of a graph using Regina's more general plantri() or canonicalPlantri() functions, into a ModelLinkGraph object that Regina can work with directly.

Graphs encoded using Regina's plantri() or canonicalPlantri() functions may be disconnected and/or non-planar. However, such a graph must be dual to a simple quadrangulation of the surface in which it embeds - otherwise the plantri format does not contain enough information to recover the embedding of the graph. This in particular is a problem for non-planar graphs (which model virtual links). If this is an issue for you, you can use Regina's extended plantri format instead; see extendedPlantri() and fromExtendedPlantri().

If you are working with output directly from the software plantri, this output must be in ASCII format, and must likewise be the dual graph of a simple quadrangulation of the sphere. The flags that must be passed to plantri to obtain such output are -adq (although you 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 corresponding to the second line of output above, you could call:

fromPlantri("bcdd,aeec,abfd,acfa,bffb,ceed");
static ModelLinkGraph fromPlantri(const std::string &plantri)
Builds a graph from a line of plantri output, using Regina's variant of the plantri ASCII format.

Regina uses its own variant of plantri's output format, which is identical for smaller graphs but which differs from plantri's own output format for larger graphs. In particular:

  • For graphs with ≤ 26 nodes, Regina and plantri use identical formats. Here Regina can happily recognise the output from plantri as described above, as well as the output from Regina's own plantri() and canonicalPlantri() functions.
  • For graphs with 27-52 nodes, Regina's and plantri's formats differ: whereas plantri uses punctuation for higher-index nodes, Regina uses the upper-case letters A,...,Z. For these larger graphs, Regina can only recognise Regina's own plantri() and canonicalPlantri() output, not plantri's punctuation-based encodings.
  • For graphs with 53 nodes or more, Regina cannot encode or decode such graphs using plantri format at all.

Note that, whilst the software plantri always outputs graphs using a particular canonical labelling, this function has no such restriction: it 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.

This routine can also interpret the "tight" format that is optionally produced by the member function canonicalPlantri() (even though such output would certainly not be produced by the software plantri). Note that, by design, the tight format can only represented connected graphs.

Warning
While this routine does some basic error checking on the input, these checks are not exhaustive. In particular, it does not test that the graph is dual to a simple quadrangulation.
Precondition
The graph being described is dual to a simple quadrangulation of the surface in which it embeds; see plantri() for further discussion on why this condition is needed.
Exceptions
InvalidArgumentThe input was not a valid representation of a graph using the plantri output format.
Parameters
plantria string containing the comma-separated sequence of alphabetical strings in plantri format, as described above.
Returns
the resulting graph.

◆ generateAllEmbeddings()

template<typename Action , typename... Args>
static void regina::ModelLinkGraph::generateAllEmbeddings ( const FacetPairing< 3 > & pairing,
bool allowReflection,
Flags< GraphConstraint > constraints,
Action && action,
Args &&... args )
static

Generates all possible local embeddings of the given 4-valent graph into some closed orientable surface.

The input 4-valent graph (which does not contain any embedding data) should be presented as a closed 3-dimensional facet pairing (since these can be generated efficiently using Regina).

This routine will, up to canonical relabelling, generate all local embeddings of the given graph into a closed orientable surface (i.e., all ModelLinkGraph objects corresponding to the input graph), each exactly once.

The graphs that are generated will be labelled canonically as described by canonical(). This means that the nodes of the graph might use a different labelling from the simplices of the given facet pairing. The argument allowReflection will be passed through to canonical().

This routine is a work in progress. Currently it is very inefficient and memory-hungry; the algorithm will be improved over time if/when it becomes important to do so.

If allowReflection is false, then if we run all possible facet pairings through this routine, the combined results should be precisely those graphs described by OEIS sequence A292206. If allowReflection is true, then (once we reach three nodes or more) the output set should be smaller.

For each graph that is generated, this routine will call action (which must be a function or some other callable object).

  • The first argument passed to action will be the graph that was generated (of type ModelLinkGraph). This will be passed as an rvalue; a typical action could (for example) take it by const reference and query it, or take it by value and modify it, or take it by rvalue reference and move it into more permanent storage.
  • If there are any additional arguments supplied in the list args, then these will be passed as subsequent arguments to action.
  • action must return void.
Warning
The API for this class or function has not yet been finalised. This means that the interface may change in new versions of Regina, without maintaining backward compatibility. If you use this class directly in your own code, please check the detailed changelog with each new release to see if you need to make changes to your code.
Precondition
The given facet pairing is connected, and is also closed (i.e., has no unmatched facets).
Python
This function is available in Python, and the action argument may be a pure Python function. However, its form is more restricted: the argument args is removed, so you simply call it as generateAllEmbeddings(pairing, allowReflection, action). Moreover, action must take exactly one argument (the graph).
Exceptions
InvalidArgumentThe given pairing is disconnected and/or has unmatched facets.
Parameters
pairingthe 4-valent graph for which we wish to produce local embeddings.
allowReflectiontrue if we consider a reflection of the surface in which the graph embeds to produce the same embedding.
constraintsindicates any constraints that the embeddings that we generate must satisfy. This should be a bitwise OR of constants from the GraphConstraint enumeration, or else GraphConstraint::All (or just empty braces {}) if we should generate every possible embedding. If several constraints are ORed together, then only embeddings that satisfy all of the these constraints will be produced.
actiona function (or other callable object) to call for each graph that is generated.
argsany additional arguments that should be passed to action, following the initial graph argument.

◆ generateAllLinks()

template<typename Action , typename... Args>
void regina::ModelLinkGraph::generateAllLinks ( Action && action,
Args &&... args ) const

Exhaustively generates all link diagrams that are modelled by this graph, up to reversal of individual link components.

If this graph has n nodes, then there will be 2^n link diagrams generated in total.

This routine is provided mainly to help with exhaustive testing. If you are not interested in "obviously" non-minimal link diagrams, then you should call generateMinimalLinks() instead.

Labelled diagrams are only generated once up to reversal of each component. Specifically, this routine will fix the orientation of each link component (always following the smallest numbered available arc away from the smallest index graph node in each link component).

In each link diagram that is generated, crossing k will always correspond to node k of this graph. If this graph is non-planar, then the resulting link diagrams will all be virtual.

For each link diagram that is generated, this routine will call action (which must be a function or some other callable object).

  • The first argument passed to action will be the link diagram that was generated (of type Link). This will be passed as an rvalue; a typical action could (for example) take it by const reference and query it, or take it by value and modify it, or take it by rvalue reference and move it into more permanent storage.
  • If there are any additional arguments supplied in the list args, then these will be passed as subsequent arguments to action.
  • action must return void.
Warning
The API for this class or function has not yet been finalised. This means that the interface may change in new versions of Regina, without maintaining backward compatibility. If you use this class directly in your own code, please check the detailed changelog with each new release to see if you need to make changes to your code.
Python
This function is available in Python, and the action argument may be a pure Python function. However, its form is more restricted: the argument args is removed, so you simply call it as generateAllLinks(action). Moreover, action must take exactly one argument (the link diagram).
Parameters
actiona function (or other callable object) to call for each link diagram that is generated.
argsany additional arguments that should be passed to action, following the initial link diagram argument.

◆ generateAnyLink()

Link regina::ModelLinkGraph::generateAnyLink ( ) const

Generates an arbitrary link diagram that is modelled by this graph.

All link diagrams modelled by this graph are identical up to switching of individual crossings and/or reversal of individual link components. This routine will generate just one of these many possible link diagrams. If you wish to generate all such diagrams, consider whether generateMinimalLinks() might be more appropriate for what you need.

Unlike generateMinimalLinks(), there is no guarantee that the diagram produced by this routine is minimal or even locally minimal in any sense. For example, it is entirely possible that the link diagram returned by this routine will have a reducing Reidemeister move.

In the link diagram that is generated, crossing k will always correspond to node k of this graph. If this graph is non-planar, then the resulting link diagram will be virtual.

◆ generateMinimalLinks()

template<typename Action , typename... Args>
void regina::ModelLinkGraph::generateMinimalLinks ( Action && action,
Args &&... args ) const

Exhaustively generates potentially-minimal link diagrams that are modelled by this graph.

Here potentially-minimal means there are no "obvious" simplification moves (such as a simplifying type II Reidemeister move, for example). The list of "obvious" moves considered here is subject to change in future versions of Regina.

By exhaustive, we mean:

  • Every minimal link diagram modelled by this graph will be generated by this routine, up to reflection and/or reversal (as explained below).
  • If a link diagram is non-minimal and modelled by this graph, it might still be generated by this routine.

In other words, this routine will generate all minimal link diagrams modelled by this graph, but there is no promise that all of the diagrams generated are minimal.

Labelled diagrams are only generated once up to reflection of the diagram and/or reversal of each component. Here "reflection" corresponds to the function Link::changeAll(), which reflects the link diagram in the surface that contains it. Specifically, this routine will fix the orientation of each link component (always following the smallest numbered available arc away from the smallest index graph node in each link component), and it will fix the upper and lower strands at node 0 so that the corresponding crossing is always positive.

In each link diagram that is generated, crossing k will always correspond to node k of this graph. If this graph is non-planar, then the resulting link diagrams will all be virtual.

For each link diagram that is generated, this routine will call action (which must be a function or some other callable object).

  • The first argument passed to action will be the link diagram that was generated (of type Link). This will be passed as an rvalue; a typical action could (for example) take it by const reference and query it, or take it by value and modify it, or take it by rvalue reference and move it into more permanent storage.
  • If there are any additional arguments supplied in the list args, then these will be passed as subsequent arguments to action.
  • action must return void.
Warning
The API for this class or function has not yet been finalised. This means that the interface may change in new versions of Regina, without maintaining backward compatibility. If you use this class directly in your own code, please check the detailed changelog with each new release to see if you need to make changes to your code.
Precondition
The cell decomposition induced by this graph has no 1-gons (which, in any link diagram that the graph models, would yield a reducing type I Reidemeister move).
Python
This function is available in Python, and the action argument may be a pure Python function. However, its form is more restricted: the argument args is removed, so you simply call it as generateMinimalLinks(action). Moreover, action must take exactly one argument (the link diagram).
Exceptions
FailedPreconditionThere is a 1-gon in the cell decomposition induced by this graph.
Parameters
actiona function (or other callable object) to call for each link diagram that is generated.
argsany additional arguments that should be passed to action, following the initial link diagram argument.

◆ genus()

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

Returns the genus of the closed orientable surface in which this graph embeds.

As described in the class notes, this surface is chosen to have the smallest possible genus: it is built from a collection of discs whose boundaries follow the nodes and arcs of this graph according to the local embedding.

If this graph is disconnected (and therefore the surface is also disconnected), then this routine will return the sum of the genus over all components.

Returns
the genus of the surface in which this graph embeds.

◆ hash()

size_t regina::TightEncodable< ModelLinkGraph >::hash ( ) const
inlineinherited

Hashes this object to a non-negative integer, allowing it to be used for keys in hash tables.

This hash function makes use of Regina's tight encodings. In particular, any two objects with the same tight encoding will have equal hashes. This implementation (and therefore the specific hash value for each object) is subject to change in future versions of Regina.

Python
For Python users, this function uses the standard Python name hash(). This allows objects of this type to be used as keys in Python dictionaries and sets.
Returns
The integer hash of this object.

◆ insertGraph() [1/2]

void regina::ModelLinkGraph::insertGraph ( const ModelLinkGraph & source)

Inserts a copy of the given graph into this graph.

The nodes of source will be copied into this graph, and placed after any pre-existing nodes. Specifically, if the original number of nodes in this graph was N, then node i of source will be copied to a new node N+i of this graph.

This routine behaves correctly when source is this graph.

Parameters
sourcethe graph whose copy will be inserted.

◆ insertGraph() [2/2]

void regina::ModelLinkGraph::insertGraph ( ModelLinkGraph && source)

Moves the contents of the given graph into this graph.

The nodes of source will be moved directly into this graph, and placed after any pre-existing nodes. Specifically, if the original number of nodes in this graph was N, then node i of source will become node N+i of this graph.

As is normal for an rvalue reference, after calling this function source will be unusable. Any arc references or node pointers that referred to either this graph or source will remain valid (and will all now refer to this graph), though if they originally referred to source then they will now return different numerical node indices.

Calling graph.insertGraph(source) (where source is an rvalue reference) is similar to calling source.moveContentsTo(graph), but it is a little faster since it does not need to leave source in a usable state.

Precondition
source is not this graph.
Python
Not present. Only the copying version of this function is available (i.e., the version that takes source as a const reference). If you want a fast move operation, call source.moveContentsTo(this).
Parameters
sourcethe graph whose contents should be moved.

◆ isConnected()

bool regina::ModelLinkGraph::isConnected ( ) const
inline

Identifies whether this graph is connected.

For the purposes of this routine, an empty graph is considered to be connected.

Warning
This routine is not thread-safe, since it caches the number of components after computing it for the first time.
Returns
true if and only if this graph is connected.

◆ isEmpty()

bool regina::ModelLinkGraph::isEmpty ( ) const
inline

Determines whether this graph is empty.

An empty graph is one with no nodes at all.

Returns
true if and only if this graph is empty.

◆ isSimple()

bool regina::ModelLinkGraph::isSimple ( ) const

Identifies whether this graph is simple; that is, has no loops or multiple edges.

Returns
true if and only if this graph is simple.

◆ moveContentsTo()

void regina::ModelLinkGraph::moveContentsTo ( ModelLinkGraph & dest)

Moves the contents of this graph into the given destination graph, leaving this graph empty but otherwise usable.

The nodes of this graph will be moved directly into dest, and placed after any pre-existing nodes. Specifically, if the original number of nodes in dest was N, then node i of this graph will become node N+i of dest.

This graph will become empty as a result, but it will otherwise remain a valid and usable ModelLinkGraph object. Any arc references or node pointers that referred to either this graph or dest will remain valid (and will all now refer to dest), though if they originally referred to this graph then they will now return different numerical node indices.

Calling graph.moveContentsTo(dest) is similar to calling dest.insertGraph(std::move(graph)); it is a little slower but it comes with the benefit of leaving this graph in a usable state.

Precondition
dest is not this graph.
Parameters
destthe graph into which the contents of this graph should be moved.

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

◆ nodes()

auto regina::ModelLinkGraph::nodes ( ) const
inline

Returns an object that allows iteration through and random access to all nodes in this graph.

The object that is returned is lightweight, and can be happily copied by value. The C++ type of the object is subject to change, so C++ users should use auto (just like this declaration does).

The returned object is guaranteed to be an instance of ListView, which means it offers basic container-like functions and supports range-based for loops. Note that the elements of the list will be pointers, so your code might look like:

for (ModelLinkGraphNode* n : graph.nodes()) { ... }
Represents a single node in a model graph for a knot or link.
Definition modellinkgraph.h:410
auto nodes() const
Returns an object that allows iteration through and random access to all nodes in this graph.
Definition modellinkgraph.h:2332

The object that is returned will remain up-to-date and valid for as long as the graph exists: even if nodes are added and/or removed, it will always reflect the nodes that are currently in the graph. Nevertheless, it is recommended to treat this object as temporary only, and to call nodes() again each time you need it.

Returns
access to the list of all nodes.

◆ operator=() [1/2]

ModelLinkGraph & regina::ModelLinkGraph::operator= ( const ModelLinkGraph & src)

Sets this to be a (deep) copy of the given graph.

Parameters
srcthe graph to copy.
Returns
a reference to this graph.

◆ operator=() [2/2]

ModelLinkGraph & regina::ModelLinkGraph::operator= ( ModelLinkGraph && src)
inlinenoexcept

Moves the contents of the given graph into this graph.

This is a fast (constant time) operation.

All nodes and cells that belong to src will be moved into this graph, and so any ModelLinkGraphNode or ModelLinkGraphCells pointers or references will remain valid.

The graph that is passed (src) will no longer be usable.

Parameters
srcthe graph to move.
Returns
a reference to this graph.

◆ operator==()

bool regina::ModelLinkGraph::operator== ( const ModelLinkGraph & other) const

Determines if this graph is combinatorially identical to the given graph.

Here "identical" means that both graphs have the same number of nodes, and in both graphs the same pairs of outgoing arcs of numbered nodes are connected by edges.

Parameters
otherthe graph to compare with this.
Returns
true if and only if the two graphs are combinatorially identical.

◆ plantri()

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

Outputs this graph in a variant of 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 letters, encoding the endpoints of the four edges in clockwise order that leave node i. The lower-case letters a,b,...,z represent nodes 0,1,...,25 respectively, and the upper-case letters A,B,...,Z represent nodes 26,27,...,51 respectively. An example of such a string is:

bcdd,aeec,abfd,acfa,bffb,ceed

For graphs with at most 26 nodes, this is identical to plantri's own dual ASCII format. For larger graphs, this format differs: plantri uses punctuation to represent higher-index nodes, whereas Regina uses upper-case letters.

Although plantri is designed to work with graphs that are connected and planar, this routine will happily produce output for disconnected and/or non-planar graphs. However, there remains an unavoidable requirement: the graph must be dual to a simple quadrangulation. In detail:

  • The dual to this 4-valent graph will be a quadrangulation of the surface in which it embeds. The plantri format inherently requires that this quadrangulation is simple: that is, the dual must have no loops or parallel edges.
  • This requirement exists because, if the dual is not simple, the embedding of the original graph cannot be uniquely reconstructed from its plantri output. In particular, the embedding becomes ambiguous around parallel edges in the original 4-valent graph.
  • For planar graphs, this requirement is relatively harmless: a parity condition shows that loops in the dual are impossible, and parallel edges in the dual mean that any link diagram that this graph models is an "obvious" connected sum.
  • For non-planar graphs, this requirement is more problematic. For example, consider the graph that models the virtual trefoil: the dual quadrangulation of the torus contains both loops and parallel edges. This makes the plantri format unusable in practice for graps that model virtual links.

If this constraint is too onerous (e.g., you are working with virtual links), you could use extendedPlantri() instead, which is not compatible with the Brinkmann-McKay plantri software but which removes this requirement for the dual quadrangulation to be simple.

For graphs that the plantri format does support, this routine is an inverse to fromPlantri(). That is, 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.

Note
The output of this function might not correspond to any possible output from the program plantri itself, even if the graph is connected and planar, the dual quadrangulation is simple, and only lower-case letters are used. 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 has between 1 and 52 nodes inclusive.
The dual to this graph is a simple quadrangulation of the surface in which it embeds.
Exceptions
FailedPreconditionThis graph is empty or has more than 52 nodes.
Returns
a plantri format ASCII representation of this graph.

◆ randomise()

void regina::ModelLinkGraph::randomise ( )

Randomly relabels this graph in an orientation-preserving manner.

The nodes will be relabelled arbitrarily. Around each node, the four outgoing arcs will be relabelled in a random way that preserves their cyclic order (thereby preserving the local embedding of the graph, without reflection).

This routine is thread-safe, and uses RandomEngine for its random number generation.

◆ 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 use plain ASCII characters where possible, and should not contain any newlines.

Within these limits, this short text ouptut should be as information-rich as possible, since in most cases this forms the basis for the Python __str__() and __repr__() functions.

Python
The Python "stringification" function __str__() will use precisely this function, and for most classes the Python __repr__() function will incorporate this into its output.
Returns
a short text representation of this object.

◆ swap()

void regina::ModelLinkGraph::swap ( ModelLinkGraph & other)
inlinenoexcept

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.

◆ tightDecode()

static ModelLinkGraph regina::ModelLinkGraph::tightDecode ( std::istream & input)
static

Reconstructs a graph from its given tight encoding.

See the page on tight encodings for details.

The tight encoding will be read from the given input stream. If the input stream contains leading whitespace then it will be treated as an invalid encoding (i.e., this routine will throw an exception). The input stream may contain further data: if this routine is successful then the input stream will be left positioned immediately after the encoding, without skipping any trailing whitespace.

Exceptions
InvalidInputThe given input stream does not begin with a tight encoding of a graph.
Python
Not present. Use tightDecoding() instead, which takes a string as its argument.
Parameters
inputan input stream that begins with the tight encoding for a graph.
Returns
the graph represented by the given tight encoding.

◆ tightDecoding()

static ModelLinkGraph regina::TightEncodable< ModelLinkGraph >::tightDecoding ( const std::string & enc)
inlinestaticinherited

Reconstructs an object of type T from its given tight encoding.

See the page on tight encodings for details.

The tight encoding should be given as a string. If this string contains leading whitespace or any trailing characters at all (including trailing whitespace), then it will be treated as an invalid encoding (i.e., this routine will throw an exception).

Exceptions
InvalidArgumentThe given string is not a tight encoding of an object of type T.
Parameters
encthe tight encoding for an object of type T.
Returns
the object represented by the given tight encoding.

◆ tightEncode()

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

Writes the tight encoding of this graph to the given output stream.

See the page on tight encodings for details.

Python
Not present. Use tightEncoding() instead, which returns a string.
Parameters
outthe output stream to which the encoded string will be written.

◆ tightEncoding()

std::string regina::TightEncodable< ModelLinkGraph >::tightEncoding ( ) const
inlineinherited

Returns the tight encoding of this object.

See the page on tight encodings for details.

Exceptions
FailedPreconditionThis may be thrown for some classes T if the object is in an invalid state. If this is possible, then a more detailed explanation of "invalid" can be found in the class documentation for T, under the member function T::tightEncode(). See FacetPairing::tightEncode() for an example of this.
Returns
the resulting encoded string.

◆ 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 not contain any newlines, and (within these constraints) should be as information-rich as is reasonable.

Unlike str(), this function may use unicode characters to make the output more pleasant to read. The string that is returned 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. Use detail() instead.
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. Use str() instead.
Parameters
outthe output stream to which to write.

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