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

#include <link/modellinkgraph.h>

Inheritance diagram for regina::ModelLinkGraph:

Public Member Functions
	ModelLinkGraph ()
	Constructs an empty graph. More...

	ModelLinkGraph (const ModelLinkGraph &copy)
	Constructs a new copy of the given graph. More...

	ModelLinkGraph (ModelLinkGraph &&src) noexcept
	Moves the given graph into this new 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...

auto	nodes () const
	Returns an object that allows iteration through and random access to all nodes in this graph. More...

ModelLinkGraph &	operator= (const ModelLinkGraph &src)
	Sets this to be a (deep) copy of the given graph. More...

ModelLinkGraph &	operator= (ModelLinkGraph &&src) noexcept
	Moves the contents of the given graph into this graph. More...

void	swap (ModelLinkGraph &other) noexcept
	Swaps the contents of this and the given graph. More...

void	swapContents (ModelLinkGraph &other) noexcept
	Deprecated routine that swaps the contents of this and the given graph. More...

bool	operator== (const ModelLinkGraph &other) const
	Determines if this graph is combinatorially identical to the given graph. More...

bool	operator!= (const ModelLinkGraph &other) const
	Determines if this graph is not combinatorially identical to 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...

template<typename Action , typename... Args>
void	generateMinimalLinks (Action &&action, Args &&... args) 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...

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

Detailed Description

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

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

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

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

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/3]

regina::ModelLinkGraph::ModelLinkGraph ( )

inline

Constructs an empty graph.

◆ ModelLinkGraph() [2/3]

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

Constructs a new copy of the given graph.

Parameters

copy	the graph to copy.

◆ ModelLinkGraph() [3/3]

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

src	the graph to move.

◆ ~ModelLinkGraph()

regina::ModelLinkGraph::~ModelLinkGraph ( )

inline

Destroys this graph.

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

Member Function Documentation

◆ canonicalPlantri()

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

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

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

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

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

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

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

Precondition: This graph is connected.; This graph has between 1 and 26 nodes inclusive.; The dual to this graph is a simple quadrangulation of the sphere. In particular, the dual must not have any parallel edges. Note that any graph that fails this condition will the model graph for a link diagram that is an "obvious" connected sum.

Parameters

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.

Returns: an optionally compressed plantri ASCII representation of this graph.

◆ cells()

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

inline

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

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

Precondition: This graph is connected.

Returns: the induced cellular decomposition of the sphere.

◆ detail()

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

inherited

Returns a detailed text representation of this object.

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

Returns: a detailed text representation of this object.

◆ findFlype()

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

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

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

Conditions that explicitly return null:

The upper and lower cells are the same.
The common cell is the inside cell at from.node().

Precondition: This graph is connected and TODO: valid.

◆ flype() [1/2]

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

inline

TODO: Document.

Exceptions

InvalidArgument there is no flype available from the given starting arc.

◆ flype() [2/2]

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

TODO: Document.

       Cell A

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

       Cell C

Conditions that explicitly throw exceptions:

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

Even if the arguments are a (non-null) result of findFlype(), this routine could still throw an exception, but only for graphs that model non-minimal and/or composite link diagrams.

Exceptions

InvalidArgument TODO.

◆ fromPlantri()

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

static

Builds a graph from a line of plantri output.

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

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

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

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

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

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

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

regina::ModelLinkGraph::fromPlantri

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

Builds a graph from a line of plantri output.

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

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

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

Warning: While this routine does some basic error checking on the input, these checks are not exhaustive. In particular, it does not test for planarity of the graph. (Of course plantri does not output non-planar graphs, but a user could still construct one by hand and passes it to this routine, in which case the resulting behaviour is undefined.)

Precondition: The graph being described is connected.; The graph being described has between 1 and 26 nodes inclusive.; The graph being described is dual to a simple quadrangulation of the sphere. In particular, the dual must not have any parallel edges. Note that any graph that fails this condition will the model graph for a link diagram that is an "obvious" connected sum.

Exceptions

InvalidArgument the input was not a valid representation of a graph using the plantri output format. As noted above, the checks performed here are not exhaustive.

Parameters

plantri a string containing the comma-separated sequence of alphabetical strings output by plantri, as described above.

Returns: the resulting graph.

◆ generateMinimalLinks()

template<typename Action , typename... Args>

void regina::ModelLinkGraph::generateMinimalLinks	(	Action &&	action,
		Args &&...	args
	)		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.

For each link 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 that was generated. 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.

TODO: PRE: Knot, not link.

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

◆ node()

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

inline

Returns the node at the given index within this graph.

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

Warning: If some nodes are added or removed then the indices of other nodes might change. If you wish to track a particular node through such operations then you should use the pointer to the relevant ModelLinkGraphNode object instead.

Parameters

index the 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 C++11 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()) { ... }

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!=()

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

inline

Determines if this graph is not 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

other the graph to compare with this.

Returns: true if and only if the two graphs are not combinatorially identical.

◆ operator=() [1/2]

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

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

Parameters

src	the 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

src	the 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

other the 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 the ASCII text format used by plantri.

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

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

bcdd,aeec,abfd,acfa,bffb,ceed

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

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

Note: The output of this function might not correspond to any possible output from the program plantri itself. This is because plantri only outputs graphs with a certain canonical labelling. In contrast, plantri() can be called on any graph that satisfies the preconditions below, and it will preserve the labels of the nodes and the order of the arcs around each node.

Precondition: This graph is connected.; This graph has between 1 and 26 nodes inclusive.; The dual to this graph is a simple quadrangulation of the sphere. In particular, the dual must not have any parallel edges. Note that any graph that fails this condition will the model graph for a link diagram that is an "obvious" connected sum.

Returns: a plantri format ASCII representation of this graph.

◆ reflect()

void regina::ModelLinkGraph::reflect ( )

Converts this graph into its reflection.

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

◆ size()

size_t regina::ModelLinkGraph::size ( ) const

inline

Returns the number of nodes in this graph.

Returns: the number of nodes.

◆ str()

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

inherited

Returns a short text representation of this object.

This text should be human-readable, should 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

other the graph whose contents should be swapped with this.

◆ swapContents()

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

inlinenoexcept

Deprecated routine that swaps the contents of this and the given graph.

Deprecated:: Use swap() instead.

Parameters

other the graph whose contents should be swapped with this.

◆ utf8()

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

inherited

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

Like str(), this text should be human-readable, should 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

out	the 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

out	the output stream to which to write.

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

link/modellinkgraph.h

Public Member Functions

Static Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ ModelLinkGraph() [1/3]

◆ ModelLinkGraph() [2/3]

◆ ModelLinkGraph() [3/3]

◆ ~ModelLinkGraph()

Member Function Documentation

◆ canonicalPlantri()

◆ cells()

◆ detail()

◆ findFlype()

◆ flype() [1/2]

◆ flype() [2/2]

◆ fromPlantri()

◆ generateMinimalLinks()

◆ node()

◆ nodes()

◆ operator!=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ plantri()

◆ reflect()

◆ size()

◆ str()

◆ swap()

◆ swapContents()

◆ utf8()

◆ writeTextLong()

◆ writeTextShort()