Sunday, September 11, 2016

#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. we discussed the following lemmas
1) An overflowing vertex can be either pushed or relabeled.

2) Vertex heights never decrease


3) The execution of the generic-push-relabel method on G maintains the attribute h as a height function.




#codingexercise
Void getcount(node head,  ref int count)
{
If (head == null) return;
getcount(head.next, ref count);
Count += 1;
}

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

No comments:

Post a Comment