In Python !

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 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, 16, 13, 0, 0, 0],

[0, 0, 10, 12, 0, 0],

[0, 4, 0, 0, 14, 0],

[0, 0, 9, 0, 0, 20],

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

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

g = Graph(graph)

source = 0; sink = 5

g.minCut(source, sink)

3 Minimum Vertex-Cut as Minimum Cut The minimum vertex-cut problem is formally stated as follows: Definition 3.1 Given an undirected graph G = (V, E) and two vertex des- ignations s and t, find a minimal set V' C {V} - {s,t} such that in G' = ({V} - {V'},{E} - {e' e E|3v e is incidental to v'}, no path exists 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, lin and lout. All edges that were incoming to l are now incoming to lin, and all edges that were outgoing from l are now outgoing from lut. A single directed edge is added from lin to lout. Now it is clear that cutting an edge between lin and lout in this graph is equivalent to removing the vertex l in the undirected graph, because now all paths that used I 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