Skip to content

Instantly share code, notes, and snippets.

@e-mon
Created May 28, 2015 03:06
Show Gist options
  • Save e-mon/2e9628160032acb8f123 to your computer and use it in GitHub Desktop.
Save e-mon/2e9628160032acb8f123 to your computer and use it in GitHub Desktop.
Dinic's Algorithm
class Dinic:
class Edge:
def __init__(self, to, cap, rev):
self.to = to
self.cap = cap
self.rev = rev
def __repr__(self):
return "(to: {0} cap: {1} rev: {2})".format(self.to, self.cap, self. rev)
def __init__(self,V):
self.V = V
self.size = [0 for i in range(V)]
self.G = [[] for i in range(V)]
def add_edge(self, _from, to, cap):
self.G[_from].append(self.Edge(to, cap, self.size[to]))
self.G[to].append(self.Edge(_from, 0, self.size[_from]))
self.size[_from] += 1
self.size[to] += 1
def bfs(self,s):
level = [-1 for i in range(self.V)]
level[s] = 0
q = []
q.append(s)
while q != []:
v = q.pop(0)
for u in self.G[v]:
if u.cap > 0 and level[u.to] < 0:
level[u.to] = level[v] + 1
q.append(u.to)
return level
def dfs(self, v, t, f):
if v == t: return f
for i in range(self.iterator[v],self.size[v]):
self.iterator[v] = i
edge = self.G[v][i]
if edge.cap > 0 and self.level[v] < self.level[edge.to]:
d = self.dfs(edge.to, t, f if f < edge.cap else edge.cap)
if d > 0:
self.G[v][i].cap -= d
self.G[edge.to][edge.rev].cap += d
return d
return 0
def max_flow(self, s, t):
flow = 0
while True:
self.level = self.bfs(s)
if self.level[t] < 0:
return flow
self.iterator = [0 for i in range(self.V)]
while True:
f = self.dfs(s, t, float('inf'))
if f == 0:
break
flow += f
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment