template<typename Node>
class libsemigroups::WordGraph< Node >

Defined in word-graph.hpp.

Instances of this class represent word graphs. If the word graph has n nodes, they are represented by the numbers \(\{0, ..., n - 1\}\), and every node has the same number m of out-edges (edges with source that node and target any other node). The number m is referred to as the out-degree of the word graph, or any of its nodes.

Template Parameters

Node	the type of the nodes in the word graph, must be an unsigned integer type.

Public Types
using	adjacency_matrix_type = Eigen::Matrix<double, Eigen::Dynamic, Eigen::Dynamic>
	The type of the adjacency matrix.

using	const_iterator_nodes
	The type of an iterator pointing to the nodes of a word graph.

using	const_iterator_targets
	The type of an iterator pointing to the targets of a node.

using	const_reverse_iterator_nodes
	The type of a reverse iterator pointing to the nodes of a word graph.

using	label_type = Node
	The type of edge labels in a word graph.

using	node_type = Node
	The type of nodes in a word graph.

using	size_type = std::size_t
	Unsigned integer type.

Public Member Functions
	WordGraph (size_type m=0, size_type n=0)
	Construct from number of nodes and out degree.

	WordGraph (WordGraph &&)
	Default move constructor.

	WordGraph (WordGraph const &)
	Default copy constructor.

template<typename OtherNode>
	WordGraph (WordGraph< OtherNode > const &that)
	Construct from WordGraph with another node type.

WordGraph &	add_nodes (size_type nr)
	Add a number of new nodes.

WordGraph &	add_to_out_degree (size_type nr)
	Add to the out-degree of every node.

const_iterator_nodes	cbegin_nodes () const noexcept
	Returns a random access iterator pointing at the first node of the word graph.

const_iterator_targets	cbegin_targets (node_type source) const
	Returns a random access iterator pointing at the target of the edge with label `0` incident to a given node.

const_iterator_targets	cbegin_targets_no_checks (node_type source) const noexcept
	Returns a random access iterator pointing at the target of the edge with label `0` incident to a given node.

const_iterator_nodes	cend_nodes () const noexcept
	Returns a random access iterator pointing one-past-the-last node of the word graph.

const_iterator_targets	cend_targets (node_type source) const
	Returns a random access iterator pointing one beyond the target of the edge with label `out_degree() - 1` incident to a given node.

const_iterator_targets	cend_targets_no_checks (node_type source) const noexcept
	Returns a random access iterator pointing one beyond the target of the edge with label `out_degree() - 1` incident to a given node.

WordGraph &	disjoint_union_inplace (WordGraph< Node > const &that)
	Unites a word graph in-place.

WordGraph &	disjoint_union_inplace_no_checks (WordGraph< Node > const &that)
	Unites a word graph in-place.

size_t	hash_value () const
	Returns a hash value.

template<typename Iterator, typename = std::enable_if_t<detail::IsIterator<Iterator>::value>>
WordGraph &	induced_subgraph (Iterator first, Iterator last)
	Modify in-place to contain the subgraph induced by a range of nodes.

WordGraph &	induced_subgraph (node_type first, node_type last)
	Modify in-place to contain the subgraph induced by a range of nodes.

template<typename Iterator, typename = std::enable_if_t<detail::IsIterator<Iterator>::value>>
WordGraph &	induced_subgraph_no_checks (Iterator first, Iterator last)
	Modify in-place to contain the subgraph induced by a range of nodes.

WordGraph &	induced_subgraph_no_checks (node_type first, node_type last)
	Modify in-place to contain the subgraph induced by a range of nodes.

WordGraph &	init (size_type m=0, size_type n=0)
	Re-initialize the word graph to have `m` nodes and out-degree `n`.

template<typename OtherNode>
WordGraph &	init (WordGraph< OtherNode > const &that)
	Re-initialize the word graph contain a copy of another.

auto	labels () const noexcept
	Returns a range object containing all labels of edges in a word graph.

auto	labels_and_targets (node_type source) const
	Returns a range object containing pairs consisting of edge labels and target nodes.

