A cut that separates a triangulation, facet pairing or link diagram into two pieces. More...

#include <triangulation/cut.h>

Inheritance diagram for regina::Cut:

Public Member Functions
	Cut (size_t size)
	Creates a new trivial cut on the given number of nodes.

	Cut (size_t side0, size_t side1)
	Creates a new cut with the given partition sizes.

	Cut (const Cut &src)
	Creates a new copy of the given cut.

	Cut (Cut &&src) noexcept
	Moves the given cut into this new cut.

template<typename iterator >
	Cut (iterator begin, iterator end)
	Creates a new cut using the given partition.

	~Cut ()
	Destroys this cut.

size_t	size () const
	Returns the total number of nodes in the underlying graph-like object.

size_t	size (int whichSide) const
	Returns the number of nodes on the given side of the partition described by this cut.

int	side (size_t node) const
	Indicates which side of the partition the given node lies on.

void	set (size_t node, int newSide)
	Allows you to set which side of the partition the given node lies on.

bool	isTrivial () const
	Determines whether this cut places all nodes on the same side of the partition.

template<int dim>
size_t	weight (const Triangulation< dim > &tri) const
	Returns the weight of this cut with respect to the dual graph of the given triangulation.

template<int dim>
size_t	weight (const FacetPairing< dim > &pairing) const
	Returns the weight of this cut with respect to the given facet pairing.

size_t	weight (const Link &link) const
	Returns the weight of this cut with respect to the given link diagram.

size_t	weight (const ModelLinkGraph &graph) const
	Returns the weight of this cut with respect to the given model link graph.

Cut &	operator= (const Cut &src)
	Sets this to be a copy of the given cut.

Cut &	operator= (Cut &&src) noexcept
	Moves the given cut into this cut.

void	swap (Cut &other) noexcept
	Swaps the contents of this and the given cut.

bool	operator== (const Cut &rhs) const
	Determines if this and the given cut are identical.

template<int dim>
std::pair< Triangulation< dim >, Triangulation< dim > >	operator() (const Triangulation< dim > &tri) const
	Partitions the given triangulation using this cut.

template<int dim>
std::pair< FacetPairing< dim >, FacetPairing< dim > >	operator() (const FacetPairing< dim > &pairing) const
	Partitions the given facet pairing using this cut.

template<int dim>
std::pair< Isomorphism< dim >, Isomorphism< dim > >	inclusion () const
	Returns the relationships between simplex numbers before and after this cut is used to partition a triangulation or facet pairing into two pieces.

bool	inc ()
	Converts this into the next cut of the same size.

bool	incFixedSizes ()
	Converts this into the next cut with the same partition sizes.

void	writeTextShort (std::ostream &out) const
	Writes a short text representation of this object to the given output stream.

void	writeTextLong (std::ostream &out) const
	A default implementation for detailed output.

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.

Detailed Description

A cut that separates a triangulation, facet pairing or link diagram into two pieces.

This is essentially the same concept as a cut in graph theory.

Specifically:

A cut in a triangulation or facet pairing partitions the top-dimensional simplices into two sides. This describes how to split the triangulation or facet pairing into two pieces, by removing all gluings between simplices on opposite sides.
A cut in a link diagram or a model link graph likewise partitions the crossings or nodes into two sides. However, since links in Regina cannot have free ends, cuts cannot be used to divide a link diagram into two smaller pieces (and likewise for model link graphs).

In general, we will use the word nodes to refer to the objects that are partitioned by the cut (e.g., the top-dimensional simplices of a triangulation, or the crossings of a link diagram), and we will use the word arcs to refer to the connections between these objects (e.g., the individual gluings between top-dimensional simplices, or the arcs between crossings in a link diagram).

The two sides of a cut are numbered 0 and 1. In Regina, a cut has a size and a weight:

The size refers to the size of the underlying graph-like object; that is, the total number of nodes (using the terminology above).
The weight is the usual concept of weight from graph theory; that is, the number of arcs that cross between the two sides of the partition. In particular, for triangulations and facet pairings, it counts the number of gluings between top-dimensional simplices that would be undone when using the cut to subdivide the object into two pieces.

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

◆ Cut() [1/5]

regina::Cut::Cut ( size_t size )

inline

Creates a new trivial cut on the given number of nodes.

All nodes will be on side 0.

Parameters

