Main changes¶
- We added two new maximum flow algorithms (preflow_push and shortest_augmenting_path) and rewrote the Edmonds–Karp algorithm in flow_fulkerson which is now in edmonds_karp. @ysitu contributed implementations of all new maximum flow algorithms. The legacy Edmonds–Karp algorithm implementation in ford_fulkerson is still available but will be removed in the next release.
- All maximum flow algorithm implementations (including the legacy ford_fulkerson) output now a residual network (i.e., a DiGraph) after computing the maximum flow. See maximum_flow documentation for the details on the conventions that NetworkX uses for defining a residual network.
- We removed the old max_flow and min_cut functions. The main entry points to flow algorithms are now the functions maximum_flow, maximum_flow_value, minimum_cut and minimum_cut_value, which have new parameters that control maximum flow computation: flow_func for specifying the algorithm that will do the actual computation (it accepts a function as argument that implements a maximum flow algorithm), cutoff for suggesting a maximum flow value at which the algorithm stops, value_only for stopping the computation as soon as we have the value of the flow, and residual that accepts as argument a residual network to be reused in repeated maximum flow computation.
- All flow algorithms are required to accept arguments for these parameters but may selectively ignored the inapplicable ones. For instance, preflow_push algorithm can stop after the preflow phase without computing a maximum flow if we only need the flow value, but both edmonds_karp and shortest_augmenting_path always compute a maximum flow to obtain the flow value.
- The new function minimum_cut returns the cut value and a node partition that defines the minimum cut. The function minimum_cut_value returns only the value of the cut, which is what the removed min_cut function used to return before 1.9.
- The functions that implement flow algorithms (i.e., preflow_push, edmonds_karp, shortest_augmenting_path and ford_fulkerson) are not imported to the base NetworkX namespace. You have to explicitly import them from the flow package:
>>> from networkx.algorithms.flow import (ford_fulkerson, preflow_push,
... edmonds_karp, shortest_augmenting_path)
- We also added a capacity-scaling minimum cost flow algorithm: capacity_scaling. It supports MultiDiGraph and disconnected networks.