This page collects various classes and functions related to word graphs in libsemigroups.

Topics
	make<Forest>
	Safely construct a Forest instance.
	to<WordGraph>
	Convert to WordGraph instance.
	make<WordGraph>
	Safely construct a WordGraph instance.

Namespaces
namespace	libsemigroups::forest
	Helper functions for the Forest class.
namespace	libsemigroups::paths
	Namespace containing helper functions for the Paths class.
namespace	libsemigroups::word_graph
	Namespace containing helper functions for the WordGraph class.

Classes
class	Forest
	Class representing a collection of spanning trees of a word graph. More...
class	Gabow< Node >
	Class implementing Gabow's algorithm for computing strongly connected components of a WordGraph. More...
class	Joiner
	Class for taking joins of word graphs. More...
class	Joiner
	Class for taking joins of word graphs. More...
class	Meeter
	Class for taking meets of word graphs. More...
class	Meeter
	Class for taking meets of word graphs. More...
class	Paths< Node >
	Range for iterating through paths in a WordGraph. More...
class	WordGraph< Node >
	Class for representing word graphs. More...
class	WordGraphView< Node >
	non-owning view over a specified range of WordGraph nodes. More...

Functions
template<typename FormatContext>
auto	format (libsemigroups::Forest const &f, FormatContext &ctx) const
	Custom formatter for Forest objects.
template<typename Node>
std::ostream &	operator<< (std::ostream &os, WordGraph< Node > const &wg)
template<typename Node>
std::ostream &	operator<< (std::ostream &os, WordGraph< Node > const &wg)
static std::string	to_human_readable_repr (Joiner const &join)
	Return a human readable representation of a Joiner object.
static std::string	to_human_readable_repr (Meeter const &meet)
	Return a human readable representation of a Meeter object.
template<typename Node>
std::string	to_human_readable_repr (WordGraph< Node > const &wg)
	Return a human readable representation of a WordGraph object.
static std::string	to_human_readable_repr (Joiner const &join)
	Return a human readable representation of a Joiner object.
static std::string	to_human_readable_repr (Meeter const &meet)
	Return a human readable representation of a Meeter object.
template<typename Node>
std::string	to_human_readable_repr (WordGraph< Node > const &wg)
	Return a human readable representation of a WordGraph object.
template<typename Node>
std::string	to_input_string (WordGraph< Node > const &wg, std::string const &prefix="", std::string const &braces="{}", std::string const &suffix="")
	Return a string that can be used to recreate a word graph.
template<typename Node>
std::string	to_input_string (WordGraph< Node > const &wg, std::string const &prefix="", std::string const &braces="{}", std::string const &suffix="")
	Return a string that can be used to recreate a word graph.

Variables
template<typename Thing>
static constexpr bool	IsWordGraph = is_specialization_of_v<Thing, WordGraph>
	Helper variable template.

Function Documentation

◆ format()

template<typename FormatContext>

auto format	(	libsemigroups::Forest const &	f,
		FormatContext &	ctx ) const

inline

This is the format function of a custom formatter for fmt and the libsemigroups::Forest class.

The intention is to provide a string representation that could be used to reconstruct the libsemigroups::Forest object. For a more human readable representation see to_human_readable_repr.

Template Parameters

FormatContext the type of the context provided in the second argument.

Parameters

f	the forest to format.
ctx	the format context.

Returns: The formatted string representation of f.

◆ operator<<() [1/2]

template<typename Node>

std::ostream & operator<<	(	std::ostream &	os,
		WordGraph< Node > const &	wg )

Output the edges of a wordGraph to a stream.

This function outputs the word graph wg to the stream os. The word graph is represented by the out-neighbours of each node ordered according to their labels. The symbol - is used to denote that an edge is not defined. For example, the word graph with 1 node, out-degree 2, and a single loop labelled 1 from node 0 to 0 is represented as {{-, 0}}.

Parameters

os	the ostream.
wg	the word graph.

Returns: The first parameter os.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Note: This function will be moved from the header word-graph.hpp to word-graph-helpers.hpp in v4 of libsemigroups.

◆ operator<<() [2/2]

template<typename Node>

std::ostream & operator<<	(	std::ostream &	os,
		WordGraph< Node > const &	wg )

Output the edges of a wordGraph to a stream.

This function outputs the word graph wg to the stream os. The word graph is represented by the out-neighbours of each node ordered according to their labels. The symbol - is used to denote that an edge is not defined. For example, the word graph with 1 node, out-degree 2, and a single loop labelled 1 from node 0 to 0 is represented as {{-, 0}}.

Parameters

os	the ostream.
wg	the word graph.

