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.
Functions | |
| ToddCoxeterImpl & | perform_lookahead () |
| Perform a lookahead. | |
| void | perform_lookahead (bool stop_early) |
| Perform a lookahead. | |
| ToddCoxeterImpl & | perform_lookahead_for (std::chrono::nanoseconds t) |
| Perform a lookahead for a specified amount of time. | |
| ToddCoxeterImpl & | perform_lookahead_until (std::function< bool()> &&pred) |
Perform a lookahead until a nullary predicate returns true. | |
| ToddCoxeterImpl & | perform_lookahead_until (std::function< bool()> const &pred) |
Perform a lookahead until a nullary predicate returns true or finished. | |
| ToddCoxeterImpl & | perform_lookbehind () |
| Perform a lookbehind. | |
| ToddCoxeterImpl & | perform_lookbehind_for (std::chrono::nanoseconds t) |
| Perform a lookbehind for a specified amount of time. | |
| template<typename Func> | |
| ToddCoxeterImpl & | perform_lookbehind_for_no_checks (std::chrono::nanoseconds t, Func &&collapser) |
| Perform a lookbehind for a specified amount of time with a collapser. | |
| template<typename Func> | |
| ToddCoxeterImpl & | perform_lookbehind_no_checks (Func &&collapser) |
| Perform a lookbehind using a function to decide whether or not to collapse nodes. | |
| ToddCoxeterImpl & | perform_lookbehind_until (std::function< bool()> &&pred) |
Perform a lookbehind until a nullary predicate returns true or finished. | |
| ToddCoxeterImpl & | perform_lookbehind_until (std::function< bool()> const &pred) |
Perform a lookbehind until a nullary predicate returns true or finished. | |
| template<typename Func> | |
| ToddCoxeterImpl & | perform_lookbehind_until_no_checks (std::function< bool()> &&pred, Func &&collapser) |
Perform a lookbehind until a nullary predicate returns true. | |
| template<typename Func> | |
| ToddCoxeterImpl & | perform_lookbehind_until_no_checks (std::function< bool()> const &pred, Func &&collapser) |
Perform a lookbehind until a nullary predicate returns true. | |
| void | shrink_to_fit () |
| Shrink the underlying word graph to remove all dead nodes. | |
| bool | standardize (Order val) |
| Standardize the current_word_graph. | |
| ToddCoxeterImpl & perform_lookahead | ( | ) |
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.
| 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.
| stop_early | whether or not to consider stopping the lookahead early if too few nodes are killed. |
| ToddCoxeterImpl & perform_lookahead_for | ( | std::chrono::nanoseconds | t | ) |
This function runs a lookahead for approximately the amount of time indicated by t, or until the lookahead is complete whichever happens first.
| t | the time to run for in nanoseconds. |
| 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.
| pred | an rvalue reference to the nullary predicate. |
|
inline |
This function runs a lookahead until the nullary predicate pred returns true, or until the lookahead is complete whichever happens first.
| pred | a const reference to the nullary predicate. |
| 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:
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.
| LibsemigroupsException | if this is a one-sided congruence and has any generating pairs (because in this case perform_lookbehind does nothing but still might take some time to run). |
| ToddCoxeterImpl & perform_lookbehind_for | ( | std::chrono::nanoseconds | t | ) |
This function runs a lookbehind for approximately the amount of time indicated by t, or until the lookbehind is complete whichever happens first.
| t | the time to run for in nanoseconds. |
| LibsemigroupsException | if this is a one-sided congruence and has any generating pairs (because in this case perform_lookbehind does nothing but still might take some time to run). |
| ToddCoxeterImpl & perform_lookbehind_for_no_checks | ( | std::chrono::nanoseconds | t, |
| Func && | collapser ) |
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.
| Func | the type of collapser. |
| 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. |
| LibsemigroupsException | if this is a one-sided congruence and has any generating pairs (because in this case perform_lookbehind does nothing but still might take some time to run). |
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. | 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.
| Func | the type of collapser. |
| 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. |
| LibsemigroupsException | if this is a one-sided congruence and has any generating pairs (because in this case perform_lookbehind does nothing but still might take some time to run). |
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. | 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.
| pred | an rvalue reference to the nullary predicate. |
| LibsemigroupsException | if this is a one-sided congruence and has any generating pairs (because in this case perform_lookbehind does nothing but still might take some time to run). |
|
inline |
This function runs a lookbehind until the nullary predicate pred returns true, or until the lookbehind is complete whichever happens first.
| pred | a const reference to the nullary predicate. |
| LibsemigroupsException | if this is a one-sided congruence and has any generating pairs (because in this case perform_lookbehind does nothing but still might take some time to run). |
| 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.
| Func | the type of collapser. |
| 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. |
| LibsemigroupsException | if this is a one-sided congruence and has any generating pairs (because in this case perform_lookbehind does nothing but still might take some time to run). |
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.
|
inline |
This function runs a lookbehind using collapser until the nullary predicate pred returns true, or until the lookbehind is complete whichever happens first.
| Func | the type of collapser. |
| 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. |
| LibsemigroupsException | if this is a one-sided congruence and has any generating pairs (because in this case perform_lookbehind does nothing but still might take some time to run). |
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. | void 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.
|
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.
| val | the order of the standardization. |
val is Order::none, then this function does nothing.
1.16.1