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 outdegree 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 outdegree 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 outdegree 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 outdegree 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 outdegree 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 outdegree 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.