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? Thanks in advance for your help and your tolerance of my ignorance :) lbe -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/maxflow-Proportionality-constraint-for-multiple-sources-tp4025881.html Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com. _______________________________________________ graph-tool mailing list [email protected] http://lists.skewed.de/mailman/listinfo/graph-tool