auto	labels_and_targets_no_checks (node_type source) const noexcept
	Returns a range object containing pairs consisting of edge labels and target nodes.

std::pair< label_type, node_type >	next_label_and_target (node_type s, label_type a) const
	Get the next target of an edge incident to a given node that doesn't equal UNDEFINED.

std::pair< label_type, node_type >	next_label_and_target_no_checks (node_type s, label_type a) const
	Get the next target of an edge incident to a given node that doesn't equal UNDEFINED.

auto	nodes () const noexcept
	Returns a range object containing all nodes in a word graph.

size_type	number_of_edges () const
	Returns the number of edges.

size_type	number_of_edges (node_type s) const
	Returns the number of edges with given source node.

size_type	number_of_edges_no_checks (node_type s) const
	Returns the number of edges with given source node.

size_type	number_of_nodes () const noexcept
	Returns the number of nodes.

bool	operator!= (WordGraph const &that) const
	Check if two word graphs are inequal.

bool	operator< (WordGraph const &that) const
	Check if a word graph is less than another.

bool	operator<= (WordGraph const &that) const
	Check if a word graph is less than or equal to another.

WordGraph &	operator= (WordGraph &&)
	Default move assignment constructor.

WordGraph &	operator= (WordGraph const &)
	Default copy assignment constructor.

bool	operator== (WordGraph const &that) const
	Check if two word graphs are equal.

bool	operator> (WordGraph const &that) const
	Check if a word graph is greater than another.

bool	operator>= (WordGraph const &that) const
	Check if a word graph is greater than or equal to another.

size_type	out_degree () const noexcept
	Returns the out-degree.

WordGraph &	remove_all_targets ()
	Remove all of the edges in the word graph.

WordGraph &	remove_label (label_type a)
	Removes a given label from the word graph.

WordGraph &	remove_label_no_checks (label_type a)
	Removes a given label from the word graph.

WordGraph &	remove_target (node_type s, label_type a)
	Remove an edge from a node with a given label.

WordGraph &	remove_target_no_checks (node_type s, label_type a)
	Remove an edge from a node with a given label.

WordGraph &	reserve (size_type m, size_type n)
	Ensures that the word graph has capacity for a given number of nodes, and out-degree.

WordGraph &	swap_targets (node_type m, node_type n, label_type a)
	Swaps the edge with specified label from one node with another.

WordGraph &	swap_targets_no_checks (node_type m, node_type n, label_type a)
	Swaps the edge with specified label from one node with another.

WordGraph &	target (node_type s, label_type a, node_type t)
	Add an edge from one node to another with a given label.

node_type	target (node_type source, label_type a) const
	Get the target of the edge with given source node and label.

node_type	target_no_checks (node_type s, label_type a) const
	Get the target of the edge with given source node and label.

WordGraph &	target_no_checks (node_type s, label_type a, node_type t)
	Add an edge from one node to another with a given label.

rx::iterator_range< const_iterator_targets >	targets (node_type source) const
	Returns a range object containing all the targets of edges with a given source.

rx::iterator_range< const_iterator_targets >	targets_no_checks (node_type source) const noexcept
	Returns a range object containing all the targets of edges with a given source.

Static Public Member Functions
static WordGraph	random (size_type number_of_nodes, size_type out_degree, std::mt19937 mt=std::mt19937(std::random_device()()))
	Construct a random word graph from number of nodes and out-degree.

Member Typedef Documentation

◆ const_iterator_nodes

template<typename Node>

using const_iterator_nodes

Initial value:

typename detail::IntRange<Node>::const_iterator

◆ const_iterator_targets

template<typename Node>

using const_iterator_targets

Initial value:

typename detail::DynamicArray2<Node>::const_iterator

◆ const_reverse_iterator_nodes

template<typename Node>

using const_reverse_iterator_nodes

Initial value:

typename detail::IntRange<Node>::const_reverse_iterator

Constructor & Destructor Documentation

◆ WordGraph() [1/2]

template<typename Node>

