Bi-directional (or) Un-directional Edges in Max-Flow

Revision en1, by rsampaths16, 2016-10-27 18:41:12

Generally while modeling Max-Flow problems to solve through Ford Fulkerson we consider edges to be directional. When we consider an edge (A,B), we consider it to be a flow-edge from A -> B. We have to observe that the case of having two directional flow-edges (A,B) and (B,A) is different from have one Bidirectional edge (A,B).

Case (i) We have two Directional edge (A,B) and (B,A). Them being two separate edges they have their own capacities C[A][B] and C[B][A]. As the flow through one edge does not affect capacity of the other, we can model the graph by spliting either of the edges using a third vertex , say C. The edges (A,B) and (B,A) can be transformed into (A,B) , (B,C) and (C,A) where the maximum capacities of (B,C) and (C,A) is the same as that of (B,A). In the implementation we show both the Flow and Residue in the same Adjacency Matrix, and Capacities in another Matrix.

Case (ii) We have an Bidirectional edge (A,B) and through symmetry we would also have the edge (B,A). The problem arises when we take their capacities into consideration. The capacities of (A,B) and (B,A) are always equal ,i.e, they have the same capacity caps (or) flow through one direction obstructs the flow through the other. For these types of edges we can model them as conditionally directed. We can have three separate Matrices in this case, Flow-Matrix : flow, Residue-Matrix : resi, and Capacity-Matrix : capa. Here we set the condition that the direction of the edge is always opposite to that of the Positive Residue. There are two conditions while modeling it this way.

Case (A) When there is no flow through edge (A,B) initially , i.e flow(A,B) = flow(B,A) = resi(A,B) = resi(B,A) = 0 and capa(A,B) = capa(B,A) = max_capa(A,B). Considering positive flow in the direction A -> B , flow(A,B) and resi(B,A) increase while both capa(A,B) and capa(B,A) decreases.

Case (B) When there is a flow in one direction (A,B) initially (say A -> B), i.e flow(A,B) = resi(B,A) = +Z , flow(B,A) = resi(A,B) = 0 and capa(A,B) = capa(B,A) = max_capa(A,B) - flow(A,B). Here there is already an established direction A -> B, and we can observe that the Residue is in the opposite direction. Residue in the same direction resi(A,B) is 0. From these observations we can tell the direction of the edge that is in consideration. Forward when there is Residue in the backward direction, and Backward when there is forward residue.

Condition to check while trying to add flow in A -> B direction

Augment(A,B):
    if capa[A][B]>0 and resi[A][B]==0 : Edge direction is A -> B or there is no direction yet
        Decrease capacity in both directions : capa[A][B]--,capa[B][A]--
        Increase flow in same direction : flow[A][B]++
        Increase residue in reverse direction : resi[B][A]++


    if capa[A][B]>0 and resi[A][B]>0 : Edge direction is B -> A
        Increase capacity in both directions : capa[A][B]++,capa[B][A]++
        Decrease flow in reverse direction : flow[B][A]--
        Decrease residue in same direction : resi[A][B]--

Thank You.

P.S : This is a solution I thought about while solving the problem Total Flow from Spoj. I would appreciate other approaches to these type of cases.

Tags maxflow, ford fulkerson, augmenting path, flow direction

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English rsampaths16 2016-10-27 18:41:12 3503 Initial revision (published)