Deprecate Ordered graph classes (#4629)

* Add deprecation warning + docstrings to Ordered constructors.

Adds explicit __init__ methods to the Ordered graph classes.
These are pass-through methods, the only purpose of which is to
raise a DeprecationWarning whenever one of the Ordered classes
is instantiated.

* Add warnings filter to conftest.

* move depr directives to class docstrings.

Works better with autoclass.

* Add depr reminder to developer/deprecations.rst.

* Add note to release_dev.

4 files changed, 94 insertions, 4 deletions

diff --git a/doc/developer/deprecations.rst b/doc/developer/deprecations.rst
index 812f4ace..1ceb637b 100644
--- a/doc/developer/deprecations.rst
+++ b/doc/developer/deprecations.rst
@@ -75,3 +75,5 @@ Version 3.0
 * Remove ``readwrite/json_graph/jit.py`` and related tests.
 * In ``utils/misc.py`` remove ``generate_unique_node`` and related tests.
 * In ``algorithms/link_analysis/hits_alg.py`` remove ``hub_matrix`` and ``authority_matrix``
+* In ``networkx.classes`` remove the ``ordered`` module and the four ``Ordered``
+  classes defined therein.
diff --git a/doc/release/release_dev.rst b/doc/release/release_dev.rst
index b19e0e2a..7ed72a03 100644
--- a/doc/release/release_dev.rst
+++ b/doc/release/release_dev.rst
@@ -100,6 +100,8 @@ Deprecations
   Deprecate ``empty_generator``.
 - [`#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.
 
 
 
diff --git a/networkx/classes/ordered.py b/networkx/classes/ordered.py
index 74bd5965..67021e5a 100644
--- a/networkx/classes/ordered.py
+++ b/networkx/classes/ordered.py
@@ -1,4 +1,10 @@
 """
+
+.. deprecated:: 2.6
+
+   The ordered variants of graph classes in this module are deprecated and
+   will be removed in version 3.0.
+
 Consistently ordered variants of the default base classes.
 Note that if you are using Python 3.6+, you shouldn't need these classes
 because the dicts in Python 3.6+ are ordered.
@@ -28,6 +34,7 @@ subgraphs and replace with code similar to:
 
 """
 from collections import OrderedDict
+import warnings
 
 from .graph import Graph
 from .multigraph import MultiGraph
@@ -42,25 +49,70 @@ __all__.extend(
 
 
 class OrderedGraph(Graph):
-    """Consistently ordered variant of :class:`~networkx.Graph`."""
+    """Consistently ordered variant of :class:`~networkx.Graph`.
+
+    .. deprecated:: 2.6
+
+       OrderedGraph is deprecated and will be removed in version 3.0.
+       Use `Graph` instead, which guarantees order is preserved for
+       Python >= 3.7
+    """
 
     node_dict_factory = OrderedDict
     adjlist_outer_dict_factory = OrderedDict
     adjlist_inner_dict_factory = OrderedDict
     edge_attr_dict_factory = OrderedDict
 
+    def __init__(self, incoming_graph_data=None, **attr):
+        warnings.warn(
+            (
+                "OrderedGraph is deprecated and will be removed in version 3.0.\n"
+                "Use `Graph` instead, which guarantees order is preserved for\n"
+                "Python >= 3.7\n"
+            ),
+            DeprecationWarning,
+            stacklevel=2,
+        )
+        super(OrderedGraph, self).__init__(incoming_graph_data, **attr)
+
 
 class OrderedDiGraph(DiGraph):
-    """Consistently ordered variant of :class:`~networkx.DiGraph`."""
+    """Consistently ordered variant of :class:`~networkx.DiGraph`.
+
+    .. deprecated:: 2.6
+
+       OrderedDiGraph is deprecated and will be removed in version 3.0.
+       Use `DiGraph` instead, which guarantees order is preserved for
+       Python >= 3.7
+    """
 
     node_dict_factory = OrderedDict
     adjlist_outer_dict_factory = OrderedDict
     adjlist_inner_dict_factory = OrderedDict
     edge_attr_dict_factory = OrderedDict
 
+    def __init__(self, incoming_graph_data=None, **attr):
+        warnings.warn(
+            (
+                "OrderedDiGraph is deprecated and will be removed in version 3.0.\n"
+                "Use `DiGraph` instead, which guarantees order is preserved for\n"
+                "Python >= 3.7\n"
+            ),
+            DeprecationWarning,
+            stacklevel=2,
+        )
+        super(OrderedDiGraph, self).__init__(incoming_graph_data, **attr)
+
 
 class OrderedMultiGraph(MultiGraph):
-    """Consistently ordered variant of :class:`~networkx.MultiGraph`."""
+    """Consistently ordered variant of :class:`~networkx.MultiGraph`.
+
+    .. deprecated:: 2.6
+
+       OrderedMultiGraph is deprecated and will be removed in version 3.0.
+       Use `MultiGraph` instead, which guarantees order is preserved for
+       Python >= 3.7
+    """
 
     node_dict_factory = OrderedDict
     adjlist_outer_dict_factory = OrderedDict
@@ -68,12 +120,43 @@ class OrderedMultiGraph(MultiGraph):
     edge_key_dict_factory = OrderedDict
     edge_attr_dict_factory = OrderedDict
 
+    def __init__(self, incoming_graph_data=None, **attr):
+        warnings.warn(
+            (
+                "OrderedMultiGraph is deprecated and will be removed in version 3.0.\n"
+                "Use `MultiGraph` instead, which guarantees order is preserved for\n"
+                "Python >= 3.7\n"
+            ),
+            DeprecationWarning,
+            stacklevel=2,
+        )
+        super(OrderedMultiGraph, self).__init__(incoming_graph_data, **attr)
+
 
 class OrderedMultiDiGraph(MultiDiGraph):
-    """Consistently ordered variant of :class:`~networkx.MultiDiGraph`."""
+    """Consistently ordered variant of :class:`~networkx.MultiDiGraph`.
+
+    .. deprecated:: 2.6
+
+       OrderedMultiDiGraph is deprecated and will be removed in version 3.0.
+       Use `MultiDiGraph` instead, which guarantees order is preserved for
+       Python >= 3.7
+    """
 
     node_dict_factory = OrderedDict
     adjlist_outer_dict_factory = OrderedDict
     adjlist_inner_dict_factory = OrderedDict
     edge_key_dict_factory = OrderedDict
     edge_attr_dict_factory = OrderedDict
+
+    def __init__(self, incoming_graph_data=None, **attr):
+        warnings.warn(
+            (
+                "OrderedMultiDiGraph is deprecated and will be removed in version 3.0.\n"
+                "Use `MultiDiGraph` instead, which guarantees order is preserved for\n"
+                "Python >= 3.7\n"
+            ),
+            DeprecationWarning,
+            stacklevel=2,
+        )
+        super(OrderedMultiDiGraph, self).__init__(incoming_graph_data, **attr)
diff --git a/networkx/conftest.py b/networkx/conftest.py
index d3b93087..53bf5dc9 100644
--- a/networkx/conftest.py
+++ b/networkx/conftest.py
@@ -28,6 +28,9 @@ def pytest_collection_modifyitems(config, items):
 @pytest.fixture(autouse=True)
 def set_warnings():
     warnings.filterwarnings(
+        "ignore", category=DeprecationWarning, message=r"Ordered.* is deprecated"
+    )
+    warnings.filterwarnings(
         "ignore",
         category=DeprecationWarning,
         message="literal_stringizer is deprecated",