Member types¶

This page contains information about the member types of the ToddCoxeter class.

using libsemigroups::congruence::ToddCoxeter::class_iterator = typename DigraphWithSources<coset_type>::const_pstislo_iterator¶

The type of a const iterator pointing to a word belonging to a particular class.

Iterators of this type point to a word_type.

enum class libsemigroups::congruence::ToddCoxeter::options::deductions¶

Values for specifying how to handle deductions.

The values in this enum can be used as the argument for deduction_policy(options::deductions).

For our purposes, a deduction is a recently defined edge in the word graph that we are attempting to construct in an instance of ToddCoxeter. The values in this enum influence how these deductions are stored and processed.

For every deduction held in the deduction stack, a depth first search through the Felsch tree of the generating pairs is performed. The aim is to only follow paths from nodes in the word graph labelled by generating pairs that actually pass through the edge described by a deduction. There are two versions of this represented by the values options::deductions::v1 and options::deductions::v2. The first version is simpler, but may involve following the same path that leads nowhere multiple times. The second version is more complex, and attempts to avoid following the same path multiple times if it is found to lead nowhere once.

The other values in this enum represent what to do if the number of deductions in the stack exceeds the value max_deductions().

It is possible to combine values of this type using operator|, for example options::deductions::v2 and options::deductions::unlimited is specified by options::deductions::v2 | options::deductions::unlimited.

An exception will be thrown if incompatible values of options::deductions are combined in this way, such as, for example options::deductions::v1 | options::deductions::v2.

Values:

enumerator v1¶: Version 1 deduction processing.

enumerator v2¶: Version 2 deduction processing.

enumerator no_stack_if_no_space¶: Do not put newly generated deductions in the stack if the stack already has size max_deductions().

enumerator purge_from_top¶: If the deduction stack has size max_deductions() and a new deduction is generated, then deductions with dead source node are are popped from the top of the stack (if any).

enumerator purge_all¶: If the deduction stack has size max_deductions() and a new deduction is generated, then deductions with dead source node are are popped from the entire of the stack (if any).

enumerator discard_all_if_no_space¶: If the deduction stack has size max_deductions() and a new deduction is generated, then all deductions in the stack are discarded.

enumerator unlimited¶: There is no limit to the number of deductions that can be put in the stack.

enum class libsemigroups::congruence::ToddCoxeter::options::froidure_pin¶

Values for specifying whether to use relations or Cayley graph.

The values in this enum can be used as the argument for froidure_pin_policy(options::froidure_pin) to specify whether the defining relations, or the left/right Cayley graph, of a FroidurePin instance, should be used in the coset enumeration.

If the number of classes in the congruence represented by a ToddCoxeter instance is relatively small, by some definition, compared to the size of the semigroup represented by the FroidurePin instance, then the froidure_pin::use_relations policy is often faster. If the number of classes is relatively large, then froidure_pin::use_cayley_graph is often faster. It is guaranteed that run will terminate in an amount of time proportionate to the size of the input if the policy froidure_pin::use_cayley_graph is used, whereas the run time when using the policy froidure_pin::use_relations can be arbitrarily high regardless of the size of the input.

Values:

enumerator none¶: No policy has been specified.

enumerator use_relations¶: Use the relations of a FroidurePin instance.

enumerator use_cayley_graph¶: Use the left or right Cayley graph of a FroidurePin instance.

enum class libsemigroups::congruence::ToddCoxeter::options::lookahead¶

Values for specifying the type of lookahead to perform.

The values in this enum can be used as the argument for lookahead(options::lookahead) to specify the type of lookahead that should be performed when using the HLT strategy.

It is possible to combine values of this type using operator|, for example a full HLT style lookahead is specified by options::lookahead::full | options::lookahead::hlt.

An exception will be thrown if incompatible values of options::lookahead are combined in this way, such as, for example options::lookahead::full | options::lookahead::partial.

Values:

enumerator full¶

A full lookahead is one starting from the initial coset.

Full lookaheads are therefore sometimes slower but may detect more coincidences than a partial lookahead.

enumerator partial¶

A partial lookahead is one starting from the current coset.

Partial lookaheads are therefore sometimes faster but may not detect as many coincidences as a full lookahead.

enumerator hlt¶: The lookahead will be done in HLT style by following the paths labelled by every relation from every coset in the range specified by lookahead::full or lookahead::partial.

enumerator felsch¶: The lookahead will be done in Felsch style where every edge is considered in every path labelled by a relation in which it occurs.

enum class libsemigroups::congruence::ToddCoxeter::options::preferred_defs¶

Values for specifying how to handle preferred definitions.

The values in this enum can be used as the argument for preferred_defs(options::preferred_defs).

While in a Felsch phase of an enumeration, a definition of the next new edge is usually made for the first node whose out-degree is not equal to the number of generators. The exact order this happens is depends on the implementation and is not specified. When following the paths from a given node labelled by a relation it might be the case that both paths end one letter before the end. It might be beneficial for the next edges defined to be the missing edges from these paths, these are what we refer to as preferred definitions. The values in this enum influence how preferred definitions are utilised.

