From 6c40450a32625c4e8f0e8e19529f72cb1eb81faf Mon Sep 17 00:00:00 2001 From: ysitu Date: Fri, 30 May 2014 13:26:08 -0400 Subject: Format api_1.9.rst --- doc/source/reference/api_1.9.rst | 95 ++++++++++++++++++++++++++++++---------- doc/source/static/networkx.css | 5 +++ 2 files changed, 76 insertions(+), 24 deletions(-) diff --git a/doc/source/reference/api_1.9.rst b/doc/source/reference/api_1.9.rst index bb887ac8..e8a189c0 100644 --- a/doc/source/reference/api_1.9.rst +++ b/doc/source/reference/api_1.9.rst @@ -2,44 +2,84 @@ Version 1.9 notes and API changes ********************************* -This page reflects API changes from networkx-1.8 to networkx-1.9. +This page reflects API changes from NetworkX 1.8 to NetworkX 1.9. Please send comments and questions to the networkx-discuss mailing list: -http://groups.google.com/group/networkx-discuss . - -* The functions in the components package algorithms/components/ such as, connected_components, connected_components_subgraph, and similar, now return generators instead of lists. In order to recover the earlier behavior use e.g. list(connected_components(G)). - +. Flow package ------------ -Complete rewrite of the flow package and new interface to flow algorithms, with backwards incompatible changes. If you had code that was using any of the flow related functions, it will not work unmodified in 1.9. But, trust us, it is worth it. The main changes are: - -1. We added two new maximum flow algorithms (:samp:`preflow_push` and :samp:`shortest_augmenting_path`) and rewrote the Edmonds-Karp algorithm in :samp:`flow_fulkerson` which is now at :samp:`edmonds_karp`. @ysitu contributed the very nice implementations of all new maximum flow algorithms [@ysitu do you want your full/real name here?]. The legacy Edmonds-Karp algorithm implementation in :samp:`ford_fulkerson` is still available but will be removed in the next release. - -2. All maximum flow algorithm implementations (including the legacy :samp:`ford_fulkerson`) output now a residual network (ie a NetworkX DiGraph) after computing the maximum flow. See :samp:`maximum_flow` documentation for the details on the conventions that NetworkX uses for defining a residual network. - -3. We removed the old :samp:`max_flow` and :samp:`min_cut` functions. The main interface to flow algorithms are now the functions :samp:`maximum_flow`, :samp:`maximum_flow_value` and :samp:`minimum_cut` and :samp:`minimum_cut_value`, which have new parameters that define NetworkX interface to flow algorithms: :samp:`flow_func` for defining the algorithm that will do the actual computation (it accepts a function as argument that implements a maximum flow algorithm), :samp:`cutoff` for defining a maximum value after which the algorithm stops, :samp:`value_only` for stopping the computation as soon as we have the value of the flow, and :samp:`residual` that accepts as argument a residual network to be reused in maximum flow computations. - -4. All algorithms accept arguments for these parameters, but not all of them can actually act according to them. For instance, :samp:`preflow_push` algorithm can stop after the :samp:`preflow` phase if we only need the value of the flow, but both :samp:`edmonds_karp` and :samp:`shortest_augmenting_path` will need to finish for obtaining the flow value. Thus, parameters not applicable to one algorithm will be accepted but ignored. - -5. The new function :samp:`minimum_cut` returns the cut value and the actual node partition that defines the minimum cut. The function :samp:`minimum_cut_value` returns only the value of the cut, which is what the removed :samp:`min_cut` function used to return before 1.9. - -6. The functions that implement flow algorithms (ie :samp:`preflow_push`, :samp:`edmonds_karp`, :samp:`shortest_augmenting_path`, and :samp:`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, +The flow package (:samp:`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. + +Main changes +============ + +1. We added two new maximum flow algorithms (:samp:`preflow_push` and + :samp:`shortest_augmenting_path`) and rewrote the Edmonds–Karp algorithm in + :samp:`flow_fulkerson` which is now in :samp:`edmonds_karp`. + `@ysitu `_ contributed implementations of all new + maximum flow algorithms. The legacy Edmonds–Karp algorithm implementation in + :samp:`ford_fulkerson` is still available but will be removed in the next + release. + +2. All maximum flow algorithm implementations (including the legacy + :samp:`ford_fulkerson`) output now a residual network (i.e., a + :samp:`DiGraph`) after computing the maximum flow. See :samp:`maximum_flow` + documentation for the details on the conventions that NetworkX uses for + defining a residual network. + +3. We removed the old :samp:`max_flow` and :samp:`min_cut` functions. The main + entry points to flow algorithms are now the functions :samp:`maximum_flow`, + :samp:`maximum_flow_value`, :samp:`minimum_cut` and + :samp:`minimum_cut_value`, which have new parameters that control maximum + flow computation: :samp:`flow_func` for specifying the algorithm that will + do the actual computation (it accepts a function as argument that implements + a maximum flow algorithm), :samp:`cutoff` for suggesting a maximum flow + value at which the algorithm stops, :samp:`value_only` for stopping the + computation as soon as we have the value of the flow, and :samp:`residual` + that accepts as argument a residual network to be reused in repeated maximum + flow computation. + +4. All flow algorithms are required to accept arguments for these parameters + but may selectively ignored the inapplicable ones. For instance, + :samp:`preflow_push` algorithm can stop after the preflow phase without + computing a maximum flow if we only need the flow value, but both + :samp:`edmonds_karp` and :samp:`shortest_augmenting_path` always compute a + maximum flow to obtain the flow value. + +5. The new function :samp:`minimum_cut` returns the cut value and a node + partition that defines the minimum cut. The function + :samp:`minimum_cut_value` returns only the value of the cut, which is what + the removed :samp:`min_cut` function used to return before 1.9. + +6. The functions that the implement flow algorithms (i.e., :samp:`preflow_push`, + :samp:`edmonds_karp`, :samp:`shortest_augmenting_path` and + :samp:`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) -7. Also added a capacity scaling minimum cost flow algorithm: :samp:`capacity_scaling`. It supports :samp:`MultiDiGraphs` and disconnected networks. +7. We also added a capacity-scaling minimum cost flow algorithm: + :samp:`capacity_scaling`. It supports :samp:`MultiDiGraph` and disconnected + networks. -8. 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: +Examples +======== + +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.1: +With NetworkX 1.8: >>> flow_value = nx.max_flow(G, 0, 6) >>> cut_value = nx.min_cut(G, 0, 6) @@ -49,7 +89,7 @@ True With NetworkX 1.9: ->>> from networkx.algorithms.flow import (ford_fulkerson, preflow_push, +>>> 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) @@ -65,3 +105,10 @@ True >>> # 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) + +Miscellaneous changes +--------------------- + +* The functions in the components package such as :samp:`connected_components`, + :samp:`connected_components_subgraph` now return generators instead of lists. + To recover the earlier behavior, use :samp:`list(connected_components(G))`. diff --git a/doc/source/static/networkx.css b/doc/source/static/networkx.css index 1b6e9f93..6c6410d2 100644 --- a/doc/source/static/networkx.css +++ b/doc/source/static/networkx.css @@ -7,3 +7,8 @@ .wy-table-responsive table td:first-child { white-space: nowrap; } + +code, .rst-content tt, .linenodiv pre, div[class^="highlight"] pre { + font-family: 'Inconsolata', 'Monaco', 'Consolas', monospace; + font-size: 85%; +} -- cgit v1.2.1 From f9f693a813c4ff64313fd92e3cc00da1253b48be Mon Sep 17 00:00:00 2001 From: ysitu Date: Fri, 30 May 2014 14:44:50 -0400 Subject: Document major changes in 1.9 --- doc/source/reference/api_1.9.rst | 61 +++++++++++++++++++++++++++++++++++++++- 1 file changed, 60 insertions(+), 1 deletion(-) diff --git a/doc/source/reference/api_1.9.rst b/doc/source/reference/api_1.9.rst index e8a189c0..3bdd0a93 100644 --- a/doc/source/reference/api_1.9.rst +++ b/doc/source/reference/api_1.9.rst @@ -106,9 +106,68 @@ True >>> 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) +Other new functionalities +------------------------- + +* A :samp:`disperson` function is added in the centrality package + (:samp:`networkx.algorithms.centrality`) for computing the dispersion of + graphs. + +* A community package (:samp:`networkx.generators.community`) is added for + generating community graphs. + +* An :samp:`is_semiconnected` function is added in the connectivity package + (:samp:`networkx.algorithms.connectivity`) for recognizing semiconnected + graphs. + +* A :samp:`stoer_wagner` function is added in the connectivity package + (:samp:`networkx.algorithms.connectivity`) for computing the weighted minimum + cuts of undirected graphs using the Stoer–Wagner algorithm. + +* The :samp:`eulerian_circuit` function in the Euler package + (:samp:`networkx.algorithm.euler`) is changed to use a linear-time algorithm. + +* A :samp:`non_edges` function in added in the function package + (:samp:`networkx.functions`) for enumerating nonexistent edges between + existing nodes of graphs. + +* The linear algebra package (:samp:`networkx.linalg`) is changed to use SciPy + sparse matrices. + +* Functions :samp:`algebraic_connectivity`, :samp:`fiedler_vector` and + :samp:`spectral_ordering` are added in the linear algebra package + (:samp:`networkx.linalg`) for computing the algebraic connectivity, Fiedler + vectors and spectral orderings of directed graphs. + +* A link prediction package (:samp:`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 (:samp:`networx.readwrite`). + +* A :samp:`goldberg_radzik` function is added in the shortest path package + (:samp:`networkx.algorithms.shortest_paths`) for computing shortest paths + using the Goldberg–Radzik algorithm. + +* A tree package (:samp:`networkx.tree`) is added to provide tree recognition + functionalities. + +* A context manager :samp:`reversed` is added in the utility package + (:samp:`networkx.utils`) for temporary in-place reversal of graphs. + Miscellaneous changes --------------------- -* The functions in the components package such as :samp:`connected_components`, +* The functions in the components package + (:samp:`networkx.algorithms.components`) such as :samp:`connected_components`, :samp:`connected_components_subgraph` now return generators instead of lists. To recover the earlier behavior, use :samp:`list(connected_components(G))`. + +* JSON helpers in the JSON graph package (:samp:`networkx.readwrite.json_graph`) + are removed. Use functions from the standard library (e.g., `json.dumps`) + instead. + +* 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. -- cgit v1.2.1 From 8e9ad0a9bf32b926ef181c1e5b2808f26ad036d9 Mon Sep 17 00:00:00 2001 From: ysitu Date: Fri, 30 May 2014 14:45:45 -0400 Subject: Add classifier for Python 3.4 support --- networkx/release.py | 1 + 1 file changed, 1 insertion(+) diff --git a/networkx/release.py b/networkx/release.py index dd866635..12238c7e 100644 --- a/networkx/release.py +++ b/networkx/release.py @@ -240,6 +240,7 @@ classifiers = [ 'Programming Language :: Python :: 3', 'Programming Language :: Python :: 3.2', 'Programming Language :: Python :: 3.3', + 'Programming Language :: Python :: 3.4', 'Topic :: Software Development :: Libraries :: Python Modules', 'Topic :: Scientific/Engineering :: Bio-Informatics', 'Topic :: Scientific/Engineering :: Information Analysis', -- cgit v1.2.1 From c7c2ac421d193053e39bfdffd2fc938911c8d2ab Mon Sep 17 00:00:00 2001 From: ysitu Date: Fri, 30 May 2014 20:15:20 -0400 Subject: Fix typos in api_1.9.rst --- doc/source/reference/api_1.9.rst | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/doc/source/reference/api_1.9.rst b/doc/source/reference/api_1.9.rst index 3bdd0a93..7cd78b57 100644 --- a/doc/source/reference/api_1.9.rst +++ b/doc/source/reference/api_1.9.rst @@ -137,7 +137,7 @@ Other new functionalities * Functions :samp:`algebraic_connectivity`, :samp:`fiedler_vector` and :samp:`spectral_ordering` are added in the linear algebra package (:samp:`networkx.linalg`) for computing the algebraic connectivity, Fiedler - vectors and spectral orderings of directed graphs. + vectors and spectral orderings of undirected graphs. * A link prediction package (:samp:`networkx.algorithms.link_prediction`) is added to provide link prediction-related functionalities. @@ -164,8 +164,8 @@ Miscellaneous changes To recover the earlier behavior, use :samp:`list(connected_components(G))`. * JSON helpers in the JSON graph package (:samp:`networkx.readwrite.json_graph`) - are removed. Use functions from the standard library (e.g., `json.dumps`) - instead. + are removed. Use functions from the standard library (e.g., + :samp:`json.dumps`) instead. * 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. -- cgit v1.2.1 From c76722407d2d3f119c0187e778704167a3868c25 Mon Sep 17 00:00:00 2001 From: ysitu Date: Fri, 30 May 2014 20:16:17 -0400 Subject: Change outdated years to 2014 --- LICENSE.txt | 2 +- doc/source/conf.py | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) diff --git a/LICENSE.txt b/LICENSE.txt index dad9f695..b9ca6913 100644 --- a/LICENSE.txt +++ b/LICENSE.txt @@ -4,7 +4,7 @@ NetworkX is distributed with the BSD license. :: - Copyright (C) 2004-2011, NetworkX Developers + Copyright (C) 2004-2014, NetworkX Developers Aric Hagberg Dan Schult Pieter Swart diff --git a/doc/source/conf.py b/doc/source/conf.py index 993b8502..ab18420c 100644 --- a/doc/source/conf.py +++ b/doc/source/conf.py @@ -53,7 +53,7 @@ master_doc = 'index' # General substitutions. project = 'NetworkX' -copyright = '2013, NetworkX Developers' +copyright = '2014, NetworkX Developers' # The default replacements for |version| and |release|, also used in various # other places throughout the built documents. -- cgit v1.2.1 From 5c6f40ae8e1d5e2642058de3c799e33981f58285 Mon Sep 17 00:00:00 2001 From: ysitu Date: Fri, 30 May 2014 20:16:43 -0400 Subject: Update installation documentation URL --- INSTALL.txt | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/INSTALL.txt b/INSTALL.txt index f418f5d6..0df6ae25 100644 --- a/INSTALL.txt +++ b/INSTALL.txt @@ -1,3 +1,3 @@ See doc/source/install.rst or -http://networkx.lanl.gov/install.html +http://networkx.github.io/documentation/latest/install.html -- cgit v1.2.1 From bf050813172905b5760d856d174d8ae1a3e2c547 Mon Sep 17 00:00:00 2001 From: ysitu Date: Fri, 30 May 2014 21:59:59 -0400 Subject: Update release URLs and development status --- networkx/release.py | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/networkx/release.py b/networkx/release.py index 12238c7e..fd789299 100644 --- a/networkx/release.py +++ b/networkx/release.py @@ -224,12 +224,12 @@ authors = {'Hagberg' : ('Aric Hagberg','hagberg@lanl.gov'), } maintainer = "NetworkX Developers" maintainer_email = "networkx-discuss@googlegroups.com" -url = 'http://networkx.lanl.gov/' -download_url="http://networkx.lanl.gov/download/networkx" +url = 'http://networkx.github.io/' +download_url= 'https://pypi.python.org/pypi/networkx/' platforms = ['Linux','Mac OSX','Windows','Unix'] keywords = ['Networks', 'Graph Theory', 'Mathematics', 'network', 'graph', 'discrete mathematics', 'math'] classifiers = [ - 'Development Status :: 4 - Beta', + 'Development Status :: 5 - Production/Stable', 'Intended Audience :: Developers', 'Intended Audience :: Science/Research', 'License :: OSI Approved :: BSD License', -- cgit v1.2.1 From e0bf6f7f40b46e25a85efe33f8fbad6e1b0482fb Mon Sep 17 00:00:00 2001 From: ysitu Date: Sat, 31 May 2014 11:24:42 -0400 Subject: Update release log --- doc/source/reference/news.rst | 99 ++++++++++++++++++++++++++----------------- 1 file changed, 61 insertions(+), 38 deletions(-) diff --git a/doc/source/reference/news.rst b/doc/source/reference/news.rst index 7d349d92..5d405453 100644 --- a/doc/source/reference/news.rst +++ b/doc/source/reference/news.rst @@ -4,14 +4,37 @@ Release Log =========== -Networkx-1.8.1 +NetworkX 1.9 +------------ +Release date: TBD + +Support for Python 3.1 is dropped in this release. + +Highlights +~~~~~~~~~~ +- 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 + +API changes +~~~~~~~~~~~ +See :doc:`api_1.9`. + +NetworkX 1.8.1 -------------- Release date: 4 August 2013 Bugfix release for missing files in source packaging -Networkx-1.8 +NetworkX 1.8 ------------ Release date: 28 July 2013 @@ -26,8 +49,8 @@ Highlights - Faster topological sort, decendents and ancestors of DAGs - Scaling parameter for force-directed layout -Bug Fixes ---------- +Bug fixes +~~~~~~~~~ - Error with average weighted connectivity for digraphs, correct normalized laplacian with self-loops, load betweenness for single node graphs, isolated nodes missing from dfs/bfs trees, normalize HITS using l1, handle density of graphs with self loops - Cleaner handling of current figure status with Matplotlib, Pajek files now don't write troublesome header line, default alpha value for GEXF files, read curved edges from yEd GraphML @@ -36,12 +59,12 @@ Bug Fixes For full details of the issues closed for this release (added features and bug fixes) see: https://github.com/networkx/networkx/issues?milestone=1&page=1&state=closed -API Changes +API changes ~~~~~~~~~~~ See :doc:`api_1.8` -Networkx-1.7 +NetworkX 1.7 ------------ Release date: 4 July 2012 @@ -60,12 +83,12 @@ Highlights For full details of the tickets closed for this release (added features and bug fixes) see: https://networkx.lanl.gov/trac/query?status=closed&group=milestone&milestone=networkx-1.7 -API Changes +API changes ~~~~~~~~~~~ See :doc:`api_1.7` -Networkx-1.6 +NetworkX 1.6 ------------ Release date: 20 November 2011 @@ -86,12 +109,12 @@ Updated all code to work with the PyPy Python implementation http://pypy.org whi For full details of the tickets closed for this release (added features and bug fixes) see: https://networkx.lanl.gov/trac/query?status=closed&group=milestone&milestone=networkx-1.6 -API Changes +API changes ~~~~~~~~~~~ See :doc:`api_1.6` -Networkx-1.5 +NetworkX 1.5 ------------ Release date: 4 June 2011 @@ -127,7 +150,7 @@ New features - :mod:`Karate Club, Florentine Families, and Davis' Women's Club ` graphs -API Changes +API changes ~~~~~~~~~~~ See :doc:`api_1.5` @@ -150,7 +173,7 @@ Bug fixes - Speedup in SciPy version of PageRank (:ticket:`554`) - Numpy PageRank node order incorrect + speedups (:ticket:`555`) -Networkx-1.4 +NetworkX 1.4 ------------ Release date: 23 January 2011 @@ -171,7 +194,7 @@ New features - :mod:`functions to get and set node and edge attributes ` - and more, see https://networkx.lanl.gov/trac/query?status=closed&group=milestone&milestone=networkx-1.4 -API Changes +API changes ~~~~~~~~~~~ - :mod:`gnp_random_graph() ` now takes a directed=True|False keyword instead of create_using @@ -184,7 +207,7 @@ Bug fixes -Networkx-1.3 +NetworkX 1.3 ------------ Release date: 28 August 2010 @@ -201,7 +224,7 @@ New features - Updated many tests to unittest style. Run with: "import networkx; networkx.test()" (requires nose testing package) - and more, see https://networkx.lanl.gov/trac/query?status=closed&group=milestone&milestone=networkx-1.3 -API Changes +API changes ~~~~~~~~~~~ - :mod:`minimum_spanning_tree() now returns a NetworkX Graph (a tree or forest) ` @@ -210,7 +233,7 @@ Bug fixes - see https://networkx.lanl.gov/trac/query?status=closed&group=milestone&milestone=networkx-1.3 -Networkx-1.2 +NetworkX 1.2 ------------ Release date: 28 July 2010 @@ -231,7 +254,7 @@ New features - and more, see https://networkx.lanl.gov/trac/query?status=closed&group=milestone&milestone=networkx-1.2 -Networkx-1.1 +NetworkX 1.1 ------------ Release date: 21 April 2010 @@ -261,7 +284,7 @@ New features - Many more tests, can be run with "import networkx; networkx.test()" - and much more, see https://networkx.lanl.gov/trac/query?status=closed&group=milestone&milestone=networkx-1.1 -API Changes +API changes ~~~~~~~~~~~ Returning dictionaries ********************** @@ -329,7 +352,7 @@ Bug fixes - Normalize eigenvector_centrality by l2 norm - :func:`read_gml` now returns multigraphs -Networkx-1.0.1 +NetworkX 1.0.1 -------------- Release date: 11 Jan 2010 @@ -339,7 +362,7 @@ See: https://networkx.lanl.gov/trac/timeline Bug fix release for missing setup.py in manifest. -Networkx-1.0 +NetworkX 1.0 ------------ Release date: 8 Jan 2010 @@ -374,7 +397,7 @@ Examples - Graph subclass example -Networkx-0.99 +NetworkX 0.99 ------------- Release date: 18 November 2008 @@ -406,7 +429,7 @@ Examples - New examples - see http://networkx.lanl.gov/examples/ -NetworkX-0.37 +NetworkX 0.37 --------------- Release date: 17 August 2008 @@ -443,7 +466,7 @@ Examples - Ubigraph examples showing 3D drawing -NetworkX-0.36 +NetworkX 0.36 --------------- Release date: 13 January 2008 @@ -466,7 +489,7 @@ Bug fixes - convert with specified nodelist now works correctly - vf2 isomorphism checker updates -NetworkX-0.35.1 +NetworkX 0.35.1 --------------- Release date: 27 July 2007 @@ -477,7 +500,7 @@ Small update to fix import readwrite problem and maintain Python2.3 compatibility. -NetworkX-0.35 +NetworkX 0.35 ------------- Release date: 22 July 2007 @@ -502,7 +525,7 @@ Bug fixes - report errors correctly when using tuples as nodes #114 - handle conversions from incomplete dict-of-dict data -NetworkX-0.34 +NetworkX 0.34 ------------- Release date: 12 April 2007 @@ -538,7 +561,7 @@ Bug fixes - don't throw exceptions for nodes not in graph (silently ignore instead) in edges_* and degree_* -NetworkX-0.33 +NetworkX 0.33 ------------- Release date: 27 November 2006 @@ -571,7 +594,7 @@ Examples -NetworkX-0.32 +NetworkX 0.32 ------------- Release date: 29 September 2006 @@ -601,7 +624,7 @@ Examples - Expected degree sequence - New pygraphviz interface -NetworkX-0.31 +NetworkX 0.31 ------------- Release date: 20 July 2006 @@ -626,7 +649,7 @@ Examples - update drawing examples -NetworkX-0.30 +NetworkX 0.30 ------------- @@ -664,7 +687,7 @@ Examples - unicode node labels -NetworkX-0.29 +NetworkX 0.29 ------------- Release date: 28 April 2006 @@ -695,7 +718,7 @@ Bug fixes periodic=True -NetworkX-0.28 +NetworkX 0.28 ------------- Release date: 13 March 2006 @@ -735,7 +758,7 @@ Bug fixes calling sequence -NetworkX-0.27 +NetworkX 0.27 ------------- @@ -768,7 +791,7 @@ Bug fixes for get_edge() -NetworkX-0.26 +NetworkX 0.26 ------------- @@ -797,7 +820,7 @@ Bug fixes - Indexes for nodes in graphs start at zero by default (was 1) -NetworkX-0.25 +NetworkX 0.25 ------------- @@ -832,7 +855,7 @@ Bug fixes - fixed Dijkstra priority queue - fixed non-recursive toposort and is_directed_acyclic graph -NetworkX-0.24 +NetworkX 0.24 ------------- Release date: 20 August 2005 @@ -847,7 +870,7 @@ Bug fixes - Attempt to add self loop should add node even if parallel edges not allowed -NetworkX-0.23 +NetworkX 0.23 ------------- Release date: 14 July 2005 @@ -892,7 +915,7 @@ Bug fixes produce the same result as if each connected component were considered separately. -NetworkX-0.22 +NetworkX 0.22 ------------- Release date: 17 June 2005 -- cgit v1.2.1 From 7292ce649eeeb09c9207ba51da130465f3685711 Mon Sep 17 00:00:00 2001 From: Jordi Torrents Date: Sat, 31 May 2014 17:40:57 +0200 Subject: Add release notes for the connectivity package. --- doc/source/reference/api_1.9.rst | 56 ++++++++++++++++++++++++++++++++++++---- 1 file changed, 51 insertions(+), 5 deletions(-) diff --git a/doc/source/reference/api_1.9.rst b/doc/source/reference/api_1.9.rst index 7cd78b57..ce7e8731 100644 --- a/doc/source/reference/api_1.9.rst +++ b/doc/source/reference/api_1.9.rst @@ -56,7 +56,7 @@ Main changes :samp:`minimum_cut_value` returns only the value of the cut, which is what the removed :samp:`min_cut` function used to return before 1.9. -6. The functions that the implement flow algorithms (i.e., :samp:`preflow_push`, +6. The functions that implement flow algorithms (i.e., :samp:`preflow_push`, :samp:`edmonds_karp`, :samp:`shortest_augmenting_path` and :samp:`ford_fulkerson`) are not imported to the base NetworkX namespace. You have to explicitly import them from the flow package: @@ -106,6 +106,56 @@ True >>> 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) +Connectivity package +-------------------- + +The flow based connecitivity and cut algorithms from the connectivity +package (:samp:`networkx.algorithms.connectivity`) were 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 local functions for flow-based connectivity and cuts accept now +arguments for the new parameters defined for the flow interface: +:samp:`flow_func` for defining the algorithm that will perform the +underlying maximum flow computations, :samp:`residual` that accepts +as argument a residual network to be reused in repeated maximum +flow computations, and :samp:`cutoff` for 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 :samp:`cutoff`. + +* 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 :samp:`edge_connectivity`, +:samp:`node_connectivity`, :samp:`minimum_edge_cut`, and +:samp:`minimum_node_cut`. All these functions accept a couple of nodes +as optional arguments for computing local versions of these functions. + +* We improved the auxiliary digraph for connectivity functions: The node +mapping dict needed for node connectivity and minimum node cuts is now a +graph attribute of the auxiliary digraph. Thus we removed the +:samp:`mapping` parameter from the local version of connectivity and cut +functions. We also changed the parameter name for the auxuliary digraph +from :samp:`aux_digraph` to :samp:`auxiliary`. + +* We changed the name of the function :samp:`all_pairs_node_connectiviy_matrix` +to :samp:`all_pairs_node_connectivity`. This function now returns a dictionary +instead of a numpy 2d array. We added a new parameter nbunch for computing node +connectivity only among pairs of nodes in nbunch. + +* A :samp:`stoer_wagner` function was added to the connectivity package +for computing the weighted minimum cuts of undirected graphs using +the Stoer–Wagner algorithm. This algorithm is not based in computing +maximum flows. Several heap implementations were also added. +:class:`BinaryHeap` is recommeded over :class:`PairingHeap` for 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), :class:`PairingHeap` +provides better performance. + Other new functionalities ------------------------- @@ -120,10 +170,6 @@ Other new functionalities (:samp:`networkx.algorithms.connectivity`) for recognizing semiconnected graphs. -* A :samp:`stoer_wagner` function is added in the connectivity package - (:samp:`networkx.algorithms.connectivity`) for computing the weighted minimum - cuts of undirected graphs using the Stoer–Wagner algorithm. - * The :samp:`eulerian_circuit` function in the Euler package (:samp:`networkx.algorithm.euler`) is changed to use a linear-time algorithm. -- cgit v1.2.1 From a86840eceab535c0d362f0ca45b6be4c690441cb Mon Sep 17 00:00:00 2001 From: ysitu Date: Sat, 31 May 2014 12:17:31 -0400 Subject: Minor edits to connectivity package changes api_1.9.rst --- doc/source/reference/api_1.9.rst | 83 ++++++++++++++++++++-------------------- 1 file changed, 42 insertions(+), 41 deletions(-) diff --git a/doc/source/reference/api_1.9.rst b/doc/source/reference/api_1.9.rst index ce7e8731..d06f8e0d 100644 --- a/doc/source/reference/api_1.9.rst +++ b/doc/source/reference/api_1.9.rst @@ -109,52 +109,53 @@ True Connectivity package -------------------- -The flow based connecitivity and cut algorithms from the connectivity -package (:samp:`networkx.algorithms.connectivity`) were adapted to take +The flow-based connecitivity and cut algorithms from the connectivity +package (:samp:`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 local functions for flow-based connectivity and cuts accept now -arguments for the new parameters defined for the flow interface: -:samp:`flow_func` for defining the algorithm that will perform the -underlying maximum flow computations, :samp:`residual` that accepts -as argument a residual network to be reused in repeated maximum -flow computations, and :samp:`cutoff` for 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 :samp:`cutoff`. - -* 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 :samp:`edge_connectivity`, -:samp:`node_connectivity`, :samp:`minimum_edge_cut`, and -:samp:`minimum_node_cut`. All these functions accept a couple of nodes -as optional arguments for computing local versions of these functions. - -* We improved the auxiliary digraph for connectivity functions: The node -mapping dict needed for node connectivity and minimum node cuts is now a -graph attribute of the auxiliary digraph. Thus we removed the -:samp:`mapping` parameter from the local version of connectivity and cut -functions. We also changed the parameter name for the auxuliary digraph -from :samp:`aux_digraph` to :samp:`auxiliary`. +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: + :samp:`flow_func` for defining the algorithm that will perform the + underlying maximum flow computations, :samp:`residual` that accepts + as argument a residual network to be reused in repeated maximum + flow computations, and :samp:`cutoff` for 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 :samp:`cutoff`. + +* 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 :samp:`edge_connectivity`, + :samp:`node_connectivity`, :samp:`minimum_edge_cut`, and + :samp:`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 + :samp:`mapping` parameter from the local versions of connectivity and cut + functions. We also changed the parameter name for the auxuliary digraph + from :samp:`aux_digraph` to :samp:`auxiliary`. * We changed the name of the function :samp:`all_pairs_node_connectiviy_matrix` -to :samp:`all_pairs_node_connectivity`. This function now returns a dictionary -instead of a numpy 2d array. We added a new parameter nbunch for computing node -connectivity only among pairs of nodes in nbunch. - -* A :samp:`stoer_wagner` function was added to the connectivity package -for computing the weighted minimum cuts of undirected graphs using -the Stoer–Wagner algorithm. This algorithm is not based in computing -maximum flows. Several heap implementations were also added. -:class:`BinaryHeap` is recommeded over :class:`PairingHeap` for 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), :class:`PairingHeap` -provides better performance. + to :samp:`all_pairs_node_connectivity`. This function now returns a dictionary + instead of a NumPy 2D array. We added a new parameter :samp:`nbunch` for + computing node connectivity only among pairs of nodes in :samp:`nbunch`. + +* A :samp:`stoer_wagner` function 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 + (:samp:`networkx.utils`) for use in this function. + :class:`BinaryHeap` is recommeded over :class:`PairingHeap` for 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), :class:`PairingHeap` + provides better performance. Other new functionalities ------------------------- -- cgit v1.2.1