Find the maximum flow

Question

Given a directed network, with a single source and a single sink, it is possible to find the maximum flow through this network, from source to sink. For example, take the below network, \$G\$:

Here, the source is node 0 and the sink 5. We can see, from the minimum cut-maximum flow theorem, that the maximum flow through this network is \$70\$ (given by the cut \$\{0\} / \{1, 2, 3, 4, 5\}\$)

Minimum cut-maximum flow theorem

For a network, a cut is a line that divides a network in two, with the sink and source in different halves. For the above network, one such cut, \$C\$, is \$\{0, 1, 3\} / \{2, 4, 5\}\$. Every cut has a value, which depends on which edges in the network is passes through. The above cut, \$C\$, passes through the edges \$1-2, 3-2\$ and \$3-4\$, which have the weights \$40, 45\$ and \$30\$ respectively. The value of a cut is defined, for the set of crossed edges \$S\$, as

The sum of the weights of all the edges in \$S\$ which pass from the source to the sink

Therefore, the value of \$C\$ is \$40 + 45 + 30 = 115\$ but the value of the cut \$\{0, 3\} / \{1, 2, 4, 5\}\$ would be \$20 + 45 + 30 = 95\$ (Note that \$10\$ is not included as it passes from the sink towards the source).

The minimum cut-maximum flow theorem states that

The maximum flow through a network is equal to the minimum value of all cuts in that network

The minimum cut of all the cuts in \$G\$ is \$\{0\} / \{1, 2, 3, 4, 5\}\$ which has a value of \$70\$. Therefore, the maximum flow through \$G\$ is also \$70\$.

Challenge

Write a function of full program that, when given a directed network as input, outputs the maximum flow through that network. You may, of course, use any method or algorithm to compute the maximum flow, not just the minimum cut-maximum flow theorem. This was simply included as one method.

You may take input in any convenient method or format, such as an adjacency matrix, a list of nodes and edges, etc. The input will always have 2 or more nodes, will be a connected graph, and will have exactly 1 source and 1 sink. The weights of the edges will always be natural numbers, as will the maximum flow. The output should reflect this, and can also be in any convenient method or format.

This is code-golf, so the shortest code, in bytes, wins.

Test cases

Both the network and the adjacency matrix are included for each test case.

Network \$G\$ (above):

[[ 0, 20,  0, 50,  0,  0],
 [ 0,  0, 40, 10,  0,  0],
 [ 0,  0,  0,  0, 25, 25],
 [ 0,  0, 45,  0, 30,  0],
 [ 0,  0,  0,  0,  0, 50],
 [ 0,  0,  0,  0,  0,  0]] -> 70 ({0} / {1, 2, 3, 4, 5})

---

[[ 0, 10, 17,  0,  0,  0,  0],
 [ 0,  0,  0,  2, 13,  0,  0],
 [ 0,  5,  0,  0,  4,  8,  0],
 [ 0,  0,  0,  0,  0,  0, 20],
 [ 0,  0,  0, 18,  0,  0,  0],
 [ 0,  0,  0,  0,  1,  0,  7],
 [ 0,  0,  0,  0,  0,  0,  0]] -> 27 (Multiple cuts e.g. {0, 1, 2} / {3, 4, 5, 6})

---

[[ 0,  6,  2,  7,  4,  0,  0,  0],
 [ 0,  0,  0,  0,  0, 10,  0,  0],
 [ 0,  8,  0,  0,  0,  0,  9,  4],
 [ 0,  0, 11,  0,  0,  0,  0,  0],
 [ 0,  0,  0,  5,  0,  0,  0,  0],
 [ 0,  0, 13,  0,  0,  0,  0, 16],
 [ 0,  0,  0, 14,  0,  0,  0, 12],
 [ 0,  0,  0,  0,  0,  0,  0,  0]] -> 19 ({0} / {1, 2, 3, 4, 5, 6, 7})

---

[[ 0, 40, 50,  0,  0,  0,  0,  0,  0],
 [ 0,  0,  0, 30, 10,  0,  0,  0,  0],
 [ 0,  0,  0, 40,  0,  0, 10,  0,  0],
 [ 0,  0,  0,  0, 15, 10,  0,  0,  0],
 [ 0,  0,  0,  0,  0,  0,  0,  0, 20],
 [ 0,  0,  0,  0,  0,  0, 15, 20,  0],
 [ 0,  0,  0,  0,  0,  0,  0, 30,  0],
 [ 0,  0,  0,  0,  0,  0,  0,  0, 50],
 [ 0,  0,  0,  0,  0,  0,  0,  0,  0]] -> 40 ({0, 1, 2, 3, 4} / {5, 6, 7, 8})

---

