template<typename Node>
class libsemigroups::Paths< Node >
Defined in paths.hpp.
This class represents a range object that facilitates iterating through the paths in a WordGraph from a given source node (possible to a target node) in a particular order.
- Template Parameters
-
| Node | the type of the nodes in the underlying WordGraph. |
So that the Paths class can be used efficiently with the functionality of rx::ranges, the usual naming conventions in libsemigroups are not used for the member functions:
of Paths. In particular, none of these member functions check their arguments, but they do not have the suffix _no_checks.
For a Paths object to be valid it must have its source node defined (using source), both the source (set using source) and target (set using target) nodes must belong to the underlying WordGraph (word_graph). This can be verified by checking source() != UNDEFINED. The functions listed above (get, next, at_end, size_hint, count) should only be called if source() != UNDEFINED, and it is the responsibility of the caller to ensure that this is the case.
Changing the value of source, target, min, max, or order resets the Paths object to point at the first word in the specified range.
|
(Note that these are not member symbols.)
|
| template<typename Node> |
| | Paths (WordGraph< Node > &&) -> Paths< Node > |
| |
| template<typename Node> |
| | Paths (WordGraph< Node > const &) -> Paths< Node > |
| |
| template<typename Node1, typename Node2> |
| auto | cbegin_pilo (WordGraph< Node1 > const &wg, Node2 source, size_t min=0, size_t max=POSITIVE_INFINITY) |
| | Returns an iterator for pilo (Path And Node In Lex Order).
|
| |
| template<typename Node1, typename Node2> |
| auto | cbegin_pislo (WordGraph< Node1 > const &wg, Node2 source, size_t min=0, size_t max=POSITIVE_INFINITY) |
| |
| template<typename Node1, typename Node2> |
| auto | cbegin_pstilo (WordGraph< Node1 > const &wg, Node2 source, Node2 target, size_t min=0, size_t max=POSITIVE_INFINITY) |
| |
| template<typename Node1, typename Node2> |
| auto | cbegin_pstislo (WordGraph< Node1 > const &wg, Node2 source, Node2 target, size_t min=0, size_t max=POSITIVE_INFINITY) |
| |
| template<typename Node> |
| auto | cend_pilo (WordGraph< Node > const &wg) |
| |
| template<typename Node> |
| auto | cend_pislo (WordGraph< Node > const &wg) |
| |
| template<typename Node> |
| auto | cend_pstilo (WordGraph< Node > const &wg) |
| |
| template<typename Node> |
| auto | cend_pstislo (WordGraph< Node > const &wg) |
| |
| template<typename Node1, typename Node2> |
| uint64_t | number_of_paths (WordGraph< Node1 > const &wg, Node2 source) |
| |
| template<typename Node1, typename Node2> |
| uint64_t | number_of_paths (WordGraph< Node1 > const &wg, Node2 source, Node2 target, size_t min, size_t max, paths::algorithm lgrthm=paths::algorithm::automatic) |
| |
| template<typename Node1, typename Node2> |
| uint64_t | number_of_paths (WordGraph< Node1 > const &wg, Node2 source, size_t min, size_t max, paths::algorithm lgrthm=paths::algorithm::automatic) |
| |
| template<typename Node1, typename Node2> |
| paths::algorithm | number_of_paths_algorithm (WordGraph< Node1 > const &wg, Node2 source) noexcept |
| |
| template<typename Node1, typename Node2> |
| paths::algorithm | number_of_paths_algorithm (WordGraph< Node1 > const &wg, Node2 source, Node2 target, size_t min, size_t max) |
| |
| template<typename Node1, typename Node2> |
| paths::algorithm | number_of_paths_algorithm (WordGraph< Node1 > const &wg, Node2 source, size_t min, size_t max) |
| |
| template<typename Node> |
| std::string | to_human_readable_repr (Paths< Node > const &p) |
| | Return a human readable representation of a Paths object.
|
| |
template<typename Node1, typename Node2>
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.
- Parameters
-
| wg | the WordGraph. |
| 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 POSITIVE_INFINITY). |
- Returns
- An iterator
it of type const_pilo_iterator pointing to a std::pair where:
it->first is a word_type consisting of the edge labels of the first path (in lexicographical order) from source of length in the range \([min, max)\); andit->second is the last node on the path from source labelled by it->first, a value of node_type.
- Exceptions
-
- Warning
- Copying iterators of this type is expensive. As a consequence, prefix incrementing
++it the returned iterator it significantly cheaper than postfix incrementing it++.
-
If the word graph 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.
- See also
- cend_pilo
template<typename Node1, typename Node2>
Returns an iterator for pislo (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.
- Parameters
-
| wg | the WordGraph. |
| 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 POSITIVE_INFINITY). |
- Returns
- An iterator
it of type detail::const_pislo_iterator pointing to a std::pair where:
it->first is a word_type consisting of the edge labels of the first path (in short-lex order) from source of length in the range \([min, max)\); andit->second is the last node on the path from source labelled by it->first, a value of node_type.
- Exceptions
-
- Warning
- Copying iterators of this type is expensive. As a consequence, prefix incrementing
++it the returned iterator it significantly cheaper than postfix incrementing it++.
-
If the word graph 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.
- See also
- cend_pislo
template<typename Node1, typename Node2>
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.
- Parameters
-
| wg | the WordGraph. |
| 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 POSITIVE_INFINITY). |
- Returns
- An iterator
it of type detail::const_pstilo_iterator pointing to a 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).
- Exceptions
-
- Warning
- Copying iterators of this type is expensive. As a consequence, prefix incrementing
++it the returned iterator it significantly cheaper than postfix incrementing it++.
-
If the word graph 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.
- See also
- cend_pstilo
template<typename Node1, typename Node2>
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.
- Parameters
-
| wg | the WordGraph. |
| 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 POSITIVE_INFINITY). |
- Returns
- An iterator
it of type detail::const_pstislo_iterator pointing to a 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).
- Exceptions
-
- Warning
- Copying iterators of this type is expensive. As a consequence, prefix incrementing
++it the returned iterator it significantly cheaper than postfix incrementing it++.
-
If the word graph 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.
- See also
- cend_pstislo
