maxflow - Proportionality constraint for multiple sources

graph-tool
#1

I am investigating using maxflow to calculate the max flow from multiple
sources based upon network constraints. Is there a way to insure that all
nodes upstream of a constraint are reduced proportionately instead of having
the constraint being honored by reducing the flow on just the minimum number
of nodes needed to meet the constraint value.

Consider the following directed graph:
<http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/file/n4025881/Network-01.png&gt;

When I calculate the maxflow with the attached program gt-test001.py
<http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/file/n4025881/gt-test001.py&gt;
, I receive the following results (minus the super nodes and reformatted for
clarity).

max flow = 39.0
E6 = 8.0
E7 = 8.0
E8 = 11.0
E9 = 12.0
E10 = 16.0
E11 = 21.0
E12 = 39.0

However, the treatment that I am looking for results in:
max flow = 39.0
E6 = 7.53
E7 = 8.47
E8 = 11.0
E9 = 12.0
E10 = 16.0
E11 = 21.0
E12 = 39.0

In this case V1 and V2 can deliver 17 but is restricted to 16 by E10 on the
outbound side of V3. I want to reduce V1 & V2 proportionately to their
capacity such that

E6 = (Capacity of E10) * (Capacity of E6)/((Capacity of E6) + (Capacity of
E7))
E6 = 16 * (8/(8+9)) = 7.53

And similarly:

E7 = (Capacity of E10) * (Capacity of E7)/((Capacity of E6) + (Capacity of
E7))
E7 = 16 * (9/(8+9)) = 8.47

I can implement this using a Linear Programming solver like glpk by adding
explicit constraints that enforce the proportionality between E6 & E7.

How should I model this when using a graph model?

Thanks in advance for your help and your tolerance of my ignorance :slight_smile:

lbe

#2

Unfortunately, this is not possible with the current algorithms
implemented in the library. Constrained max-flow is a whole different
beast, which requires different approaches.

The algorithms implemented are guaranteed to compute the correct maximum
flow, and provide *one* possible distribution of the residuals. You are
on your own to find alternative ones.

However in your case it does not seem very difficult to change things a
posteriori: You can always redistribute the flows among the sources in
any way, as long as the remaining edges are not affected.

Best,
Tiago