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

[Arun Reddy Kandoor]

(forgot to add lemon user in cc)

---------- Forwarded message ----------

HI Alpar,

Many thanks for your solution. You phrased the problem correctly and I have
started working using the directions given in the second method.

     * 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)

Also, Is there an example file for my reference which uses a preflow class
for undirected graphs? It would help me a lot if you have any.

Thanks,
Arun


On Fri, Oct 22, 2010 at 7:33 AM, Alpár Jüttner <alpar at cs.elte.hu> wrote:

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


-- 
Arun



-- 
Arun
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20101022/746a42a2/attachment.html>