#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.

We reviewed relabel-to-front algorithm next. This algorithm improves the running time of the maximum flow problem by choosing the order of basic operations carefully and managing the network data structure efficiently.  We saw what admissible edges are. If a vertex u is overflowing and (u,v) is an admissible edge, the push (u,v) applies and while it does not create any new admissible edge, it may cause the edge u,v to become admissible. The admissible edges also applies to relabel operation.

Now we see neighbor lists. Edges in this algorithm are organized into "neighbor lists". Given a flow network G = (V,E), the neighbor list is simply a linked list of vertices v for which there may be a residual edge (u,v).  The relabel to front algorithm cycles through each neighbor list in an arbitrary order that is fixed throughout the execution of the algorithm.

The neighboring vertices are the ones to which the excess flow at u is discharged through admissible edges. This discharge operation includes relabeling to cause edges leaving u to become admissible. As we know relabel operations are performed when push is not possible and this iteration happens for each vertex in the neighboring list. If the relabel happens, the neighboring list is reset and the currently evaluated neighbor points to the head. If the push happens, the current is not changed because this may be repeated. If neigher push nor relabel applies, the current is updated to the next neighbor.

In fact, one of the properties of the discharge operation is that when it calls push, the push applies to (u,v) and when it calls relabel, the relabel applies to (u,v). The relabel only applies when we can show that all the edges leaving u are inadmissible. This depends on the neighbors and their number. If the discharge starts and ends with the head of the list, all the edges are inadmissible.  The list may not be completely traversed as the current is not always updated.

When the list is completely traversed, the calls, the procedure relabels u. This resets the pass and to pass over a neighbor, the edge(u,v) must be deemed admissible. Since the initialization and progress guarantee that each neighbor is evaluated, all the edges leaving u have been deemed inadmissible. At the termination of the pass, push operations do not create admissible edges and the only other operation relabel must have but a relabeled vertex has no entering admissible edges and u is not relabeled. Therefore at the end of the pass, all edges leaving u remain inadmissible.

#codingexercise

Given a BST find the maximum N elements in the tree

List<node> GetMaxN(node root, int N)

{

var inorder = ToInOrder(root);

assert (inorder.Count > N);

return inorder.GetRange(inOrder.Count - N, N).ToList();

}

Another way to do this would be to augment the tree data structure with the rank of the node. The rank informs how the number of elements in the right subtree of the current node. It stands for the number of nodes that have value more than the current. If the rank is N-1, then the current node inclusive and the right subtree are the number of nodes required.

void GetMaxN(node root, int N, ref List<Node> nodes)

{

if (!root) return;

GetMaxN(root.left, N, ref nodes);

if (root.data > N) { GetMaxN(root.right, N, ref nodes); }

else {

nodes.Add(root);

GetMaxN(root.right, N-1, ref nodes);

}

}

The same holds for finding the minimum N elements in the tree

List<node> GetMinN(node root, int N)

{

var inorder = ToInOrder(root);

assert (inorder.Count > N);

return inorder.GetRange(0, N).ToList();

}

Given a binary tree, defining a term “complete path sum” as, sum of values of nodes lying in a path from root to the leaf; Now given a value ‘k’, we have to find the k-heavy path and prune the binary tree i.e. prune/delete nodes for which complete path sum is smaller than k.

node PruneKHeavy(Node root, int K, ref int sum)
{
if (root== null) return;
sum += root.data;
root.left= PruneKHeavy(root.left, K, ref sum);
root.right = PruneKHeavy(root.right, K, ref sum);
if (root.left == null && root.right == null) 
{
if (sum < k ){
Sum -= root.data;
delete root;
root = null;
Return root;
}
}
sum-=root.data;
return root;
}