size	the number of nodes in the underlying graph-like object.

◆ Cut() [2/5]

regina::Cut::Cut	(	size_t	side0,
		size_t	side1 )

inline

Creates a new cut with the given partition sizes.

The total number of nodes under consideration will be side0 + side1; the first side0 nodes will be on side 0, and the remaining side1 nodes will be on side 1.

Parameters

side0	the number of nodes on side 0 of the partition.
side1	the number of nodes on side 1 of the partition.

◆ Cut() [3/5]

regina::Cut::Cut ( const Cut & src )

inline

Creates a new copy of the given cut.

Parameters

src	the cut to copy.

◆ Cut() [4/5]

regina::Cut::Cut ( Cut && src )

inlinenoexcept

Moves the given cut into this new cut.

This is a fast (constant time) operation.

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

Parameters

src	the cut to move.

◆ Cut() [5/5]

template<typename iterator >

regina::Cut::Cut	(	iterator	begin,
		iterator	end )

Creates a new cut using the given partition.

Here a cut on n nodes is described by a sequence of n integers, each equal to 0 or 1, indicating which side of the partition each node lies on.

Precondition: The type iterator, when dereferenced, can be cast to an int.

Warning: This routine computes the number of nodes by subtracting end - begin, and so ideally iterator should be a random access iterator type for which this operation is constant time.

Exceptions

InvalidArgument Some element of the given sequence is neither 0 nor 1.

Python: Instead of a pair of iterators, this routine takes a python list of integers.

Parameters

begin	an iterator pointing to the beginning of the 0-1 sequence of sides.
end	a past-the-end iterator indicating the end of the 0-1 sequence of sides.

◆ ~Cut()

regina::Cut::~Cut ( )

inline

Destroys this cut.

Member Function Documentation

◆ detail()

std::string regina::Output< Cut, supportsUtf8 >::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.

◆ inc()

bool regina::Cut::inc ( )

Converts this into the next cut of the same size.

The total number of nodes will stay the same, but the number on each side of the partition may change.

To iterate through all cuts of the given size, you should create a new Cut(size) and then make repeated calls to inc().

If this is already the last partition in such an iteration (i.e., all nodes are already on side 1), then this routine will return false and convert this into the first such partition.

The order of iteration using inc() is lexicographical in the sequence of sides. In particular, if you wish to avoid seeing each cut again with sides 0 and 1 swapped, then you can use the fact that all cuts with side(0) == 0 will be seen before any cuts with side(0) == 1.

Returns: true if the partition was successfully incremented, or false if this was already the last partition in such an iteration.

◆ incFixedSizes()

bool regina::Cut::incFixedSizes ( )

inline

Converts this into the next cut with the same partition sizes.

Specifically, the number of nodes on each side of the partition will remain the same.

To iterate through all cuts with the given parititon sizes, you should create a new Cut(side0, side1) and then make repeated calls to incFixedSizes().

If this is already the last partition in such an iteration, then this routine will return false and convert this into the first such permutation.

The order of iteration using incFixedSizes() is lexicographical in the sequence of sides. In particular, if you wish to avoid seeing each cut again with sides 0 and 1 swapped, then you can use the fact that all cuts with side(0) == 0 will be seen before any cuts with side(0) == 1.

Returns: true if the partition was successfully incremented, or false if this was already the last partition in such an iteration.

◆ inclusion()

template<int dim>

std::pair< Isomorphism< dim >, Isomorphism< dim > > regina::Cut::inclusion ( ) const

Returns the relationships between simplex numbers before and after this cut is used to partition a triangulation or facet pairing into two pieces.

Specifically: let from be a trianglation or facet pairing, and let (a, b) be the result of partitioning from using this cut, so (a, b) = cut(from).

Then this routine returns two isomorphisms p and q, where p describes how a appears as a subcomplex of from, and q describes how b appears as a subcomplex of from. These isomorphisms will be in the direction from a and b to from.

The only interesting parts of these isomorphisms are the mappings between the indices of top-dimensional simplices; all of the facet permutations within each top-dimensional simplex will be identity permutations.

Python: Since Python does not support templates, the dimension dim should be passed as an argument to this function.

Template Parameters

dim	indicates which type of isomorphisms to return. Specifically, this integer parameter indicates the dimension of triangulation on which these isomorphisms act.

Returns: the two inclusion maps corresponding to this partition.

