calculating excess flow and overflowing in max flow algorithm

Question

I am reading push flow algorithms at following link.

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxflowPushRelabel

It is mentioned that Excess Flow - We define the excess flow e as e(u) = f(V,u), the net flow into u. A vertex u ∊ V-{s,t} is overflowing / active if e(u) > 0.

I am looking for example with simple flow network how do we calculate e(u) ?

Thanks for your time and help.

Answer 1

In the diagram below there is a source node (S), a sink node (T), and an internal node (A).

The numbers give the flow (say in litres per second). There are 3 litres per second entering A, but only 1 litre per second leaving A, so the excess flow for A is 2.

Note

1. In a push-relabel algorithm, the excess flow for internal nodes cannot be negative. In other words, you are not allowed to have more flow leaving than enters.

2. The source node is allowed to generate flow (it does not count as an internal node so note 1 does not apply)

3. During the algorithm, the excess flow is reduced until at the end all vertices have 0 excess flow

4. You could compute the excess flow by adding up all incoming flow, and subtracting all outgoing flow.

5. However, in practice, the algorithm maintains an array of excess flows and updates the value as the algorithm progresses.