This page contains documentation of the member functions of ToddCoxeter that can be used to modify the state of a ToddCoxeter instance. In other words, for modifying the WordGraph that is the output of the algorithm in a way that preserves it up to isomorphism.
◆ perform_lookahead() [1/2]
| ToddCoxeterImpl & perform_lookahead |
( |
| ) |
|
◆ perform_lookahead() [2/2]
| void perform_lookahead |
( |
bool | stop_early | ) |
|
This function can be used to explicitly perform a lookahead. The style and extent of this lookahead are controlled by the settings lookahead_style and lookahead_extent.
If the argument stop_early is true, then the settings lookahead_stop_early_interval and lookahead_stop_early_ratio are used to determine whether or not the lookahead should be aborted early. If stop_early is false, then these settings are ignored.
- Parameters
-
| stop_early | whether or not to consider stopping the lookahead early if too few nodes are killed. |
- Deprecated
- This function is deprecated and will be removed from
libsemigroups in v4. Use perform_lookahead_until instead.
◆ perform_lookahead_for()
This function runs a lookahead for approximately the amount of time indicated by t, or until the lookahead is complete whichever happens first.
- Parameters
-
| t | the time to run for in nanoseconds. |
- Returns
- A reference to
*this.
◆ perform_lookahead_until() [1/2]
| ToddCoxeterImpl & perform_lookahead_until |
( |
std::function< bool()> && | pred | ) |
|
This function runs a lookahead until the nullary predicate pred returns true, or until the lookahead is complete whichever happens first.
- Parameters
-
| pred | an rvalue reference to the nullary predicate. |
- Returns
- A reference to
*this.
◆ perform_lookahead_until() [2/2]
| ToddCoxeterImpl & perform_lookahead_until |
( |
std::function< bool()> const & | pred | ) |
|
|
inline |
This function runs a lookahead until the nullary predicate pred returns true, or until the lookahead is complete whichever happens first.
- Parameters
-
| pred | a const reference to the nullary predicate. |
- Returns
- A reference to
*this.
◆ perform_lookbehind()
| ToddCoxeterImpl & perform_lookbehind |
( |
| ) |
|
This function performs a "lookbehind" which is defined as follows. For every node n in the so-far computed WordGraph (obtained from current_word_graph) we use the current word graph to rewrite the current short-lex least path from the initial node to n. If this rewritten word is not equal to the original word, and it also labels a path from the initial node in the current word graph to a node m, then m and n represent the same congruence class. Thus we may collapse m and n (i.e. quotient the word graph by the least congruence containing the pair m and n).
The intended use case for this function is when you have a large word graph in a partially enumerated ToddCoxeter instance, and you would like to minimise this word graph as far as possible.
For example, if we take the following monoid presentation of B. H. Neumann for the trivial group:
using options = detail::ToddCoxeterImpl::options;
tc.lookahead_extent(options::lookahead_extent::full)
.lookahead_style(options::lookahead_style::felsch);
tc.run_until([&tc]() -> bool {
return tc.current_word_graph().number_of_nodes_active() >=
12'000'000;
});
tc.perform_lookbehind();
tc.number_of_classes();
For an implementation of presentations for semigroups or monoids.
Definition presentation.hpp:103
bool contains_empty_word() const noexcept
Return whether the empty word is a valid relation word.
Definition presentation.hpp:539
word_type const & alphabet() const noexcept
Return the alphabet of the presentation.
Definition presentation.hpp:184
@ twosided
Value representing a two-sided congruence.
Definition types.hpp:71
void add_inverse_rules(Presentation< Word > &p, Word const &vals, typename Presentation< Word >::letter_type e=UNDEFINED)
Add rules for inverses.
void add_rule(Presentation< Word > &p, Word const &lhop, Word const &rhop)
Add a rule to the presentation by reference and check.
Definition presentation.hpp:907
Doing tc.run() in the previous example will simply grow the underlying word graph until your computer runs out of memory. The authors of libsemigroups were not able to find any combination of the many settings for ToddCoxeter where running tc returned an answer. We also tried with GAP and ACE but neither of these seemed able to return an answer either.
- Returns
- A reference to
*this.
- Exceptions
-
◆ perform_lookbehind_for()
This function runs a lookbehind for approximately the amount of time indicated by t, or until the lookbehind is complete whichever happens first.
- Parameters
-
| t | the time to run for in nanoseconds. |
- Returns
- A reference to
*this.
- Exceptions
-
◆ perform_lookbehind_for_no_checks()
This function runs a lookbehind using collapser for approximately the amount of time indicated by t, or until the lookbehind is complete whichever happens first. See perform_lookbehind_no_checks(Func&&) for more details.
- Template Parameters
-
| Func | the type of collapser. |
- Parameters
-
| t | the time to run for in nanoseconds. |
| collapser | a function taking three arguments: d_first, first, and last which rewrites the word given by [first, last) and writes the output into d_first. |
- Returns
- A reference to
*this.
- Exceptions
-
- Warning
- No checks are performed on the argument
collapser to ensure that the word graph produced by using it to collapse nodes is valid. It is the responsibility of the caller to ensure that this is valid.
◆ perform_lookbehind_no_checks()
template<typename Func>
| ToddCoxeterImpl & perform_lookbehind_no_checks |
( |
Func && | collapser | ) |
|
This function perform a lookbehind using the function collapser to decide whether or not to collapse nodes. For example, it might be the case that collapser uses a KnuthBendix instance to determine whether or not nodes in the graph represent the same class of the congruence. More specifically, the shortlex least path from the initial node to every node n is rewritten using collapser, and if the rewritten word labels a path in the graph to a node m, then it is assumed that m and n represent the same class of the congruence, and they are marked for collapsing. For example, perform_lookbehind calls perform_lookbehind_no_checks where collapser is the member function reduce_no_run_no_checks.
- Template Parameters
-
| Func | the type of collapser. |
- Parameters
-
| collapser | a function taking three arguments: d_first, first, and last which rewrites the word given by [first, last) and writes the output into d_first. |
- Returns
- A reference to
*this.
- Exceptions
-
- Warning
- No checks are performed on the argument
collapser to ensure that the word graph produced by using it to collapse nodes is valid. It is the responsibility of the caller to ensure that this is valid.
◆ perform_lookbehind_until() [1/2]
| ToddCoxeterImpl & perform_lookbehind_until |
( |
std::function< bool()> && | pred | ) |
|
This function runs a lookbehind until the nullary predicate pred returns true, or until the lookbehind is complete whichever happens first.
- Parameters
-
| pred | an rvalue reference to the nullary predicate. |
- Returns
- A reference to
*this.
- Exceptions
-
◆ perform_lookbehind_until() [2/2]
| ToddCoxeterImpl & perform_lookbehind_until |
( |
std::function< bool()> const & | pred | ) |
|
|
inline |
This function runs a lookbehind until the nullary predicate pred returns true, or until the lookbehind is complete whichever happens first.
- Parameters
-
| pred | a const reference to the nullary predicate. |
- Returns
- A reference to
*this.
- Exceptions
-
◆ perform_lookbehind_until_no_checks() [1/2]
template<typename Func>
| ToddCoxeterImpl & perform_lookbehind_until_no_checks |
( |
std::function< bool()> && | pred, |
|
|
Func && | collapser ) |
This function runs a lookbehind using collapser until the nullary predicate pred returns true, or until the lookbehind is complete whichever happens first.
- Template Parameters
-
| Func | the type of collapser. |
- Parameters
-
| pred | an rvalue reference to the nullary predicate. |
| collapser | a function taking three arguments: d_first, first, and last which rewrites the word given by [first, last) and writes the output into d_first. |
- Returns
- A reference to
*this.
- Exceptions
-
- Warning
- No checks are performed on the argument
collapser to ensure that the word graph produced by using it to collapse nodes is valid. It is the responsibility of the caller to ensure that this is valid.
◆ perform_lookbehind_until_no_checks() [2/2]
template<typename Func>
| ToddCoxeterImpl & perform_lookbehind_until_no_checks |
( |
std::function< bool()> const & | pred, |
|
|
Func && | collapser ) |
|
inline |
This function runs a lookbehind using collapser until the nullary predicate pred returns true, or until the lookbehind is complete whichever happens first.
- Template Parameters
-
| Func | the type of collapser. |
- Parameters
-
| pred | a const reference to the nullary predicate. |
| collapser | a function taking three arguments: d_first, first, and last which rewrites the word given by [first, last) and writes the output into d_first. |
- Returns
- A reference to
*this.
- Exceptions
-
- Warning
- No checks are performed on the argument
collapser to ensure that the word graph produced by using it to collapse nodes is valid. It is the responsibility of the caller to ensure that this is valid.
◆ shrink_to_fit()
This function triggers a full enumeration, and standardization, and removes from word_graph any dead nodes.
If finished returns false, then this function does nothing.
◆ standardize()
| bool standardize |
( |
Order | val | ) |
|
|
inline |
This function standardizes the return value of current_word_graph, and does not trigger any enumeration. See standardization_order for a full description. The return value of this function indicates whether or not the current_word_graph was modified. In other words, if this function returns true, then the word graph was not previously standardized with respect to val, and was modified by calling this function if false is returned, then the word graph was previously standardized with respect to val (although this might not have been known), and was not modified by calling this function.
- Parameters
-
| val | the order of the standardization. |
- Returns
- Whether or not the word graph was modified by the standardization.
- Note
- If
val is Order::none, then this function does nothing.
- See also
- standardize
-
current_spanning_tree.
