Merge pull request #1914 from Arafatk/patch-5

minimum_st_node_cut incorrect  if source and target are connected 

2 files changed, 9 insertions, 1 deletions

diff --git a/networkx/algorithms/connectivity/cuts.py b/networkx/algorithms/connectivity/cuts.py
index 763a8e4a..0288f5e2 100644
--- a/networkx/algorithms/connectivity/cuts.py
+++ b/networkx/algorithms/connectivity/cuts.py
@@ -285,7 +285,8 @@ def minimum_st_node_cut(G, s, t, flow_func=None, auxiliary=None, residual=None):
     mapping = H.graph.get('mapping', None)
     if mapping is None:
         raise nx.NetworkXError('Invalid auxiliary digraph.')
-
+    if G.has_edge(s, t) or G.has_edge(t, s):
+        return []
     kwargs = dict(flow_func=flow_func, residual=residual, auxiliary=H)
 
     # The edge cut in the auxiliary digraph corresponds to the node cut in the
diff --git a/networkx/algorithms/connectivity/tests/test_cuts.py b/networkx/algorithms/connectivity/tests/test_cuts.py
index 1086cf9c..264bc4af 100644
--- a/networkx/algorithms/connectivity/tests/test_cuts.py
+++ b/networkx/algorithms/connectivity/tests/test_cuts.py
@@ -238,6 +238,13 @@ def tests_min_cut_complete_directed():
         for flow_func in flow_funcs:
             assert_equal(4, len(interface_func(G, flow_func=flow_func)))
 
+def tests_minimum_st_node_cut():
+    G = nx.Graph()
+    G.add_nodes_from([0, 1, 2, 3, 7, 8, 11, 12])
+    G.add_edges_from([(7, 11), (1, 11), (1, 12), (12, 8), (0, 1)])
+    nodelist = minimum_st_node_cut(G, 7, 11)
+    assert(nodelist == [])
+
 def test_invalid_auxiliary():
     G = nx.complete_graph(5)
     assert_raises(nx.NetworkXError, minimum_st_node_cut, G, 0, 3,