## iof-tools / networkxMiCe / networkx-master / doc / release / api_1.9.rst @ 5cef0f13

History | View | Annotate | Download (10.3 KB)

1 |
********************************* |
---|---|

2 |
Version 1.9 notes and API changes |

3 |
********************************* |

4 | |

5 |
This page reflects API changes from NetworkX 1.8 to NetworkX 1.9. |

6 | |

7 |
Please send comments and questions to the networkx-discuss mailing list: |

8 |
<http://groups.google.com/group/networkx-discuss>. |

9 | |

10 |
Flow package |

11 |
------------ |

12 | |

13 |
The flow package (:samp:`networkx.algorithms.flow`) is completely rewritten |

14 |
with backward *incompatible* changes. It introduces a new interface to flow |

15 |
algorithms. Existing code that uses the flow package will not work unmodified |

16 |
with NetworkX 1.9. |

17 | |

18 |
Main changes |

19 |
============ |

20 | |

21 |
1. We added two new maximum flow algorithms (:samp:`preflow_push` and |

22 |
:samp:`shortest_augmenting_path`) and rewrote the Edmonds–Karp algorithm in |

23 |
:samp:`flow_fulkerson` which is now in :samp:`edmonds_karp`. |

24 |
`@ysitu <https://github.com/ysitu>`_ contributed implementations of all new |

25 |
maximum flow algorithms. The legacy Edmonds–Karp algorithm implementation in |

26 |
:samp:`ford_fulkerson` is still available but will be removed in the next |

27 |
release. |

28 | |

29 |
2. All maximum flow algorithm implementations (including the legacy |

30 |
:samp:`ford_fulkerson`) output now a residual network (i.e., a |

31 |
:samp:`DiGraph`) after computing the maximum flow. See :samp:`maximum_flow` |

32 |
documentation for the details on the conventions that NetworkX uses for |

33 |
defining a residual network. |

34 | |

35 |
3. We removed the old :samp:`max_flow` and :samp:`min_cut` functions. The main |

36 |
entry points to flow algorithms are now the functions :samp:`maximum_flow`, |

37 |
:samp:`maximum_flow_value`, :samp:`minimum_cut` and |

38 |
:samp:`minimum_cut_value`, which have new parameters that control maximum |

39 |
flow computation: :samp:`flow_func` for specifying the algorithm that will |

40 |
do the actual computation (it accepts a function as argument that implements |

41 |
a maximum flow algorithm), :samp:`cutoff` for suggesting a maximum flow |

42 |
value at which the algorithm stops, :samp:`value_only` for stopping the |

43 |
computation as soon as we have the value of the flow, and :samp:`residual` |

44 |
that accepts as argument a residual network to be reused in repeated maximum |

45 |
flow computation. |

46 | |

47 |
4. All flow algorithms are required to accept arguments for these parameters |

48 |
but may selectively ignored the inapplicable ones. For instance, |

49 |
:samp:`preflow_push` algorithm can stop after the preflow phase without |

50 |
computing a maximum flow if we only need the flow value, but both |

51 |
:samp:`edmonds_karp` and :samp:`shortest_augmenting_path` always compute a |

52 |
maximum flow to obtain the flow value. |

53 | |

54 |
5. The new function :samp:`minimum_cut` returns the cut value and a node |

55 |
partition that defines the minimum cut. The function |

56 |
:samp:`minimum_cut_value` returns only the value of the cut, which is what |

57 |
the removed :samp:`min_cut` function used to return before 1.9. |

58 | |

59 |
6. The functions that implement flow algorithms (i.e., :samp:`preflow_push`, |

60 |
:samp:`edmonds_karp`, :samp:`shortest_augmenting_path` and |

61 |
:samp:`ford_fulkerson`) are not imported to the base NetworkX namespace. You |

62 |
have to explicitly import them from the flow package: |

63 | |

64 |
>>> from networkx.algorithms.flow import (ford_fulkerson, preflow_push, |

65 |
... edmonds_karp, shortest_augmenting_path) # doctest: +SKIP |

66 | |

67 | |

68 |
7. We also added a capacity-scaling minimum cost flow algorithm: |

69 |
:samp:`capacity_scaling`. It supports :samp:`MultiDiGraph` and disconnected |

70 |
networks. |

71 | |

72 |
Examples |

