| 20 | |
| 21 | # This is a sample depth first search to be used at max_flow |
| 22 | def depth_first_search(self, vertex, sink, flow): |
| 23 | if vertex == sink or not flow: |
| 24 | return flow |
| 25 | |
| 26 | for i in range(self.ptr[vertex], len(self.adj[vertex])): |
| 27 | e = self.adj[vertex][i] |
| 28 | if self.lvl[e[0]] == self.lvl[vertex] + 1: |
| 29 | p = self.depth_first_search(e[0], sink, min(flow, e[2] - e[3])) |
| 30 | if p: |
| 31 | self.adj[vertex][i][3] += p |
| 32 | self.adj[e[0]][e[1]][3] -= p |
| 33 | return p |
| 34 | self.ptr[vertex] = self.ptr[vertex] + 1 |
| 35 | return 0 |
| 36 | |
| 37 | # Here we calculate the flow that reaches the sink |
| 38 | def max_flow(self, source, sink): |