Path iterators¶

This page contains information about the functionality of the ActionDigraph class for iterating through paths.

inline const_panilo_iterator libsemigroups::ActionDigraph::cbegin_panilo(node_type source, size_t min = 0, size_t max = POSITIVE_INFINITY) const¶

Returns an iterator for PANILO (Path And Node In Lex Order).

Returns a forward iterator pointing to a pair consisting of the edge labels of the first path (in lexicographical order) starting at source with length in the range \([min, max)\) and the last node of that path.

If incremented, the iterator will point to the next least edge labelling of a path (in lexicographical order), and its last node, with length in the range \([min, max)\). Iterators of the type returned by this function are equal whenever they point to equal objects.

See also

cend_panilo

Warning

Copying iterators of this type is expensive. As a consequence, prefix incrementing ++it the returned iterator it significantly cheaper than postfix incrementing it++.

Warning

If the action digraph represented by this contains a cycle that is reachable from source, then there are infinitely many paths starting at source, and so max should be chosen with some care.

Parameters:

source – the source node
min – the minimum length of a path to enumerate (defaults to 0)
max – the maximum length of a path to enumerate (defaults to libsemigroups::POSITIVE_INFINITY).

Throws:

LibsemigroupsException – if source is not a node in the digraph.

Returns:

An iterator it of type const_panilo_iterator pointing to a std::pair where:

it->first is a libsemigroups::word_type consisting of the edge labels of the first path (in lexicographical order) from source of length in the range \([min, max)\); and
it->second is the last node on the path from source labelled by it->first, a value of node_type.

inline const_panislo_iterator libsemigroups::ActionDigraph::cbegin_panislo(node_type source, size_t min = 0, size_t max = POSITIVE_INFINITY) const¶

Returns an iterator for PANISLO (Path And Node In Short Lex Order).

Returns a forward iterator pointing to a pair consisting of the edge labels of the first path (in short-lex order) starting at source with length in the range \([min, max)\) and the last node of that path.

If incremented, the iterator will point to the next least edge labelling of a path (in short-lex order), and its last node, with length in the range \([min, max)\). Iterators of the type returned by this function are equal whenever they point to equal objects.

See also

cend_panislo

Warning

Copying iterators of this type is expensive. As a consequence, prefix incrementing ++it the returned iterator it significantly cheaper than postfix incrementing it++.

Warning

If the action digraph represented by this contains a cycle that is reachable from source, then there are infinitely many paths starting at source, and so max should be chosen with some care.

Parameters:

source – the source node
min – the minimum length of a path to enumerate (defaults to 0)
max – the maximum length of a path to enumerate (defaults to libsemigroups::POSITIVE_INFINITY).

Throws:

LibsemigroupsException – if source is not a node in the digraph.

Returns:

An iterator it of type const_panislo_iterator pointing to a std::pair where:

it->first is a libsemigroups::word_type consisting of the edge labels of the first path (in short-lex order) from source of length in the range \([min, max)\); and
it->second is the last node on the path from source labelled by it->first, a value of node_type.

inline const_pilo_iterator libsemigroups::ActionDigraph::cbegin_pilo(node_type source, size_t min = 0, size_t max = POSITIVE_INFINITY) const¶

Returns an iterator for PILO (Path In Lex Order).

Returns a forward iterator pointing to the edge labels of the first path (in lexicographical order) starting at source with length in the range \([min, max)\).

If incremented, the iterator will point to the next least edge labelling of a path (in lexicographical order), with length in the range \([min, max)\). Iterators of the type returned by this function are equal whenever they point to equal objects.

See also

cend_pilo

Warning

Copying iterators of this type is expensive. As a consequence, prefix incrementing ++it the returned iterator it significantly cheaper than postfix incrementing it++.

Warning

If the action digraph represented by this contains a cycle that is reachable from source, then there are infinitely many paths starting at source, and so max should be chosen with some care.

Parameters:

source – the source node
min – the minimum length of a path to enumerate (defaults to 0)
max – the maximum length of a path to enumerate (defaults to libsemigroups::POSITIVE_INFINITY).

Throws:

LibsemigroupsException – if source is not a node in the digraph.

Returns:

An iterator it of type const_pilo_iterator pointing to a libsemigroups::word_type consisting of the edge labels of the first path (in lexicographical order) from source of length in the range \([min, max)\).

