#algorithm discussion continued
Today we continue reading the flow networks. We were looking at maximum flows

Maximum flows can also be calculated using "push-relabel" method. This method works in a more localized manner than Ford Fulkerson method. It works on one vertex at a time, looking only at the vertex's neighbour in the residual network. Thus it avoids examining the entire residual network to find an augmenting path. Also, they do not maintain flow conservation. Instead they maintain a preflow property which goes to say that the total flow into a vertex may exceed the flow out.

 Each vertex has an outflow pipe leading to an arbitrarily large reservoir that can accumulate fluid. In addition, each vertex, it's reservoir, and all its pipe connections sit on a platform whose height increases as the algorithm progresses. The height is used to push fluids only downhill which means from a higher vertex to a lower vertex even though there may be flows from a lower vertex to a higher vertex that may be positive.

The only outgoing flow from a vertex u that is not already saturated with flow are those that connect to vertices at the same level or at a higher level. In order to make a flow outbound from u we relabel it by pushing it one unit higher than its neighbors. This helps us rid an overflowing vertex u of its excess flow. By repeating this iteratively we get maximum flow.

The proof to show that preflow under such conditions becomes maximum will be discussed shortly.

This method performs two basic operations: pushing flow excess from a vertex to one of its neighbors and relabeling a vertex.

#codingexercise

Void getkthfirst(node head, int k, ref int count, ref node kthfirst)

{

If (head == null) return;

count = count + 1;

if (count==k) { kthfirst = head; return;}

Getkthfirst(head.next, k, ref count, ref kthfirst);

}

Bool isEqual(node tree1, node tree2)
{
if (tree1 == null && tree2 == null) return true;
if (tree1 == null || tree2 == null) return false:
if(tree1.data != tree2.data) return false;
Return isEqual(tree1.left, tree2.left) && isEqual(tree1.right, tree2.right);
}

If we define G as graph (V, E) with source s and sink t with a preflow f and a height function h, then if h(u) >= h(v) + 1, then (u,v) is not an edge in the residual network