(self, source, sink)
| 36 | |
| 37 | # Here we calculate the flow that reaches the sink |
| 38 | def max_flow(self, source, sink): |
| 39 | flow, self.q[0] = 0, source |
| 40 | for l in range(31): # l = 30 maybe faster for random data # noqa: E741 |
| 41 | while True: |
| 42 | self.lvl, self.ptr = [0] * len(self.q), [0] * len(self.q) |
| 43 | qi, qe, self.lvl[source] = 0, 1, 1 |
| 44 | while qi < qe and not self.lvl[sink]: |
| 45 | v = self.q[qi] |
| 46 | qi += 1 |
| 47 | for e in self.adj[v]: |
| 48 | if not self.lvl[e[0]] and (e[2] - e[3]) >> (30 - l): |
| 49 | self.q[qe] = e[0] |
| 50 | qe += 1 |
| 51 | self.lvl[e[0]] = self.lvl[v] + 1 |
| 52 | |
| 53 | p = self.depth_first_search(source, sink, INF) |
| 54 | while p: |
| 55 | flow += p |
| 56 | p = self.depth_first_search(source, sink, INF) |
| 57 | |
| 58 | if not self.lvl[sink]: |
| 59 | break |
| 60 | |
| 61 | return flow |
| 62 | |
| 63 | |
| 64 | # Example to use |
no test coverage detected