Release date: 21 June 2014
Support for Python 3.1 is dropped in this release.
Completely rewritten maximum flow and flow-based connectivity algorithms with backwards incompatible interfaces
Community graph generators
Stoer–Wagner minimum cut algorithm
Linear-time Eulerian circuit algorithm
Linear algebra package changed to use SciPy sparse matrices
Algebraic connectivity, Fiedler vector, spectral ordering algorithms
Link prediction algorithms
Goldberg–Radzik shortest path algorithm
Semiconnected graph and tree recognition algorithms
The flow package (
networkx.algorithms.flow) is completely rewritten
with backward incompatible changes. It introduces a new interface to flow
algorithms. Existing code that uses the flow package will not work unmodified
with NetworkX 1.9.
We added two new maximum flow algorithms (
shortest_augmenting_path) and rewrote the Edmonds–Karp algorithm in
flow_fulkersonwhich is now in
edmonds_karp. @ysitu contributed implementations of all new maximum flow algorithms. The legacy Edmonds–Karp algorithm implementation in
ford_fulkersonis 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_flowdocumentation for the details on the conventions that NetworkX uses for defining a residual network.
We removed the old
min_cutfunctions. The main entry points to flow algorithms are now the functions
minimum_cut_value, which have new parameters that control maximum flow computation:
flow_funcfor specifying the algorithm that will do the actual computation (it accepts a function as argument that implements a maximum flow algorithm),
cutofffor suggesting a maximum flow value at which the algorithm stops,
value_onlyfor stopping the computation as soon as we have the value of the flow, and
residualthat 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_pushalgorithm can stop after the preflow phase without computing a maximum flow if we only need the flow value, but both
shortest_augmenting_pathalways compute a maximum flow to obtain the flow value.
The new function
minimum_cutreturns the cut value and a node partition that defines the minimum cut. The function
minimum_cut_valuereturns only the value of the cut, which is what the removed
min_cutfunction used to return before 1.9.
The functions that implement flow algorithms (i.e.,
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
MultiDiGraphand disconnected networks.
Below are some small examples illustrating how to obtain the same output than in NetworkX 1.8.1 using the new interface to flow algorithms introduced in 1.9:
>>> import networkx as nx >>> G = nx.icosahedral_graph() >>> nx.set_edge_attributes(G, 'capacity', 1)
With NetworkX 1.8:
>>> flow_value = nx.max_flow(G, 0, 6) >>> cut_value = nx.min_cut(G, 0, 6) >>> flow_value == cut_value True >>> flow_value, flow_dict = nx.ford_fulkerson(G, 0, 6)
With NetworkX 1.9:
>>> from networkx.algorithms.flow import (ford_fulkerson, preflow_push, ... edmonds_karp, shortest_augmenting_path) >>> flow_value = nx.maximum_flow_value(G, 0, 6) >>> cut_value = nx.minimum_cut_value(G, 0, 6) >>> flow_value == cut_value True >>> # Legacy: this returns the exact same output than ford_fulkerson in 1.8.1 >>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6, flow_func=ford_fulkerson) >>> # We strongly recommend to use the new algorithms: >>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6) >>> # If no flow_func is passed as argument, the default flow_func >>> # (preflow-push) is used. Therefore this is the same than: >>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6, flow_func=preflow_push) >>> # You can also use alternative maximum flow algorithms: >>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6, flow_func=shortest_augmenting_path) >>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6, flow_func=edmonds_karp)
The flow-based connecitivity and cut algorithms from the connectivity
networkx.algorithms.connectivity) are adapted to take
advantage of the new interface to flow algorithms. As a result, flow-based
connectivity algorithms are up to 10x faster than in NetworkX 1.8 for some
problems, such as sparse networks with highly skewed degree distributions.
A few backwards incompatible changes were introduced.
The functions for local connectivity and cuts accept now arguments for the new parameters defined for the flow interface:
flow_funcfor defining the algorithm that will perform the underlying maximum flow computations,
residualthat accepts as argument a residual network to be reused in repeated maximum flow computations, and
cutofffor defining a maximum flow value at which the underlying maximum flow algorithm stops. The big speed improvement with respect to 1.8 comes mainly from the reuse of the residual network and the use of
We removed the flow-based local connectivity and cut functions from the base namespace. Now they have to be explicitly imported from the connectivity package. The main entry point to flow-based connectivity and cut functions are the functions
minimum_node_cut. All these functions accept a couple of nodes as optional arguments for computing local connectivity and cuts.
We improved the auxiliary network for connectivity functions: The node mapping dict needed for node connectivity and minimum node cuts is now a graph attribute of the auxiliary network. Thus we removed the
mappingparameter from the local versions of connectivity and cut functions. We also changed the parameter name for the auxuliary digraph from
We changed the name of the function
all_pairs_node_connectivity. This function now returns a dictionary instead of a NumPy 2D array. We added a new parameter
nbunchfor computing node connectivity only among pairs of nodes in
stoer_wagnerfunction is added to the connectivity package for computing the weighted minimum cuts of undirected graphs using the Stoer–Wagner algorithm. This algorithm is not based on maximum flows. Several heap implementations are also added in the utility package (
networkx.utils) for use in this function.
BinaryHeapis recommended over
PairingHeapfor Python implementations without optimized attribute accesses (e.g., CPython) despite a slower asymptotic running time. For Python implementations with optimized attribute accesses (e.g., PyPy),
PairingHeapprovides better performance.
Other new functionalities#
dispersonfunction is added in the centrality package (
networkx.algorithms.centrality) for computing the dispersion of graphs.
A community package (
networkx.generators.community) is added for generating community graphs.
is_semiconnectedfunction is added in the connectivity package (
networkx.algorithms.connectivity) for recognizing semiconnected graphs.
eulerian_circuitfunction in the Euler package (
networkx.algorithm.euler) is changed to use a linear-time algorithm.
non_edgesfunction in added in the function package (
networkx.functions) for enumerating nonexistent edges between existing nodes of graphs.
The linear algebra package (
networkx.linalg) is changed to use SciPy sparse matrices.
spectral_orderingare added in the linear algebra package (
networkx.linalg) for computing the algebraic connectivity, Fiedler vectors and spectral orderings of undirected graphs.
A link prediction package (
networkx.algorithms.link_prediction) is added to provide link prediction-related functionalities.
Write Support for the graph6 and sparse6 formats is added in the read/write package (
goldberg_radzikfunction is added in the shortest path package (
networkx.algorithms.shortest_paths) for computing shortest paths using the Goldberg–Radzik algorithm.
A tree package (
networkx.tree) is added to provide tree recognition functionalities.
A context manager
reversedis added in the utility package (
networkx.utils) for temporary in-place reversal of graphs.
The functions in the components package (
networkx.algorithms.components) such as
connected_components_subgraphnow return generators instead of lists. To recover the earlier behavior, use
JSON helpers in the JSON graph package (
networkx.readwrite.json_graph) are removed. Use functions from the standard library (e.g.,
Support for Python 3.1 is dropped. Basic support is added for Jython 2.7 and IronPython 2.7, although they remain not officially supported.
Numerous reported issues are fixed.