WordGraph	(	size_type	m = 0,
		size_type	n = 0 )

explicit

This function constructs a word graph with m nodes and where the maximum out-degree of any node is n. There are no edges in the defined word graph.

Parameters

m	the number of nodes in the word graph (default: 0).
n	the out-degree of every node (default: 0).

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: \(O(mn)\) where m is the number of nodes, and n is the out-degree of the word graph.

◆ WordGraph() [2/2]

template<typename Node>

template<typename OtherNode>

WordGraph ( WordGraph< OtherNode > const & that )

This function can be used to construct a WordGraph<Node> as a copy of a WordGraph<OtherNode> so long as sizeof(OtherNode) <= sizeof(Node).

Parameters

that	the word graph to copy.

Note: Any edge with target UNDEFINED in that will have target static_cast<Node>(UNDEFINED) in the constructed word graph.

Member Function Documentation

◆ add_nodes()

template<typename Node>

WordGraph & add_nodes ( size_type nr )

This function modifies a word graph in-place so that it has nr new nodes added.

Parameters

nr	the number of nodes to add.

Returns: A reference to *this.

Exceptions: This function guarantees not to throw a LibsemigroupsException. If an exception is thrown, this is guaranteed not to be modified (strong exception guarantee).

Complexity: Linear in (number_of_nodes() + nr) * out_degree().

Iterator validity: This function modifies the object defined by this, any iterators, pointers or references pointing into this may be invalidated by a call to this function.

◆ add_to_out_degree()

template<typename Node>

WordGraph & add_to_out_degree ( size_type nr )

This function modifies a word graph in-place so that the out-degree is increased by nr.

Parameters

nr	the number of new out-edges for every node.

Returns: A reference to *this.

Exceptions: This function guarantees not to throw a LibsemigroupsException. If an exception is thrown, this is guaranteed not to be modified (strong exception guarantee).

Complexity: \(O(mn)\) where m is the number of nodes, and n is the new out degree of the word graph.

Iterator validity: This function modifies the object defined by this, any iterators, pointers or references pointing into this may be invalidated by a call to this function.

◆ cbegin_nodes()

template<typename Node>

const_iterator_nodes cbegin_nodes ( ) const

inlinenoexcept

This function returns a random access iterator pointing at the first node on the word graph.

Returns: An const_iterator_nodes.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant.

◆ cbegin_targets()

template<typename Node>

const_iterator_targets cbegin_targets ( node_type source ) const

nodiscard

This function returns a random access iterator pointing at the target of the edge with label 0 incident to the source node source. This target might equal UNDEFINED.

Parameters

source the source node in the word graph.

Returns: A const_iterator_targets.

Exceptions

LibsemigroupsException if source is out of range (i.e. greater than or equal to number_of_nodes).

Complexity: Constant.

◆ cbegin_targets_no_checks()

template<typename Node>

const_iterator_targets cbegin_targets_no_checks ( node_type source ) const

inlinenodiscardnoexcept

This function returns a random access iterator pointing at the target of the edge with label 0 incident to the source node source. This target might equal UNDEFINED.

Parameters

source a node in the word graph.

Returns: A const_iterator_targets.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant.

Warning: No checks whatsoever on the validity of the arguments are performed.

See also: cbegin_targets.

◆ cend_nodes()

template<typename Node>

const_iterator_nodes cend_nodes ( ) const

inlinenodiscardnoexcept

This function returns a random access iterator pointing one beyond the last node in the word graph.

Returns: An const_iterator_nodes.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant.

◆ cend_targets()

template<typename Node>

const_iterator_targets cend_targets ( node_type source ) const

nodiscard

This function returns a random access iterator pointing one beyond the target of the edge with label out_degree() - 1 incident to the source node source. This target might equal UNDEFINED.

Parameters

source a node in the word graph.

Returns: A const_iterator_targets.

Exceptions

LibsemigroupsException if source is out of range (i.e. greater than or equal to number_of_nodes).

Complexity: Constant.

◆ cend_targets_no_checks()

template<typename Node>

