We were discussing skip graphs yesterday. Graphs also come useful in visualizing flow networks
Flow networks can model many problems, including liquids through pipes, parts through assembly lines and information through communication networks.
Each directed edge can be considered a conduit with a stated capacity. Vertices are conduit junctions. One may be a source another may be a sink. The total amount of flow entering a vertex must be the same as the outgoing.  This is called flow conservation.
One of the most talked about problems with flow networks is to maximize the flow where we compute the greatest rate at which we can ship material from source to sink without violating any capacity constraints.
Denoting the flow f as a non-negative quantity f(u,v) from vertex u to vertex v. The absolute value of f is defined as the sum of flows f(s,v) - the sum of flows f(v,s). The second component involving the sum f(v,s) is usually zero.
Generally for a flow network, the edges are directed. If an edge (v1,v2) belongs to the set of edges E, then edge (v2, v1) should not belong to the edges E. If they exist they are called antiparallel edges. If a flow network has antiparallel edges, it is transformed to one without any.
A maximum flow problem may have several sources and sinks. Fortunately, this is no harder than an ordinary maximum flow problem with a single source and a sink. We just need to add an imaginary supersource and an imaginary supersink and directed edges with infinite capacity to each of the source and from each of the sink.



#puzzle
A king divides his fifteen elephants among his three sons such that the first gets half, the send gets three quarters of remaining and the third gets half of remaining. How much does each get?

Let us add an imaginary elephant. Then the first gets 8, the second gets 6 and the last gets one leaving the imaginary one aside.

#codingexercise
Add all the greater values to every node in a BST

void AddGreater(node root, ref int greater)
{
if (root == null) return;
AddGreater(root.right);
greater += root.data;
root.data = greater;
AddGreater(root.right, greater);
}

# Given a histogram in terms of a list of bar heights of unit width, find the maximum water that can be retained between the bars
int GetRetention(List<int>h, int n)
{
var left = new int[n]{};
var right = new int[n]{};
int held = 0;

left[0] = h[0];
for (int i = 1; i < n; i++)
   left [i] = max(left[i-1], h[i]);

   right[n-1] = h[n-1];
    for (int i = n-2; i >= 0; i--)
       right[i] = max(right[i+1], h[i]);

for (int i =0; i < n; i++)
    held += min(left[i], right[i]) - h[i];

return held;
}