random_acyclic

ActionDigraph libsemigroups::ActionDigraph::random_acyclic(T const nr_nodes, T const out_degree, T const nr_edges, std::mt19937 mt = std::mt19937(std::random_device()()))

Constructs a random acyclic ActionDigraph from mt with the specified number of nodes and edges, and out-degree.

Complexity

At least \(O(mn)\) where m is the number of nodes, and n is the out-degree of the digraph.

Parameters

• nr_nodes: the number of nodes

• out_degree: the out-degree of every node

• nr_edges: the out-degree of every node

• mt: a std::mt19937 used as a random source (defaults to: std::mt19937(std::random_device()()))

Exceptions

• LibsemigroupsException: if any of the following hold:

  • nr_nodes is less than 2

  • out_degree is less than 2

  • nr_edges exceeds the product of nr_nodes and out_degree

  • nr_edges exceeds the product of nr_nodes and nr_nodes - 1 divided by 2.