We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
all_node_cuts returns incorrect cuts
The function `all_node_cuts` returns node cut-sets for the K2 (complete graph with two nodes), but there exist no.

### Current Behavior

Consider the following graph, consisting of two nodes connected by an edge:
```python
graph = nx.Graph()
graph.add_edge(1,2)
list(all_node_cuts(graph)
>>> [{1}, {2}]
```
This graph has no node cut-sets because removing any vertex does not increase the number of connected components

### Expected Behavior

Return no node cut-sets:
```python
graph = nx.Graph()
graph.add_edge(1,2)
list(all_node_cuts(graph)
>>> []
```

### Steps to Reproduce

The above example

### Environment

Python version: 3.10.10
NetworkX version: 2.6.3


--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `networkx/algorithms/connectivity/kcutsets.py`
Content:
```
1 """
2 Kanevsky all minimum node k cutsets algorithm.
3 """
4 import copy
5 from collections import defaultdict
6 from itertools import combinations
7 from operator import itemgetter
8 
9 import networkx as nx
10 from networkx.algorithms.flow import (
11     build_residual_network,
12     edmonds_karp,
13     shortest_augmenting_path,
14 )
15 
16 from .utils import build_auxiliary_node_connectivity
17 
18 default_flow_func = edmonds_karp
19 
20 
21 __all__ = ["all_node_cuts"]
22 
23 
24 def all_node_cuts(G, k=None, flow_func=None):
25     r"""Returns all minimum k cutsets of an undirected graph G.
26 
27     This implementation is based on Kanevsky's algorithm [1]_ for finding all
28     minimum-size node cut-sets of an undirected graph G; ie the set (or sets)
29     of nodes of cardinality equal to the node connectivity of G. Thus if
30     removed, would break G into two or more connected components.
31 
32     Parameters
33     ----------
34     G : NetworkX graph
35         Undirected graph
36 
37     k : Integer
38         Node connectivity of the input graph. If k is None, then it is
39         computed. Default value: None.
40 
41     flow_func : function
42         Function to perform the underlying flow computations. Default value is
43         :func:`~networkx.algorithms.flow.edmonds_karp`. This function performs
44         better in sparse graphs with right tailed degree distributions.
45         :func:`~networkx.algorithms.flow.shortest_augmenting_path` will
46         perform better in denser graphs.
47 
48 
49     Returns
50     -------
51     cuts : a generator of node cutsets
52         Each node cutset has cardinality equal to the node connectivity of
53         the input graph.
54 
55     Examples
56     --------
57     >>> # A two-dimensional grid graph has 4 cutsets of cardinality 2
58     >>> G = nx.grid_2d_graph(5, 5)
59     >>> cutsets = list(nx.all_node_cuts(G))
60     >>> len(cutsets)
61     4
62     >>> all(2 == len(cutset) for cutset in cutsets)
63     True
64     >>> nx.node_connectivity(G)
65     2
66 
67     Notes
68     -----
69     This implementation is based on the sequential algorithm for finding all
70     minimum-size separating vertex sets in a graph [1]_. The main idea is to
71     compute minimum cuts using local maximum flow computations among a set
72     of nodes of highest degree and all other non-adjacent nodes in the Graph.
73     Once we find a minimum cut, we add an edge between the high degree
74     node and the target node of the local maximum flow computation to make
75     sure that we will not find that minimum cut again.
76 
77     See also
78     --------
79     node_connectivity
80     edmonds_karp
81     shortest_augmenting_path
82 
83     References
84     ----------
85     .. [1]  Kanevsky, A. (1993). Finding all minimum-size separating vertex
86             sets in a graph. Networks 23(6), 533--541.
87             http://onlinelibrary.wiley.com/doi/10.1002/net.3230230604/abstract
88 
89     """
90     if not nx.is_connected(G):
91         raise nx.NetworkXError("Input graph is disconnected.")
92 
93     # Address some corner cases first.
94     # For complete Graphs
95     if nx.density(G) == 1:
96         for cut_set in combinations(G, len(G) - 1):
97             yield set(cut_set)
98         return
99     # Initialize data structures.
100     # Keep track of the cuts already computed so we do not repeat them.
101     seen = []
102     # Even-Tarjan reduction is what we call auxiliary digraph
103     # for node connectivity.
104     H = build_auxiliary_node_connectivity(G)
105     H_nodes = H.nodes  # for speed
106     mapping = H.graph["mapping"]
107     # Keep a copy of original predecessors, H will be modified later.
108     # Shallow copy is enough.
109     original_H_pred = copy.copy(H._pred)
110     R = build_residual_network(H, "capacity")
111     kwargs = {"capacity": "capacity", "residual": R}
112     # Define default flow function
113     if flow_func is None:
114         flow_func = default_flow_func
115     if flow_func is shortest_augmenting_path:
116         kwargs["two_phase"] = True
117     # Begin the actual algorithm
118     # step 1: Find node connectivity k of G
119     if k is None:
120         k = nx.node_connectivity(G, flow_func=flow_func)
121     # step 2:
122     # Find k nodes with top degree, call it X:
123     X = {n for n, d in sorted(G.degree(), key=itemgetter(1), reverse=True)[:k]}
124     # Check if X is a k-node-cutset
125     if _is_separating_set(G, X):
126         seen.append(X)
127         yield X
128 
129     for x in X:
130         # step 3: Compute local connectivity flow of x with all other
131         # non adjacent nodes in G
132         non_adjacent = set(G) - X - set(G[x])
133         for v in non_adjacent:
134             # step 4: compute maximum flow in an Even-Tarjan reduction H of G
135             # and step 5: build the associated residual network R
136             R = flow_func(H, f"{mapping[x]}B", f"{mapping[v]}A", **kwargs)
137             flow_value = R.graph["flow_value"]
138 
139             if flow_value == k:
140                 # Find the nodes incident to the flow.
141                 E1 = flowed_edges = [
142                     (u, w) for (u, w, d) in R.edges(data=True) if d["flow"] != 0
143                 ]
144                 VE1 = incident_nodes = {n for edge in E1 for n in edge}
145                 # Remove saturated edges form the residual network.
146                 # Note that reversed edges are introduced with capacity 0
147                 # in the residual graph and they need to be removed too.
148                 saturated_edges = [
149                     (u, w, d)
150                     for (u, w, d) in R.edges(data=True)
151                     if d["capacity"] == d["flow"] or d["capacity"] == 0
152                 ]
153                 R.remove_edges_from(saturated_edges)
154                 R_closure = nx.transitive_closure(R)
155                 # step 6: shrink the strongly connected components of
156                 # residual flow network R and call it L.
157                 L = nx.condensation(R)
158                 cmap = L.graph["mapping"]
159                 inv_cmap = defaultdict(list)
160                 for n, scc in cmap.items():
161                     inv_cmap[scc].append(n)
162                 # Find the incident nodes in the condensed graph.
163                 VE1 = {cmap[n] for n in VE1}
164                 # step 7: Compute all antichains of L;
165                 # they map to closed sets in H.
166                 # Any edge in H that links a closed set is part of a cutset.
167                 for antichain in nx.antichains(L):
168                     # Only antichains that are subsets of incident nodes counts.
169                     # Lemma 8 in reference.
170                     if not set(antichain).issubset(VE1):
171                         continue
172                     # Nodes in an antichain of the condensation graph of
173                     # the residual network map to a closed set of nodes that
174                     # define a node partition of the auxiliary digraph H
175                     # through taking all of antichain's predecessors in the
176                     # transitive closure.
177                     S = set()
178                     for scc in antichain:
179                         S.update(inv_cmap[scc])
180                     S_ancestors = set()
181                     for n in S:
182                         S_ancestors.update(R_closure._pred[n])
183                     S.update(S_ancestors)
184                     if f"{mapping[x]}B" not in S or f"{mapping[v]}A" in S:
185                         continue
186                     # Find the cutset that links the node partition (S,~S) in H
187                     cutset = set()
188                     for u in S:
189                         cutset.update((u, w) for w in original_H_pred[u] if w not in S)
190                     # The edges in H that form the cutset are internal edges
191                     # (ie edges that represent a node of the original graph G)
192                     if any(H_nodes[u]["id"] != H_nodes[w]["id"] for u, w in cutset):
193                         continue
194                     node_cut = {H_nodes[u]["id"] for u, _ in cutset}
195 
196                     if len(node_cut) == k:
197                         # The cut is invalid if it includes internal edges of
198                         # end nodes. The other half of Lemma 8 in ref.
199                         if x in node_cut or v in node_cut:
200                             continue
201                         if node_cut not in seen:
202                             yield node_cut
203                             seen.append(node_cut)
204 
205                 # Add an edge (x, v) to make sure that we do not
206                 # find this cutset again. This is equivalent
207                 # of adding the edge in the input graph
208                 # G.add_edge(x, v) and then regenerate H and R:
209                 # Add edges to the auxiliary digraph.
210                 # See build_residual_network for convention we used
211                 # in residual graphs.
212                 H.add_edge(f"{mapping[x]}B", f"{mapping[v]}A", capacity=1)
213                 H.add_edge(f"{mapping[v]}B", f"{mapping[x]}A", capacity=1)
214                 # Add edges to the residual network.
215                 R.add_edge(f"{mapping[x]}B", f"{mapping[v]}A", capacity=1)
216                 R.add_edge(f"{mapping[v]}A", f"{mapping[x]}B", capacity=0)
217                 R.add_edge(f"{mapping[v]}B", f"{mapping[x]}A", capacity=1)
218                 R.add_edge(f"{mapping[x]}A", f"{mapping[v]}B", capacity=0)
219 
220                 # Add again the saturated edges to reuse the residual network
221                 R.add_edges_from(saturated_edges)
222 
223 
224 def _is_separating_set(G, cut):
225     """Assumes that the input graph is connected"""
226     if len(cut) == len(G) - 1:
227         return True
228 
229     H = nx.restricted_view(G, cut, [])
230     if nx.is_connected(H):
231         return False
232     return True
233
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/networkx/algorithms/connectivity/kcutsets.py b/networkx/algorithms/connectivity/kcutsets.py
--- a/networkx/algorithms/connectivity/kcutsets.py
+++ b/networkx/algorithms/connectivity/kcutsets.py
@@ -92,10 +92,11 @@
 
     # Address some corner cases first.
     # For complete Graphs
+
     if nx.density(G) == 1:
-        for cut_set in combinations(G, len(G) - 1):
-            yield set(cut_set)
+        yield from ()
         return
+
     # Initialize data structures.
     # Keep track of the cuts already computed so we do not repeat them.
     seen = []
@@ -129,7 +130,7 @@
     for x in X:
         # step 3: Compute local connectivity flow of x with all other
         # non adjacent nodes in G
-        non_adjacent = set(G) - X - set(G[x])
+        non_adjacent = set(G) - {x} - set(G[x])
         for v in non_adjacent:
             # step 4: compute maximum flow in an Even-Tarjan reduction H of G
             # and step 5: build the associated residual network R

{"golden_diff": "diff --git a/networkx/algorithms/connectivity/kcutsets.py b/networkx/algorithms/connectivity/kcutsets.py\n--- a/networkx/algorithms/connectivity/kcutsets.py\n+++ b/networkx/algorithms/connectivity/kcutsets.py\n@@ -92,10 +92,11 @@\n \n     # Address some corner cases first.\n     # For complete Graphs\n+\n     if nx.density(G) == 1:\n-        for cut_set in combinations(G, len(G) - 1):\n-            yield set(cut_set)\n+        yield from ()\n         return\n+\n     # Initialize data structures.\n     # Keep track of the cuts already computed so we do not repeat them.\n     seen = []\n@@ -129,7 +130,7 @@\n     for x in X:\n         # step 3: Compute local connectivity flow of x with all other\n         # non adjacent nodes in G\n-        non_adjacent = set(G) - X - set(G[x])\n+        non_adjacent = set(G) - {x} - set(G[x])\n         for v in non_adjacent:\n             # step 4: compute maximum flow in an Even-Tarjan reduction H of G\n             # and step 5: build the associated residual network R\n", "issue": "all_node_cuts returns incorrect cuts\nThe function `all_node_cuts` returns node cut-sets for the K2 (complete graph with two nodes), but there exist no.\r\n\r\n### Current Behavior\r\n\r\nConsider the following graph, consisting of two nodes connected by an edge:\r\n```python\r\ngraph = nx.Graph()\r\ngraph.add_edge(1,2)\r\nlist(all_node_cuts(graph)\r\n>>> [{1}, {2}]\r\n```\r\nThis graph has no node cut-sets because removing any vertex does not increase the number of connected components\r\n\r\n### Expected Behavior\r\n\r\nReturn no node cut-sets:\r\n```python\r\ngraph = nx.Graph()\r\ngraph.add_edge(1,2)\r\nlist(all_node_cuts(graph)\r\n>>> []\r\n```\r\n\r\n### Steps to Reproduce\r\n\r\nThe above example\r\n\r\n### Environment\r\n\r\nPython version: 3.10.10\r\nNetworkX version: 2.6.3\r\n\n", "before_files": [{"content": "\"\"\"\nKanevsky all minimum node k cutsets algorithm.\n\"\"\"\nimport copy\nfrom collections import defaultdict\nfrom itertools import combinations\nfrom operator import itemgetter\n\nimport networkx as nx\nfrom networkx.algorithms.flow import (\n    build_residual_network,\n    edmonds_karp,\n    shortest_augmenting_path,\n)\n\nfrom .utils import build_auxiliary_node_connectivity\n\ndefault_flow_func = edmonds_karp\n\n\n__all__ = [\"all_node_cuts\"]\n\n\ndef all_node_cuts(G, k=None, flow_func=None):\n    r\"\"\"Returns all minimum k cutsets of an undirected graph G.\n\n    This implementation is based on Kanevsky's algorithm [1]_ for finding all\n    minimum-size node cut-sets of an undirected graph G; ie the set (or sets)\n    of nodes of cardinality equal to the node connectivity of G. Thus if\n    removed, would break G into two or more connected components.\n\n    Parameters\n    ----------\n    G : NetworkX graph\n        Undirected graph\n\n    k : Integer\n        Node connectivity of the input graph. If k is None, then it is\n        computed. Default value: None.\n\n    flow_func : function\n        Function to perform the underlying flow computations. Default value is\n        :func:`~networkx.algorithms.flow.edmonds_karp`. This function performs\n        better in sparse graphs with right tailed degree distributions.\n        :func:`~networkx.algorithms.flow.shortest_augmenting_path` will\n        perform better in denser graphs.\n\n\n    Returns\n    -------\n    cuts : a generator of node cutsets\n        Each node cutset has cardinality equal to the node connectivity of\n        the input graph.\n\n    Examples\n    --------\n    >>> # A two-dimensional grid graph has 4 cutsets of cardinality 2\n    >>> G = nx.grid_2d_graph(5, 5)\n    >>> cutsets = list(nx.all_node_cuts(G))\n    >>> len(cutsets)\n    4\n    >>> all(2 == len(cutset) for cutset in cutsets)\n    True\n    >>> nx.node_connectivity(G)\n    2\n\n    Notes\n    -----\n    This implementation is based on the sequential algorithm for finding all\n    minimum-size separating vertex sets in a graph [1]_. The main idea is to\n    compute minimum cuts using local maximum flow computations among a set\n    of nodes of highest degree and all other non-adjacent nodes in the Graph.\n    Once we find a minimum cut, we add an edge between the high degree\n    node and the target node of the local maximum flow computation to make\n    sure that we will not find that minimum cut again.\n\n    See also\n    --------\n    node_connectivity\n    edmonds_karp\n    shortest_augmenting_path\n\n    References\n    ----------\n    .. [1]  Kanevsky, A. (1993). Finding all minimum-size separating vertex\n            sets in a graph. Networks 23(6), 533--541.\n            http://onlinelibrary.wiley.com/doi/10.1002/net.3230230604/abstract\n\n    \"\"\"\n    if not nx.is_connected(G):\n        raise nx.NetworkXError(\"Input graph is disconnected.\")\n\n    # Address some corner cases first.\n    # For complete Graphs\n    if nx.density(G) == 1:\n        for cut_set in combinations(G, len(G) - 1):\n            yield set(cut_set)\n        return\n    # Initialize data structures.\n    # Keep track of the cuts already computed so we do not repeat them.\n    seen = []\n    # Even-Tarjan reduction is what we call auxiliary digraph\n    # for node connectivity.\n    H = build_auxiliary_node_connectivity(G)\n    H_nodes = H.nodes  # for speed\n    mapping = H.graph[\"mapping\"]\n    # Keep a copy of original predecessors, H will be modified later.\n    # Shallow copy is enough.\n    original_H_pred = copy.copy(H._pred)\n    R = build_residual_network(H, \"capacity\")\n    kwargs = {\"capacity\": \"capacity\", \"residual\": R}\n    # Define default flow function\n    if flow_func is None:\n        flow_func = default_flow_func\n    if flow_func is shortest_augmenting_path:\n        kwargs[\"two_phase\"] = True\n    # Begin the actual algorithm\n    # step 1: Find node connectivity k of G\n    if k is None:\n        k = nx.node_connectivity(G, flow_func=flow_func)\n    # step 2:\n    # Find k nodes with top degree, call it X:\n    X = {n for n, d in sorted(G.degree(), key=itemgetter(1), reverse=True)[:k]}\n    # Check if X is a k-node-cutset\n    if _is_separating_set(G, X):\n        seen.append(X)\n        yield X\n\n    for x in X:\n        # step 3: Compute local connectivity flow of x with all other\n        # non adjacent nodes in G\n        non_adjacent = set(G) - X - set(G[x])\n        for v in non_adjacent:\n            # step 4: compute maximum flow in an Even-Tarjan reduction H of G\n            # and step 5: build the associated residual network R\n            R = flow_func(H, f\"{mapping[x]}B\", f\"{mapping[v]}A\", **kwargs)\n            flow_value = R.graph[\"flow_value\"]\n\n            if flow_value == k:\n                # Find the nodes incident to the flow.\n                E1 = flowed_edges = [\n                    (u, w) for (u, w, d) in R.edges(data=True) if d[\"flow\"] != 0\n                ]\n                VE1 = incident_nodes = {n for edge in E1 for n in edge}\n                # Remove saturated edges form the residual network.\n                # Note that reversed edges are introduced with capacity 0\n                # in the residual graph and they need to be removed too.\n                saturated_edges = [\n                    (u, w, d)\n                    for (u, w, d) in R.edges(data=True)\n                    if d[\"capacity\"] == d[\"flow\"] or d[\"capacity\"] == 0\n                ]\n                R.remove_edges_from(saturated_edges)\n                R_closure = nx.transitive_closure(R)\n                # step 6: shrink the strongly connected components of\n                # residual flow network R and call it L.\n                L = nx.condensation(R)\n                cmap = L.graph[\"mapping\"]\n                inv_cmap = defaultdict(list)\n                for n, scc in cmap.items():\n                    inv_cmap[scc].append(n)\n                # Find the incident nodes in the condensed graph.\n                VE1 = {cmap[n] for n in VE1}\n                # step 7: Compute all antichains of L;\n                # they map to closed sets in H.\n                # Any edge in H that links a closed set is part of a cutset.\n                for antichain in nx.antichains(L):\n                    # Only antichains that are subsets of incident nodes counts.\n                    # Lemma 8 in reference.\n                    if not set(antichain).issubset(VE1):\n                        continue\n                    # Nodes in an antichain of the condensation graph of\n                    # the residual network map to a closed set of nodes that\n                    # define a node partition of the auxiliary digraph H\n                    # through taking all of antichain's predecessors in the\n                    # transitive closure.\n                    S = set()\n                    for scc in antichain:\n                        S.update(inv_cmap[scc])\n                    S_ancestors = set()\n                    for n in S:\n                        S_ancestors.update(R_closure._pred[n])\n                    S.update(S_ancestors)\n                    if f\"{mapping[x]}B\" not in S or f\"{mapping[v]}A\" in S:\n                        continue\n                    # Find the cutset that links the node partition (S,~S) in H\n                    cutset = set()\n                    for u in S:\n                        cutset.update((u, w) for w in original_H_pred[u] if w not in S)\n                    # The edges in H that form the cutset are internal edges\n                    # (ie edges that represent a node of the original graph G)\n                    if any(H_nodes[u][\"id\"] != H_nodes[w][\"id\"] for u, w in cutset):\n                        continue\n                    node_cut = {H_nodes[u][\"id\"] for u, _ in cutset}\n\n                    if len(node_cut) == k:\n                        # The cut is invalid if it includes internal edges of\n                        # end nodes. The other half of Lemma 8 in ref.\n                        if x in node_cut or v in node_cut:\n                            continue\n                        if node_cut not in seen:\n                            yield node_cut\n                            seen.append(node_cut)\n\n                # Add an edge (x, v) to make sure that we do not\n                # find this cutset again. This is equivalent\n                # of adding the edge in the input graph\n                # G.add_edge(x, v) and then regenerate H and R:\n                # Add edges to the auxiliary digraph.\n                # See build_residual_network for convention we used\n                # in residual graphs.\n                H.add_edge(f\"{mapping[x]}B\", f\"{mapping[v]}A\", capacity=1)\n                H.add_edge(f\"{mapping[v]}B\", f\"{mapping[x]}A\", capacity=1)\n                # Add edges to the residual network.\n                R.add_edge(f\"{mapping[x]}B\", f\"{mapping[v]}A\", capacity=1)\n                R.add_edge(f\"{mapping[v]}A\", f\"{mapping[x]}B\", capacity=0)\n                R.add_edge(f\"{mapping[v]}B\", f\"{mapping[x]}A\", capacity=1)\n                R.add_edge(f\"{mapping[x]}A\", f\"{mapping[v]}B\", capacity=0)\n\n                # Add again the saturated edges to reuse the residual network\n                R.add_edges_from(saturated_edges)\n\n\ndef _is_separating_set(G, cut):\n    \"\"\"Assumes that the input graph is connected\"\"\"\n    if len(cut) == len(G) - 1:\n        return True\n\n    H = nx.restricted_view(G, cut, [])\n    if nx.is_connected(H):\n        return False\n    return True\n", "path": "networkx/algorithms/connectivity/kcutsets.py"}], "after_files": [{"content": "\"\"\"\nKanevsky all minimum node k cutsets algorithm.\n\"\"\"\nimport copy\nfrom collections import defaultdict\nfrom itertools import combinations\nfrom operator import itemgetter\n\nimport networkx as nx\nfrom networkx.algorithms.flow import (\n    build_residual_network,\n    edmonds_karp,\n    shortest_augmenting_path,\n)\n\nfrom .utils import build_auxiliary_node_connectivity\n\ndefault_flow_func = edmonds_karp\n\n\n__all__ = [\"all_node_cuts\"]\n\n\ndef all_node_cuts(G, k=None, flow_func=None):\n    r\"\"\"Returns all minimum k cutsets of an undirected graph G.\n\n    This implementation is based on Kanevsky's algorithm [1]_ for finding all\n    minimum-size node cut-sets of an undirected graph G; ie the set (or sets)\n    of nodes of cardinality equal to the node connectivity of G. Thus if\n    removed, would break G into two or more connected components.\n\n    Parameters\n    ----------\n    G : NetworkX graph\n        Undirected graph\n\n    k : Integer\n        Node connectivity of the input graph. If k is None, then it is\n        computed. Default value: None.\n\n    flow_func : function\n        Function to perform the underlying flow computations. Default value is\n        :func:`~networkx.algorithms.flow.edmonds_karp`. This function performs\n        better in sparse graphs with right tailed degree distributions.\n        :func:`~networkx.algorithms.flow.shortest_augmenting_path` will\n        perform better in denser graphs.\n\n\n    Returns\n    -------\n    cuts : a generator of node cutsets\n        Each node cutset has cardinality equal to the node connectivity of\n        the input graph.\n\n    Examples\n    --------\n    >>> # A two-dimensional grid graph has 4 cutsets of cardinality 2\n    >>> G = nx.grid_2d_graph(5, 5)\n    >>> cutsets = list(nx.all_node_cuts(G))\n    >>> len(cutsets)\n    4\n    >>> all(2 == len(cutset) for cutset in cutsets)\n    True\n    >>> nx.node_connectivity(G)\n    2\n\n    Notes\n    -----\n    This implementation is based on the sequential algorithm for finding all\n    minimum-size separating vertex sets in a graph [1]_. The main idea is to\n    compute minimum cuts using local maximum flow computations among a set\n    of nodes of highest degree and all other non-adjacent nodes in the Graph.\n    Once we find a minimum cut, we add an edge between the high degree\n    node and the target node of the local maximum flow computation to make\n    sure that we will not find that minimum cut again.\n\n    See also\n    --------\n    node_connectivity\n    edmonds_karp\n    shortest_augmenting_path\n\n    References\n    ----------\n    .. [1]  Kanevsky, A. (1993). Finding all minimum-size separating vertex\n            sets in a graph. Networks 23(6), 533--541.\n            http://onlinelibrary.wiley.com/doi/10.1002/net.3230230604/abstract\n\n    \"\"\"\n    if not nx.is_connected(G):\n        raise nx.NetworkXError(\"Input graph is disconnected.\")\n\n    # Address some corner cases first.\n    # For complete Graphs\n\n    if nx.density(G) == 1:\n        yield from ()\n        return\n\n    # Initialize data structures.\n    # Keep track of the cuts already computed so we do not repeat them.\n    seen = []\n    # Even-Tarjan reduction is what we call auxiliary digraph\n    # for node connectivity.\n    H = build_auxiliary_node_connectivity(G)\n    H_nodes = H.nodes  # for speed\n    mapping = H.graph[\"mapping\"]\n    # Keep a copy of original predecessors, H will be modified later.\n    # Shallow copy is enough.\n    original_H_pred = copy.copy(H._pred)\n    R = build_residual_network(H, \"capacity\")\n    kwargs = {\"capacity\": \"capacity\", \"residual\": R}\n    # Define default flow function\n    if flow_func is None:\n        flow_func = default_flow_func\n    if flow_func is shortest_augmenting_path:\n        kwargs[\"two_phase\"] = True\n    # Begin the actual algorithm\n    # step 1: Find node connectivity k of G\n    if k is None:\n        k = nx.node_connectivity(G, flow_func=flow_func)\n    # step 2:\n    # Find k nodes with top degree, call it X:\n    X = {n for n, d in sorted(G.degree(), key=itemgetter(1), reverse=True)[:k]}\n    # Check if X is a k-node-cutset\n    if _is_separating_set(G, X):\n        seen.append(X)\n        yield X\n\n    for x in X:\n        # step 3: Compute local connectivity flow of x with all other\n        # non adjacent nodes in G\n        non_adjacent = set(G) - {x} - set(G[x])\n        for v in non_adjacent:\n            # step 4: compute maximum flow in an Even-Tarjan reduction H of G\n            # and step 5: build the associated residual network R\n            R = flow_func(H, f\"{mapping[x]}B\", f\"{mapping[v]}A\", **kwargs)\n            flow_value = R.graph[\"flow_value\"]\n\n            if flow_value == k:\n                # Find the nodes incident to the flow.\n                E1 = flowed_edges = [\n                    (u, w) for (u, w, d) in R.edges(data=True) if d[\"flow\"] != 0\n                ]\n                VE1 = incident_nodes = {n for edge in E1 for n in edge}\n                # Remove saturated edges form the residual network.\n                # Note that reversed edges are introduced with capacity 0\n                # in the residual graph and they need to be removed too.\n                saturated_edges = [\n                    (u, w, d)\n                    for (u, w, d) in R.edges(data=True)\n                    if d[\"capacity\"] == d[\"flow\"] or d[\"capacity\"] == 0\n                ]\n                R.remove_edges_from(saturated_edges)\n                R_closure = nx.transitive_closure(R)\n                # step 6: shrink the strongly connected components of\n                # residual flow network R and call it L.\n                L = nx.condensation(R)\n                cmap = L.graph[\"mapping\"]\n                inv_cmap = defaultdict(list)\n                for n, scc in cmap.items():\n                    inv_cmap[scc].append(n)\n                # Find the incident nodes in the condensed graph.\n                VE1 = {cmap[n] for n in VE1}\n                # step 7: Compute all antichains of L;\n                # they map to closed sets in H.\n                # Any edge in H that links a closed set is part of a cutset.\n                for antichain in nx.antichains(L):\n                    # Only antichains that are subsets of incident nodes counts.\n                    # Lemma 8 in reference.\n                    if not set(antichain).issubset(VE1):\n                        continue\n                    # Nodes in an antichain of the condensation graph of\n                    # the residual network map to a closed set of nodes that\n                    # define a node partition of the auxiliary digraph H\n                    # through taking all of antichain's predecessors in the\n                    # transitive closure.\n                    S = set()\n                    for scc in antichain:\n                        S.update(inv_cmap[scc])\n                    S_ancestors = set()\n                    for n in S:\n                        S_ancestors.update(R_closure._pred[n])\n                    S.update(S_ancestors)\n                    if f\"{mapping[x]}B\" not in S or f\"{mapping[v]}A\" in S:\n                        continue\n                    # Find the cutset that links the node partition (S,~S) in H\n                    cutset = set()\n                    for u in S:\n                        cutset.update((u, w) for w in original_H_pred[u] if w not in S)\n                    # The edges in H that form the cutset are internal edges\n                    # (ie edges that represent a node of the original graph G)\n                    if any(H_nodes[u][\"id\"] != H_nodes[w][\"id\"] for u, w in cutset):\n                        continue\n                    node_cut = {H_nodes[u][\"id\"] for u, _ in cutset}\n\n                    if len(node_cut) == k:\n                        # The cut is invalid if it includes internal edges of\n                        # end nodes. The other half of Lemma 8 in ref.\n                        if x in node_cut or v in node_cut:\n                            continue\n                        if node_cut not in seen:\n                            yield node_cut\n                            seen.append(node_cut)\n\n                # Add an edge (x, v) to make sure that we do not\n                # find this cutset again. This is equivalent\n                # of adding the edge in the input graph\n                # G.add_edge(x, v) and then regenerate H and R:\n                # Add edges to the auxiliary digraph.\n                # See build_residual_network for convention we used\n                # in residual graphs.\n                H.add_edge(f\"{mapping[x]}B\", f\"{mapping[v]}A\", capacity=1)\n                H.add_edge(f\"{mapping[v]}B\", f\"{mapping[x]}A\", capacity=1)\n                # Add edges to the residual network.\n                R.add_edge(f\"{mapping[x]}B\", f\"{mapping[v]}A\", capacity=1)\n                R.add_edge(f\"{mapping[v]}A\", f\"{mapping[x]}B\", capacity=0)\n                R.add_edge(f\"{mapping[v]}B\", f\"{mapping[x]}A\", capacity=1)\n                R.add_edge(f\"{mapping[x]}A\", f\"{mapping[v]}B\", capacity=0)\n\n                # Add again the saturated edges to reuse the residual network\n                R.add_edges_from(saturated_edges)\n\n\ndef _is_separating_set(G, cut):\n    \"\"\"Assumes that the input graph is connected\"\"\"\n    if len(cut) == len(G) - 1:\n        return True\n\n    H = nx.restricted_view(G, cut, [])\n    if nx.is_connected(H):\n        return False\n    return True\n", "path": "networkx/algorithms/connectivity/kcutsets.py"}]}