◆ isTrivial()

bool regina::Cut::isTrivial ( ) const

Determines whether this cut places all nodes on the same side of the partition.

Returns: true if all nodes are on side 0 or all nodes are on side 1, or false if both sides of the partition are non-empty.

◆ operator()() [1/2]

template<int dim>

std::pair< FacetPairing< dim >, FacetPairing< dim > > regina::Cut::operator() ( const FacetPairing< dim > & pairing ) const

Partitions the given facet pairing using this cut.

This routine will return two facet pairings: the first will contain all the top-dimensional simplices on side 0 of this cut, and the second will contain all the top-dimensional simplices on side 1. All matchings between simplex facets within the same side of the partition will be preserved, but any matchings that cross the partition will be lost (and so the corresponding simplex facets will become unmatched).

You can call inclusion() if you need to know how the simplex numbers of the resulting pairings correspond to the simplex numbers of the original pairing.

Precondition: The given facet pairing has precisely size() top-dimensional simplices.; Since empty facet pairings are not allowed, this cut must have at least one top-dimensional simplex on each side.

Exceptions

InvalidArgument	The given facet pairing does not have precisely size() top-dimensional simplices.
FailedPrecondition	This cut has all of its top-dimensional simplices on the same side.

Parameters

pairing the facet pairing to partition.

Returns: the two resulting facet pairings, one for each side of the partition.

◆ operator()() [2/2]

template<int dim>

std::pair< Triangulation< dim >, Triangulation< dim > > regina::Cut::operator() ( const Triangulation< dim > & tri ) const

Partitions the given triangulation using this cut.

This routine will return two triangulations: the first will contain all the top-dimensional simplices on side 0 of this cut, and the second will contain all the top-dimensional simplices on side 1. All gluings within the same side of the partition will be preserved, but any gluings that cross the partition will be lost (and so the corresponding simplex facets will become boundary).

You can call inclusion() if you need to know how the simplex numbers of the resulting triangulations correspond to the simplex numbers of the original triangulation.

If any of the facets that cross the partition are locked in the source triangulation tri, this will not prevent the operation from occurring (since the source triangulation will not be changed). The two triangulations that are returned will have no simplex and/or facet locks at all.

Precondition: The given triangulation has precisely size() top-dimensional simplices.

Exceptions

InvalidArgument The given triangulation does not have precisely size() top-dimensional simplices.

Parameters

tri	the triangulation to partition.

Returns: the two resulting triangulations, one for each side of the partition.

◆ operator=() [1/2]

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

inline

Sets this to be a copy of the given cut.

It does not matter if this and the given cut have different sizes (i.e., work with different numbers of nodes); if they do then this cut will be resized as a result.

Parameters

src	the cut to copy.

Returns: a reference to this cut.

◆ operator=() [2/2]

Cut & regina::Cut::operator= ( Cut && src )

inlinenoexcept

Moves the given cut into this cut.

This is a fast (constant time) operation.

It does not matter if this and the given cut have different sizes (i.e., work with different numbers of nodes); if they do then this cut will be resized as a result.

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

Parameters

src	the cut to move.

Returns: a reference to this cut.

◆ operator==()

bool regina::Cut::operator== ( const Cut & rhs ) const

inline

Determines if this and the given cut are identical.

Two cuts are considered identical if they describe the same partition of nodes into sides 0 and 1.

It does not matter if this and the given cut have different sizes; in this case they will be considered different.

Parameters

rhs	the cut to compare with this.

Returns: true if and only if this and the given cut are identical.

◆ set()

void regina::Cut::set	(	size_t	node,
		int	newSide )

inline

Allows you to set which side of the partition the given node lies on.

Exceptions

InvalidArgument The given side is not 0 or 1.

Parameters

node	the node being changed; this must be between 0 and size()-1 inclusive.
newSide	the side of the partition that the given node should lie on; this must be either 0 or 1.

◆ side()

int regina::Cut::side ( size_t node ) const

inline

Indicates which side of the partition the given node lies on.

Parameters

node	the node being queried; this must be between 0 and size()-1 inclusive.

Returns: the corresponding side of the partition; this will be either 0 or 1.

◆ size() [1/2]

size_t regina::Cut::size ( ) const

inline

Returns the total number of nodes in the underlying graph-like object.