const_iterator_targets cend_targets_no_checks ( node_type source ) const

inlinenodiscardnoexcept

This function returns a random access iterator pointing one beyond the target of the edge with label out_degree() - 1 incident to the source node source. This target might equal UNDEFINED.

Parameters

source a node in the word graph.

Returns: A const_iterator_targets.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant.

Warning: No checks whatsoever on the validity of the arguments are performed.

See also: cend_targets.

◆ disjoint_union_inplace()

template<typename Node>

WordGraph & disjoint_union_inplace ( WordGraph< Node > const & that )

This function changes a WordGraph object in-place to contain the disjoint union of itself and that. The node n of that is mapped to this->number_of_nodes() + n.

Parameters

that	the word graph to unite.

Returns: A reference to *this.

Exceptions

LibsemigroupsException if *this and that do not have the same out-degree.

◆ disjoint_union_inplace_no_checks()

template<typename Node>

WordGraph & disjoint_union_inplace_no_checks ( WordGraph< Node > const & that )

This function changes a WordGraph object in-place to contain the disjoint union of itself and that. The node n of that is mapped to this->number_of_nodes() + n.

Parameters

that	the word graph to unite.

Returns: A reference to *this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Warning: This function does not check its arguments, and it is assumed that *this and that have equal out degree.

◆ hash_value()

template<typename Node>

size_t hash_value ( ) const

inlinenodiscard

Returns: A value of type size_t.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Linear in number_of_nodes times out_degree.

◆ induced_subgraph() [1/2]

template<typename Node>

template<typename Iterator, typename = std::enable_if_t<detail::IsIterator<Iterator>::value>>

WordGraph & induced_subgraph	(	Iterator	first,
		Iterator	last )

This function modifies a WordGraph object in-place to contain its subgraph induced by the range of nodes first to last.

Template Parameters

Iterator the type of first and last (should be iterators).

Parameters

first	iterator pointing at the first node.
last	iterator pointing one beyond the last node.

Returns: A reference to *this.

Exceptions

LibsemigroupsException	if any value in the range specified by `first` and `last` is not a node of the word graph.
LibsemigroupsException	if any target of any edge with source node in the range specified by `first` and `last` does not belong to the same range.

◆ induced_subgraph() [2/2]

template<typename Node>

WordGraph & induced_subgraph	(	node_type	first,
		node_type	last )

This function modifies a WordGraph object in-place to contain its subgraph induced by the range of nodes first to last.

Parameters

first	the first node.
last	one more than the last node.

Returns: A reference to *this.

Exceptions

LibsemigroupsException	if `first` or `last` is out of range.
LibsemigroupsException	if any edge with source in the range `first` to `last` has target outside the range `first` to `last`.

◆ induced_subgraph_no_checks() [1/2]

template<typename Node>

template<typename Iterator, typename = std::enable_if_t<detail::IsIterator<Iterator>::value>>

WordGraph & induced_subgraph_no_checks	(	Iterator	first,
		Iterator	last )

This function modifies a WordGraph object in-place to contain its subgraph induced by the range of nodes first to last.

Template Parameters

Iterator the type of first and last (should be iterators).

Parameters

first	the first node.
last	one more than the last node.

Returns: A reference to *this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Warning: This function performs no checks whatsoever and will result in a corrupted word graph if there are any edges from the nodes \(0, \ldots, n - 1\) to nodes larger than \(n - 1\).

◆ induced_subgraph_no_checks() [2/2]

template<typename Node>

WordGraph & induced_subgraph_no_checks	(	node_type	first,
		node_type	last )

This function modifies a WordGraph object in-place to contain its subgraph induced by the range of nodes first to last.

Parameters

first	the first node.
last	one more than the last node.

Returns: A reference to *this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Warning: This function performs no checks whatsoever and will result in a corrupted word graph if there are any edges from the nodes \(0, \ldots, n - 1\) to nodes larger than \(n - 1\).

◆ init() [1/2]

template<typename Node>

WordGraph & init	(	size_type	m = 0,
		size_type	n = 0 )

