Word graphs and related functionality

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

Topics
	make<Forest>
	Safely construct a Forest 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	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...

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

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

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

static 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() [2/3]

static 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() [3/3]

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

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.

Warning

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