Ford-Fulkerson
[[Category:Max-Flow]
General Information
Algorithmic problem:Max-Flow Problems Prerequisites: Type of algorithm: loop
Auxiliary data: A pointer p of type "pointer to a B-tree node".
Abstract View
Invariant: Before and after each iteration:
- p points to some node N of the B-tree and
- the searched key is in the range of N.
Variant: p is redirected from the current node N to some child of the current node.
Break condition:
- p points to a leaf of the B-tree or (that is, inclusive-or)
- the searched key is in the node to which p points.
Induction Basis
Abstract view: p is initialized so as to point to the root of the B-tree.
Implementation: Obvious.
Proof: Obvious.
Induction Step
Abstract view: Find a flow-augmenting path and increase [math]\displaystyle{ f }[/math] along this path by the maximal value such that the flow value of each [math]\displaystyle{ a\in A }[/math] remains in the interval [math]\displaystyle{ [0...c(a)] }[/math].
Implementation:
- Apply a graph traversal algorithm from [math]\displaystyle{ s }[/math] as follows:
- if [math]\displaystyle{ f(v,w)\lt c(v,w) }[/math], [math]\displaystyle{ (v,w)\in A }[/math] can be used for going forward in the direction [math]\displaystyle{ v \rightarrow w }[/math];
- if [math]\displaystyle{ f(v,w)\gt 0 }[/math], [math]\displaystyle{ (v,w)\in A }[/math] can be used for going forward in the direction [math]\displaystyle{ w\rightarrow v }[/math]; .
- Terminate this graph traversal once either is seen or all reachable nodes were seen (whatever occurs first).
- In the latter case, the break condition of the loop applies.
- Otherwise,
- let [math]\displaystyle{ p }[/math] denote the current path of the traversal (which is an [math]\displaystyle{ (s,t) }[/math]-path in this case);
- let [math]\displaystyle{ x }[/math] denote the minimum of the values [math]\displaystyle{ c(a)-f(a) }[/math] on all forward arcs of [math]\displaystyle{ p }[/math];
- let [math]\displaystyle{ y }[/math] denote the minimum of the values [math]\displaystyle{ f(a) }[/math] on all backward arcs of [math]\displaystyle{ p }[/math].
- For each arc [math]\displaystyle{ a \in A }[/math] on [math]\displaystyle{ p }[/math], increase the flow value by [math]\displaystyle{ min{x,y} }[/math] if [math]\displaystyle{ a }[/math] is a forward arc on [math]\displaystyle{ p }[/math], otherwise, decrease the flow value by [math]\displaystyle{ min{x,y} }[/math].
Correctness: If the graph traversal does not hit [math]\displaystyle{ t }[/math], the break condition is fulfilled, so nothing is to show. So consider the case that the graph traversal does hit [math]\displaystyle{ t }[/math]. Then [math]\displaystyle{ p }[/math] is an [math]\displaystyle{ (s,t) }[/math]-path. By definition of [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math], the capacity constraints are preserved. To see that the flow conservation conditions are preserved as well, only the internal nodes [math]\displaystyle{ p }[/math] of are relevant. Let [math]\displaystyle{ v }[/math] be such an internal node, and let [math]\displaystyle{ u }[/math] and [math]\displaystyle{ w }[/math] denote the immediate predecessor and successor of [math]\displaystyle{ v }[/math] on [math]\displaystyle{ p }[/math], respectively. Basically, there are four cases:
- Either [math]\displaystyle{ (u,v) }[/math] is on [math]\displaystyle{ p }[/math] as a forward arc or [math]\displaystyle{ (v,u) }[/math] is on [math]\displaystyle{ p }[/math] as a backward arc.
- Either [math]\displaystyle{ (v,w) }[/math] is on [math]\displaystyle{ p }[/math] as a forward arc or [math]\displaystyle{ (w,v) }[/math] is on [math]\displaystyle{ p }[/math] as a backward arc.
It is easy to check preservation of the flow conservation conditions for each of these four cases.
Pseudocode
B-TREE-FIND(x,k)
1 i = 1
2 while i ≤ x.n and k > x.keyi
3 i = i + 1
4 if i ≤ x.n and k == x.keyi
5 return (x.i)
6 elseif x.leaf
7 return NIL
8 else DISK-READ(x.ci)
9 return B-TREE-FIND(x.ci,k)
Complexity
Statement: The asymptotic complexity is in [math]\displaystyle{ \Theta(\log n) }[/math] in the worst case.
Proof: Follows immediately from the fact that the height of B-tree with n nodes is in [math]\displaystyle{ \Theta(\log n) }[/math] (cf. the remark clause of the B-Trees page).