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.

ToddCoxeter.complete(self: ToddCoxeter) → float

Returns the proportion of edges defined in the active part of the current word graph.

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 WordGraph.out_degree applied to current_word_graph.

Returns:: The proportion of edges defined in the active part of current_word_graph.
Return type:: float

>>> from libsemigroups_pybind11 import (Presentation, presentation, ToddCoxeter,
... congruence_kind)
>>> from datetime import timedelta
>>> p = Presentation("bcd")
>>> p.contains_empty_word(True)
<monoid presentation with 3 letters, 0 rules, and length 0>
>>> presentation.add_rule(p, "bb", "")
>>> presentation.add_rule(p, "cd", "")
>>> presentation.add_rule(p, "ccc", "")
>>> presentation.add_rule(p, "bcbcbcbcbcbcbc", "")
>>> presentation.add_rule(p, "bcbdbcbdbcbdbc", "")
>>> tc = ToddCoxeter(congruence_kind.twosided, p)
>>> tc.run()
>>> tc.complete()
1.0

ToddCoxeter.current_spanning_tree(self: ToddCoxeter) → Forest

Get the current possible spanning tree of the underlying word graph.

This function returns the current value of a possible spanning tree (a Forest) for the underlying WordGraph (returned by current_word_graph). This spanning tree is only populated during calls to standardize and as such might contain nothing, or a spanning tree of a previous value of current_word_graph. Some care should be used with the return value of this function, and it might be better to use the function spanning_tree, which has none of these limitation. If Runner.finished returns True, and standardize has been called prior to a call to this function, then the returned Forest will represent a valid spanning tree for the WordGraph returned by current_word_graph or word_graph.

Returns:: A possible spanning tree of the underlying WordGraph.
Return type:: Forest

ToddCoxeter.current_word_graph(self: ToddCoxeter) → WordGraph

Get the current 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 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 and shrink_to_fit can be used to modify the returned word graph in-place to have (possibly) more reasonable characteristics.

Returns:: The underlying WordGraph.
Return type:: WordGraph

ToddCoxeter.is_standardized(*args, **kwargs)

Overloaded function.

is_standardized(self: ToddCoxeter) → bool

Check if the word graph is currently standardized with respect to any order. 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.
Return type:: bool

is_standardized(self: ToddCoxeter, val: Order) → bool

Check if the word graph is currently standardized with respect to a given order.

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

Parameters:: val (Order) – the Order to check for.
Returns:: Whether or not the current word graph is standardized with respect to a given order.
Return type:: bool

ToddCoxeter.number_of_edges_active(self: ToddCoxeter) → int

Return the number of edges in the active part of the current word graph.

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.

Returns:: The number of edges that are incident to active nodes.
Return type:: int

>>> from libsemigroups_pybind11 import (Presentation, presentation, ToddCoxeter,
... congruence_kind)
>>> from datetime import timedelta
>>> p = Presentation("bcd")
>>> p.contains_empty_word(True)
<monoid presentation with 3 letters, 0 rules, and length 0>
>>> presentation.add_rule(p, "bb", "")
>>> presentation.add_rule(p, "cd", "")
>>> presentation.add_rule(p, "ccc", "")
>>> presentation.add_rule(p, "bcbcbc", "")
>>> presentation.add_rule(p, "bcbdbcbd", "")
>>> tc = ToddCoxeter(congruence_kind.twosided, p)
>>> tc.number_of_classes()
12
>>> tc.number_of_edges_active()
36

ToddCoxeter.number_of_large_collapses(self: ToddCoxeter) → int

Return the number of large collapses that have occurred.

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.
Return type:: int

>>> from libsemigroups_pybind11 import (Presentation, presentation, ToddCoxeter,
... congruence_kind)
>>> from datetime import timedelta
>>> p = Presentation("bcd")
>>> p.contains_empty_word(True)
<monoid presentation with 3 letters, 0 rules, and length 0>
>>> presentation.add_rule(p, "bb", "")
>>> presentation.add_rule(p, "cd", "")
>>> presentation.add_rule(p, "ccc", "")
>>> presentation.add_rule(p, "bcbcbcbcbcbcbc", "")
>>> presentation.add_rule(p, "bcbdbcbdbcbdbcbdbcbdbcbdbcbdbcbd", "")
>>> tc = ToddCoxeter(congruence_kind.twosided, p)
>>> tc.run_for(timedelta(milliseconds=10))
>>> tc.finished()
False
>>> tc.number_of_large_collapses()
0

ToddCoxeter.number_of_nodes_active(self: ToddCoxeter) → int

Return the number of nodes in the active part of the current word graph.

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.

Returns:: The number of nodes that are active.
Return type:: int

>>> from libsemigroups_pybind11 import (Presentation, presentation, ToddCoxeter,
... congruence_kind)
>>> from datetime import timedelta
>>> p = Presentation("bcd")
>>> p.contains_empty_word(True)
<monoid presentation with 3 letters, 0 rules, and length 0>
>>> presentation.add_rule(p, "bb", "")
>>> presentation.add_rule(p, "cd", "")
>>> presentation.add_rule(p, "ccc", "")
>>> presentation.add_rule(p, "bcbcbc", "")
>>> presentation.add_rule(p, "bcbdbcbd", "")
>>> tc = ToddCoxeter(congruence_kind.twosided, p)
>>> tc.number_of_classes()
12
>>> tc.number_of_nodes_active()
12

ToddCoxeter.spanning_tree(self: ToddCoxeter) → Forest

Get the spanning tree of the underlying word graph. This function returns 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 spanning tree of the underlying WordGraph.
Return type:: Forest

ToddCoxeter.standardization_order(self: ToddCoxeter) → Order

Get the current standardization order of the underlying word graph.

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; 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 todd_coxeter.normal_forms or todd_coxeter.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 todd_coxeter.normal_forms and todd_coxeter.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 todd_coxeter.normal_forms and todd_coxeter.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 todd_coxeter.normal_forms and todd_coxeter.normal_forms will be ordered by the 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.
Return type:: Order

ToddCoxeter.word_graph(self: ToddCoxeter) → WordGraph

Get the word graph after performing a full congruence enumeration.

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 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 ToddCoxeter.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 ToddCoxeter.generating_pairs.

Returns:: The underlying WordGraph.
Return type:: WordGraph