73 |
======== |

74 | |

75 |
Below are some small examples illustrating how to obtain the same output than in |

76 |
NetworkX 1.8.1 using the new interface to flow algorithms introduced in 1.9: |

77 | |

78 |
>>> import networkx as nx |

79 |
>>> G = nx.icosahedral_graph() |

80 |
>>> nx.set_edge_attributes(G, 'capacity', 1) |

81 | |

82 |
With NetworkX 1.8: |

83 | |

84 |
>>> flow_value = nx.max_flow(G, 0, 6) # doctest: +SKIP |

85 |
>>> cut_value = nx.min_cut(G, 0, 6) # doctest: +SKIP |

86 |
>>> flow_value == cut_value # doctest: +SKIP |

87 |
True |

88 |
>>> flow_value, flow_dict = nx.ford_fulkerson(G, 0, 6) # doctest: +SKIP |

89 | |

90 |
With NetworkX 1.9: |

91 | |

92 |
>>> from networkx.algorithms.flow import (ford_fulkerson, preflow_push, |

93 |
... edmonds_karp, shortest_augmenting_path) # doctest: +SKIP |

94 |
>>> flow_value = nx.maximum_flow_value(G, 0, 6) # doctest: +SKIP |

95 |
>>> cut_value = nx.minimum_cut_value(G, 0, 6) # doctest: +SKIP |

96 |
>>> flow_value == cut_value # doctest: +SKIP |

97 |
True |

98 |
>>> # Legacy: this returns the exact same output than ford_fulkerson in 1.8.1 |

99 |
>>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6, flow_func=ford_fulkerson) # doctest: +SKIP |

100 |
>>> # We strongly recommend to use the new algorithms: |

101 |
>>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6) # doctest: +SKIP |

102 |
>>> # If no flow_func is passed as argument, the default flow_func |

103 |
>>> # (preflow-push) is used. Therefore this is the same than: |

104 |
>>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6, flow_func=preflow_push) # doctest: +SKIP |

105 |
>>> # You can also use alternative maximum flow algorithms: |

106 |
>>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6, flow_func=shortest_augmenting_path) # doctest: +SKIP |

107 |
>>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6, flow_func=edmonds_karp) # doctest: +SKIP |

108 | |

109 |
Connectivity package |

110 |
-------------------- |

111 | |

112 |
The flow-based connecitivity and cut algorithms from the connectivity |

113 |
package (:samp:`networkx.algorithms.connectivity`) are adapted to take |

114 |
advantage of the new interface to flow algorithms. As a result, flow-based |

115 |
connectivity algorithms are up to 10x faster than in NetworkX 1.8 for some |

116 |
problems, such as sparse networks with highly skewed degree distributions. |

117 |
A few backwards *incompatible* changes were introduced. |

118 | |

119 |
* The functions for local connectivity and cuts accept now |

120 |
arguments for the new parameters defined for the flow interface: |

121 |
:samp:`flow_func` for defining the algorithm that will perform the |

122 |
underlying maximum flow computations, :samp:`residual` that accepts |

123 |
as argument a residual network to be reused in repeated maximum |

124 |
flow computations, and :samp:`cutoff` for defining a maximum flow |

125 |
value at which the underlying maximum flow algorithm stops. The big |

126 |
speed improvement with respect to 1.8 comes mainly from the reuse |

127 |
of the residual network and the use of :samp:`cutoff`. |

128 | |

129 |
* We removed the flow-based local connectivity and cut functions from |

130 |
the base namespace. Now they have to be explicitly imported from the |

131 |
connectivity package. The main entry point to flow-based connectivity |

132 |
and cut functions are the functions :samp:`edge_connectivity`, |

133 |
:samp:`node_connectivity`, :samp:`minimum_edge_cut`, and |

134 |
:samp:`minimum_node_cut`. All these functions accept a couple of nodes |

135 |
as optional arguments for computing local connectivity and cuts. |

136 | |

137 |
* We improved the auxiliary network for connectivity functions: The node |

138 |
mapping dict needed for node connectivity and minimum node cuts is now a |

139 |
graph attribute of the auxiliary network. Thus we removed the |

140 |
:samp:`mapping` parameter from the local versions of connectivity and cut |

141 |
functions. We also changed the parameter name for the auxuliary digraph |

