On 20.11.2014 19:47, LearnedByError wrote: > 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> > > 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> > , 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?
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 -- Tiago de Paula Peixoto <[email protected]>
signature.asc
Description: OpenPGP digital signature
_______________________________________________ graph-tool mailing list [email protected] http://lists.skewed.de/mailman/listinfo/graph-tool
