Statistics
| Branch: | Revision:

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.