142 |
from :samp:`aux_digraph` to :samp:`auxiliary`. |

143 | |

144 |
* We changed the name of the function :samp:`all_pairs_node_connectiviy_matrix` |

145 |
to :samp:`all_pairs_node_connectivity`. This function now returns a dictionary |

146 |
instead of a NumPy 2D array. We added a new parameter :samp:`nbunch` for |

147 |
computing node connectivity only among pairs of nodes in :samp:`nbunch`. |

148 | |

149 |
* A :samp:`stoer_wagner` function is added to the connectivity package |

150 |
for computing the weighted minimum cuts of undirected graphs using |

151 |
the Stoer–Wagner algorithm. This algorithm is not based on maximum flows. |

152 |
Several heap implementations are also added in the utility package |

153 |
(:samp:`networkx.utils`) for use in this function. |

154 |
:class:`BinaryHeap` is recommended over :class:`PairingHeap` for Python |

155 |
implementations without optimized attribute accesses (e.g., CPython) |

156 |
despite a slower asymptotic running time. For Python implementations |

157 |
with optimized attribute accesses (e.g., PyPy), :class:`PairingHeap` |

158 |
provides better performance. |

159 | |

160 |
Other new functionalities |

161 |
------------------------- |

162 | |

163 |
* A :samp:`disperson` function is added in the centrality package |

164 |
(:samp:`networkx.algorithms.centrality`) for computing the dispersion of |

165 |
graphs. |

166 | |

167 |
* A community package (:samp:`networkx.generators.community`) is added for |

168 |
generating community graphs. |

169 | |

170 |
* An :samp:`is_semiconnected` function is added in the connectivity package |

171 |
(:samp:`networkx.algorithms.connectivity`) for recognizing semiconnected |

172 |
graphs. |

173 | |

174 |
* The :samp:`eulerian_circuit` function in the Euler package |

175 |
(:samp:`networkx.algorithm.euler`) is changed to use a linear-time algorithm. |

176 | |

177 |
* A :samp:`non_edges` function in added in the function package |

178 |
(:samp:`networkx.functions`) for enumerating nonexistent edges between |

179 |
existing nodes of graphs. |

180 | |

181 |
* The linear algebra package (:samp:`networkx.linalg`) is changed to use SciPy |

182 |
sparse matrices. |

183 | |

184 |
* Functions :samp:`algebraic_connectivity`, :samp:`fiedler_vector` and |

185 |
:samp:`spectral_ordering` are added in the linear algebra package |

186 |
(:samp:`networkx.linalg`) for computing the algebraic connectivity, Fiedler |

187 |
vectors and spectral orderings of undirected graphs. |

188 | |

189 |
* A link prediction package (:samp:`networkx.algorithms.link_prediction`) is |

190 |
added to provide link prediction-related functionalities. |

191 | |

192 |
* Write Support for the graph6 and sparse6 formats is added in the read/write |

193 |
package (:samp:`networx.readwrite`). |

194 | |

195 |
* A :samp:`goldberg_radzik` function is added in the shortest path package |

196 |
(:samp:`networkx.algorithms.shortest_paths`) for computing shortest paths |

197 |
using the Goldberg–Radzik algorithm. |

198 | |

199 |
* A tree package (:samp:`networkx.tree`) is added to provide tree recognition |

200 |
functionalities. |

201 | |

202 |
* A context manager :samp:`reversed` is added in the utility package |

203 |
(:samp:`networkx.utils`) for temporary in-place reversal of graphs. |

204 | |

205 |
Miscellaneous changes |

206 |
--------------------- |

207 | |

208 |
* The functions in the components package |

209 |
(:samp:`networkx.algorithms.components`) such as :samp:`connected_components`, |

210 |
:samp:`connected_components_subgraph` now return generators instead of lists. |

211 |
To recover the earlier behavior, use :samp:`list(connected_components(G))`. |

212 | |

213 |
* JSON helpers in the JSON graph package (:samp:`networkx.readwrite.json_graph`) |

214 |
are removed. Use functions from the standard library (e.g., |

215 |
:samp:`json.dumps`) instead. |

216 | |

217 |
* Support for Python 3.1 is dropped. Basic support is added for Jython 2.7 and |

218 |
IronPython 2.7, although they remain not officially supported. |

219 | |

220 |
* Numerous reported issues are fixed. |