Ford-Fulkerson: Difference between revisions

Latest revision as of 11:49, 23 June 2015

General information

Algorithmic problem: Max-flow problems (standard version)

Type of algorithm: loop

Abstract view

Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations:

The flow [math]\displaystyle{ f }[/math] is a feasible flow.
If all upper bounds are integral, [math]\displaystyle{ f }[/math] is integral as well.

Variant: The flow value of [math]\displaystyle{ f }[/math] increases.

Break condition: There is no flow-augmenting path.

Induction basis

Abstract view: We start with some feasible flow, for example, the zero flow.

Implementation: Obvious.

Proof: Obvious.

Induction step

Abstract view: Find a flow-augmenting path and increase [math]\displaystyle{ f }[/math] along this path up to saturation. If no path is found, the break condition applies, and the loop is terminated.

Proof: If the graph traversal does not hit [math]\displaystyle{ t }[/math], the break condition is fulfilled, and nothing is to show. So consider the case that the graph traversal does hit [math]\displaystyle{ t }[/math]. Then an [math]\displaystyle{ (s,t) }[/math]-path is found. Augmenting along this path up to saturation preserves feasibility of the flow.

Correctness

Due to the invariant, the flow is feasible before and after each iteration. Termination results from the complexity considerations below. Due to the max-flow min-cut theorem, the break condition implies that the final flow is maximum.

Complexity

Statement: If all capacity values are integral, the asymptotic worst-case complexity is [math]\displaystyle{ \mathcal{O} (m\cdot F) }[/math], where [math]\displaystyle{ m = |A| }[/math] and [math]\displaystyle{ F }[/math] is the maximum total flow value.

Proof: A graph search from [math]\displaystyle{ s }[/math] requires [math]\displaystyle{ \Omicron (m) }[/math] . Obviously, determining [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] and changing the flow values along [math]\displaystyle{ p }[/math] requires [math]\displaystyle{ \mathcal{O}(m) }[/math] as well. It is also evident that, before and after each iteration, the flow values on all arcs are integral. In particular, the total flow value is integral. The variant implies that, in case of integral capacity values, the total flow value increases by at least one unit in every iteration. Since the total flow value is always in the interval [math]\displaystyle{ [0...F] }[/math], this may happen at most [math]\displaystyle{ F }[/math] times.

Remark: The number of nodes is irrelevant because at most [math]\displaystyle{ m }[/math] nodes are reachable from [math]\displaystyle{ s }[/math] (not including [math]\displaystyle{ s }[/math] itself).

