Page MenuHomec4science
Files F94102939

bridge.py
No OneTemporary
Actions

File Metadata

Created
Tue, Dec 3, 22:37

bridge.py
View Options

#!/usr/bin/python
class LkList:
def __init__(self, x, _prev, _next):
self.x = x
self._prev = _prev
self._next = _next
class Queue:
def __init__(self):
self.head = None
self.tail = None
self.N = 0
def enqueue(self, x):
if self.head is not None:
self.head._prev = LkList(x, None, self.head)
self.head = self.head._prev
else:
self.head = LkList(x, None, None)
self.tail = self.head
self.N += 1
def dequeue(self):
if self.tail is None:
return None
else:
x = self.tail.x
if self.tail._prev is not None:
self.tail._prev._next = None
else:
self.head = None
self.tail = self.tail._prev
self.N -= 1
return x
def __len__(self):
return self.N
class BridgeFlow:
def __init__(self, N, n, A, s = -1, t = -1):
self.s = 0 if s < 0 else s
self.t = N-1 if t < 0 else t
self.n = n # number of bridges per island
self.N = N # total size of the graph
self.A = A
def __len__(self):
return self.N
# run bfs starting from source
# path = buffer in which to store the parent of the visited nodes
def find_augmenting_path(self, path):
# distance counter
visited = [False for i in range(self.N)]
visited[self.s] = True
Q = Queue() # bsf queue
Q.enqueue(self.s)
while len(Q) > 0:
u = Q.dequeue() # dequeue
# deduce adjacency for efficiency
adj = 0
if u == 0:
adj = range(1,self.n + 1)
elif u <= self.n:
adj = range(self.n + 1, 2 * self.n + 1)
else:
adj = [2 * self.n + 1]
for v in range(self.N):
# filter u -> v and not visited
if self.A[u][v] > 0 and not visited[v]:
#print("From %d, visited %d" % (u+1,v+1))
visited[v] = True
Q.enqueue(v)
# compile path array
path[v] = u
return visited[self.t]
def parseinput(fstream):
line = fstream.readline().split(' ')
n = int(line[0]) # number of nodes
m = int(line[1]) # number of edges
# Setup Adj matrix
A = [[0 for i in range(2 * n + 2)] for i in range(2 * n + 2)]
# layout:
# i = 0 -> source
# i = 1,...,n -> island A
# i = n + 1, ..., 2n -> island B
# i = 2n + 1 -> sink
# assign bridges
for i in range(m):
line = fstream.readline().split(' ')
a = int(line[0])
b = int(line[1]) + n
A[a][b] = 1
A[b][a] = 1
# assign source and sink
for i in range(1, n + 1):
A[0][i] = 2
A[i][0] = 2
A[2 * n + 1][n + i] = 2
A[n + i][2 * n + 1] = 2
return BridgeFlow(2 * n + 2, n, A)
# ford-kulkerson for a flow s.t. for all paths from s to t : min capacity = 1
def ford_kulkerson_unit(flow):
n = flow.N
if n < 2:
raise Exception("Entering a sinkless flow")
# paths memorization
P = []
# path storage
path = [-1 for i in range(n)]
while flow.find_augmenting_path(path):
# update flow
# Warning: suppose that min capacity is 1, not the general case
# Notice: max-flow = len(P)
v = n-1
while v > 0:
u = path[v] # get parent vertex
flow.A[u][v] -= 1 # decrease capacity on residual graph
flow.A[v][u] += 1 # increase capacity on residual graph
v = u
P.append(path)
return len(P)
import sys
graph = parseinput(sys.stdin)
print(ford_kulkerson_unit(graph))

Event Timeline

c4science · Help