This function puts a word graph into the state that it would have been in if it had just been newly constructed with the same parameters m and n.

Parameters

m	the number of nodes in the word graph.
n	the out-degree of every node.

Returns: A reference to *this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: \(O(mn)\) where \(m\) is the number of nodes, and \(n\) is the out-degree of the word graph.

◆ init() [2/2]

template<typename Node>

template<typename OtherNode>

WordGraph & init ( WordGraph< OtherNode > const & that )

This function puts a word graph into the same state that it would have been in if it had just been newly copy constructed with the same parameter that.

Parameters

that	the word graph to copy.

Returns: A reference to *this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: \(O(mn)\) where m is the number of nodes, and n is the out-degree of the word graph.

Note: Any edge with target UNDEFINED in that will have target static_cast<Node>(UNDEFINED) in *this.

◆ labels()

template<typename Node>

auto labels ( ) const

inlinenodiscardnoexcept

This function returns a range object containing all the labels of edges in a word graph.

Returns: A range object.

Exceptions: This function is noexcept and is guaranteed never to throw.

◆ labels_and_targets()

template<typename Node>

auto labels_and_targets ( node_type source ) const

nodiscard

This function returns a range object containing all the edge labels and targets of edges with source source.

Parameters

source the source node.

Returns: A range object.

Exceptions

LibsemigroupsException if source is out of bounds.

◆ labels_and_targets_no_checks()

template<typename Node>

auto labels_and_targets_no_checks ( node_type source ) const

inlinenodiscardnoexcept

This function returns a range object containing all the edge labels and targets of edges with source source.

Parameters

source the source node.

Returns: A range object.

Exceptions: This function is noexcept and is guaranteed never to throw.

Warning: This function performs no checks whatsoever and assumes that source is a valid node of the word graph (i.e. it is not greater than or equal to number_of_nodes).

◆ next_label_and_target()

template<typename Node>

std::pair< label_type, node_type > next_label_and_target	(	node_type	s,
		label_type	a ) const

nodiscard

This function returns the next target of an edge with label greater than or equal to a that is incident to the node s.

If target(s, b) equals UNDEFINED for every value b in the range \([a, n)\), where \(n\) is the return value of out_degree() then x.first and x.second equal UNDEFINED.

Parameters

s	the node.
a	the label.

Returns

Returns a std::pair x where:

x.first is adjacent to s via an edge labelled x.second; and
x.second is the minimum value in the range \([a, n)\) such that target(s, x.second) is not equal to UNDEFINED where \(n\) is the return value of out_degree(); If no such value exists, then {UNDEFINED, UNDEFINED} is returned.

Exceptions

LibsemigroupsException if s does not represent a node in this, or a is not a valid edge label.

Complexity: At worst \(O(n)\) where \(n\) equals out_degree().

See also: next_label_and_target_no_checks.

◆ next_label_and_target_no_checks()

template<typename Node>

std::pair< label_type, node_type > next_label_and_target_no_checks	(	node_type	s,
		label_type	a ) const

nodiscard

This function returns the next target of an edge with label greater than or equal to a that is incident to the node s.

Parameters

s	the source node.
a	the label.

Returns

Returns a std::pair x where:

x.first is adjacent to s via an edge labelled x.second;
x.second is the minimum value in the range \([a, n)\) such that target(s, x.second) is not equal to UNDEFINED (where \(n\) is the return value of out_degree); and If no such value exists, then {UNDEFINED, UNDEFINED} is returned.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: At worst \(O(n)\) where \(n\) equals out_degree().

Warning: This function does not check its arguments, in particular it is not verified that the parameter s represents a node of this, or that a is a valid label.

See also: next_label_and_target.

◆ nodes()

template<typename Node>

auto nodes ( ) const

inlinenodiscardnoexcept

This function returns a range object containing all the nodes in a word graph.

Returns: A range object.

Exceptions: This function is noexcept and is guaranteed never to throw.

◆ number_of_edges() [1/2]

template<typename Node>

size_type number_of_edges ( ) const

