Accessors

This page contains the documentation of the various member functions of the ToddCoxeter class that can be used to access the state of an instance.

Those functions with the prefix current_ do not perform any further enumeration.

Functions
float	complete () const noexcept
	Return the proportion of edges defined in the active part of the word graph.
Forest const &	current_spanning_tree () const
	Get the current possible spanning tree of the underlying word graph.
word_graph_type const &	current_word_graph () const noexcept
	Get the current word graph.
bool	is_standardized () const
	Check if the word graph is currently standardized with respect to any order.
bool	is_standardized (Order val) const
	Check if the word graph is currently standardized with respect to a given order.
uint64_t	number_of_edges_active () const noexcept
	Return the number of edges in the active part of the current word graph.
uint64_t	number_of_large_collapses () const noexcept
	Return the number of large collapses that have occurred.
uint64_t	number_of_nodes_active () const noexcept
	Return the number of nodes in the active part of the current word graph.
Forest const &	spanning_tree ()
	Get the spanning tree of the underlying word graph.
Order	standardization_order () const noexcept
	Get the current standardization order of the underlying word graph.
word_graph_type const &	word_graph ()
	Get the word graph after performing a full congruence enumeration.

Function Documentation

complete()

float complete ( ) const

inlinenodiscardnoexcept

This function returns the proportion (as a float) of the edges defined. This value is number_of_edges_active divided by number_of_nodes_active multiplied by out_degree applied to current_word_graph.

Returns

The proportion of edges defined in the active part of current_word_graph.

Exceptions

This function is noexcept and is guaranteed never to throw.

current_spanning_tree()

Forest const & current_spanning_tree ( ) const

inline

This function returns a const reference to the current value of a possible spanning tree (a Forest) for the underlying WordGraph (returned by current_word_graph).

Returns

A const reference to a spanning tree of the underlying WordGraph.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Warning

This function returns a reference to the current spanning tree, if this is reinitialized then the value of this reference will become invalid. I.e. rather than storing a reference to the return value of this function in a variable, it's probably better to call current_spanning_tree again.

Deprecated

This function is deprecated and will be removed from libsemigroups in v4. Please use current_word_graph().current_spanning_tree() instead.

current_word_graph()

word_graph_type const & current_word_graph ( ) const

inlinenoexcept

In some sense, the purpose of the Todd-Coxeter algorithm is to produce a WordGraph of the action of a set of generators on the classes of a congruence. This function can be used to obtain a reference to that WordGraph as it currently exists within a ToddCoxeter instance. This function does not trigger any enumeration.

The WordGraph returned by this function may be in a rather complicated state. No guarantees are given: about the values of the active nodes (i.e. they may be any non-negative integers in any order); that the number of nodes (including those that are inactive) should coincide with the number of active nodes; that the graph is complete; or that the graph is compatible with the relations of the presentation or with the generating_pairs.

The functions standardize(Order) and shrink_to_fit can be used to modify the returned word graph in-place to have (possibly) more reasonable characteristics.

Returns

A const reference to the underlying WordGraph.

Exceptions

This function is noexcept and is guaranteed never to throw.

See also

number_of_nodes_active

number_of_edges_active

is_standardized() [1/2]

bool is_standardized ( ) const

inline

This function returns true if the current_word_graph has been standardized with respect to the any Order other than Order::none.

Returns

Whether or not the current word graph is standardized with respect to any order.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Deprecated

This function is deprecated and will be removed from libsemigroups in v4. Please use current_word_graph().is_standardized() instead.

is_standardized() [2/2]

bool is_standardized ( Order val ) const

inline

This function returns true if the current_word_graph has been standardized with respect to the order val; and false if not.

Parameters

val	the Order to check for.

Returns

Whether or not the current word graph is standardized with respect to a given order.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Deprecated

This function is deprecated and will be removed from libsemigroups in v4. Please use current_word_graph().is_standardized(val) instead.

number_of_edges_active()

uint64_t number_of_edges_active ( ) const

inlinenodiscardnoexcept

This function returns the number of edges in the active part of the current_word_graph. Recall that current_word_graph can grow and shrink drastically during a congruence enumeration. As such to avoid unnecessary memory allocations, where possible, the nodes in the current_word_graph are "recycled" leading to the situation where some of the nodes in current_word_graph are "active" and others are "inactive". In other words, the "active" nodes correspond to the part of the word graph that actually represents the classes of the congruence we are trying to enumerate; and the "inactive" nodes are only there to be "recycled" into "active" nodes if they are required later on.

