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.
|
| | Paths (Paths &&) |
| | Default move constructor.
|
| | Paths (Paths const &) |
| | Default copy constructor.
|
| | Paths (WordGraph< Node > const &wg) |
| | Construct from a WordGraph.
|
| bool | at_end () const |
| | Check if the range is exhausted.
|
| uint64_t | count () const |
| | Get the size of the range.
|
| node_type | current_target () const |
| | Get the current target node of the path labelled by get.
|
| output_type | get () const |
| | Get the current path in the range.
|
| Paths & | init (WordGraph< Node > const &wg) |
| | Reinitialize a Paths object.
|
| size_type | max () const noexcept |
| | Get the maximum length of path in the range.
|
| Paths & | max (size_type val) noexcept |
| | Set the maximum length of path in the range.
|
| size_type | min () const noexcept |
| | Get the minimum length of path in the range.
|
| Paths & | min (size_type val) noexcept |
| | Set the minimum length of path in the range.
|
| void | next () |
| | Advance to the next path in the range.
|
| Paths & | operator= (Paths &&) |
| | Default move assignment operator.
|
| Paths & | operator= (Paths const &) |
| | Default copy assignment operator.
|
| Order | order () const noexcept |
| | Get the order of the paths in the range.
|
| Paths & | order (Order val) |
| | Set the order of the paths in the range.
|
| uint64_t | size_hint () const |
| | Get the size of the range.
|
| node_type | source () const noexcept |
| | Get the current source node of every path in the range.
|
| Paths & | source (node_type n) |
| | Set the source node of every path in the range.
|
| Paths & | source_no_checks (node_type n) noexcept |
| | Set the source node of every path in the range.
|
| node_type | target () const noexcept |
| | Get the current target node of every path in the range.
|
| Paths & | target (node_type n) |
| | Set the target node of every path in the range.
|
| Paths & | target_no_checks (node_type n) noexcept |
| | Set the target node of every path in the range.
|
| void | throw_if_source_undefined () const |
| | Throw an exception if the source node has not been defined (using source).
|
| WordGraph< Node > const & | word_graph () const noexcept |
| | The underlying WordGraph.
|
|
(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, v4::paths::algorithm lgrthm=v4::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, v4::paths::algorithm lgrthm=v4::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
-
- 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
-
- 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
-
- Returns
- An iterator
it 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
-
- 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
1.16.1