nodiscard

This function returns the total number of edges (i.e. values s and a such that target(s, a) is not UNDEFINED) in the word graph.

Returns: The total number of edges, a value of type size_type.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: \(O(mn)\) where m is number_of_nodes() and n is out_degree().

◆ number_of_edges() [2/2]

template<typename Node>

size_type number_of_edges ( node_type s ) const

nodiscard

This function returns the number of edges incident to the given source node s.

Parameters

s the node.

Returns: A value of type size_type.

Exceptions

LibsemigroupsException if s is not a node.

Complexity: \(O(n)\) where n is out_degree().

◆ number_of_edges_no_checks()

template<typename Node>

size_type number_of_edges_no_checks ( node_type s ) const

nodiscard

This function returns the number of edges incident to the given source node s.

Parameters

s the node.

Returns: A value of type size_type.

Complexity: \(O(n)\) where n is out_degree().

Warning: No checks are performed that the argument s is actually a node in the word graph.

◆ number_of_nodes()

template<typename Node>

size_type number_of_nodes ( ) const

inlinenodiscardnoexcept

This function returns the number of nodes in the word graph.

Returns: The number of nodes in the word graph.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant.

◆ operator!=()

template<typename Node>

bool operator!= ( WordGraph< Node > const & that ) const

inlinenodiscard

This function returns true if *this and that are not equal, and false if they are equal.

Parameters

that	the word graph for comparison.

Returns: Whether or not *this and that are not equal.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: At worst \(O(nm)\) where \(n\) is the number of nodes and \(m\) is the out-degree of the word graph.

◆ operator<()

template<typename Node>

bool operator< ( WordGraph< Node > const & that ) const

inlinenodiscard

This function returns true if *this is less than that. This operator defines a linear order on word graphs.

Parameters

that	the word graph for comparison.

Returns: Whether or not *this is strictly less than that.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: At worst \(O(nm)\) where \(n\) is the number of nodes and \(m\) is the out-degree of the word graph.

◆ operator<=()

template<typename Node>

bool operator<= ( WordGraph< Node > const & that ) const

inlinenodiscard

This function returns true if *this is less or equal to that. This operator defines a linear order on word graphs.

Parameters

that	the word graph for comparison.

Returns: Whether or not *this is less than or equal to that.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: At worst \(O(nm)\) where \(n\) is the number of nodes and \(m\) is the out-degree of the word graph.

◆ operator==()

template<typename Node>

bool operator== ( WordGraph< Node > const & that ) const

inlinenodiscard

This function returns true if *this and that are equal, and false if not.

Parameters

that	the word graph for comparison.

Returns: Whether or not *this and that are equal.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: At worst \(O(nm)\) where \(n\) is the number of nodes and \(m\) is the out-degree of the word graph.

◆ operator>()

template<typename Node>

bool operator> ( WordGraph< Node > const & that ) const

inlinenodiscard

This function returns true if *this is greater than that. This operator defines a linear order on word graphs.

Parameters

that	the word graph for comparison.

Returns: Whether or not *this is strictly greater than that.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: At worst \(O(nm)\) where \(n\) is the number of nodes and \(m\) is the out-degree of the word graph.

◆ operator>=()

template<typename Node>

bool operator>= ( WordGraph< Node > const & that ) const

inlinenodiscard

This function returns true if *this is greater or equal to that. This operator defines a linear order on word graphs.

Parameters

that	the word graph for comparison.

Returns: Whether or not *this is greater than or equal to that.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: At worst \(O(nm)\) where \(n\) is the number of nodes and \(m\) is the out-degree of the word graph.

◆ out_degree()

template<typename Node>

size_type out_degree ( ) const

inlinenodiscardnoexcept

This function returns the number of edge labels in the word graph.

Returns: The number of edge labels, a value of type size_type.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant.

◆ random()

template<typename Node>

static WordGraph random	(	size_type	number_of_nodes,
		size_type	out_degree,
		std::mt19937	mt = std::mt19937(std::random_device()()) )

static

