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

[Alpár Jüttner]

If I understand you correctly (please tell me if I'm wrong), your
problem is the following:

(By considering only the part of the solution that originates from a
certain source s), you are given a flow value y[e] for each arc, and y
represents the sum of s-t flows for each t. Then you want to separate
these flows, i.e you want to obtain an s-t flow x_t, such that
x_1+x_3+... = y.

This problem can be solved by path decomposition:

      * Repeat the following for each destination t.
              * Set x_t=0.
              * Repeat the following until x_t is of the desired flow.
                      * Find an s-t path using only those arcs e for
                        which y[e]>0.
                      * Determine the min flow value M along this path
                      * Increase the x_t values along this path by M.
                      * Decrease the y along this path by M.

If you want to achieve this with less programming, you can also use the
max-flow algorithm (e.g. the Preflow class) for the decomposition:

      * Repeat the following for each destination t.
              * Find a maximum s-t flow x_t with y[e] as the capacity of
                e for each arc e.
              * Decrease y by x_t. (i.e. y[e]:=y[e]-x_t[e] for each arc
                e)

Regards,
Alpar

On Thu, 2010-10-21 at 15:34 -0400, Arun Reddy Kandoor wrote:
> 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 
> 
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user