inline const_pislo_iterator libsemigroups::ActionDigraph::cbegin_pislo(node_type source, size_t min = 0, size_t max = POSITIVE_INFINITY) const¶

Returns an iterator for PISLO (Path In Short Lex Order).

Returns a forward iterator pointing to the edge labels of the first path (in short-lex order) starting at source with length in the range \([min, max)\).

If incremented, the iterator will point to the next least edge labelling of a path (in short-lex order), with length in the range \([min, max)\). Iterators of the type returned by this function are equal whenever they point to equal objects.

See also

cend_pislo

Warning

Copying iterators of this type is expensive. As a consequence, prefix incrementing ++it the returned iterator it significantly cheaper than postfix incrementing it++.

Warning

If the action digraph represented by this contains a cycle that is reachable from source, then there are infinitely many paths starting at source, and so max should be chosen with some care.

Parameters:

source – the source node
min – the minimum length of a path to enumerate (defaults to 0)
max – the maximum length of a path to enumerate (defaults to libsemigroups::POSITIVE_INFINITY).

Throws:

LibsemigroupsException – if source is not a node in the digraph.

Returns:

An iterator it of type const_pislo_iterator pointing to a libesemigroups::word_type consisting of the edge labels of the first path (in short-lex order) from source of length in the range \([min, max)\).

inline const_pstilo_iterator libsemigroups::ActionDigraph::cbegin_pstilo(node_type source, node_type target, size_t min = 0, size_t max = POSITIVE_INFINITY) const¶

Returns an iterator for PSTILO (Path Source Target In Lex Order).

Returns a forward iterator pointing to the edge labels of the first path (in lexicographical order) starting at the node source and ending at the node target with length in the range \([min, max)\).

If incremented, the iterator will point to the next least edge labelling of a path (in lexicographical order). Iterators of the type returned by this function are equal whenever they point to equal objects.

See also

cend_pstilo

Warning

Copying iterators of this type is expensive. As a consequence, prefix incrementing ++it the returned iterator it significantly cheaper than postfix incrementing it++.

Warning

If the action digraph represented by this contains a cycle that is reachable from source, then there may be infinitely many paths starting at source, and so max should be chosen with some care.

Parameters:

source – the first node
target – the last node
min – the minimum length of a path to enumerate (defaults to 0)
max – the maximum length of a path to enumerate (defaults to libsemigroups::POSITIVE_INFINITY).

Throws:

LibsemigroupsException – if target or source is not a node in the digraph.

Returns:

An iterator it of type const_pstilo_iterator pointing to a libsemigroups::word_type consisting of the edge labels of the first path (in lexicographical order) from the node source to the node target with length in the range \([min, max)\) (if any).

inline const_pstislo_iterator libsemigroups::ActionDigraph::cbegin_pstislo(node_type source, node_type target, size_t min = 0, size_t max = POSITIVE_INFINITY) const¶

Returns an iterator for PSTISLO (Path Source Target In Short Lex Order).

Returns a forward iterator pointing to the edge labels of the first path (in short-lex order) starting at the node source and ending at the node target with length in the range \([min, max)\).

If incremented, the iterator will point to the next least edge labelling of a path (in short-lex order). Iterators of the type returned by this function are equal whenever they point to equal objects.

See also

cend_pstislo

Warning

Copying iterators of this type is expensive. As a consequence, prefix incrementing ++it the returned iterator it significantly cheaper than postfix incrementing it++.

Warning

If the action digraph represented by this contains a cycle that is reachable from source, then there may be infinitely many paths starting at source, and so max should be chosen with some care.

Parameters:

source – the first node
target – the last node
min – the minimum length of a path to enumerate (defaults to 0)
max – the maximum length of a path to enumerate (defaults to libsemigroups::POSITIVE_INFINITY).

Throws:

LibsemigroupsException – if target or source is not a node in the digraph.

Returns:

An iterator it of type const_pstislo_iterator pointing to a libsemigroups::word_type consisting of the edge labels of the first path (in short-lex order) from the node source to the node target with length in the range \([min, max)\) (if any).

inline const_panilo_iterator libsemigroups::ActionDigraph::cend_panilo() const¶

Returns an iterator for PANILO (Path And Node In Lex Order).

Returns a forward iterator pointing to one after the last path from any node in the digraph.