In a Max Flow problem, how to find all possible sets of paths that give max flow?

Question

I understand that Ford-Fulkerson Algorithm can find the maximum flow that can flow from source (s) to sink (t) in a flow network.
But is there an algorithm that finds all possible sets of paths that give the max flow?

An example:
In this network below, all edges have a capacity of 1. It's not hard to see that the max flow from s to t is 3. But how to find the combinations of paths that carry that flow?

Expected outputs:
Path set 1: s-0-1-t, s-2-3-t, s-5-6-t
Path set 2: s-0-1-t, s-2-4-t, s-5-6-t
Path set 3: s-0-3-t, s-2-4-t, s-5-6-t
Path set 4: s-0-4-t, s-2-3-t, s-5-6-t

A similar question was asked here but didn't seem to get a clear answer.

Allomorph

Can we assume that all of the arcs are cap 1? That makes the problem a lot easier. – Dapper

@DavidEisenstat Yes, all arcs are cap 1. – Allomorph

Answer 1

Per your comment, I'm assuming that all arcs are directed and capacity 1.

The high-level pseudocode is

define EnumerateFlows(G, s, t):
    if G has no s-t path:
        yield []  # solution with no paths
    else:
        for P in EnumeratePaths(G, s, t):
            derive G' = G - P
            let s-u be the first arc in P
            derive G'' = G' - {arcs s-v such that v < u}  # ensure canonically ordered solutions only
            for F in EnumerateFlows(G'', s, t):
                yield [P, F...]  # solution with P followed by the elements of F

where the return value of the function is a list of all of the yields made in its body. The output needs postprocessing to remove the non-maximum flows.

EnumeratePaths undoubtedly has a solution on Stack Overflow, but for completeness,

define EnumeratePaths(G, s, t):
    if s = t:
        yield [s]
    else:
        for u in {successors of s in t}:
            for P in EnumeratePaths(G - {s-u}, u, t):
                yield [s, P...]

To improve EnumerateFlows, it's worth adding a check to make sure that there still exists a max flow in the residual graph.

As for low-level implementation advice, my suggestion would be to use an adjacency list representation for G and splice arcs in and out of the lists. On the other hand, maybe your graphs are small enough that it doesn't matter.

Dapper