Counting paths¶
This page contains information about the functionality of the ActionDigraph
class for counting paths.
-
inline uint64_t libsemigroups::ActionDigraph::number_of_paths(node_type source) const¶
Returns the number of paths from a source node.
- Complexity
At worst \(O(nm)\) where \(n\) is the number of nodes and \(m\) is the out-degree of the digraph.
Warning
If the number of paths exceeds 2 ^ 64, then return value of this function will not be correct.
- Parameters
source – the source node.
- Throws
LibsemigroupsException – if
source
is not a node in the digraph.- Returns
A value of type
uint64_t
.
-
inline uint64_t libsemigroups::ActionDigraph::number_of_paths(node_type source, node_type target, size_t min, size_t max, algorithm lgrthm = algorithm::automatic) const¶
Returns the number of paths between a pair of nodes with length in a given range.
- Complexity
The complexity depends on the value of
lgrthm
as follows:algorithm::dfs: \(O(r)\) where \(r\) is the number of paths in the digraph starting at
source
algorithm::matrix: at worst \(O(n ^ 3 k)\) where \(n\) is the number of nodes and \(k\) equals
max
.algorithm::acyclic: at worst \(O(nm)\) where \(n\) is the number of nodes and \(m\) is the out-degree of the digraph (only valid if the subdigraph induced by the nodes reachable from
source
is acyclic)algorithm::trivial: constant (only valid in some circumstances)
algorithm::automatic: attempts to select the fastest algorithm of the preceding algorithms and then applies that.
Warning
If
lgrthm
is algorithm::automatic, then it is not always the case that the fastest algorithm is used.Warning
If the number of paths exceeds 2 ^ 64, then return value of this function will not be correct.
- Parameters
source – the first node
target – the last node
min – the minimum length of a path
max – the maximum length of a path
lgrthm – the algorithm to use (defaults to: algorithm::automatic).
- Throws
LibsemigroupsException – if:
source
is not a node in the digraph.target
is not a node in the digraph.the algorithm specified by
lgrthm
is not applicable.
- Returns
A value of type
uint64_t
.
-
inline uint64_t libsemigroups::ActionDigraph::number_of_paths(node_type source, size_t min, size_t max, algorithm lgrthm = algorithm::automatic) const¶
Returns the number of paths starting at a given node with length in a given range.
- Complexity
The complexity depends on the value of
lgrthm
as follows:algorithm::dfs: \(O(r)\) where \(r\) is the number of paths in the digraph starting at
source
algorithm::matrix: at worst \(O(n ^ 3 k)\) where \(n\) is the number of nodes and \(k\) equals
max
.algorithm::acyclic: at worst \(O(nm)\) where \(n\) is the number of nodes and \(m\) is the out-degree of the digraph (only valid if the subdigraph induced by the nodes reachable from
source
is acyclic)algorithm::trivial: at worst \(O(nm)\) where \(n\) is the number of nodes and \(m\) is the out-degree of the digraph (only valid in some circumstances)
algorithm::automatic: attempts to select the fastest algorithm of the preceding algorithms and then applies that.
Warning
If
lgrthm
is algorithm::automatic, then it is not always the case that the fastest algorithm is used.Warning
If the number of paths exceeds 2 ^ 64, then return value of this function will not be correct.
- Parameters
source – the first node
min – the minimum length of a path
max – the maximum length of a path
lgrthm – the algorithm to use (defaults to: algorithm::automatic).
- Throws
LibsemigroupsException – if:
source
is not a node in the digraph.the algorithm specified by
lgrthm
is not applicable.
- Returns
A value of type
uint64_t
.
-
inline algorithm libsemigroups::ActionDigraph::number_of_paths_algorithm(node_type source) const noexcept¶
Returns the algorithm used by number_of_paths().
- Complexity
Constant
- Parameters
source – the source node.
- Throws
(None) – This function is
noexcept
and is guaranteed never to throw.- Returns
A value of type algorithm.
-
inline algorithm libsemigroups::ActionDigraph::number_of_paths_algorithm(node_type source, node_type target, size_t min, size_t max) const¶
Returns the algorithm used by number_of_paths().
Returns the algorithm used by number_of_paths() to compute the number of paths originating at the given source node and ending at the given target node with length in the range \([min, max)\).
- Complexity
At worst \(O(nm)\) where \(n\) is the number of nodes and \(m\) is the out-degree of the digraph.
- Parameters
source – the source node
target – the target node
min – the minimum length of paths to count
max – the maximum length of paths to count
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
A value of type algorithm.
-
inline algorithm libsemigroups::ActionDigraph::number_of_paths_algorithm(node_type source, size_t min, size_t max) const¶
Returns the algorithm used by number_of_paths().
Returns the algorithm used by number_of_paths() to compute the number of paths originating at the given source node with length in the range \([min, max)\).
- Complexity
At worst \(O(nm)\) where \(n\) is the number of nodes and \(m\) is the out-degree of the digraph.
- Parameters
source – the source node
min – the minimum length of paths to count
max – the maximum length of paths to count
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
A value of type algorithm.