The maximum number of preferred definitions held at any time is defined by the value of max_preferred_defs(). These definitions are stored in a circular buffer, where newer preferred definitions displace older ones once the number exceeds max_preferred_defs().

Note

The values in this enum roughly correspond to ACE’s “pmode” options.

Warning

If the option preferred_defs::deferred is used then the next edges defined are always taken from the preferred definitions circular buffer, regardless of the proportion of undefined edges in the word graph. In ACE, preferred definitions are only made if the proportion of undefined edges is sufficiently low (or the “fill factor” is sufficiently high). This is not currently implemented in libsemigroups and there are examples where using preferred definitions causes an enumeration to run for longer than if they are not used.

Values:

enumerator none¶: Do not use preferred definitions at all.

enumerator immediate_no_stack¶: Immediately define the new edge and do not stack the corresponding deductions.

enumerator immediate_yes_stack¶: Immediately define the new edge and do stack the corresponding deductions.

enumerator deferred¶: Add the preferred definition to the preferred definition buffer.

enum class libsemigroups::congruence::ToddCoxeter::options::strategy¶

Values for defining the strategy.

The values in this enum can be used as the argument for the member function strategy(options::strategy) to specify which strategy should be used when performing a coset enumeration.

Several of the strategies mimic ACE strategies of the same name. The ACE strategy “R*” is equivalent to strategy(options::strategy::hlt).save(true).

Values:

enumerator hlt¶

This value indicates that the HLT (Hazelgrove-Leech-Trotter) strategy should be used.

This is analogous to ACE’s R-style.

enumerator felsch¶

This value indicates that the Felsch strategy should be used.

This is analogous to ACE’s C-style.

enumerator random¶

This value indicates that a random combination of the HLT and Felsch strategies should be used.

A random strategy (and associated options) are selected from one of the 10 options:

HLT + full lookahead + no deduction processing + standardization
HLT + full lookahead + deduction processing + standardization
HLT + full lookahead + no deduction processing + no standardization
HLT + full lookahead + deduction processing + no standardization
HLT + partial lookahead + no deduction processing + standardization
HLT + partial lookahead + deduction processing + standardization
HLT + partial lookahead + no deduction processing + no standardization
HLT + partial lookahead + deduction processing + no standardization
Felsch + standardization
Felsch + no standardization

and this strategy is then run for approximately the amount of time specified by the setting random_interval(T).

enumerator CR¶

This strategy is meant to mimic the ACE strategy of the same name.

The Felsch is run until at least f_defs() nodes are defined, then the HLT strategy is run until at least hlt_defs() divided by length_of_generating_pairs() nodes have been defined. These steps are repeated until the enumeration terminates.

enumerator R_over_C¶

This strategy is meant to mimic the ACE strategy R/C.

The HLT strategy is run until the first lookahead is triggered (when number_of_cosets_active() is at least next_lookhead()). A full lookahead is then performed, and then the CR strategy is used.

enumerator Cr¶

This strategy is meant to mimic the ACE strategy Cr.

The Felsch strategy is run until at least f_defs() new nodes have been defined, the HLT strategy is then run until at least hlt_defs() divided by length_of_generating_pairs() new nodes are defined, and then the Felsch strategy is run.

enumerator Rc¶

This strategy is meant to mimic the ACE strategy Rc.

The HLT strategy is run until at least hlt_defs() divided by length_of_generating_pairs() new nodes have been defined, the Felsch strategy is then run until at least f_defs() new nodes are defined, and then the HLT strategy is run.

enum class libsemigroups::congruence::ToddCoxeter::order¶

The possible arguments for standardize(order).

The values in this enum can be used as the argument for standardize(order) to specify which ordering should be used. The normal forms for congruence classes are given with respect to one of the orders specified by the values in this enum.

Values:

enumerator none¶: No standardization has been done.

enumerator shortlex¶: Normal forms are the short-lex least word belonging to a given congruence class.

enumerator lex¶

The congruence classes are ordered lexicographically by their normal form.

The normal forms themselves are essentially arbitrary because there is not necessarily a lexicographically least word in every class.

enumerator recursive¶: Normal forms are the recursive-path least word belonging to a given congruence class.

using libsemigroups::congruence::ToddCoxeter::sort_free_function_type = bool(word_type const&, word_type const&)¶

Type of the argument to sort_generating_pairs.

A type alias for free functions that can be used as an argument to sort_generating_pairs.

using libsemigroups::congruence::ToddCoxeter::sort_function_type = std::function<bool(word_type const&, word_type const&)>¶

Type of the argument to sort_generating_pairs.

A type alias for functions that can be used as an argument to sort_generating_pairs.

using libsemigroups::congruence::ToddCoxeter::table_type = detail::DynamicArray2<coset_type>¶

Type of the underlying table.

This is the type of the coset table stored inside a ToddCoxeter instance.