Regina 7.4 Calculation Engine
|
Represents an undirected 4-valent graph with a specific embedding in some closed orientable surface. More...
#include <link/modellinkgraph.h>
Public Member Functions | |
ModelLinkGraph () | |
Constructs an empty graph. | |
ModelLinkGraph (const Link &link) | |
Constructs the graph that models the given link. | |
ModelLinkGraph (const ModelLinkGraph ©) | |
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. | |
ModelLinkGraphNode * | node (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. | |
ModelLinkGraph & | operator= (const ModelLinkGraph &src) |
Sets this to be a (deep) copy of the given graph. | |
ModelLinkGraph & | operator= (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 ModelLinkGraphCells & | cells () 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, ModelLinkGraphArc > | findFlype (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. | |
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.
|
inline |
Constructs an empty graph.
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().
link | the link that this new graph will model. |
regina::ModelLinkGraph::ModelLinkGraph | ( | const ModelLinkGraph & | copy | ) |
Constructs a new copy of the given graph.
copy | the graph to copy. |
|
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.
src | the graph to move. |
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.
InvalidArgument | Regina could not interpret the given string as representing a graph using any of the supported string types. |
description | a string that describes a 4-valent graph with embedding. |
|
inline |
Destroys this graph.
The ModelLinkGraphNode objects contained in this graph will also be destroyed.
ModelLinkGraph regina::ModelLinkGraph::canonical | ( | bool | allowReflection = true | ) | const |
Returns the canonical relabelling of this graph.
Here "relabelling" allows for any combination of:
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.
allowReflection | true 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. |
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:
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".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.
FailedPrecondition | This graph is empty or has more than 52 nodes. |
allowReflection | true 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. |
tight | false 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. |
|
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.
InvalidArgument | This graph induces more cells than should ever be possible. This should never occur unless the graph is malformed in some way. |
|
inline |
Returns the number of connected components in this graph.
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).
|
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.
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.
FailedPrecondition | This graph is empty or has more than 52 nodes. |
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 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.
from | the 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. |
|
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".
InvalidArgument | There is no suitable flype on this graph from the given starting location (that is, findFlype() returns a pair of null arcs). |
from | the 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. |
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:
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.
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.)InvalidArgument | One 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. |
from | the 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. |
left | the 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. |
right | the 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. |
|
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
InvalidArgument | The input was not a valid representation of a graph using Regina's extended plantri format. |
text | the representation of a graph using Regina's extended plantri format, as described in extendedPlantri(). |
|
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:
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:
A,...,Z
. For these larger graphs, Regina can only recognise Regina's own plantri() and canonicalPlantri() output, not plantri's punctuation-based encodings.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.
InvalidArgument | The input was not a valid representation of a graph using the plantri output format. |
plantri | a string containing the comma-separated sequence of alphabetical strings in plantri format, as described above. |
|
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).
void
.generateAllEmbeddings(pairing, allowReflection, action)
. Moreover, action must take exactly one argument (the graph).InvalidArgument | The given pairing is disconnected and/or has unmatched facets. |
pairing | the 4-valent graph for which we wish to produce local embeddings. |
allowReflection | true if we consider a reflection of the surface in which the graph embeds to produce the same embedding. |
constraints | indicates 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. |
action | a function (or other callable object) to call for each graph that is generated. |
args | any additional arguments that should be passed to action, following the initial graph argument. |
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).
void
.action | a function (or other callable object) to call for each link diagram that is generated. |
args | any additional arguments that should be passed to action, following the initial link diagram argument. |
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.
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:
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).
void
.FailedPrecondition | There is a 1-gon in the cell decomposition induced by this graph. |
action | a function (or other callable object) to call for each link diagram that is generated. |
args | any additional arguments that should be passed to action, following the initial link diagram argument. |
|
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.
|
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.
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.
source | the graph whose copy will be inserted. |
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.
source.moveContentsTo(this)
.source | the graph whose contents should be moved. |
|
inline |
Identifies whether this graph is connected.
For the purposes of this routine, an empty graph is considered to be connected.
true
if and only if this graph is connected.
|
inline |
Determines whether this graph is empty.
An empty graph is one with no nodes at all.
true
if and only if this graph is empty. bool regina::ModelLinkGraph::isSimple | ( | ) | const |
Identifies whether this graph is simple; that is, has no loops or multiple edges.
true
if and only if this graph is simple. 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.
dest | the graph into which the contents of this graph should be moved. |
|
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.
index | the index of the requested node. This must be between 0 and size()-1 inclusive. |
|
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:
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.
ModelLinkGraph & regina::ModelLinkGraph::operator= | ( | const ModelLinkGraph & | src | ) |
Sets this to be a (deep) copy of the given graph.
src | the graph to copy. |
|
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.
src | the graph to move. |
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.
other | the graph to compare with this. |
true
if and only if the two graphs are combinatorially identical. 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:
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.
FailedPrecondition | This graph is empty or has more than 52 nodes. |
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.
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.
|
inline |
Returns the number of nodes in this graph.
|
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.
__str__()
will use precisely this function, and for most classes the Python __repr__()
function will incorporate this into its output.
|
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.
other | the graph whose contents should be swapped with this. |
|
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.
InvalidInput | The given input stream does not begin with a tight encoding of a graph. |
input | an input stream that begins with the tight encoding for a graph. |
|
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).
InvalidArgument | The given string is not a tight encoding of an object of type T. |
enc | the tight encoding for an object of type T. |
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.
out | the output stream to which the encoded string will be written. |
|
inlineinherited |
Returns the tight encoding of this object.
See the page on tight encodings for details.
FailedPrecondition | This 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. |
|
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.
void regina::ModelLinkGraph::writeTextLong | ( | std::ostream & | out | ) | const |
Writes a detailed text representation of this graph to the given output stream.
out | the output stream to which to write. |
void regina::ModelLinkGraph::writeTextShort | ( | std::ostream & | out | ) | const |
Writes a short text representation of this graph to the given output stream.
out | the output stream to which to write. |