Fix fast_gnp_random_graph for directed graphs (issue #3389) (#5077)

* Fix fast_gnp_random_graph for directed graphs (issue #3389)

* Test that G(n,p) graphs are generated with correct edge probabilities

* Simplify fast_gnp_random_graph(..., directed=True)

When generating directed graphs, use the standard algorithm for undirected graphs,
then do the same thing with edges from w to v.

* Test all gnp generators, rather than just one generator four times

* Run black on test_random_graphs.py

2 files changed, 35 insertions, 18 deletions

diff --git a/networkx/generators/random_graphs.py b/networkx/generators/random_graphs.py
index 4a658f8f..d187023d 100644
--- a/networkx/generators/random_graphs.py
+++ b/networkx/generators/random_graphs.py
@@ -78,28 +78,12 @@ def fast_gnp_random_graph(n, p, seed=None, directed=False):
     if p <= 0 or p >= 1:
         return nx.gnp_random_graph(n, p, seed=seed, directed=directed)
 
-    w = -1
     lp = math.log(1.0 - p)
 
     if directed:
         G = nx.DiGraph(G)
-        # Nodes in graph are from 0,n-1 (start with v as the first node index).
-        v = 0
-        while v < n:
-            lr = math.log(1.0 - seed.random())
-            w = w + 1 + int(lr / lp)
-            if v == w:  # avoid self loops
-                w = w + 1
-            while v < n <= w:
-                w = w - n
-                v = v + 1
-                if v == w:  # avoid self loops
-                    w = w + 1
-            if v < n:
-                G.add_edge(v, w)
-    else:
-        # Nodes in graph are from 0,n-1 (start with v as the second node index).
         v = 1
+        w = -1
         while v < n:
             lr = math.log(1.0 - seed.random())
             w = w + 1 + int(lr / lp)
@@ -107,7 +91,19 @@ def fast_gnp_random_graph(n, p, seed=None, directed=False):
                 w = w - v
                 v = v + 1
             if v < n:
-                G.add_edge(v, w)
+                G.add_edge(w, v)
+
+    # Nodes in graph are from 0,n-1 (start with v as the second node index).
+    v = 1
+    w = -1
+    while v < n:
+        lr = math.log(1.0 - seed.random())
+        w = w + 1 + int(lr / lp)
+        while w >= v and v < n:
+            w = w - v
+            v = v + 1
+        if v < n:
+            G.add_edge(v, w)
     return G
 
 
diff --git a/networkx/generators/tests/test_random_graphs.py b/networkx/generators/tests/test_random_graphs.py
index d0068cd6..95c5dac3 100644
--- a/networkx/generators/tests/test_random_graphs.py
+++ b/networkx/generators/tests/test_random_graphs.py
@@ -247,6 +247,27 @@ class TestGeneratorsRandom:
                 edges += sum(1 for _ in generator(10, 0.99999, directed=True).edges())
             assert abs(edges / float(runs) - 90) <= runs * 2.0 / 100
 
+            # assert that edges are generated with correct probability
+            runs = 5000
+            n = 5
+            for p in [0.2, 0.8]:
+                for directed in [False, True]:
+                    edge_counts = [[0] * 5 for row in range(5)]
+                    for i in range(runs):
+                        G = generator(n, p, directed=directed)
+                        for (v, w) in G.edges:
+                            edge_counts[v][w] += 1
+                            if not directed:
+                                edge_counts[w][v] += 1
+                    for v in range(n):
+                        for w in range(n):
+                            if v == w:
+                                # There should be no loops
+                                assert edge_counts[v][w] == 0
+                            else:
+                                # Each edge should have been generated with probability close to p
+                                assert abs(edge_counts[v][w] / float(runs) - p) <= 0.03
+
     def test_gnm(self):
         G = nx.gnm_random_graph(10, 3)
         assert len(G) == 10