[Lemon-user] Path decomposition and identification of flows

[Dimitris Paraskevopoulos]

Dear all,

May I refer to the query below:
http://lemon.cs.elte.hu/pipermail/lemon-user/2010-October/000287.html
...and ask you what if we had a flow that starts from s, and before reaching t, has split and follows two parallel paths for a while and then meets at t.

For example, lets say we have a flow of 10 units from node 1 to node 7. Here are some possible flows:

Node 1 -Node 2: 10 units flow. then:
Node 2-Node 3: 5 units
Node 3-node 4:5 units
Node 4-Node 7:5 units and...

Node 2-Node 6:5 units
Node 6-Node 7:5 units

With 2-3-4-7 and 2-6-7 two parallel paths that start from Node 2 and end at node 7.

Will the following procedure (posted by Alp?r) identify the parallel flows of this commodity?

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

As with the case of Aran (link given above), I have different commodity flows with s-t and k, and I would like to know which arcs were used by each commodity, when solving the MCF.

Any solution that would solve my problem, is greatly appreciated.

Many thanks!

Dimitris
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20150401/1b6e9b0e/attachment.html>