Meeter

This class exists for its call operators which can be used to find the meet of two word graphs with the same WordGraph::out_degree. This class implements the same algorithm as that used for computing a finite state automata recognising the intersection of the languages accepted by two given automata.

The input word graphs need not be complete, and the root nodes can also be specified.

Public Member Functions
	Meeter ()
	Default constructor.
	Meeter (Meeter &&)
	Default move constructor.
	Meeter (Meeter const &)
	Default copy constructor.
template<typename Node>
void	call_no_checks (WordGraph< Node > &xy, WordGraph< Node > const &x, Node xroot, WordGraph< Node > const &y, Node yroot)
	Replace the contents of a word graph with the join/meet of two given word graphs with respect to given root vertices.
template<typename Node>
void	call_no_checks (WordGraph< Node > &xy, WordGraph< Node > const &x, size_t xnum_nodes_reachable_from_root, Node xroot, WordGraph< Node > const &y, size_t ynum_nodes_reachable_from_root, Node yroot)
	Replace the contents of a word graph with the join/meet of two given word graphs with respect to given root vertices.
template<typename Node>
void	call_no_checks (WordGraph< Node > &xy, WordGraph< Node > const &x, WordGraph< Node > const &y)
	Replace the contents of a word graph with the join/meet of two given word graphs with respect to given root vertices.
template<typename Node, typename... Args>
auto	call_no_checks (WordGraph< Node > const &x, Args &&... args)
	Returns a word graph containing the join/meet of two given word graphs.
template<typename Node>
bool	is_subrelation (WordGraph< Node > const &x, WordGraph< Node > const &y)
	Check if the language accepted by one word graph is contained in that defined by another word graph.
template<typename Node1, typename Node2>
bool	is_subrelation (WordGraph< Node1 > const &x, Node2 xroot, WordGraph< Node1 > const &y, Node2 yroot)
	Check if the language accepted by one word graph is contained in that defined by another word graph.
template<typename Node>
bool	is_subrelation_no_checks (WordGraph< Node > const &x, WordGraph< Node > const &y)
	Check if the language accepted by one word graph is contained in that defined by another word graph.
template<typename Node1, typename Node2>
bool	is_subrelation_no_checks (WordGraph< Node1 > const &x, Node2 xroot, WordGraph< Node1 > const &y, Node2 yroot)
	Check if the language accepted by one word graph is contained in that defined by another word graph.
template<typename Node1, typename Node2>
bool	is_subrelation_no_checks (WordGraph< Node1 > const &x, size_t xnum_nodes_reachable_from_root, Node2 xroot, WordGraph< Node1 > const &y, size_t ynum_nodes_reachable_from_root, Node2 yroot)
	Check if the language accepted by one word graph is contained in that accepted by another word graph.
template<typename Node>
void	operator() (WordGraph< Node > &xy, WordGraph< Node > const &x, Node xroot, WordGraph< Node > const &y, Node yroot)
	Replace the contents of a word graph with the join/meet of two given word graphs with respect to given root vertices.
template<typename Node>
void	operator() (WordGraph< Node > &xy, WordGraph< Node > const &x, WordGraph< Node > const &y)
	Replace the contents of a word graph with the join/meet of two given word graphs with respect to given root vertices.
template<typename Node, typename... Args>
auto	operator() (WordGraph< Node > const &x, Args &&... args)
	Returns a word graph containing the join/meet of two given word graphs.
Meeter &	operator= (Meeter &&)
	Default move assignment operator.
Meeter &	operator= (Meeter const &)
	Default copy assignment operator.

Constructor & Destructor Documentation

Meeter() [1/3]

Meeter

(

)

Default constructor.

Meeter() [2/3]

Meeter

(

Meeter const &

)

Default copy constructor.

Meeter() [3/3]

Meeter

(

Meeter &&

)

Default move constructor.

Member Function Documentation

call_no_checks() [1/4]

template<typename Node>

void call_no_checks	(	WordGraph< Node > &	xy,
		WordGraph< Node > const &	x,
		Node	xroot,
		WordGraph< Node > const &	y,
		Node	yroot )

This function replaces the contents of the word graph xy with the join/meet of the word graphs x and y. This function is the same as the 7-argument variant but it computes the number of nodes reachable from xroot and yroot.

Template Parameters

Node	the type of the nodes in the word graphs which are parameters to this function.

Parameters

xy	the word graph to store the result.
x	the first word graph to join/meet.
xroot	the node to use as a root in x.
y	the second word graph to join/meet.
yroot	the node to use as a root in y.

