add_edge -> increase_capacity

[thorehusfeldt]

This just bit me in the ass when I solved elementarymath (and added the “same” edge twice). The chanced name avoids this mistake, I think.

https://github.com/exoji2e/notebook/blob/c05317bc88debbd5023fbef9d59312bb99d9da1b/code/Graphs/flow.py#L6

Also, dfs can be made local to max_flow. This again saves some typing and makes the structure clearer:

class Flow:
    def __init__(self, nvertices):
        self.G = [defaultdict(int) for _ in range(nvertices)]

    def increase_capacity(self, u, v, cap):
        self.G[u][v] += cap

    def max_flow(self, source, to):

        def dfs(u, hi):
            if u in self.reached:
                return 0
            if u == to:
                return hi
            G = self.G
            self.reached.add(u)
            for v, cap in G[u].items():
                if cap:
                    f = dfs(v, min(hi, cap))
                    if f:
                        G[u][v] -= f
                        G[v][u] += f
                        return f
            return 0

        flow = 0
        while True:
            self.reached = set()
            pushed = dfs(source, float("inf"))
            if not pushed:
                break
            flow += pushed
        return flow # cut = self.reached, f(u,v) = cap(u,v) - self.G[u][v]

[thorehusfeldt]

Here’s the code with capacity scaling. This solves mincut on Kattis. Note the minimal changes to the simpler version. I propose to add this, one can easily not type in the lines with lo, so it wouldn’t low anybody down.

from typing import List, Dict, Optional, Set
from collections import defaultdict

class FordFulkersonDFS:
    def __init__(self, n):
        self.G: List[Dict[int, int]] = [
            defaultdict(int) for _ in range(n)
        ]  # neighbourhood dict, N[u] = {v_1: cap_1, v_2: cap_2, ...}
        self.S: Set[int] = set()  # redundant

    def add_edge(self, u, v, w):
        """ Add edge (u,v,w): u->v with weight w """
        self.G[u][v] += w

    def find_flow(self, source: int, to: int) -> int:
        def dfs(u: int, hi: int) -> Optional[int]: # nonzero
            G = self.G
            S = self.S
            if u in S:
                return None
            if u == to:
                return hi
            S.add(u)
            for v, cap in G[u].items():
                if cap > lo:
                    f = dfs(v, min(hi, cap))
                    if f:
                        G[u][v] -= f
                        G[v][u] += f
                        return f
            return None

        flow = 0
        hi = 10 ** 9 # MAXCAP
        lo = hi // 2
        while True:
            self.S = set()
            pushed = dfs(s, hi)  
            if not pushed:
                if lo == 0:
                    break
                else:
                    lo //= 2
            else:
                flow += pushed
        return flow

[exoji2e]

Please have a look at e35d589, it incorporates most of your proposed changes, but I didn't like return None leading to else: flow += pushed.

[thorehusfeldt]

Your while loop is much better. I think this whole thing came out great.

self.min_edge doesn’t need to belong to the object, it’s just a local variable to max_flow that is readable in the scope of dfs, much like sink. And lo and hi were good names. But never mind.

[exoji2e]

I let min_edge be part of the object because I want to be able to easily move out dfs, and I dislike accessing variables inside a local function that is defined below it. min_cap would be a better name.

Btw, I previously solved mincut with a Dijkstra instead of scaling edges. (Not using the heapkey sum(caps), but instead -min(caps), always pushing along the widest path to the sink.) Complexity-wise equivalent adding an extra log-factor, but this scaling is twice as fast!