Note

This is the documentation for the current state of the development branch of rustworkx. The documentation or APIs here can change prior to being released.

rustworkx.undirected_gnp_random_graph#

undirected_gnp_random_graph(num_nodes, probability, /, seed=None)#

Return a \(G_{np}\) random undirected graph, also known as an Erdős-Rényi graph or a binomial graph.

For number of nodes \(n\) and probability \(p\), the \(G_{n,p}\) graph algorithm creates \(n\) nodes, and for all the \(n (n - 1)/2\) possible edges, each edge is created independently with probability \(p\). In general, for any probability \(p\), the expected number of edges returned is \(m = p n (n - 1)/2\). If \(p = 0\) or \(p = 1\), the returned graph is not random and will always be an empty or a complete graph respectively. An empty graph has zero edges and a complete undirected graph has \(n (n - 1)/2\) edges. The run time is \(O(n + m)\) where \(m\) is the expected number of edges mentioned above. When \(p = 0\), run time always reduces to \(O(n)\), as the lower bound. When \(p = 1\), run time always goes to \(O(n + n (n - 1)/2)\), as the upper bound. For other probabilities, this algorithm [1] runs in \(O(n + m)\) time.

For \(0 < p < 1\), the algorithm is based on the implementation of the networkx function fast_gnp_random_graph [2]

Parameters:
  • num_nodes (int) – The number of nodes to create in the graph

  • probability (float) – The probability of creating an edge between two nodes

  • seed (int) – An optional seed to use for the random number generator

Returns:

A PyGraph object

Return type:

PyGraph