Warning

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

call_no_checks() [2/4]

template<typename Node>

void call_no_checks	(	WordGraph< Node > &	xy,
		WordGraph< Node > const &	x,
		size_t	xnum_nodes_reachable_from_root,
		Node	xroot,
		WordGraph< Node > const &	y,
		size_t	ynum_nodes_reachable_from_root,
		Node	yroot )

This function replaces the contents of the word graph xy with the join/meet of the word graphs x and y.

Template Parameters

Node	the type of the nodes in the word graphs which are parameters to this function.

Parameters

xy	the word graph to store the result.
x	the first word graph to join/meet.
xnum_nodes_reachable_from_root	the number of nodes reachable in x from the node xroot (for the circumstance where this number is known apriori, and does not have to be recomputed).
xroot	the node to use as a root in x.
y	the second word graph to join/meet.
ynum_nodes_reachable_from_root	the number of nodes reachable in y from the node yroot.
yroot	the node to use as a root in y.

Warning

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

call_no_checks() [3/4]

template<typename Node>

void call_no_checks	(	WordGraph< Node > &	xy,
		WordGraph< Node > const &	x,
		WordGraph< Node > const &	y )

This function replaces the contents of the word graph xy with the join/meet of the word graphs x and y. This function is the same as the 5-argument variant but it uses 0 as the root node in both x and y.

Template Parameters

Node	the type of the nodes in the word graphs which are parameters to this function.

Parameters

xy	the word graph to store the result.
x	the first word graph to join/meet.
y	the second word graph to join/meet.

Warning

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

call_no_checks() [4/4]

template<typename Node, typename... Args>

auto call_no_checks ( WordGraph< Node > const & x, Args &&... args )

nodiscard

This function returns a word graph containing the join/meet of the word graphs x and y. If n is the number of arguments, then this function constructs a word graph to contain the result, forwards this and the other arguments to the overload of call_no_checks with n + 1 parameters, then returns the word graph containing the result.

Template Parameters

Node	the type of the nodes in the word graphs which are parameters to this function.
Args	parameter pack for the remaining arguments.

Parameters

x	the first word graph to join/meet.
args	the remaining parameters.

Warning

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

is_subrelation() [1/2]

template<typename Node>

bool is_subrelation	(	WordGraph< Node > const &	x,
		WordGraph< Node > const &	y )

This function returns true if the language accepted by x with initial node 0 and accept state every node, is a subset of the corresponding language in y. This version of the function is the same as the 2-argument overload of is_subrelation_no_checks, except that this function throws if its arguments are invalid.

Template Parameters

Node	the type of the nodes in the word graphs which are parameters to this function.

Parameters

x	the word graph whose language we are checking might be a subset.
y	the word graph whose language we are checking might be a superset.

Returns

Whether or not x is a subrelation of y.

Exceptions

LibsemigroupsException

if any of the following hold: x has no nodes; y has no nodes; x.out_degree() != y.out_degree().

is_subrelation() [2/2]

template<typename Node1, typename Node2>

bool is_subrelation	(	WordGraph< Node1 > const &	x,
		Node2	xroot,
		WordGraph< Node1 > const &	y,
		Node2	yroot )

This function returns true if the language accepted by x with initial node xroot and accept state every node, is a subset of the corresponding language in y. This version of the function is the same as the 4-argument overload of is_subrelation_no_checks, except that this function throws if its arguments are invalid.

Template Parameters

Node	the type of the nodes in the word graphs which are parameters to this function.

Parameters

x	the word graph whose language we are checking might be a subset.
xroot	the node to use as the initial state in x.
y	the word graph whose language we are checking might be a superset.
yroot	the node to use as an initial state in y.

Returns

Whether or not x is a subrelation of y.

Exceptions

LibsemigroupsException

if any of the following hold: xroot isn't a node in x; yroot isn't a node in y; x.out_degree() != y.out_degree().

is_subrelation_no_checks() [1/3]

template<typename Node>

bool is_subrelation_no_checks	(	WordGraph< Node > const &	x,
		WordGraph< Node > const &	y )

This function returns true if the language accepted by x with initial node xroot and accept state every node, is a subset of the corresponding language in y. This version of the function is similar to the 4-argument overload, except that 0 is used as the root node in both x and y.

Template Parameters

Node	the type of the nodes in the word graphs which are parameters to this function.

Parameters