@@ Line 1: / Line 1: @@
-[[Category:Max-Flow]
+== General information ==
-[[Category:Algortihms]]
-== 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".
+'''Algorithmic problem:''' [[Max-Flow Problems#Standard version|Max-flow problems (standard version)]] <br>
-== Abstract View ==
+'''Type of algorithm:''' loop<br>
-'''Invariant:''' Before and after each iteration:
-# '''''p''''' points to some node '''''N''''' of the B-tree and
-# the searched key is in the [[Directed Tree#Ranges of Search Tree Nodes|range]] of '''''N'''''.
-'''Variant:''' '''''p''''' is redirected from the current node '''''N''''' to some child of the current node.
+== Abstract view ==
-'''Break condition:'''
+'''Invariant:'''
-# '''''p''''' points to a leaf of the B-tree or (that is, inclusive-or)
+After <math>i \ge 0</math> iterations:
-# the searched key is in the node to which '''''p''''' points.
+# The flow <math>f</math> is a [[basic flow definitions#Feasible flow|feasible flow]].
+# If all upper bounds are integral, <math>f</math> is integral as well.
-== Induction Basis ==
+'''Variant:''' The [[Basic flow definitions#Flow value|flow value]] of <math>f</math> increases.
-'''Abstract view:''' '''''p''''' is initialized so as to point to the root of the B-tree.
+'''Break condition:''' There is no [[Basic flow definitions#Flow-augmenting paths and saturated arcs|flow-augmenting path]].
+== Induction basis ==
+'''Abstract view:''' We start with some feasible flow, for example, the zero flow.
 '''Implementation:''' Obvious.
@@ Line 26: / Line 23: @@
 '''Proof:''' Obvious.
-== Induction Step ==
+== Induction step ==
-'''Abstract view:''' Find a flow-augmenting path and increase <math>f</math> along this path by the maximal value such that the flow value of each <math>a\in A</math> remains in the interval <math>[0...c(a)]</math>.<br>
+'''Abstract view:''' Find a [[Basic flow definitions#Flow-augmenting path|flow-augmenting path]] and increase <math>f</math> along this path up to saturation. If no path is found, the break condition applies, and the loop is terminated.
-'''Implementation:'''
-# Apply a graph traversal algorithm from <math>s</math> as follows:
+'''Proof:''' If the graph traversal does not hit <math>t</math>, the break condition is fulfilled, and nothing is to show. So consider the case that the graph traversal does hit <math>t</math>. Then an <math>(s,t)</math>-path is found. [[Basic flow definitions#Augmenting along a path|Augmenting along this path up to saturation]] preserves feasibility of the flow.
-##if <math>f(v,w)<c(v,w)</math>, <math>(v,w)\in A</math> can be used for going forward in the direction <math>v \rightarrow w</math>;
-##if <math>f(v,w)>0</math>, <math>(v,w)\in A</math>  can be used for going forward in the direction <math> 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>p</math> denote the current path of the traversal (which is an <math>(s,t)</math>-path in this case);
-##let <math>x</math> denote the minimum of the values <math>c(a)-f(a)</math> on all forward arcs of <math>p</math>;
-##let <math>y</math> denote the minimum of the values <math>f(a)</math> on all backward arcs of <math>p</math>.
-##For each arc <math>a \in A</math> on <math>p</math>, increase the flow value by <math>min{x,y}</math> if <math>a</math> is a forward arc on <math>p</math>, otherwise, decrease the flow value by <math>min{x,y}</math>.
-'''Correctness:''' If the graph traversal does not hit <math>t</math>, the break condition is fulfilled, so nothing is to show. So consider the case that the graph traversal does hit <math>t</math>. Then <math>p</math> is an <math>(s,t)</math>-path. By definition of <math>x</math> and <math>y</math>, the capacity constraints are preserved. To see that the flow conservation conditions are preserved as well, only the internal nodes <math>p</math> of  are relevant. Let <math>v</math> be such an internal node, and let <math>u</math> and <math>w</math> denote the immediate predecessor and successor of <math>v</math> on <math>p</math>, respectively. Basically, there are four cases:
+== Correctness ==
-*Either <math>(u,v)</math> is on <math>p</math> as a forward arc or <math>(v,u)</math> is on <math>p</math>  as a backward arc.
-*Either <math>(v,w)</math> is on <math>p</math> as a forward arc or <math>(w,v)</math> is on <math>p</math> as a backward arc.
-It is easy to check preservation of the flow conservation conditions for each of these four cases.
-== Pseudocode ==
+Due to the invariant, the flow is feasible before and after each iteration. Termination results from the complexity considerations below. Due to the [[Max-flow min-cut|max-flow min-cut theorem]], the break condition implies that the final flow is maximum.
-<code>
- B-TREE-FIND(''x,k'')
-''i'' = 1
-'''while''' i &le; ''x.n'' and ''k'' &gt; ''x.key<sub>i</sub>''
-        ''i'' = ''i'' + 1
-'''if''' ''i'' &le; ''x.n'' and ''k'' == ''x.key<sub>i</sub>''
-        '''return''' (''x.i'')
-'''elseif''' '' x.leaf''
-        '''return''' NIL
-'''else''' DISK-READ(''x.c<sub>i</sub>'')
-        '''return''' B-TREE-FIND(''x.c<sub>i</sub>,k'')
-</code>
 == Complexity ==
-'''Statement:''' The asymptotic complexity is in <math>\Theta(\log n)</math> in the worst case.
+'''Statement:''' If all capacity values are integral, the asymptotic worst-case complexity is <math>\mathcal{O} (m\cdot F)</math>, where <math>m = |A|</math> and <math>F</math> is the maximum total flow value.
+'''Proof:''' A graph search from <math>s</math> requires <math>\Omicron (m)</math> . Obviously, determining <math>x</math> and <math>y</math> and changing the flow values along <math>p</math> requires <math>\mathcal{O}(m)</math> as well.
+It is also evident that, before and after each iteration, the flow values on all arcs are integral. In particular, the total flow value is integral. The variant implies that, in case of integral capacity values, the total flow value increases by at least one unit in every iteration. Since the total flow value is always in the interval <math>[0...F]</math>, this may happen at most <math>F</math> times.
-'''Proof:''' Follows immediately from the fact that the height of B-tree with '''''n''''' nodes is in <math>\Theta(\log n)</math> (cf. the remark clause of the [[B-Trees]] page).
+'''Remark:'''
+The number of nodes is irrelevant because at most <math>m</math> nodes are reachable from <math>s</math> (not including <math>s</math> itself).