[Lemon-user] identifying flow ids in a multicommodity flow

[Arun Reddy Kandoor]

Hello all,

I have been using lemon for simple graph manipulations and shortest path
computations before. As part of solving a bigger problem, I am faced with a
smaller sub problem described below, and was wondering if there a way for it
using lemon.
The problem is as follows:
In an undirected graph with 4 nodes (0,1,2,3) and edges (0-1, 1-2, 2-3, 3-1)
with capacity of 100 units each, I have a demand of 150units to be
transferred between 0-1, 50 units between 0-2 and 50 units between 1-2
respectively.

Demand matrix between the nodes:
0 1 2
0 0.0 150 50
1 150 0.0 50
2 50 50 0.0

I have computed the cumulative flows along each edge using a MIP formulation
and got the result as below (here Y[a,b,c] means flow originating from node
'a' and it's value on edge b-c. ):
Y[0,0,1] = 100,
Y[0,0,3] = 100,
Y[0,3,2] = 100,
Y[0,2,1] = 50,
Y[1,1,0] = 100,
Y[1,1,2] = 100,
Y[1,3,0] = 50,
Y[1,2,3] = 50,
Y[2,3,0] = 50,
Y[2,2,1] = 50,
Y[2,2,3] = 50.

By observing the solution above, I can tell that, for the required 150 units
between 0-1, 100 units is sent on 0-1 edge and remaining 50 units along
0-3,3-2,2-1. And similarly, for the required 50 units between 0-2, 50 units
is sent on 0-3,3-2, and for the required 50 units between 1-2, it is sent on
edge 1-2.
But, is there a way one could identify paths for each flow using the above
resulting cumulative flows? I have tried to think of ways to segregate flows
one by one, but could not proceed much.

I apologize if I am not clear with my formulation and would be happy to
clear any queries you may have. Also, please pardon my ignorance, if you
feel I am stating a much bigger problem.

Thanks & Regards,
-- 
Arun
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20101021/b41d8f33/attachment.html>