This function constructs a random word graph with number_of_nodes nodes and out-degree out_degree.

Parameters

number_of_nodes	the number of nodes.
out_degree	the out-degree of every node.
mt	a std::mt19937 used as a random source (defaults to: std::mt19937(std::random_device()())).

Returns: A random word graph.

Exceptions

LibsemigroupsException

if any of the following hold:

number_of_nodes is less than 2
out_degree is less than 2

Complexity: \(O(mn)\) where m is the number of nodes, and n is the out-degree of the word graph.

◆ remove_all_targets()

template<typename Node>

WordGraph & remove_all_targets ( )

inline

Set every target of every source with every possible label to UNDEFINED.

Returns: A reference to *this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: \(O(mn)\) where m is the number of nodes and n is the out-degree.

◆ remove_label()

template<typename Node>

WordGraph & remove_label ( label_type a )

This function removes the label a from a WordGraph object in-place. This reduces the out-degree by 1.

Parameters

a	the label to remove.

Returns: A reference to *this.

Exceptions

LibsemigroupsException if a is out of range.

◆ remove_label_no_checks()

template<typename Node>

WordGraph & remove_label_no_checks ( label_type a )

This function removes the label a from a WordGraph object in-place. This reduces the out-degree by 1.

Parameters

a	the label to remove.

Returns: A reference to *this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Warning: No checks are performed on the argument, and, in particular, it assumed that a is not out of range.

◆ remove_target()

template<typename Node>

WordGraph & remove_target	(	node_type	s,
		label_type	a )

This function removes the edge with source node s labelled by a.

Parameters

s	the source node.
a	the label of the edge from `s`.

Returns: A reference to *this.

Exceptions

LibsemigroupsException if s or a is out of range.

Complexity: Constant.

◆ remove_target_no_checks()

template<typename Node>

WordGraph & remove_target_no_checks	(	node_type	s,
		label_type	a )

inline

This function removes the edge with source node s labelled by a.

Parameters

s	the source node.
a	the label of the edge from `s`.

Returns: A reference to *this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

Warning: No checks whatsoever on the validity of the arguments are performed.

◆ reserve()

template<typename Node>

WordGraph & reserve	(	size_type	m,
		size_type	n )

This function ensures that the word graph has capacity for m nodes and n labels.

Parameters

m	the number of nodes.
n	the out-degree.

Returns: A reference to *this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: \(O(mn)\) where m is the number of nodes and n is the out-degree.

Iterator validity: This function modifies the object defined by this, any iterators, pointers or references pointing into this may be invalidated by a call to this function.

Note: Does not modify number_of_nodes() or out_degree().

◆ swap_targets()

template<typename Node>

WordGraph & swap_targets	(	node_type	m,
		node_type	n,
		label_type	a )

This function swaps the target of the edge from the node m labelled a with the target of the edge from the node n labelled a.

Parameters

m	the first node.
n	the second node.
a	the label.

Returns: A reference to *this.

Exceptions

LibsemigroupsException if m, n, or a are out of range.

Complexity: Constant

◆ swap_targets_no_checks()

template<typename Node>

WordGraph & swap_targets_no_checks	(	node_type	m,
		node_type	n,
		label_type	a )

inline

This function swaps the target of the edge from the node m labelled a with the target of the edge from the node n labelled a.

Parameters

m	the first node.
n	the second node.
a	the label.

Returns: A reference to *this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant

Warning: No checks whatsoever on the validity of the arguments are performed.

◆ target() [1/2]

template<typename Node>

WordGraph & target	(	node_type	s,
		label_type	a,
		node_type	t )

If s and t are nodes in this, and a is in the range [0, out_degree()), then this function adds an edge from a to b labelled a.

Parameters

s	the source node.
a	the label of the edge.
t	the range node.

Returns: A reference to *this.

Exceptions

LibsemigroupsException if s, a, or t is not valid. If an exception is thrown, this is guaranteed not to be modified (strong exception guarantee).

Complexity: Constant.

◆ target() [2/2]

template<typename Node>