Exceptions

This function is noexcept and is guaranteed never to throw.

Deprecated

This function is deprecated and will be removed from libsemigroups in v4. Use current_word_graph().number_of_edges_active() instead.

number_of_large_collapses()

uint64_t number_of_large_collapses ( ) const

inlinenodiscardnoexcept

This function returns the number of "large" collapses that have occurred in the graph during any run of a ToddCoxeter instance. What qualifies as a "large" collapse can be specified using large_collapse.

Returns

The number of large collapses.

Exceptions

This function is noexcept and is guaranteed never to throw.

number_of_nodes_active()

uint64_t number_of_nodes_active ( ) const

inlinenodiscardnoexcept

This function returns the number of nodes in the active part of the current_word_graph. Recall that current_word_graph can grow and shrink drastically during a congruence enumeration. As such to avoid unnecessary memory allocations, where possible, the nodes in the current_word_graph are "recycled" leading to the situation where some of the nodes in current_word_graph are "active" and others are "inactive". In other words, the "active" nodes correspond to the part of the word graph that actually represents the classes of the congruence we are trying to enumerate; and the "inactive" nodes are only there to be "recycled" into "active" nodes if they are required later on.

Exceptions

This function is noexcept and is guaranteed never to throw.

Deprecated

This function is deprecated and will be removed from libsemigroups in v4. Use current_word_graph().number_of_nodes_active() instead.

spanning_tree()

Forest const & spanning_tree

(

)

This function returns a const reference to a spanning tree (a Forest) for the underlying WordGraph (returned by word_graph) with the nodes appearing in short-lex order. This function triggers a full congruence enumeration.

Returns

A const reference to a spanning tree of the underlying WordGraph.

Deprecated

This function is deprecated and will be removed from libsemigroups in v4. Please use current_word_graph().current_spanning_tree() instead.

standardization_order()

Order standardization_order ( ) const

inlinenoexcept

This function returns the standardization order currently used in the underlying word graph. The return value of this function will be the argument of the most recent call to standardize(Order); or Order::none.

The return value of this function indicates the following:

• Order::none implies that no standardization has been performed and:
  • the return value of reduce will essentially arbitrary;
  • the return values of normal_forms will be essentially arbitrary;
  • the classes of the congruence will be indexed in an arbitrary order;
• Order::shortlex implies that:
  • the return value of reduce will be the short-lex least word belonging to a given congruence class;
  • the return values of normal_forms will be in short-lex order;
  • the classes of the congruence will be indexed in short-lex order on the short-lex least word;
• Order::lex implies that:
  • the return values of normal_forms will be ordered lexicographically.
  • the return values of reduce and the indexes of class are essentially arbitrary because there is not necessarily a lexicographically least word in every class;
• Order::recursive implies that:
  • the return value of reduce will be the recursive path least word belonging to a given congruence class;
  • the return values of normal_forms will be in recursive path order;
  • the classes of the congruence will be indexed in recursive path order on the recursive path least word.

Returns

The current standardization order.

Exceptions

This function is noexcept and is guaranteed never to throw.

Deprecated

This function is deprecated and will be removed from libsemigroups in v4. Please use current_word_graph().standardization_order() instead.

word_graph()

word_graph_type const & word_graph

(

)

In some sense, the purpose of the Todd-Coxeter algorithm is to produce a WordGraph of the action of a set of generators on the classes of a congruence. This function can be used to obtain a reference to that WordGraph instance. This function triggers a full enumeration.

The WordGraph returned by this function may be in a rather complicated state. The active nodes (and nodes) will be \(\{0, \ldots, n - 1\}\) where \(n\) is the number of classes in the congruence if presentation contains the empty word; or the number of classes plus one if presentation does not contain the empty word. The returned WordGraph is also short-lex standardized. The returned WordGraph will usually be complete and compatible with the relations of the presentation and with the generating_pairs. The WordGraph may not be complete or compatible for some values of the settings. For example, if the setting lower_bound is used but is not the same as the number of classes in the congruence, then the WordGraph returned by this function may not be compatible with the relations of presentation or generating_pairs.

Returns

A const reference to the underlying WordGraph.