Repository: networkx/networkx (python)

Issue:
`maximal_independent_set` returns a list

This is not a bug in a strict sense - the nodes in the list do comprise a maximal independent set - but it is strange (and arguably semantically inconsistent) to return a list of nodes instead of a set.

Though it'd technically be a breaking change, I think my vote would be to update the implementation to return a set instead of a list. If we wanted to be cautious, we could raise a FutureWarning; the downside is I can't think of a way to give a "do X to make this warning go away & future-proof your code" recipe, at least not without introducing new API (which I'm -1 on).

I'd be inclined to simply change it without a runtime warning.

**Context**

I ran into this while attempting to show that a mis returned by `maximal_independent_set` is (often) just one of many possible maximal independent sets; i.e.

```python
>>> G = nx.path_graph(4)
>>> G.add_edges_from([(1, 4), (2, 4)])  # Add a triangle
>>> mis = nx.maximal_independent_set(G)
>>> all_mis = {
...     frozenset(c)
...     for c in nx.enumerate_all_cliques(nx.complement(G))
...     if len(c) > 1
... }
>>> mis in all_mis  # this is where I ran into the issue
Traceback (most recent call last)
   ...
TypeError: cannot use 'list' as a set element (unhashable type: 'list')
>>> set(mis) in all_mis  # What I was expecting
True



Patch:
diff --git a/networkx/algorithms/mis.py b/networkx/algorithms/mis.py
index 1bf5b0a462b..d6d9cc0147b 100644
--- a/networkx/algorithms/mis.py
+++ b/networkx/algorithms/mis.py
@@ -35,8 +35,8 @@ def maximal_independent_set(G, nodes=None, seed=None):
 
     Returns
     -------
-    indep_nodes : list
-       List of nodes that are part of a maximal independent set.
+    indep_nodes : set
+       Set of nodes that are part of a maximal independent set.
 
     Raises
     ------
@@ -106,10 +106,10 @@ def maximal_independent_set(G, nodes=None, seed=None):
     neighbors = set.union(*[set(G.adj[v]) for v in nodes])
     if set.intersection(neighbors, nodes):
         raise nx.NetworkXUnfeasible(f"{nodes} is not an independent set of G")
-    indep_nodes = list(nodes)
+    indep_nodes = set(nodes)
     available_nodes = set(G.nodes()).difference(neighbors.union(nodes))
     while available_nodes:
         node = seed.choice(list(available_nodes))
-        indep_nodes.append(node)
+        indep_nodes.add(node)
         available_nodes.difference_update(list(G.adj[node]) + [node])
     return indep_nodes


Test patch:
diff --git a/networkx/algorithms/tests/test_mis.py b/networkx/algorithms/tests/test_mis.py
index 02be02d4c33..5a7b67ac7a8 100644
--- a/networkx/algorithms/tests/test_mis.py
+++ b/networkx/algorithms/tests/test_mis.py
@@ -12,13 +12,13 @@
 
 def test_random_seed():
     G = nx.empty_graph(5)
-    assert nx.maximal_independent_set(G, seed=1) == [1, 0, 3, 2, 4]
+    assert nx.maximal_independent_set(G, seed=1) == {1, 0, 3, 2, 4}
 
 
 @pytest.mark.parametrize("graph", [nx.complete_graph(5), nx.complete_graph(55)])
 def test_K5(graph):
     """Maximal independent set for complete graphs"""
-    assert all(nx.maximal_independent_set(graph, [n]) == [n] for n in graph)
+    assert all(nx.maximal_independent_set(graph, [n]) == {n} for n in graph)
 
 
 def test_exceptions():