Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

retworkx random G(n,p) does not accept exact 0 and 1 probabilities #172

Closed
MoAllabbad opened this issue Oct 16, 2020 · 2 comments · Fixed by #174
Closed

retworkx random G(n,p) does not accept exact 0 and 1 probabilities #172

MoAllabbad opened this issue Oct 16, 2020 · 2 comments · Fixed by #174
Assignees
@MoAllabbad
Labels
bug Something isn't working

Comments

@MoAllabbad
Copy link
Contributor

MoAllabbad commented Oct 16, 2020 •
edited

Information

  • retworkx version: 0.6.0
  • Python version: 3.8.3
  • Rust version: 1.47
  • Operating system: Arch Linux

What is the current behavior?

Calling either undirected_gnp_random_graph(num_nodes, probability) or directed_gnp_random_graph(num_nodes, probability) for probability= 0 or 1 throws an error.

What is the expected behavior?

The expected behavior is to match that of networkx, where passing 0 for the probability returns an empty graph and passing 1 for the probability returns a full graph

Steps to reproduce the problem

Call either retworkx.undirected_gnp_random_graph(n,p) or retworkx.directed_gnp_random_graph(n,p) with p=0 or p=1.
@MoAllabbad MoAllabbad added the bug Something isn't working label Oct 16, 2020
@MoAllabbad
Copy link
Contributor Author

I am working on this!

@MoAllabbad MoAllabbad mentioned this issue Oct 16, 2020
Closed
@MoAllabbad
Copy link
Contributor Author

I found another potential issue while trying to add to the gnp docs. The docs for both directed_gnp and undirected_gnp say:

This algorithm 1 runs in O(n+m) time, where m is the expected number of edges, which equals pn(n−1)/2.

But I don't think that m is correct for directed_gnp, only for undirected_gnp, as it also says in the directed_gnp docs that:

The Gn,p graph algorithm chooses each of the n(n−1) possible edges with probability p.

@MoAllabbad MoAllabbad mentioned this issue Oct 18, 2020
Merged
mtreinish pushed a commit that referenced this issue Oct 18, 2020
@MoAllabbad
Change G(n,p) to accept exact 0 or 1 probabilities (#174)
7db288c 
When p=0, we'll have an empty graph with n nodes and zero edges.
When p=1, we'll have a complete graph with n n(n-1) edges
for directed graphs and n(n-1)/2 edges for undirected graphs.
The time complexity stays the same. Let m be the max number of edges,
then run time is O(n+p*m), which reduces to O(n) when p=0 and, when
p=1 becomes O(n+n(n-1)) = O(n^2).

Fixes #172
@MoAllabbad MoAllabbad changed the title Change retworkx random G_n,p to accept exact 0 and 1 probabilities retworkx random G(n,p) does not accept exact 0 and 1 probabilities Nov 9, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@MoAllabbad MoAllabbad

Labels
bug Something isn't working
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Change G(n,p) to accept exact 0 or 1 probabilities MoAllabbad/retworkx
1 participant
@MoAllabbad