node_type target	(	node_type	source,
		label_type	a ) const

nodiscard

This function returns the target of the edge with source node source and label a.

Parameters

source	the node.
a	the label.

Returns: Returns the node adjacent to source via the edge labelled a, or UNDEFINED; both are values of type node_type.

Exceptions

LibsemigroupsException if source or a is not valid.

Complexity: Constant.

◆ target_no_checks() [1/2]

template<typename Node>

node_type target_no_checks	(	node_type	s,
		label_type	a ) const

inlinenodiscard

This function returns the the target of the edge with source node s and label a.

Parameters

s	the node.
a	the label.

Returns: Returns the node adjacent to s via the edge labelled a, or UNDEFINED; both are values of type node_type.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

Warning: This function does not verify s or a is valid.

◆ target_no_checks() [2/2]

template<typename Node>

WordGraph & target_no_checks	(	node_type	s,
		label_type	a,
		node_type	t )

inline

This function adds an edge from the node s to the node t with label a.

Parameters

s	the source node.
a	the label of the edge from `s` to `t`.
t	the target node.

Returns: A reference to *this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

Warning: No checks whatsoever on the validity of the arguments are performed.

◆ targets()

template<typename Node>

rx::iterator_range< const_iterator_targets > targets ( node_type source ) const

nodiscard

This function returns a range object containing all the targets of edges with source source.

Parameters

source the source node.

Returns: A range object.

Exceptions

LibsemigroupsException if source is out of range (i.e. it is greater than or equal to number_of_nodes)

◆ targets_no_checks()

template<typename Node>

rx::iterator_range< const_iterator_targets > targets_no_checks ( node_type source ) const

inlinenodiscardnoexcept

This function returns a range object containing all the targets of edges with source source.

Parameters

source the source node.

Returns: A range object.

Exceptions: This function is noexcept and is guaranteed never to throw.

Warning: This function performs no checks whatsoever and assumes that source is a valid node of the word graph (i.e. it is not greater than or equal to number_of_nodes).

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

/Users/jdm3/libsemigroups/include/libsemigroups/cong-class.hpp
/Users/jdm3/libsemigroups/include/libsemigroups/word-graph.hpp

Public Types

Public Member Functions

Static Public Member Functions

Member Typedef Documentation

◆ const_iterator_nodes

◆ const_iterator_targets

◆ const_reverse_iterator_nodes

Constructor & Destructor Documentation

◆ WordGraph() [1/2]

◆ WordGraph() [2/2]

Member Function Documentation

◆ add_nodes()

◆ add_to_out_degree()

◆ cbegin_nodes()

◆ cbegin_targets()

◆ cbegin_targets_no_checks()

◆ cend_nodes()

◆ cend_targets()

◆ cend_targets_no_checks()

◆ disjoint_union_inplace()

◆ disjoint_union_inplace_no_checks()

◆ hash_value()

◆ induced_subgraph() [1/2]

◆ induced_subgraph() [2/2]

◆ induced_subgraph_no_checks() [1/2]

◆ induced_subgraph_no_checks() [2/2]

◆ init() [1/2]

◆ init() [2/2]

◆ labels()

◆ labels_and_targets()

◆ labels_and_targets_no_checks()

◆ next_label_and_target()

◆ next_label_and_target_no_checks()

◆ nodes()

◆ number_of_edges() [1/2]

◆ number_of_edges() [2/2]

◆ number_of_edges_no_checks()

◆ number_of_nodes()

◆ operator!=()

◆ operator<()

◆ operator<=()

◆ operator==()

◆ operator>()

◆ operator>=()

◆ out_degree()

◆ random()

◆ remove_all_targets()

◆ remove_label()

◆ remove_label_no_checks()

◆ remove_target()

◆ remove_target_no_checks()

◆ reserve()

◆ swap_targets()

◆ swap_targets_no_checks()

◆ target() [1/2]

◆ target() [2/2]

◆ target_no_checks() [1/2]

◆ target_no_checks() [2/2]

◆ targets()

◆ targets_no_checks()