Repository: networkx/networkx

Issue:
all_node_cuts returns too few and incorrect cuts.
This could be a documentation issue, a bug or a user understanding issue. Are these cases pathological for the algorithm?

Given a square graph:

     a -- b
     |    |
     c -- d

Based on a cursory reading of the documentation, I would have expected all_node_cuts() to return:

    [{'a','d'}, {'c','b'}]

I get `[{'a','c'}]` but if this is a valid node cut then surely {a,b}, {b,d}, {c,d} are also equally valid and a function called "all node cuts" should return them. 

    G = nx.Graph([('a','b'), ('a','c'), ('c','d'), ('b','d')])
    print( G.nodes() )
    print( G.edges() )
    print( list(nx.all_node_cuts(G)) )

    >>> ['a', 'c', 'b', 'd']
    >>> [('a', 'c'), ('a', 'b'), ('c', 'd'), ('b', 'd')]
    >>> [{'a', 'c'}]

Expanding to a hexagon, we see similar pattern of node cuts. There are many isometric node cuts omitted from the results list. Two of the proposed cuts fail to create "two or more connected components" as the documentation suggests.

    G = nx.Graph([('a','b'), ('b','c'), ('c','d'),('d','e'), ('e','f'),('f','a')])
    list(nx.all_node_cuts(G))
    >>> [{'a', 'c'}, {'a', 'b'}, {'b', 'c'}]


Discussion:

Patch:
diff --git a/networkx/algorithms/connectivity/kcutsets.py b/networkx/algorithms/connectivity/kcutsets.py
index 2ad8bdfb4..c3457139a 100644
--- a/networkx/algorithms/connectivity/kcutsets.py
+++ b/networkx/algorithms/connectivity/kcutsets.py
@@ -3,6 +3,7 @@
 Kanevsky all minimum node k cutsets algorithm.
 """
 from operator import itemgetter
+from itertools import combinations
 
 import networkx as nx
 from .utils import build_auxiliary_node_connectivity
@@ -86,6 +87,22 @@ def all_node_cuts(G, k=None, flow_func=None):
     if not nx.is_connected(G):
         raise nx.NetworkXError('Input graph is disconnected.')
 
+    # Addess some corner cases first.
+    # For cycle graphs
+    if G.order() == G.size():
+        if all(2 == d for n, d in G.degree()):
+            seen = set()
+            for u in G:
+                for v in nx.non_neighbors(G, u):
+                    if (u, v) not in seen and (v, u) not in seen:
+                        yield {v, u}
+                        seen.add((v, u))
+            return
+    # For complete Graphs
+    if nx.density(G) == 1:
+        for cut_set in combinations(G, len(G)-1):
+            yield set(cut_set)
+        return
     # Initialize data structures.
     # Keep track of the cuts already computed so we do not repeat them.
     seen = []


Test patch:
diff --git a/networkx/algorithms/connectivity/tests/test_kcutsets.py b/networkx/algorithms/connectivity/tests/test_kcutsets.py
index e11547faf..9ca49698a 100644
--- a/networkx/algorithms/connectivity/tests/test_kcutsets.py
+++ b/networkx/algorithms/connectivity/tests/test_kcutsets.py
@@ -241,3 +241,27 @@ def test_non_repeated_cuts():
     assert_true(len(solution) == len(cuts))
     for cut in cuts:
         assert_true(cut in solution)
+
+
+def test_cycle_graph():
+    G = nx.cycle_graph(5)
+    solution = [{0, 2}, {0, 3}, {1, 3}, {1, 4}, {2, 4}]
+    cuts = list(nx.all_node_cuts(G))
+    assert_true(len(solution) == len(cuts))
+    for cut in cuts:
+        assert_true(cut in solution)
+
+
+def test_complete_graph():
+    G = nx.complete_graph(5)
+    solution = [
+        {0, 1, 2, 3},
+        {0, 1, 2, 4},
+        {0, 1, 3, 4},
+        {0, 2, 3, 4},
+        {1, 2, 3, 4},
+    ]
+    cuts = list(nx.all_node_cuts(G))
+    assert_true(len(solution) == len(cuts))
+    for cut in cuts:
+        assert_true(cut in solution)