Repository: networkx/networkx
Pull request: Remove instances of random.sample from sets (deprecated in Python 3.9)
Closes #4555

I took a conservative approach and used `sorted` to convert sets to lists. This may cause a performance hit, but I figured this was safer from the perspective of reproducibility, though I'm not sure it's necessary. In some circumstances it may be sufficient to simply convert to `list` directly.

Problem statement:
Random sampling from set has been deprecated in Python 3.9
Python 3.9 has deprecated calling `random.sample` on sets, so users will now see a warning if they do something like:

```python
>>> import networkx as nx
>>> G = nx.path_graph(25)
>>> import random
>>> random.sample(G.nodes(), k=3)
DeprecationWarning: Sampling from a set deprecated
since Python 3.9 and will be removed in a subsequent version.
[15, 1, 2]
```

It doesn't look like this will have an affect on `PythonRandomInterface`, but there are a few instances of the `sample(G.nodes(), **kwargs)` in the test suite which should be fixed.

Hints from issue discussion:
Looks like it can also raise a TypeError with input `G`. The suggested fix is `sorted(G)`.

```
>>> random.sample(G, k=3)
TypeError: Population must be a sequence.  For dicts or sets, use sorted(d).
```

Commit message: add sorted to random.sample in internet_as_graphs.

Patch to review:
diff --git a/networkx/algorithms/approximation/tests/test_maxcut.py b/networkx/algorithms/approximation/tests/test_maxcut.py
index 897d25594cc..ec75b59f178 100644
--- a/networkx/algorithms/approximation/tests/test_maxcut.py
+++ b/networkx/algorithms/approximation/tests/test_maxcut.py
@@ -39,7 +39,7 @@ def test_one_exchange_basic():
     for (u, v, w) in G.edges(data=True):
         w["weight"] = random.randrange(-100, 100, 1) / 10
 
-    initial_cut = set(random.sample(G.nodes(), k=5))
+    initial_cut = set(random.sample(sorted(G.nodes()), k=5))
     cut_size, (set1, set2) = maxcut.one_exchange(
         G, initial_cut, weight="weight", seed=5
     )
@@ -71,7 +71,7 @@ def test_negative_weights():
     for (u, v, w) in G.edges(data=True):
         w["weight"] = -1 * random.random()
 
-    initial_cut = set(random.sample(G.nodes(), k=5))
+    initial_cut = set(random.sample(sorted(G.nodes()), k=5))
     cut_size, (set1, set2) = maxcut.one_exchange(G, initial_cut, weight="weight")
 
     # make sure it is a valid cut
diff --git a/networkx/algorithms/centrality/betweenness.py b/networkx/algorithms/centrality/betweenness.py
index 87a843f047d..ca4e0c01a07 100644
--- a/networkx/algorithms/centrality/betweenness.py
+++ b/networkx/algorithms/centrality/betweenness.py
@@ -120,7 +120,7 @@ def betweenness_centrality(
     if k is None:
         nodes = G
     else:
-        nodes = seed.sample(G.nodes(), k)
+        nodes = seed.sample(sorted(G.nodes()), k)
     for s in nodes:
         # single source shortest paths
         if weight is None:  # use BFS
diff --git a/networkx/algorithms/tests/test_triads.py b/networkx/algorithms/tests/test_triads.py
index e0e45dfe196..a57b11af745 100644
--- a/networkx/algorithms/tests/test_triads.py
+++ b/networkx/algorithms/tests/test_triads.py
@@ -36,7 +36,7 @@ def test_is_triad():
     G = nx.karate_club_graph()
     G = G.to_directed()
     for i in range(100):
-        nodes = sample(G.nodes(), 3)
+        nodes = sample(sorted(G.nodes()), 3)
         G2 = G.subgraph(nodes)
         assert nx.is_triad(G2)
 
diff --git a/networkx/algorithms/triads.py b/networkx/algorithms/triads.py
index 8269b3f7d1d..29b1130ce5f 100644
--- a/networkx/algorithms/triads.py
+++ b/networkx/algorithms/triads.py
@@ -395,7 +395,7 @@ def random_triad(G):
     G2 : subgraph
        A randomly selected triad (order-3 NetworkX DiGraph)
     """
-    nodes = sample(G.nodes(), 3)
+    nodes = sample(sorted(G.nodes()), 3)
     G2 = G.subgraph(nodes)
     return G2
 
diff --git a/networkx/generators/directed.py b/networkx/generators/directed.py
index 0e6009b5732..86929d665f9 100644
--- a/networkx/generators/directed.py
+++ b/networkx/generators/directed.py
@@ -367,7 +367,7 @@ def sample(v, nodes):
         def sample(v, nodes):
             if not self_loops:
                 nodes = nodes - {v}
-            return seed.sample(nodes, k)
+            return seed.sample(sorted(nodes), k)
 
     G = nx.empty_graph(n, create_using)
     nodes = set(G)
diff --git a/networkx/generators/internet_as_graphs.py b/networkx/generators/internet_as_graphs.py
index 2c93ab0e9d9..1df72af0d4a 100644
--- a/networkx/generators/internet_as_graphs.py
+++ b/networkx/generators/internet_as_graphs.py
@@ -308,7 +308,7 @@ def add_cp_peering_link(self, cp, to_kind):
                 node_options.remove(j)
 
         if len(node_options) > 0:
-            j = self.seed.sample(node_options, 1)[0]
+            j = self.seed.sample(sorted(node_options), 1)[0]
             self.add_edge(cp, j, "peer")
             self.G.nodes[cp]["peers"] += 1
             self.G.nodes[j]["peers"] += 1


Code review comments:
diff_hunk: @@ -120,7 +120,7 @@ def betweenness_centrality(
     if k is None:
         nodes = G
     else:
-        nodes = seed.sample(G.nodes(), k)
+        nodes = seed.sample(sorted(G.nodes()), k)
path: networkx/algorithms/centrality/betweenness.py
text: @user1:
Unfortunately, nodes are not sortable in general.Using `sorted` should be fine in tests where we know what the nodes are, but in the package code itself we should use `list`.

@author:
Yup this was an oversight on my part - should be fixed in 2e2a63e.