Draft 2.6 release notes (#4828)

* external -> internal gallery link.

* Add section on NXEPs.

* Go through PRs and add to release notes.

* go through release_dev -- add some "improvements"

* Apply suggestions.

Co-Authored-By: Jarrod Millman <jarrod.millman@gmail.com>

* Apply suggestions.

Co-Authored-By: Jarrod Millman <jarrod.millman@gmail.com>

Co-authored-by: Dan Schult <dschult@colgate.edu>
Co-authored-by: Jarrod Millman <jarrod.millman@gmail.com>

2 files changed, 117 insertions, 5 deletions

diff --git a/doc/developer/deprecations.rst b/doc/developer/deprecations.rst
index 57254771..619e3281 100644
--- a/doc/developer/deprecations.rst
+++ b/doc/developer/deprecations.rst
@@ -85,4 +85,5 @@ Version 3.0
 * In ``networkx.classes`` remove the ``ordered`` module and the four ``Ordered``
   classes defined therein.
 * In ``utils/decorators.py`` remove ``preserve_random_state``.
-* Remove ``testing``.
+* In ``algorithms/community/quality.py`` remove ``coverage`` and ``performance``.
+* Remove ``testing``.
\ No newline at end of file
diff --git a/doc/release/release_dev.rst b/doc/release/release_dev.rst
index dbb7f846..b9dba4c3 100644
--- a/doc/release/release_dev.rst
+++ b/doc/release/release_dev.rst
@@ -9,8 +9,7 @@ NetworkX is a Python package for the creation, manipulation, and study of the
 structure, dynamics, and functions of complex networks.
 
 For more information, please visit our `website <https://networkx.org/>`_
-and our `gallery of examples
-<https://networkx.org/documentation/latest/auto_examples/index.html>`_.
+and our :ref:`gallery of examples <examples_gallery>`
 Please send comments and questions to the `networkx-discuss mailing list
 <http://groups.google.com/group/networkx-discuss>`_.
 
@@ -22,25 +21,119 @@ X contributors. Highlights include:
 
 - Dropped support for Python 3.6.
 - NumPy, SciPy, Matplotlib, and pandas are now default requirements.
+- Improved example gallery
+- Removed code for supporting Jython/IronPython
+- The ``__str__`` method for graph objects is more informative and concise.
+- Improved import time
+- Improved test coverage
+- New documentation theme
+- Add functionality for drawing self-loop edges
+- Add approximation algorithms for Traveling Salesman Problem
+
+New functions:
+
+- Panther algorithm
+- maximum cut heuristics
+- equivalence_classes
+- dedensification
+- random_ordered_tree
+- forest_str
+- snap_aggregation
+- networkx.approximation.diameter
+- partition_quality
+- prominent_group
+- prefix_tree_recursive
+- topological_generations
+
+NXEPs
+-----
+
+**N**\etwork\ **X** **E**\nhancement **P**\roposals capture changes
+that are larger in scope than typical pull requests, such as changes to
+fundamental data structures.
+The following proposals have come under consideration since the previous
+release:
+
+- :ref:`NXEP2`
+- :ref:`NXEP3`
 
 Improvements
 ------------
 
+- [`#3886 <https://github.com/networkx/networkx/pull/3886>`_]
+  Adds the Panther algorithm for top-k similarity search.
+- [`#4138 <https://github.com/networkx/networkx/pull/4138>`_]
+  Adds heuristics for approximating solution to the maximum cut problem.
+- [`#4183 <https://github.com/networkx/networkx/pull/4183>`_]
+  Adds ``equivalence_classes`` to public API.
+- [`#4193 <https://github.com/networkx/networkx/pull/4193>`_]
+  ``nx.info`` is more concise.
+- [`#4198 <https://github.com/networkx/networkx/pull/4198>`_]
+  Improve performance of ``transitivity``.
+- [`#4206 <https://github.com/networkx/networkx/pull/4206>`_]
+  UnionFind.union selects the heaviest root as the new root
+- [`#4240 <https://github.com/networkx/networkx/pull/4240>`_]
+  Adds ``dedensification`` function in a new ``summarization`` module.
+- [`#4294 <https://github.com/networkx/networkx/pull/4294>`_]
+  Adds ``forest_str`` for string representation of trees.
 - [`#4319 <https://github.com/networkx/networkx/pull/4319>`_]
   pagerank uses scipy by default now.
 - [`#4317 <https://github.com/networkx/networkx/pull/4317>`_]
   New ``source`` argument to ``has_eulerian_path`` to look for path starting at
   source.
+- [`#4356 <https://github.com/networkx/networkx/pull/4356>`_]
+  Use ``bidirectional_djikstra`` in ``shortest_path`` for weighted graphs
+  to improve performance.
+- [`#4361 <https://github.com/networkx/networkx/pull/4361>`_]
+  Adds ``nodelist`` argument to ``triadic_census``
+- [`#4435 <https://github.com/networkx/networkx/pull/4435>`_]
+  Improve ``group_betweenness_centrality``.
+- [`#4446 <https://github.com/networkx/networkx/pull/4446>`_]
+  Add ``sources`` parameter to allow computing ``harmonic_centrality`` from a
+  subset of nodes.
+- [`#4463 <https://github.com/networkx/networkx/pull/4463>`_]
+  Adds the ``snap`` summarization algorithm.
+- [`#4476 <https://github.com/networkx/networkx/pull/4476>`_]
+  Adds the ``diameter`` function for approximating the lower bound on the
+  diameter of a graph.
+- [`#4519 <https://github.com/networkx/networkx/pull/4519>`_]
+  Handle negative weights in clustering algorithms.
+- [`#4528 <https://github.com/networkx/networkx/pull/4528>`_]
+  Improved performance of ``edge_boundary``.
+- [`#4560 <https://github.com/networkx/networkx/pull/4560>`_]
+  Adds ``prominent_group`` function to find prominent group of size k in
+  G according to group_betweenness_centrality.
+- [`#4588 <https://github.com/networkx/networkx/pull/4588>`_]
+  Graph intersection now works when input graphs don't have the same node sets.
+- [`#4607 <https://github.com/networkx/networkx/pull/4607>`_]
+  Adds approximation algorithms for solving the traveling salesman problem,
+  including ``christofides``, ``greedy_tsp``, ``simulated_annealing_tsp``,
+  and ``threshold_accepting_tsp``.
 - [`#4640 <https://github.com/networkx/networkx/pull/4640>`_]
   ``prefix_tree`` now uses a non-recursive algorithm. The original recursive
   algorithm is still available via ``prefix_tree_recursive``.
 - [`#4659 <https://github.com/networkx/networkx/pull/4659>`_]
   New ``initial_graph`` argument to ``barabasi_albert_graph`` and
   ``dual_barabasi_albert_graph`` to supply an initial graph to the model.
+- [`#4690 <https://github.com/networkx/networkx/pull/4690>`_]
+  ``modularity_max`` now supports edge weights.
+- [`#4727 <https://github.com/networkx/networkx/pull/4727>`_]
+  Improved performance of ``scale_free_graph``.
+- [`#4757 <https://github.com/networkx/networkx/pull/4757>`_]
+  Adds ``topological_generations`` function for DAG stratification.
+- [`#4768 <https://github.com/networkx/networkx/pull/4768>`_]
+  Improved reproducibility of geometric graph generators.
+- [`#4769 <https://github.com/networkx/networkx/pull/4769>`_]
+  Adds ``margins`` keyword to ``draw_networkx_nodes`` to control node clipping
+  in images with large node sizes.
+- [`#4812 <https://github.com/networkx/networkx/pull/4812>`_]
+  Use ``scipy`` implementation for ``hits`` algorithm to improve performance.
 
 API Changes
 -----------
 
+- [`#4183 <https://github.com/networkx/networkx/pull/4183>`_]
+  ``partition`` argument of `quotient_graph` now accepts dicts
 - [`#4190 <https://github.com/networkx/networkx/pull/4190>`_]
   Removed ``tracemin_chol``.  Use ``tracemin_lu`` instead.
 - [`#4216 <https://github.com/networkx/networkx/pull/4216>`_]
@@ -54,16 +147,23 @@ API Changes
   addition to the API change this may cause a performance regression for
   large graphs.
 - [`#4384 <https://github.com/networkx/networkx/pull/4384>`_]
-  Added edge_key parameter for MultiGraphs in to_pandas_edgelist
+  Added ``edge_key`` parameter for MultiGraphs in to_pandas_edgelist
+- [`#4461 <https://github.com/networkx/networkx/pull/4461>`_]
+  Added ``create_using`` parameter to ``binomial_tree``
 - [`#4466 <https://github.com/networkx/networkx/pull/4466>`_]
   `relabel_nodes` used to raise a KeyError for a key in `mapping` that is not
   a node in the graph, but it only did this when `copy` was `False`. Now
   any keys in `mapping` which are not in the graph are ignored.
+- [`#4502 <https://github.com/networkx/networkx/pull/4502>`_]
+  Moves ``maximum_independent_set`` to the ``clique`` module in ``approximation``.
+- [`#4536 <https://github.com/networkx/networkx/pull/4536>`_]
+  Deprecate ``performance`` and ``coverage`` in favor of ``partition_quality``,
+  which computes both metrics simultaneously and is more efficient.
 - [`#4573 <https://github.com/networkx/networkx/pull/4573>`_]
   `label_propagation_communities` returns a `dict_values` object of community
   sets of nodes instead of a generator of community sets. It is still iterable,
   so likely will still work in most user code and a simple fix otherwise:
-  e.g., add `iter( ... )` surrounding the function call.
+  e.g., add ``iter( ... )`` surrounding the function call.
 - [`#4545 <https://github.com/networkx/networkx/pull/4545>`_]
   `prefix_tree` used to return `tree, root` but root is now always 0
   instead of a UUID generate string. So the function returns `tree`.
@@ -73,6 +173,9 @@ API Changes
   The function `naive_greedy_modularity_communities` now returns a
   list of communities (like `greedy_modularity_communities`) instead
   of a generator of communities.
+- [`#4786 <https://github.com/networkx/networkx/pull/4786>`_]
+  Deprecate the ``attrs`` keyword argument in favor of explicit keyword
+  arguments in the ``json_graph`` module.
 
 Deprecations
 ------------
@@ -103,14 +206,22 @@ Deprecations
   Deprecate ``consume``.
 - [`#4448 <https://github.com/networkx/networkx/pull/4448>`_]
   Deprecate ``iterable``.
+- [`#4536 <https://github.com/networkx/networkx/pull/4536>`_]
+  Deprecate ``performance`` and ``coverage`` in favor of ``parition_quality``.
 - [`#4545 <https://github.com/networkx/networkx/pull/4545>`_]
   Deprecate ``generate_unique_node``.
 - [`#4599 <https://github.com/networkx/networkx/pull/4599>`_]
   Deprecate ``empty_generator``.
+- [`#4600 <https://github.com/networkx/networkx/pull/4600>`_]
+  Deprecate ``default_opener``.
 - [`#4617 <https://github.com/networkx/networkx/pull/4617>`_]
   Deprecate ``hub_matrix`` and ``authority_matrix``
 - [`#4629 <https://github.com/networkx/networkx/pull/4629>`_]
   Deprecate the ``Ordered`` graph classes.
+- [`#4802 <https://github.com/networkx/networkx/pull/4802>`_]
+  The ``nx_yaml`` function has been removed along with the dependency on
+  ``pyyaml``. Removal implemented via module ``__getattr__`` to patch security
+  warnings related to ``pyyaml.Loader``.
 - [`#4826 <https://github.com/networkx/networkx/pull/4826>`_]
   Deprecate ``preserve_random_state``.
 - [`#4827 <https://github.com/networkx/networkx/pull/4827>`_]