Given a digraph G with weights on all links.   Weights=natural numbers.

In the structure of G there are no directed loops. 

But there are two special nodes.
Material will enter G through a node, called ENTRY NODE and leave G through another  node, called EXIT NODE.
Only the entry node has a pseudolink to it from an infinite capacity source. The pseudolink is NOT part of G. All other nodes  have incoming links that belong to G.
Only the exit node has a pseudolink from it to an infinite capacity sink. The pseudolink is NOT part of G. All other nodes  have outgoing links that belong to G.

Let Nnodes = the number of nodes in G.
Labels assigned to all nodes in G, with 1 assigned to the entry node, and Nnodes assigned to exit node. All other nodes (INTERIOR NODES) receive labels between 2 and Nnodes-1.

Let Nlinks = the number of links in G.
There are two arrays A[1],..., A[Nlinks] and B[1],...,B[Nlinks] such that for each natural number K, 0<K<=Nlinks,
 A[K]->B[K] is a link in G.  (K is an invisible natural number label assigned to each link.)
In addition, A[0] = Nlinks, B[0] = Nnodes, A[Nlinks+1] = B[Nlinks+1] = 0 for computer use.
Therefore, for any nodes I,J in G,  I->J is a link if and only if there exists a unique natural number K<=Nlinks such that
I=A[K] and J=B[K].
 
In addition, a third array W[1],...,W[Nlinks] contains the weights, W[K] is the weight on link A[K]->B[K]. The weight W[K] is also called the CAPACITY of link A[K]->B[K].   CAP[K] = W[K]  (renaming)

In addition, a fourth array FL[1],..,FL[Nlinks] is a dynamic flow of material through the links (imagine water through pipes)

Condition [1]:  for all links, flow through any link <= capacity of that link,
      0<= FL[K]<=W[K] for every natural number K<=Nlinks.

Note: FL[K] is dynamic and may change during discussion of G, but W[K] never changes, and comes with G as fixed data.

Condition [2]: for any node H, total flow into H = total flow out of H:   Tin = Tout.

Let Tin = total flow into H:   (subprogram)
  Tin=0; for (K=1...Nlinks) if (B[K]==H) Tin=Tin + FL[K];
Let Tout = total flow out of H:  (subprogram)
  Tout=0; for (K=1...Nlinks) if (A[K]==H] Tout=Tout + FL[K];


A flow of material will enter the entry node (with label 1), flows through the graph, and leaves the graph at the exit node (with label Nnodes).
TASK: determine the maximum flow that can enter and leave the graph.
The excess of any greater flow would spill over at the entry node.

A fifth array D[1], ..., D[Nlinks] gives the difference between capacity of a link and the flow in that link:
   D[K] = W[K] - FL[K]  for link K.
D[K] is also dynamic because FL[K] is dynamic. It is always a non-negative integer: D[K] >= 0.
A link is saturated if the flow through it is equal to the capacity: FL[K]=W[K]. 
 Link K is saturated if and only if D[K]=0. 


Theorem In a digraph with directed links with weights, the flow from the entry node (through the graph) to the exit node is equal to the sum of the flows in the links from nodes in any subset S containing the entry node to the complement S' containg the exit node minus the sum of the flows in the links from nodes in S' to nodes in S.

Think of a boundary existing between S and S', cutting across links.  The net flow in all those links = flow from entry node to exit node.

The CAPACITY of a cut pair S,S' is the sum of all the capacities of links joining nodes in S to nodes in S' (not the reverse links).  The flow from entry node to exit node <= the capacity of the cut.

 Total flow = flow from entry node to exit node.

Theorem ((Max-flow, Min-Cut) In a digraph with directed links with integer weights, the maximum flow from entry node to exit node is equal to the minimum value of the capacities of all the cuts in the network.

for K=1 to Nlinks, A[K]->B[K] are all the links.  W[K] = capacity of each link,  FL[K] = actual flow through the link

for all H , 1<=H<=Nnodes, S[H]=1 if and only if H is in subset S, otherwise S[H]=0 if H is not in S.

CutCap(S) = sum of all capacities of links from nodes in S to nodes in S' 


 CapMat[I][J] = Capacity of link I->J, else 0 of no link from I to J exists (or link exists but is closed Capacity=0)


Define a subset S of nodes 1,...,N as follows:
[0]  1 is in S
[1]  if    I is in S   and   flow in link  I-->J  is less than capacity,   then   J is in S
[2]  if   I is in S and flow in link J<--I is greater than 0   then   J is in S.

Case I    N is in S.
  Then the flow in every link from S to S' is equal to the capacity of that link   (rule [1]).
  Also, there is no flow in any link from S' to S  (rule [2])


A directed link in a path from entry node to exit node is FORWARD if motion along the path from entry to exit nodes goes from tail to head of the link. It is BACKWARD if motion goes from head to tail.

A path from entry node to exit node is an AUGMENTING PATH if it contains no saturated links in the forward direction, and no empty links in the reverse direction.


A flow from entry node to exit node is maximum  if and only if  there is no flow-augmenting path from entry node to exit node.