[[ 0, 5, 8, 3, 3, 7, 0, 0, 0, 7],
 [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 4],
 [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 9],
 [ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
 [ 0, 0, 0, 0, 0, 0, 0, 4, 0, 0],
 [ 0, 0, 0, 0, 0, 0, 0, 0, 6, 0],
 [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
 [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 6],
 [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 5],
 [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] -> 28 ({0, 1, 3, 5, 8} / {2, 4, 6, 7, 9})

---

[[0, 5],
 [0, 0]] -> 5

Answer 1

Charcoal, 37 36 34 bytes

Ｉ⌊ＥＥＸ²⁻Ｌθ²↨⁺Ｘ²⊖Ｌθ⊗ι²ΣＥθ∧§ιμΣΦ묧ιξ

Try it online! Link is to verbose version of code. Explanation:

   Ｅ…Ｘ²⁻Ｌθ²Ｘ²⊖Ｌθ                    Loop over all cuts...
  Ｅ             ↨⊗ι²                ... converted to base 2
                    ΣＥθ∧§ιμ         Sum rows in source cut
                           ΣΦ묧ιξ  Sum columns in sink cut
Ｉ⌊                                  Print the minimum

The range is constructed so that the base 2 values are 100...000 to 111...110 whereby the 1 bits refer to the source cut (thus the left bit, which is actually element 0, is the source itself) and the 0 bits refer to the sink cut.

Answer 2

JavaScript (ES6), 96 bytes

f=(m,k=1,b)=>k*2>>m.length?b:f(m,k+2,m.map((r,y)=>r.map((v,x)=>t+=k>>y&~k>>x&1&&v),t=0)|t>b?b:t)

Try it online!

Commented

f = (                   // f is a recursive function taking:
  m,                    //   m[] = adjacency matrix
  k = 1,                //   k = counter, initialized to 1 and always odd
  b                     //   b = best value so far, initially undefined
) =>                    //
  k * 2 >> m.length ?   // if k is greater than or equal to 2 ** (m.length - 1):
    b                   //   stop the recursion and return b
  :                     // else:
    f(                  //   do a recursive call to f:
      m,                //     pass m[] unchanged
      k + 2,            //     add 2 to k
                        //     we make sure that k remains odd so that the source
                        //     is always included in the 1st half of the cut
      m.map((r, y) =>   //     for each row r[] at position y in m[]:
        r.map((v, x) => //       for each value v at position x in r[]:
          t +=          //         update t:
            k >> y &    //           if the y-th bit in k is set
            ~k >> x & 1 //           and the x-th bit in k is not set:
            && v        //             add v to t, otherwise add nothing
        ),              //       end of inner map()
        t = 0           //       start with t = 0
      ) |               //     end of outer map()
      t > b ? b : t     //     if t <= b or b is still undefined, update b to t
    )                   //   end of recursive call

Answer 3

05AB1E, 27 bytes

ā2.ŒʒD{Q}<ʒZ%PË}εнèøyθè˜O}ß

Takes the input in a similar format as the test cases in the challenge description.

Try it online or verify all test cases.

Explanation:

ā          # Push a list in the range [1, (implicit) input-length]
           # (without popping the input itself)
 2.Π      # Get all partitions of two parts of this list
           # (note: this also contains partitions with empty parts, but that doesn't
           #  matter, since the second filter also takes care of those)
    ʒ   }  # Filter out partitions where the first item of the first part is larger
           # than the first item of the second part, by:
     D{    #  Sorting the two parts of a copy (based on their first items)
       Q   #  Check that the partition and sorted partition are still the same
<          # Now decrease the values of each remaining partition by 1
 ʒ    }    # Filter out partitions where the sink and source are in the same part, by:
  Z        #  Getting the flattened maximum (without popping)
   %       #  Modulo this maximum on each value,
           #  this causes this maximum (the sink) to become 0 as well
    P      #  Take the product of both partitions (empty parts become 1)
     Ë     #  And check that both products are the same (thus both 0)
ε        } # Now that we have all valid cuts left, we map the partitions to:
 н         #  Get the first part of the current partition
  è        #  Index its values into the (implicit) input-matrix
   ø       #  Zip/transpose; swapping rows/columns
    yθ     #  Get the last part of the current partition
      è    #  Index its values into this transposed list of lists
       ˜O  #  And get the flattened sum
ß          # After the map: pop and push the minimum
           # (after which it is output implicitly as result)

Try it online to see a step-by-step input to output process.

Answer 4

Jelly, 24 bytes

JṖŒPỊẸ$Ƈ,ḟ@Œp;U$ʋ€Jœị⁸§Ṃ

A monadic Link accepting a list of lists of non-negative integers (an adjacency matrix), which yields the maximal flow integer.

Try it online! Or see the test-suite.

How?

Implements the minimum-cut maximal-flow method.

JṖŒPỊẸ$Ƈ,ḟ@Œp;U$ʋ€Jœị⁸§Ṃ - Link: adjacency matrix, A (n by n)
J                        - range of length (A) -> [1,2,3,...,n]
 Ṗ                       - pop -> [1,2,3,...,n-1]
  ŒP                     - power-set (all posible selections)
       Ƈ                 - keep only those for which:
      $                  -   last two links as a monad:
    Ị                    -     insignificant (true for 1, false for 2,3,...)
     Ẹ                   -     any? (i.e. only the selections containing a 1)
                 €       - for each:
                  J      -   with range of length (A) as the right argument of
                ʋ        -   last four links as a dyad - i.e. f(selections, J)
          @              -     with swapped arguments:
         ḟ               -       filter discard those from (J) which are in (selection)
        ,                -     (selection) pair (that) - i.e. a cut
           Œp            -     Cartesian product - i.e. all pairs of nodes where lines
                                                   could be present across this cut
               $         - last two links as a monad:
              U          -   reverse each
             ;           -   concatenate (giving us the pairs of nodes in both orders)
                     ⁸   - chain's left agument, A
                   œị    - (pair) multi-dimensional index into (A) (vectorises)
                      §  - sum each resulting list of weights
                       Ṃ - minimum