Page MenuHomec4science
Files F94103168

bridge_queue.py
No OneTemporary
Actions

File Metadata

Created
Tue, Dec 3, 22:40

bridge_queue.py
View Options

#!/usr/bin/python
from queue import Queue
class BridgeFlow:
def __init__(self, N, n, A, E, 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.E = E # adjacency set, constant
self.A = A # adjacency / weight matrix, variable for residual graph computing
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.put(self.s)
while not Q.empty() and not visited[self.t]:
u = Q.get() # get
"""
# deduce adjacency for efficiency
adj = []
if u == 0:
# source
adj = range(1,self.n + 1)
elif u <= self.n:
# island A
# undirected, so it takes also the source
adj = list(range(self.n + 1, 2 * self.n + 1)) + [0]
elif u < (2 * self.n + 1):
# island B
# undirected, so it takes also the bridges in A
adj = list(range(1,self.n + 1)) + [2 * self.n + 1]
else:
# sink found
return True
adj = range(self.n + 1, 2 * self.n + 1)
"""
for v in self.E[u]:
# 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))
# check if the source
visited[v] = True
Q.put(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)]
E = [[] 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
E[a].append(b)
E[b].append(a)
# 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
E[0].append(i)
E[i].append(0)
E[2 * n + 1].append(n + i)
E[n + i].append(2 * n + 1)
return BridgeFlow(2 * n + 2, n, A, E)
# 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