#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 performs two basic operations: pushing flow excess from a vertex to one of its neighbors and relabeling a vertex.
The Push operation applies only if u is an overflowing vertex, cf(u,v) > 0 and h(u) = h(v) + 1. The push operation updates the preflow f and the excess flows for u and v. It assumes that we can compute residual capacity in constant time given c and f.
All the flow is downward  in the flow network so all the residual edges are at the same level, one level down or upwards. If h(u) is greater than h(v) + 1, then (u,v) is not an edge in the residual network. This is why the original edge (u,v) is also a residual edge because we set h(u) = h(v) + 1 and we try to increase the flow in this direction.
There are two interesting observations on the push operation. First, the push operation does not depend on the heights of u and v. Second, the only qualifying residual edges only exist one level down and therefore no other heights need to be considered.
A push is a saturating push if edge (u,v) in the residual network becomes saturated and a non-saturating push otherwise. This leads to a property that after a nonsaturating push from u to v, the vertex v is no longer overflowing.
The relabel operation applies only if u is overflowing and if u.h is <= v.h for all edges. We relabel an overflowing vertex u if for every vertex v for which there is residual capacity from u to v, flow cannot be pushed from u to v because v is not downhill from u.
def relabel(u):
    u.h = 1 + min([ v.h for v in adjacencies(u)])

The generic push-relabel algorithm uses the following subroutine to create an initial preflow in the flow network

Initialize-Preflow(G,s)
for each vertex v belonging to G.V
     v.h = 0
     v.e = 0
for each edge (u,v) belonging to G.E
    (u,v).f = 0
s.h = |G.V|
for each vertex v belonging to s.Adj
     (s, v).f = c(s, v)
      v.e = c(s,v)
      s.e = s.e - c(s,v)



Now we look into the lemmas
1) An overflowing vertex can be either pushed or relabeled.
This follows from the premise that the push operation only applies to residual edges. In turn these edges (u,v) are those where the h(u) <= h(v) + 1. If the push operation does not apply, that means the h(u) is less than the h(v). Thus a relabel operation applies to u.

2) Vertex heights never decrease
When the push operation happens, we never decrease the height of u.
Whenever a relabel operation applies, its height increases by at least 1.
In the latter case,the  height of u must be less than the height of v for relabeling. Furthermore,
the height is set to one more than the minimum of the heights of all v. So there is no decrease in the height of u.

3) The execution of the generic-push-relabel method on G maintains the attribute h as a height function.
The generic-push-relabel method is as follows:
    Initialize-Preflow(G, s)
    while there exists an applicable push or relabel operation
              select an applicable push or relabel operation and perform it.

The initialize-preflow sets the preflow of all edges with source as the originating vertex to the capacity of those edges and zero otherwise. Also, the height of the source vertex is set to the absolute number of vertices.

Since the initialization is already there, the proof is by induction. If we took a residual edge (u,v) that leaves u, then the relabel operation ensures that u.h <= v.h + 1 afterwards. if the edge was incident on u from say w then
w.h <= u.h + 1 and
w.h < u.h + 1 afterwards. Thus the relabel operation  leaves h as the height function.
In the push operation, the height changes by 1 when the edge is added so the height remains a height function. When the edge is removed, the residual network removes the corresponding constraint and h again remains a height function

#codingexercise

Void getsum(node head,  ref int sum)

{

If (head == null) return;

getsum(head.next, ref sum);

Sum += head.data;

}

Bool islesser(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 islesser(tree1.left, tree2.left) && islesser(tree1.right, tree2.right);
}