number_of_paths(node_type const, size_t const, size_t const, algorithm const) constΒΆ

uint64_t libsemigroups::ActionDigraph::number_of_paths(node_type const source, size_t const min, size_t const max, algorithm const lgrthm = algorithm::automatic) const

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

Return

A value of type uint64_t.

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

Exceptions
  • LibsemigroupsException: if:

    • source is not a node in the digraph.

    • the algorithm specified by lgrthm is not applicable.