(forgot to add lemon user in cc)<br><br><div><div class="gmail_quote">---------- Forwarded message ----------<br><br>HI Alpar,<div><br></div><div>Many thanks for your solution. You phrased the problem correctly and I have started working using the directions given in the second method.</div>
<div class="im"><div><br></div><div> * Repeat the following for each destination t.<br>
* Find a maximum s-t flow x_t with y[e] as the capacity of<br> e for each arc e.<br> * Decrease y by x_t. (i.e. y[e]:=y[e]-x_t[e] for each arc<br> e)</div><div><br></div>
</div><div>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. </div><div><br></div><div>Thanks,<br>Arun <div><div></div><div class="h5">
<br><br><div class="gmail_quote">On Fri, Oct 22, 2010 at 7:33 AM, Alpár Jüttner <span dir="ltr"><<a href="mailto:alpar@cs.elte.hu" target="_blank">alpar@cs.elte.hu</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">If I understand you correctly (please tell me if I'm wrong), your<br>
problem is the following:<br>
<br>
(By considering only the part of the solution that originates from a<br>
certain source s), you are given a flow value y[e] for each arc, and y<br>
represents the sum of s-t flows for each t. Then you want to separate<br>
these flows, i.e you want to obtain an s-t flow x_t, such that<br>
x_1+x_3+... = y.<br>
<br>
This problem can be solved by path decomposition:<br>
<br>
* Repeat the following for each destination t.<br>
* Set x_t=0.<br>
* Repeat the following until x_t is of the desired flow.<br>
* Find an s-t path using only those arcs e for<br>
which y[e]>0.<br>
* Determine the min flow value M along this path<br>
* Increase the x_t values along this path by M.<br>
* Decrease the y along this path by M.<br>
<br>
If you want to achieve this with less programming, you can also use the<br>
max-flow algorithm (e.g. the Preflow class) for the decomposition:<br>
<br>
* Repeat the following for each destination t.<br>
* Find a maximum s-t flow x_t with y[e] as the capacity of<br>
e for each arc e.<br>
* Decrease y by x_t. (i.e. y[e]:=y[e]-x_t[e] for each arc<br>
e)<br>
<br>
Regards,<br>
Alpar<br>
<div><div></div><div><br>
On Thu, 2010-10-21 at 15:34 -0400, Arun Reddy Kandoor wrote:<br>
> Hello all,<br>
><br>
><br>
> I have been using lemon for simple graph manipulations and shortest<br>
> path computations before. As part of solving a bigger problem, I am<br>
> faced with a smaller sub problem described below, and was wondering if<br>
> there a way for it using lemon.<br>
> The problem is as follows:<br>
> In an undirected graph with 4 nodes (0,1,2,3) and edges (0-1, 1-2,<br>
> 2-3, 3-1) with capacity of 100 units each, I have a demand of 150units<br>
> to be transferred between 0-1, 50 units between 0-2 and 50 units<br>
> between 1-2 respectively.<br>
><br>
><br>
> Demand matrix between the nodes:<br>
> 0 1 2<br>
> 0 0.0 150 50<br>
> 1 150 0.0 50<br>
> 2 50 50 0.0<br>
><br>
><br>
> I have computed the cumulative flows along each edge using a MIP<br>
> formulation and got the result as below (here Y[a,b,c] means flow<br>
> originating from node 'a' and it's value on edge b-c. ):<br>
> Y[0,0,1] = 100,<br>
> Y[0,0,3] = 100,<br>
> Y[0,3,2] = 100,<br>
> Y[0,2,1] = 50,<br>
> Y[1,1,0] = 100,<br>
> Y[1,1,2] = 100,<br>
> Y[1,3,0] = 50,<br>
> Y[1,2,3] = 50,<br>
> Y[2,3,0] = 50,<br>
> Y[2,2,1] = 50,<br>
> Y[2,2,3] = 50.<br>
><br>
><br>
> By observing the solution above, I can tell that, for the required 150<br>
> units between 0-1, 100 units is sent on 0-1 edge and remaining 50<br>
> units along 0-3,3-2,2-1. And similarly, for the required 50 units<br>
> between 0-2, 50 units is sent on 0-3,3-2, and for the required 50<br>
> units between 1-2, it is sent on edge 1-2.<br>
> But, is there a way one could identify paths for each flow using the<br>
> above resulting cumulative flows? I have tried to think of ways to<br>
> segregate flows one by one, but could not proceed much.<br>
><br>
><br>
> I apologize if I am not clear with my formulation and would be happy<br>
> to clear any queries you may have. Also, please pardon my ignorance,<br>
> if you feel I am stating a much bigger problem.<br>
><br>
><br>
> Thanks & Regards,<br>
> --<br>
> Arun<br>
><br>
</div></div>> _______________________________________________<br>
> Lemon-user mailing list<br>
> <a href="mailto:Lemon-user@lemon.cs.elte.hu" target="_blank">Lemon-user@lemon.cs.elte.hu</a><br>
> <a href="http://lemon.cs.elte.hu/mailman/listinfo/lemon-user" target="_blank">http://lemon.cs.elte.hu/mailman/listinfo/lemon-user</a><br>
<br>
<br>
</blockquote></div><br><br clear="all"><br></div></div>-- <br>Arun <br>
</div>
</div><br><br clear="all"><br>-- <br>Arun <br>
</div>