Paths helpers

This page contains the documentation for the paths subpackage, that contains helper functions for the Paths class.

Contents

number_of_paths_algorithm(…)

Overloaded function.

number_of_paths(…)

Overloaded function.

Full API

This page contains the documentation for the paths subpackage, that contains helper functions for the Paths class.

paths.number_of_paths(*args, **kwargs)

Overloaded function.

paths.number_of_paths(wg: WordGraph, source: int) → int | PositiveInfinity

Returns the number of paths from a source node.

This function returns the number of paths in the word graph wg starting at source.

Parameters:

  • wg (WordGraph) – the word graph.

  • source (int) – the source node.

Returns:

The number of paths.

Return type:

int | PositiveInfinity

Raises:

LibsemigroupsError – if source is not a node of the word graph wg.

Complexity:

At worst \(O(nm)\) where \(n\) is the number of nodes and \(m\) is the out-degree of the word graph.

Note

If libsemigroups is compiled with the flag --enable-eigen, then this function makes use of the Eigen library for linear algebra (see [GJ+10]).

Warning

If the number of paths exceeds 2 ** 64, then return value of this function will not be correct.

paths.number_of_paths(wg: WordGraph, source: int, min: int, max: int | PositiveInfinity, lgrthm: paths.algorithm = paths.algorithm.automatic) → int | PositiveInfinity

Returns the number of paths starting at a given node with length in a given range.

This function returns the number of paths starting at a given node with length in a given range.

Parameters:
Returns:

The number of paths.

Return type:

int | PositiveInfinity

Complexity:

The complexity depends on the value of lgrthm as follows:

  • paths.algorithm.dfs: \(O(r)\) where \(r\) is the number of paths in the word graph starting at source

  • paths.algorithm.matrix: at worst \(O(n ^ 3 k)\) where \(n\) is the number of nodes and \(k\) equals max.

  • paths.algorithm.acyclic: at worst \(O(nm)\) where \(n\) is the number of nodes and \(m\) is the out-degree of the word graph (only valid if the subgraph induced by the nodes reachable from source is acyclic)

  • paths.algorithm.trivial: at worst \(O(nm)\) where \(n\) is the number of nodes and \(m\) is the out-degree of the word graph (only valid in some circumstances)

  • paths.algorithm.automatic: attempts to select the fastest algorithm of the preceding algorithms and then applies that.

Note

If libsemigroups is compiled with the flag --enable-eigen, then this function makes use of the Eigen library for linear algebra (see [GJ+10]).

Warning

If the number of paths exceeds 2 ** 64, then return value of this function will not be correct.

Warning

If lgrthm is paths.algorithm.automatic, then it is not always the case that the fastest algorithm is used.

paths.number_of_paths(wg: WordGraph, source: int, target: int, min: int, max: int | PositiveInfinity, lgrthm: paths.algorithm = paths.algorithm.automatic) → int | PositiveInfinity

Returns the number of paths starting at the node source and ending at node target with length in a given range.

This function returns the number of paths starting at the node source and ending at node target with length in a given range.

Parameters:
Returns:

The number of paths.

Return type:

int | PositiveInfinity

Complexity:

The complexity depends on the value of lgrthm as follows:

  • paths.algorithm.dfs: \(O(r)\) where \(r\) is the number of paths in the word graph starting at source

  • paths.algorithm.matrix: at worst \(O(n ^ 3 k)\) where \(n\) is the number of nodes and \(k\) equals max.

  • paths.algorithm.acyclic: at worst \(O(nm)\) where \(n\) is the number of nodes and \(m\) is the out-degree of the word graph (only valid if the subgraph induced by the nodes reachable from source is acyclic)

  • paths.algorithm.trivial: at worst \(O(nm)\) where \(n\) is the number of nodes and \(m\) is the out-degree of the word graph (only valid in some circumstances)

  • paths.algorithm.automatic: attempts to select the fastest algorithm of the preceding algorithms and then applies that.

Note

If libsemigroups is compiled with the flag --enable-eigen, then this function makes use of the Eigen library for linear algebra (see [GJ+10]).

Warning

If the number of paths exceeds 2 ** 64, then return value of this function will not be correct.

Warning

If lgrthm is paths.algorithm.automatic, then it is not always the case that the fastest algorithm is used.

paths.number_of_paths_algorithm(*args, **kwargs)

Overloaded function.

paths.number_of_paths_algorithm(wg: WordGraph, source: int) → paths.algorithm

Returns the paths.algorithm used by number_of_paths.

This function returns the algorithm that would be used by a call to number_of_paths with the same arguments.

Parameters:

  • wg (WordGraph) – the word graph.

  • source (int) – the source node.

Returns:

The algorithm.

Return type:

paths.algorithm

Complexity:

Constant.

paths.number_of_paths_algorithm(wg: WordGraph, source: int, min: int, max: int | PositiveInfinity) → paths.algorithm

Returns the paths.algorithm used by number_of_paths.

This function 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).

Parameters:

  • wg (WordGraph) – the word graph.

  • source (int) – the source node.

  • min (int) – the minimum length of paths to count.

  • max (int | PositiveInfinity) – the maximum length of paths to count.

Returns:

The algorithm.

Return type:

paths.algorithm

Complexity:

At worst \(O(nm)\) where \(n\) is the number of nodes and \(m\) is the out-degree of the word graph.

paths.number_of_paths_algorithm(wg: WordGraph, source: int, target: int, min: int, max: int | PositiveInfinity) → paths.algorithm

Returns the paths.algorithm used by number_of_paths.

This function 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).

Parameters:

  • wg (WordGraph) – the word graph.

  • source (int) – the source node.

  • target (int) – the target node.

  • min (int) – the minimum length of paths to count.

  • max (int | PositiveInfinity) – the maximum length of paths to count.

Returns:

The algorithm.

Return type:

paths.algorithm

Complexity:

At worst \(O(nm)\) where \(n\) is the number of nodes and \(m\) is the out-degree of the word graph.