# 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
• 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
• 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.