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

The relabel to front algorithm maintains a list of the vertices in the network. It starts from the front and scans the list repeatedly selecting an overflowing vertex u and then removing the excess at that vertex. The push and relabel operations happen as usual in the push-relabel-algorithm until u has no positive excess. On relabeling a vertex, it is moved to the front and the algorithm begins its scan again.

This algorithm works on admissible edges which are edges in the residual network through which flow can be pushed. In such case, cf(u,v) > 0 and h(u) = h(v) + 1 otherwise (u,v) is inadmissible

Another property can be stated this way: 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. If a vertex u is overflowing and there are no admissible edges leaving u, then relabel of the vertex u applies. After this operation, there is at least one admissible edge leaving u but there are no admissible edges entering u. Recall that an admissible edge is one where we can push flow and its not saturated yet. Also the relabel operation applies to a vertex that is overflowing and to an edge that is upwards or at same level and by definition, there must be one edge outbound from u so that the flow occurs and the height of u increases. Relabel gives u the greatest height allowed by the constraints on heights function. Initially there was no admissible edges leaving u and consequently no push possible and that was why the relabel occurred.After the relabel the height of u is adjusted to be one unit higher than the a minimum v and hence one outbound edge. At this time there are no admissible edges entering u because if it were the destination vertex v would be higher than one level over height of u before the relabel and we know already there are no residual edges between vertices whose heights differ by 1. Also relabel does not change the residual network. Therefore the property that there are at least one admissible edge leaving u but there are no admissible edges entering u.

#codingexercise

Given two rectangles, find whether they are overlapping or not?
static bool intersects(Rectangle r1, Rectangle r2)
{
bool isdisjoint = false;
// are  they disjoint along x axis ?
if (r1.tl.x < r2.tl.x)
   isdisjoint = r1.br.x < r2.tl.x;
else
  isdisjoint = r2.br.x < r1.tl.x;
if (isdisjoint == true) return false;

// are they disjoint along y-axis ?
if (r1.br.y < r2.br.y)
   isdisjoint = r1.tl.y < r2.br.y;
else
  isdisjoint = r2.tl.y < r1.br.y;
return isdisjoint == false;
}
https://d.docs.live.net/d609fb70e39b65c8/AppInfrastructure.doc