Regina Calculation Engine
|
Represents an undirected 4-valent planar graph with a specific planar embedding. More...
#include <link/modellinkgraph.h>
Public Types | |
typedef void(* | Use) (Link *, void *) |
A routine that can do arbitrary processing upon a knot or link. More... | |
Public Member Functions | |
ModelLinkGraph () | |
Constructs an empty graph. More... | |
ModelLinkGraph (const ModelLinkGraph ©) | |
Constructs a new copy of the given graph. More... | |
~ModelLinkGraph () | |
Destroys this graph. More... | |
size_t | size () const |
Returns the number of nodes in this graph. More... | |
ModelLinkGraphNode * | node (size_t index) const |
Returns the node at the given index within this graph. More... | |
void | swapContents (ModelLinkGraph &other) |
Swaps the contents of this and the given graph. More... | |
void | reflect () |
Converts this graph into its reflection. More... | |
const ModelLinkGraphCells & | cells () const |
Returns details of the cellular decomposition of the sphere that is induced by this graph. More... | |
std::pair< ModelLinkGraphArc, ModelLinkGraphArc > | findFlype (const ModelLinkGraphArc &from) const |
TODO: Flype is between arc– and arc, i.e., over the region defined by cell(arc). More... | |
ModelLinkGraph * | flype (const ModelLinkGraphArc &from, const ModelLinkGraphArc &left, const ModelLinkGraphArc &right) const |
TODO: Document. More... | |
ModelLinkGraph * | flype (const ModelLinkGraphArc &from) const |
TODO: Document. More... | |
void | generateMinimalLinks (Use use, void *useArgs=0) const |
TODO: Document. More... | |
std::string | plantri () const |
Outputs this graph in the ASCII text format used by plantri. More... | |
std::string | canonicalPlantri (bool useReflection=true, bool tight=false) const |
Outputs a text representation of this graph in the plantri ASCII format, using a canonical relabelling of nodes and arcs, and with optional compression. More... | |
void | writeTextShort (std::ostream &out) const |
Writes a short text representation of this graph to the given output stream. More... | |
void | writeTextLong (std::ostream &out) const |
Writes a detailed text representation of this graph to the given output stream. More... | |
ModelLinkGraph & | operator= (const ModelLinkGraph &)=delete |
std::string | str () const |
Returns a short text representation of this object. More... | |
std::string | utf8 () const |
Returns a short text representation of this object using unicode characters. More... | |
std::string | detail () const |
Returns a detailed text representation of this object. More... | |
Static Public Member Functions | |
static ModelLinkGraph * | fromPlantri (const std::string &plantri) |
Builds a graph from a line of plantri output. More... | |
Represents an undirected 4-valent planar graph with a specific planar embedding.
This can be used as the model graph for a knot or link diagram, where each node of the graph becomes a crossing.
Current this class does not support circular graph components (which, in a link diagram, would correspond to zero-crossing unknot components of the link).
This class is primarily designed for enumerating knots and links. If you wish to study the underlying graph of an existing link, you do not need to create a ModelLinkGraph - instead the Link class already gives you direct access to the graph structure. In particular, if you include link/graph.h, you can use a Link directly as a directed graph type with the Boost Graph Library.
typedef void(* regina::ModelLinkGraph::Use) (Link *, void *) |
A routine that can do arbitrary processing upon a knot or link.
Such routines are used to process links that are found when running generateMinimalLinks().
The first parameter passed should be a link, which must be deallocated by this routine. The second parameter may contain arbitrary data as passed to generateMinimalLinks().
Note that the first parameter might be null
to signal that link generation has finished.
|
inline |
Constructs an empty graph.
regina::ModelLinkGraph::ModelLinkGraph | ( | const ModelLinkGraph & | copy | ) |
Constructs a new copy of the given graph.
copy | the graph to copy. |
|
inline |
Destroys this graph.
The ModelLinkGraphNode objects contained in this graph will also be destroyed.
std::string regina::ModelLinkGraph::canonicalPlantri | ( | bool | useReflection = true , |
bool | tight = false |
||
) | const |
Outputs a text representation of this graph in the plantri ASCII format, using a canonical relabelling of nodes and arcs, and with optional compression.
This routine is similar to plantri(), but with two significant differences:
true
then we allow for reflection also.true
, then this routine uses an abbreviated output format. The resulting compression is only trivial (it reduces the length by roughly 40%), but the resulting string is still human-parseable (though with a little more effort required). This compression will simply remove the commas, and for each node it will suppress the destination of the first arc (since this can be deduced from the canonical labelling).Regardless of whether tight is true
or false
, the resulting string can be parsed by fromPlantri() to reconstruct the original graph. Note however that, due to the canonical labelling, the resulting graph might be a relabelling of the original (and might even be a reflection of the original, if useReflection was passed as true
).
See plantri() for further details on the ASCII format itself.
The running time for this routine is quadratic in the size of the graph.
useReflection | 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 details of the cellular decomposition of the sphere that is induced by this graph.
This cellular decomposition will only be computed on demand. This means that the first call to this function will take linear time (as the decomposition is computed), but subsequent calls will be constant time (since the decomposition is cached).
|
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::pair<ModelLinkGraphArc, ModelLinkGraphArc> regina::ModelLinkGraph::findFlype | ( | const ModelLinkGraphArc & | from | ) | const |
TODO: Flype is between arc– and arc, i.e., over the region defined by cell(arc).
Returns (null, null) iff flype() will refuse to work with this. Otherwise returns (left outgoing arc, right outgoing arc).
Conditions that explicitly return null:
ModelLinkGraph* regina::ModelLinkGraph::flype | ( | const ModelLinkGraphArc & | from, |
const ModelLinkGraphArc & | left, | ||
const ModelLinkGraphArc & | right | ||
) | const |
TODO: Document.
Cell A __ __ \ / ----> left X Cell B __/ \__from ----> right Cell C
Conditions that explicitly return 0:
|
inline |
TODO: Document.
|
static |
Builds a graph from a line of plantri output.
The software plantri, by Gunnar Brinkmann and Brendan McKay, can be used to enumerate 4-valent planar graphs (amongst many other things). This routine converts a piece of output from plantri into a ModelLinkGraph object that Regina can work with directly.
The output from plantri must be in ASCII format, and must be the dual graph of a simple quadrangulation of the sphere. The corresponding flags that must be passed to plantri to obtain such output are -adq
(although you will may wish to pass additional flags to expand or restrict the classes of graphs that plantri builds).
When run with these flags, plantri produces output in the following form:
6 bbcd,adca,abee,affb,cffc,deed 6 bcdd,aeec,abfd,acfa,bffb,ceed 6 bcde,affc,abfd,acee,addf,becb
Each line consists of an integer (the number of nodes in the graph), followed by a comma-separated sequence of alphabetical strings that encode the edges leaving each node.
This function only takes the comma-separated sequence of alphabetical strings. So, for example, to construct the graph correpsonding to the second line of output above, you could call:
Regina can only recognise graphs in this format with up to 26 nodes. If the graph contains more than 27 nodes then the plantri output will contain punctuation, Regina will not be able to parse it, and this function will return null
.
The given string does not need to be come from the program plantri itself. Whereas plantri always outputs graphs with a particular canonical labelling, this function can accept an arbitrary ordering of nodes and arcs - in particular, it can accept the string g.plantri()
for any graph g that meets the preconditions below. Nevertheless, the graph must still meet these preconditions, since otherwise the plantri format might not be enough to uniquely reconstruct the graph and its planar embedding.
This routine can also interpret the "tight" format that is output by the member function canonicalPlantri() (even though such output would certainly not be produced by the program plantri).
plantri | a string containing the comma-separated sequence of alphabetical strings output by plantri, as described above. |
null
if the input was found to be invalid. void regina::ModelLinkGraph::generateMinimalLinks | ( | Use | use, |
void * | useArgs = 0 |
||
) | const |
TODO: Document.
Only aims for minimal, ignores reflections.
Node n will become crossing n.
Arc (0,0) will always be forwards, and crossing 0 will always be positive.
TODO: PRE: Knot, not link.
|
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. |
std::string regina::ModelLinkGraph::plantri | ( | ) | const |
Outputs this graph in the ASCII text format used by plantri.
The software plantri, by Gunnar Brinkmann and Brendan McKay, can be used to enumerate 4-valent planar graphs (amongst many other things). This routine outputs this graph in a format that mimics plantri's own dual ASCII format (i.e., the format that plantri outputs when run with the flags -adq
).
Specifically, the output will be a comma-separated sequence of alphabetical strings. The ith such string will consist of four lower-case letters, encoding the endpoints of the four edges in clockwise order that leave node i. The letters a
,b
,c
,... represent nodes 0,1,2,... respectively. An example of such a string is:
bcdd,aeec,abfd,acfa,bffb,ceed
This routine is an inverse to fromPlantri(): for any graph g that satisfies the preconditions below, fromPlantri(g.plantri())
is identical to g. Likewise, for any string s that satisfies the preconditions for fromPlantri(), calling fromPlantri(s).plantri()
will recover the original string s.
It is important to note the preconditions below: in particular, that this graph must be dual to a simple quadrangulation of the sphere. This is because the planar embeddings for more general graphs (i.e., the duals of non-simple quadrangulations) cannot always be uniquely reconstructed from their plantri output.
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 fit on a single line, and should not end with a newline. Where possible, it should use plain ASCII characters.
__str__()
.
|
inline |
Swaps the contents of this and the given graph.
All nodes that belong to this graph will be moved to other, and all nodes that belong to other will be moved to this graph.
In particular, any ModelLinkGraphNode pointers or references and any ModelLinkGraphArc objects will remain valid.
This routine will behave correctly if other is in fact this graph.
other | the graph whose contents should be swapped with this. |
|
inherited |
Returns a short text representation of this object using unicode characters.
Like str(), this text should be human-readable, should fit on a single line, and should not end with a newline. In addition, it may use unicode characters to make the output more pleasant to read. This string will be encoded in UTF-8.
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. |