Repository: networkx/networkx

Issue:
Wrong random_lobster implementation?
Hi, it seems that [networkx.random_lobster's implementation logic](https://github.com/networkx/networkx/blob/4e9771f04192e94a5cbdd71249a983d124a56593/networkx/generators/random_graphs.py#L1009) is not aligned with the common definition as given in [wolfram mathworld](http://mathworld.wolfram.com/LobsterGraph.html) or [Wikipedia](https://en.wikipedia.org/wiki/List_of_graphs#Lobster).
For example, it can not produce the simplest lobster graph examples such as ![lobster_example](https://www.researchgate.net/profile/Dr_Nasreen_Khan/publication/256292297/figure/fig5/AS:669566174756876@1536648424468/A-diameter-2-lobster-graph.png).

Discussion:
pep8speaks: Hello @austinorr! Thanks for opening this PR. We checked the lines you've touched for [PEP 8](https://www.python.org/dev/peps/pep-0008) issues, and found:

* In the file [`networkx/generators/random_graphs.py`](https://github.com/networkx/networkx/blob/144bd8e935c69c177b0a86d1e9dd94570829d056/networkx/generators/random_graphs.py):

> [Line 1021:11](https://github.com/networkx/networkx/blob/144bd8e935c69c177b0a86d1e9dd94570829d056/networkx/generators/random_graphs.py#L1021): [E211](https://duckduckgo.com/?q=pep8%20E211) whitespace before '('
> [Line 1023:1](https://github.com/networkx/networkx/blob/144bd8e935c69c177b0a86d1e9dd94570829d056/networkx/generators/random_graphs.py#L1023): [W293](https://duckduckgo.com/?q=pep8%20W293) blank line contains whitespace

* In the file [`networkx/generators/tests/test_random_graphs.py`](https://github.com/networkx/networkx/blob/144bd8e935c69c177b0a86d1e9dd94570829d056/networkx/generators/tests/test_random_graphs.py):

> [Line 96:79](https://github.com/networkx/networkx/blob/144bd8e935c69c177b0a86d1e9dd94570829d056/networkx/generators/tests/test_random_graphs.py#L96): [W291](https://duckduckgo.com/?q=pep8%20W291) trailing whitespace
> [Line 100:54](https://github.com/networkx/networkx/blob/144bd8e935c69c177b0a86d1e9dd94570829d056/networkx/generators/tests/test_random_graphs.py#L100): [E225](https://duckduckgo.com/?q=pep8%20E225) missing whitespace around operator
> [Line 109:80](https://github.com/networkx/networkx/blob/144bd8e935c69c177b0a86d1e9dd94570829d056/networkx/generators/tests/test_random_graphs.py#L109): [W291](https://duckduckgo.com/?q=pep8%20W291) trailing whitespace
> [Line 120:1](https://github.com/networkx/networkx/blob/144bd8e935c69c177b0a86d1e9dd94570829d056/networkx/generators/tests/test_random_graphs.py#L120): [W293](https://duckduckgo.com/?q=pep8%20W293) blank line contains whitespace
> [Line 121:47](https://github.com/networkx/networkx/blob/144bd8e935c69c177b0a86d1e9dd94570829d056/networkx/generators/tests/test_random_graphs.py#L121): [E261](https://duckduckgo.com/?q=pep8%20E261) at least two spaces before inline comment
> [Line 121:89](https://github.com/networkx/networkx/blob/144bd8e935c69c177b0a86d1e9dd94570829d056/networkx/generators/tests/test_random_graphs.py#L121): [E501](https://duckduckgo.com/?q=pep8%20E501) line too long (92 > 88 characters)


dschult: Could you add a line or two to the docs saying that this method doesn't select uniformly randomly from all possible lobsters. And maybe some language that p1 and p2 are used repeatedly until failure to add an edge which stops that branch of the process. Then @silent567 should be happy with this too.
austinorr: Yep, good idea, I’ll push an edit shortly. You’re hoping to document this entirely within the function docstring right?
dschult: I was thinking of just within the docstring for that function yes. Open to other ideas, but that seems the most simple.

austinorr: Ok great. While I’m in there, any interest in the `is_caterpillar` or the `is_lobster` functions in the tests? Should they stay inside the test scope, or be moved to a reusable utility module?
austinorr: @dschult docstring changes are ready to review.
dschult: Thanks! This looks good.  

As for the ```is_lobster``` functions, they could be moved to a module in the algorithms section of the code. But I think that only makes sense if someone implements more algorithms for lobsters and caterpillars. But I must say I don't know much about the literature on this topic. 

Let's commit it as is and then open a new PR if other algorithms are desirable.
Thanks!!

Patch:
diff --git a/networkx/generators/random_graphs.py b/networkx/generators/random_graphs.py
index e4f2c569d..745f64e4d 100644
--- a/networkx/generators/random_graphs.py
+++ b/networkx/generators/random_graphs.py
@@ -1000,6 +1000,11 @@ def random_lobster(n, p1, p2, seed=None):
     leaf nodes. A caterpillar is a tree that reduces to a path graph
     when pruning all leaf nodes; setting `p2` to zero produces a caterpillar.
 
+    This implementation iterates on the probabilities `p1` and `p2` to add
+    edges at levels 1 and 2, respectively. Graphs are therefore constructed
+    iteratively with uniform randomness at each level rather than being selected
+    uniformly at random from the set of all possible lobsters.
+
     Parameters
     ----------
     n : int
@@ -1011,19 +1016,29 @@ def random_lobster(n, p1, p2, seed=None):
     seed : integer, random_state, or None (default)
         Indicator of random number generation state.
         See :ref:`Randomness<randomness>`.
+
+    Raises
+    ------
+    NetworkXError
+        If `p1` or `p2` parameters are >= 1 because the while loops would never finish.
     """
+    p1, p2 = abs(p1), abs(p2)
+    if any([p >= 1 for p in [p1, p2]]):
+        raise nx.NetworkXError("Probability values for `p1` and `p2` must both be < 1.")
+
     # a necessary ingredient in any self-respecting graph library
     llen = int(2 * seed.random() * n + 0.5)
     L = path_graph(llen)
     # build caterpillar: add edges to path graph with probability p1
     current_node = llen - 1
     for n in range(llen):
-        if seed.random() < p1:  # add fuzzy caterpillar parts
+        while seed.random() < p1:  # add fuzzy caterpillar parts
             current_node += 1
             L.add_edge(n, current_node)
-            if seed.random() < p2:  # add crunchy lobster bits
+            cat_node = current_node
+            while seed.random() < p2:  # add crunchy lobster bits
                 current_node += 1
-                L.add_edge(current_node - 1, current_node)
+                L.add_edge(cat_node, current_node)
     return L  # voila, un lobster!
 
 


Test patch:
diff --git a/networkx/generators/tests/test_random_graphs.py b/networkx/generators/tests/test_random_graphs.py
index f958dceab..8f2d68415 100644
--- a/networkx/generators/tests/test_random_graphs.py
+++ b/networkx/generators/tests/test_random_graphs.py
@@ -91,7 +91,38 @@ class TestGeneratorsRandom:
         constructor = [(10, 20, 0.8), (20, 40, 0.8)]
         G = random_shell_graph(constructor, seed)
 
+        def is_caterpillar(g):
+            """
+            A tree is a caterpillar iff all nodes of degree >=3 are surrounded
+            by at most two nodes of degree two or greater.
+            ref: http://mathworld.wolfram.com/CaterpillarGraph.html
+            """
+            deg_over_3 = [n for n in g if g.degree(n) >= 3]
+            for n in deg_over_3:
+                nbh_deg_over_2 = [nbh for nbh in g.neighbors(n) if g.degree(nbh) >= 2]
+                if not len(nbh_deg_over_2) <= 2:
+                    return False
+            return True
+
+        def is_lobster(g):
+            """
+            A tree is a lobster if it has the property that the removal of leaf
+            nodes leaves a caterpillar graph (Gallian 2007)
+            ref: http://mathworld.wolfram.com/LobsterGraph.html
+            """
+            non_leafs = [n for n in g if g.degree(n) > 1]
+            return is_caterpillar(g.subgraph(non_leafs))
+
         G = random_lobster(10, 0.1, 0.5, seed)
+        assert max([G.degree(n) for n in G.nodes()]) > 3
+        assert is_lobster(G)
+        pytest.raises(NetworkXError, random_lobster, 10, 0.1, 1, seed)
+        pytest.raises(NetworkXError, random_lobster, 10, 1, 1, seed)
+        pytest.raises(NetworkXError, random_lobster, 10, 1, 0.5, seed)
+
+        # docstring says this should be a caterpillar
+        G = random_lobster(10, 0.1, 0.0, seed)
+        assert is_caterpillar(G)
 
         # difficult to find seed that requires few tries
         seq = random_powerlaw_tree_sequence(10, 3, seed=14, tries=1)