In Python !

Please don't repost the previous answer as it was not correct.thanks

I am looking to modify the code given below that gives traditional min-cut of a graph to min vertex cut of a graph based on the following idea:

Code to modify ( taken from geeks for geeks "Find minimum s-t cut in a flow network"):

from collections import defaultdict

# This class represents a directed graph using adjacency matrix representation

class Graph:

def __init__(self,graph):

self.graph = graph # residual graph

self.org_graph = [i[:] for i in graph]

self. ROW = len(graph)

self.COL = len(graph[0])

'''Returns true if there is a path from source 's' to sink 't' in

residual graph. Also fills parent[] to store the path '''

def BFS(self,s, t, parent):

# Mark all the vertices as not visited

visited =[False]*(self.ROW)

# Create a queue for BFS

queue=[]

# Mark the source node as visited and enqueue it

queue.append(s)

visited[s] = True

# Standard BFS Loop

while queue:

#Dequeue a vertex from queue and print it

u = queue.pop(0)

# Get all adjacent vertices of the dequeued vertex u

# If a adjacent has not been visited, then mark it

# visited and enqueue it

for ind, val in enumerate(self.graph[u]):

if visited[ind] == False and val > 0 :

queue.append(ind)

visited[ind] = True

parent[ind] = u

# If we reached sink in BFS starting from source, then return

# true, else false

return True if visited[t] else False

# Returns the min-cut of the given graph

def minCut(self, source, sink):

# This array is filled by BFS and to store path

parent = [-1]*(self.ROW)

max_flow = 0 # There is no flow initially

# Augment the flow while there is path from source to sink

while self.BFS(source, sink, parent) :

# Find minimum residual capacity of the edges along the

# path filled by BFS. Or we can say find the maximum flow

# through the path found.

path_flow = float("Inf")

s = sink

while(s != source):

path_flow = min (path_flow, self.graph[parent[s]][s])

s = parent[s]

# Add path flow to overall flow

max_flow += path_flow

# update residual capacities of the edges and reverse edges

# along the path

v = sink

while(v != source):

u = parent[v]

self.graph[u][v] -= path_flow

self.graph[v][u] += path_flow

v = parent[v]

# print the edges which initially had weights

# but now have 0 weight

for i in range(self.ROW):

for j in range(self.COL):

if self.graph[i][j] == 0 and self.org_graph[i][j] > 0:

print str(i) + " - " + str(j)

# Create a graph given in the above diagram

graph = [[0, 1, 1, 0, 0, 0],

[0, 0, 1, 1, 0, 0],

[0, 1, 0, 0, 1, 0],

[0, 0, 1, 0, 0, 1],

[0, 0, 0, 7, 0, 4],

[0, 0, 0, 0, 0, 0]]

g = Graph(graph)

source = 0; sink = 5

g.minCut(source, sink)

Minimum Vertex-Cut as Minimum Cut 3 The minimum vertex-cut problem is formally stated as follows: Definition 3.1 Given an undirected graph G = (V, E) and two verter des- ignations s and t, find a minimal set V' C {V} {s,t} such that in G' = ({V} {V'}, {E} {e' e E[3, e' is incidental to v' }, no path erists from s to t. We can cast this problem relatively easily as a minimum cut problem in a directed graph. We simply create edges in either direction for each undirected edge in the original graph. Then we split each vertex l into two, l;n and lut. All edges that were incoming to l are now incoming to l;n, and all edges that were outgoing from 1 are now outgoing from l,ut. A single directed edge is added from l;n to lut. Now it is clear that cutting an edge between ln and lout in this graph is equivalent to removing the vertex l in the undirected graph, because now all paths that usedI are disconnected. This formulation gives us a simple algorithm to extend Algorithm 2.1 to provide a complete solution. Algorithm 3.1 shows pseudo-code for the complete problem. Minimum Vertex-Cut as Minimum Cut 3 The minimum vertex-cut problem is formally stated as follows: Definition 3.1 Given an undirected graph G = (V, E) and two verter des- ignations s and t, find a minimal set V' C {V} {s,t} such that in G' = ({V} {V'}, {E} {e' e E[3, e' is incidental to v' }, no path erists from s to t. We can cast this problem relatively easily as a minimum cut problem in a directed graph. We simply create edges in either direction for each undirected edge in the original graph. Then we split each vertex l into two, l;n and lut. All edges that were incoming to l are now incoming to l;n, and all edges that were outgoing from 1 are now outgoing from l,ut. A single directed edge is added from l;n to lut. Now it is clear that cutting an edge between ln and lout in this graph is equivalent to removing the vertex l in the undirected graph, because now all paths that usedI are disconnected. This formulation gives us a simple algorithm to extend Algorithm 2.1 to provide a complete solution. Algorithm 3.1 shows pseudo-code for the complete