In particular, if you are working with a triangulation or facet pairing, then this returns the number of top-dimensional simplices.

Returns: the total number of nodes.

◆ size() [2/2]

size_t regina::Cut::size ( int whichSide ) const

inline

Returns the number of nodes on the given side of the partition described by this cut.

It will always be true that size(0) + size(1) == size().

Warning: This routine runs in linear time, since the sizes of the individual sides are not cached. This is in contrast to the overall total size(), which is cached, and which runs in constant time.

Exceptions

InvalidArgument The given side is not 0 or 1.

Parameters

whichSide the side of the partition to query; this must be either 0 or 1.

Returns: the number of nodes on the given side.

◆ str()

std::string regina::Output< Cut, supportsUtf8 >::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::Cut::swap ( Cut & other )

inlinenoexcept

Swaps the contents of this and the given cut.

Parameters

other the cut whose contents are to be swapped with this.

◆ utf8()

std::string regina::Output< Cut, supportsUtf8 >::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.

◆ weight() [1/4]

template<int dim>

size_t regina::Cut::weight ( const FacetPairing< dim > & pairing ) const

Returns the weight of this cut with respect to the given facet pairing.

This is the number of matchings between facets of simplices in the given pairing that cross the partition described by this cut.

In other words, this routine counts the number of facets of top-dimensional simplices on side 0 of the cut that are paired with a facet of some top-dimensional simplex on side 1.

Precondition: The given facet pairing has precisely size() top-dimensional simplices.

Exceptions

InvalidArgument The given facet pairing does not have precisely size() top-dimensional simplices.

Parameters

pairing the facet pairing under consideration.

Returns: the weight of this cut with respect to pairing.

◆ weight() [2/4]

size_t regina::Cut::weight ( const Link & link ) const

Returns the weight of this cut with respect to the given link diagram.

This is the number of arcs in the link diagram that cross the partition described by this cut.

Precondition: The given link diagram has precisely size() crossings.

Exceptions

InvalidArgument The given link diagram does not have precisely size() crossings.

Parameters

link	the link diagram under consideration.

Returns: the weight of this cut with respect to link.

◆ weight() [3/4]

size_t regina::Cut::weight ( const ModelLinkGraph & graph ) const

Returns the weight of this cut with respect to the given model link graph.

This is the number of arcs in the graph that cross the partition described by this cut.

Precondition: The given graph has precisely size() nodes.

Exceptions

InvalidArgument The given graph does not have precisely size() nodes.

Parameters

graph the model link graph under consideration.

Returns: the weight of this cut with respect to graph.

◆ weight() [4/4]

template<int dim>

size_t regina::Cut::weight ( const Triangulation< dim > & tri ) const

Returns the weight of this cut with respect to the dual graph of the given triangulation.

This is the number of gluings in the given triangulation that cross the partition described by this cut.

In other words, this routine counts the number of facets of top-dimensional simplices on side 0 of the cut that are glued to a facet of some top-dimensional simplex on side 1.

Precondition: The given triangulation has precisely size() top-dimensional simplices.

Exceptions

InvalidArgument The given triangulation does not have precisely size() top-dimensional simplices.

Parameters

tri	the triangulation under consideration.

Returns: the weight of this cut with respect to tri.

◆ writeTextLong()

void regina::ShortOutput< Cut, false >::writeTextLong ( std::ostream & out ) const

inlineinherited

A default implementation for detailed output.

This routine simply calls T::writeTextShort() and appends a final newline.

Python: Not present. Instead you can call detail() from the subclass T, which returns this output as a string.

Parameters

out	the output stream to which to write.

◆ writeTextShort()

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

Writes a short text representation of this object 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:

triangulation/cut.h

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ Cut() [1/5]

◆ Cut() [2/5]

◆ Cut() [3/5]

◆ Cut() [4/5]

◆ Cut() [5/5]

◆ ~Cut()

Member Function Documentation

◆ detail()

◆ inc()

◆ incFixedSizes()

◆ inclusion()

◆ isTrivial()

◆ operator()() [1/2]

◆ operator()() [2/2]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ set()

◆ side()

◆ size() [1/2]

◆ size() [2/2]

◆ str()

◆ swap()

◆ utf8()

◆ weight() [1/4]

◆ weight() [2/4]

◆ weight() [3/4]

◆ weight() [4/4]

◆ writeTextLong()

◆ writeTextShort()