networmix / netgraph Goto Github PK

Cyclic dict of predecessors (e.g. from BFS) causes calc_graph_cap to loop indefinitely.

Per subj, capacity calculation is terribly broken (algorithm is flawed) - it gives incorrect results for some cases. To make the matters worse, I missed it in the test coverage by expecting incorrect result in the corresponding test.

It would be helpful to add an algorithm for finding bottleneck edges in the graph.
We can define a bottleneck edge as an edge which capacity needs to be increased to increase the max-flow for a given src-dst pair. There will be a number of interesting subtile problems to make this algorithm useful for networking applications (think we would prefer to improve the capacity over the shortest paths, not any paths).

Maybe we should think of applying dimensioning approach instead (LP problem)? We could easily formulate this problem as a set of linear equations and solve them. But this would require runtime dependency on a linear solver.

Adds new shorter paths even if multipath is off

calc_max_flow uses calc_graph_cap function to calculate graph capacity. This function works great when there are no cycles in the supplied dict of predecessors. However, calc_max_flow is calculating predecessors with modified BFS that can return dict of predecessors with cycles.

Need to add _adj alias for successors