Returns: The first parameter os.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ to_human_readable_repr() [1/6]

std::string to_human_readable_repr ( Joiner const & join )

inlinestaticnodiscard

Return a human readable representation of a Joiner object.

Parameters

join	the Joiner object.

Returns: A string containing the representation.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Note: This function will be moved from the header word-graph.hpp to word-graph-helpers.hpp in v4 of libsemigroups.

◆ to_human_readable_repr() [2/6]

std::string to_human_readable_repr ( Meeter const & meet )

inlinestaticnodiscard

Return a human readable representation of a Meeter object.

Parameters

meet	the Meeter object.

Returns: A string containing the representation.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Note: This function will be moved from the header word-graph.hpp to word-graph-helpers.hpp in v4 of libsemigroups.

◆ to_human_readable_repr() [3/6]

template<typename Node>

std::string to_human_readable_repr ( WordGraph< Node > const & wg )

nodiscard

Return a human readable representation of a WordGraph object.

Template Parameters

Node	the type of the nodes in the underlying WordGraph.

Parameters

wg	the WordGraph object.

Returns: A string containing the representation.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Note: This function will be moved from the header word-graph.hpp to word-graph-helpers.hpp in v4 of libsemigroups.

◆ to_human_readable_repr() [4/6]

std::string to_human_readable_repr ( Joiner const & join )

inlinestaticnodiscard

Return a human readable representation of a Joiner object.

Parameters

join	the Joiner object.

Returns: A string containing the representation.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ to_human_readable_repr() [5/6]

std::string to_human_readable_repr ( Meeter const & meet )

inlinestaticnodiscard

Return a human readable representation of a Meeter object.

Parameters

meet	the Meeter object.

Returns: A string containing the representation.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ to_human_readable_repr() [6/6]

template<typename Node>

std::string to_human_readable_repr ( WordGraph< Node > const & wg )

nodiscard

Return a human readable representation of a WordGraph object.

Template Parameters

Node	the type of the nodes in the underlying WordGraph.

Parameters

wg	the WordGraph object.

Returns: A string containing the representation.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ to_input_string() [1/2]

template<typename Node>

std::string to_input_string	(	WordGraph< Node > const &	wg,
		std::string const &	prefix = "",
		std::string const &	braces = "{}",
		std::string const &	suffix = "" )

nodiscard

This function returns a std::string containing the input required to construct a copy of the argument wg.

Template Parameters

Node	the type of the nodes of `wg`.

Parameters

wg	the word graph.
prefix	a prefix for the returned string (defaults to an empty string).
braces	the braces to use in the string (defaults to "{}").
suffix	a suffix for the returned string (defaults to an empty string).

Returns: A string containing the input required to recreate wg.

Exceptions

LibsemigroupsException if the argument braces is not of length 2.

Note: This function will be moved from the header word-graph.hpp to word-graph-helpers.hpp in v4 of libsemigroups.

◆ to_input_string() [2/2]

template<typename Node>

std::string to_input_string	(	WordGraph< Node > const &	wg,
		std::string const &	prefix = "",
		std::string const &	braces = "{}",
		std::string const &	suffix = "" )

nodiscard

This function returns a std::string containing the input required to construct a copy of the argument wg.

Template Parameters

Node	the type of the nodes of `wg`.

Parameters

wg	the word graph.
prefix	a prefix for the returned string (defaults to an empty string).
braces	the braces to use in the string (defaults to "{}").
suffix	a suffix for the returned string (defaults to an empty string).

Returns: A string containing the input required to recreate wg.

Exceptions

LibsemigroupsException if the argument braces is not of length 2.

Variable Documentation

◆ IsWordGraph

template<typename Thing>

bool IsWordGraph = is_specialization_of_v<Thing, WordGraph>

staticconstexpr

The value of this variable is true if the template parameter Thing is WordGraph for any template parameters.

Template Parameters

Thing a type.

Deprecated: This alias is deprecated and will be removed from libsemigroups in v4, please use is_specialization_of_v<Thing, WordGraph> instead.

Topics

Namespaces

Classes

Functions

Variables

Function Documentation

◆ format()

◆ operator<<() [1/2]

◆ operator<<() [2/2]

◆ to_human_readable_repr() [1/6]

◆ to_human_readable_repr() [2/6]

◆ to_human_readable_repr() [3/6]

◆ to_human_readable_repr() [4/6]

◆ to_human_readable_repr() [5/6]

◆ to_human_readable_repr() [6/6]

◆ to_input_string() [1/2]

◆ to_input_string() [2/2]

Variable Documentation

◆ IsWordGraph