===========================================================================
CSC 373H1 / L0101      Tutorial Notes -- Week  7           Spring 2012
===========================================================================

Note to myself: residualGraph.pdf final2008F_q5.pdf


PART I. "Question 5"

Introduce the problem in a previous final exam, as given in final2008F_q5.pdf.
You can rephrase it more simply as:
 
Suppose G = (V, E, c) is a network flow problem with a maximum flow f.
Let e_0 \in E be an edge with f(e_0) = c(e_0) > 0.
Consider G' = (V, E, c') where c'(e) = c(e) for all e in E\{e_0}, and
c'(e_0) = c(e_0) - 1.
Given f and the residual graph G_f, describe an efficient algorithm for 
updating the maximum flow f to form a maximum flow for G'.

For example, consider the flow problem shown in residualGraph.pdf.  
The residual graph for a maximal flow is shown on p.3 (labelled p.7).  
Consider the edge e_0 = (5, 4), which is saturated with flow 6.
 
Note: The students have this flow graph on the last page
of the slides linked by, "Demo: Ford-Fulkerson Method" on the
course homepage.
 
One Key Idea: To solve this problem, we first need to remove one unit of 
flow from f(e_0), say e_0 = (u,v) to recover a feasible flow.
Therefore, we also need to remove one unit of flow from some v-t path, 
and one unit from some s-u path. 
 
What are suitable s-u and v-t paths?  Well they better have
at least one unit of flow on them... so they must be reverse
edges in the residual graph. Eg we can use a u to s path,
and a t to v path in G_f. 

Note these paths had better not have cycles in them... since we 
plan on reducing the flow by one for every edge in the path... 
and if we do this more than once for any given edge we may make 
the updated flow negative.

To find suitable paths we need to remember breadth first 
search (from CSC263) (which will avoid having cycles).

================
PART II

Briefly Review BFS (if necessary):

Breadth first search (BFS).
 Given a directed graph G = (V, E) and a start vertex z \in V
 BFS computes the tree of shortest paths (in the sense of number of 
 edges) from z to any reachable vertex v in G. This tree is composed
 of edges (u.prev, u) (for v unreachable from z, and v = z itself, 
 we have v.prev = null).

 Set v.visited = false and v.prev = null for all vertices v in V
 q = empty queue (a FIFO data structure)
 z.visited = true
 q.append(z) (z is the start vertex)
 while not q.empty()
   %LI: For every vertex u on the queue q u.visited = true, and
   %    either u = z  or u.prev is the second last vertex on a path from z to
   %    u which has the minimal number of edges for any z->u path.
   u = q.dequeue()
   for each edge e = (u,v) in E
     if not v.visited
       v.prev = u
       v.visited = true
       q.append(v)
     end
   end
 end

You can also add the following statement to the loop invariant:

LIplus: The number of edges in the z->u paths is a nondecreasing function
of the vertex u's position in the queue, and this length for the last
item in the queue is no bigger than one plus this length for the first
item in the queue.


Part III

Return to the solution of  "Question 5", where we
were recovering a feasible flow for G'.

Use BFS to find a path from u to s, and path from t to v, in G_f..  
Such a paths must exist in the residual graph since
there is a flow of f(e_0) > 0 on edge e_0 = (u,v).
 
Every edge on these paths must have a capacity in the residual graph 
that is >=1.  For the example with e_0 = (u,v) = (5,4), such a
path u-s path could be (5, 3, s).  And such a t-v path could be (t,4).

Update the flow along these paths by decreasing the 
forward flow by one, and increasing the reverse flow by one.
For the edge e_0, we simply decrease the reverse flow by one
(since the capacity c'(e_0) = c(e_0) - 1, the forward flow stays
at 0).

Sketch the resulting flow.  It is a feasible flow for the graph G'.

Part IV

Is the resulting flow a maximal flow?

Second Key Idea: The resulting flow need not be maximal.

Case 1: If the edge e_0 was part of a min cut, then we have
decreased this cut by one.  And this must be therefore be a 
minimum cut. (The min cut cannot decrease by more than one.)
Since the value of the updated flow has been reduced by exactly
the new flow is a max flow for this case.

Case 2: Edge e_0 is not in a min cut....  hmmm...

This case applies for the edge e_0 = (5,4). A min cut is A = {s, 3} for 
the origninal graph, and this has capacity 19.  It turns out
the new graph G' has a min cut of 19 as well.

For the desired updated flow algorithm, we don't want to check 
whether the edge e_0 is in SOME min cut.  Rather, we simply use 
the updated feasible flow, and the corresponding residual graph G'_f,
and try to find ONE MORE augmenting path (say using BFS). 

The reason it is only one more augmenting path, is that the origninal 
flow had value F, which is equal to the min cut capacity C of the graph.  
The updated flow has value F-1, and the min cut of G' is either C or C-1 
(= F or F-1).  In Case 2 the min cut capacity remains the same, so
our updated flow is NOT maximal.

Therefore, in the correct algorithm, after updating the flow to be 
feasible, we need to search for one more augmenting path from s to t 
in the residual graph G_f'.  (Use BFS.) 
 
If we find such a path, we were in case 2, if we don't, we were in case 1.
Either way, we get the max flow.
 
In the current case, we get the augmenting path (s,3,5,2,4,t), and
the max flow has value 19, the same as the orignal flow.

Nasty question.

=====

If there is time, consider attempting to efficiently update a max flow when
the capacity of one edge e_0 is increased by one.

(It is easier... Simply update that edge in the residual graph,
and check for an augmenting s-t path in the new residual graph.
The min cut can increase by either zero or one, so at most we 
will only find one such augmenting path.)