x	the word graph whose language we are checking might be a subset.
y	the word graph whose language we are checking might be a superset.

Returns

Whether or not x is a subrelation of y.

Warning

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

is_subrelation_no_checks() [2/3]

template<typename Node1, typename Node2>

bool is_subrelation_no_checks	(	WordGraph< Node1 > const &	x,
		Node2	xroot,
		WordGraph< Node1 > const &	y,
		Node2	yroot )

This function returns true if the language accepted by x with initial node xroot and accept state every node, is a subset of the corresponding language in y. This version of the function is similar to the 6-argument overload, except that here we must compute the number of nodes in x and y reachable from xroot and yroot, respectively.

Template Parameters

Node1	the type of the nodes in the word graphs which are parameters to this function.
Node2	the type of the nodes to use as roots.

Parameters

x	the word graph whose language we are checking might be a subset.
xroot	the node to use as the initial state in x.
y	the word graph whose language we are checking might be a superset.
yroot	the node to use as an initial state in y.

Returns

Whether or not x is a subrelation of y.

Warning

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

is_subrelation_no_checks() [3/3]

template<typename Node1, typename Node2>

bool is_subrelation_no_checks ( WordGraph< Node1 > const & x, size_t xnum_nodes_reachable_from_root, Node2 xroot, WordGraph< Node1 > const & y, size_t ynum_nodes_reachable_from_root, Node2 yroot )

nodiscard

This function returns true if the language accepted by x with initial node xroot and accept state every node, is a subset of the corresponding language in y.

Template Parameters

Node1	the type of the nodes in the word graphs which are parameters to this function.
Node2	the type of the nodes to use as roots.

Parameters

x	the word graph whose language we are checking might be a subset.
xnum_nodes_reachable_from_root	the number of nodes reachable in x from the node xroot (for the circumstance where this number is known apriori, and does not have to be recomputed).
xroot	the node to use as the initial state in x.
y	the word graph whose language we are checking might be a superset.
ynum_nodes_reachable_from_root	the number of nodes reachable in y from the node yroot.
yroot	the node to use as an initial state in y.

Returns

Whether or not x is a subrelation of y.

Warning

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

operator()() [1/3]

template<typename Node>

void operator()	(	WordGraph< Node > &	xy,
		WordGraph< Node > const &	x,
		Node	xroot,
		WordGraph< Node > const &	y,
		Node	yroot )

This function replaces the contents of the word graph xy with the join/meet of the word graphs x and y. This function is the same as the 5-argument overload of call_no_checks but it throws if its arguments aren't valid.

Template Parameters

Node	the type of the nodes in the word graphs which are parameters to this function.

Parameters

xy	the word graph to store the result.
x	the first word graph to join/meet.
xroot	the node to use as a root in x.
y	the second word graph to join/meet.
yroot	the node to use as a root in y.

Exceptions

LibsemigroupsException

if any of the following hold: xroot isn't a node in x; yroot isn't a node in y; x.out_degree() != y.out_degree().

operator()() [2/3]

template<typename Node>

void operator()	(	WordGraph< Node > &	xy,
		WordGraph< Node > const &	x,
		WordGraph< Node > const &	y )

This function replaces the contents of the word graph xy with the join/meet of the word graphs x and y. This function is the same as the 3-argument overload of call_no_checks but it throws if its arguments aren't valid.

Template Parameters

Node	the type of the nodes in the word graphs which are parameters to this function.

Parameters

xy	the word graph to store the result.
x	the first word graph to join/meet.
y	the second word graph to join/meet.

Exceptions

LibsemigroupsException

if any of the following hold: x has no nodes; y has no nodes; x.out_degree() != y.out_degree().

operator()() [3/3]

template<typename Node, typename... Args>

auto operator() ( WordGraph< Node > const & x, Args &&... args )

nodiscard

This function is the same as the overload of call_no_checks with the same signature, the difference being that this function throws if the arguments are invalid.

Template Parameters

Node	the type of the nodes in the word graphs which are parameters to this function.
Args	parameter pack for the remaining arguments.

Parameters

x	the first word graph to join/meet.
args	the remaining arguments.

Exceptions

LibsemigroupsException

if the arguments aren't valid. See the relevant operator() for more details.

operator=() [1/2]

Meeter & operator=

(

Meeter &&

)

Default move assignment operator.

operator=() [2/2]

Meeter & operator=

(

Meeter const &

)

Default copy assignment operator.

---

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

• /Users/jdm/libsemigroups/include/libsemigroups/word-graph.hpp