Repository: networkx/networkx

Issue:
Add to tutorial info about edge order
With Python 3.6 or later the behavior of Graph/DiGraph is ordered because dict's became ordered with that version.

And... The order of adjacency reporting... g.adj, g.successors, g.predecessors is now the order of edge adding.
But the order of g.edges is not always the order of edge adding. The order of g.edges is the order of the adjacencies which includes both the order of the nodes and each node's adjacencies.

```python
g = nx.DiGraph()
g.add_edge(2, 1)   # adds the nodes in order 2, 1
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(1, 2)
assert list(g.successors(2)) == [1, 4]
assert list(g.edges) == [(2, 1), (2, 4), (1, 3), (1, 2)]
```

We should add this kind of info to the tutorial.  (thought of because of question #4248 )

Discussion:

Patch:
diff --git a/.circleci/config.yml b/.circleci/config.yml
index 13930673a..cbdeb8b48 100644
--- a/.circleci/config.yml
+++ b/.circleci/config.yml
@@ -54,6 +54,7 @@ jobs:
             pip install --upgrade pip wheel setuptools
             pip install -r requirements.txt
             pip install -r requirements/extra.txt
+            pip install -r requirements/example-requirements.txt
             pip install -r requirements/example.txt
             pip install -U -r requirements/doc.txt
 
diff --git a/.github/workflows/deploy-docs.yml b/.github/workflows/deploy-docs.yml
index 146b16959..27c5c891a 100644
--- a/.github/workflows/deploy-docs.yml
+++ b/.github/workflows/deploy-docs.yml
@@ -30,7 +30,7 @@ jobs:
     - name: Mayavi setup
       run: |
         sudo apt-get --no-install-recommends install -y libxkbcommon-x11-0 optipng libxcb-icccm4 libxcb-image0 libxcb-keysyms1 libxcb-randr0 libxcb-render-util0 xcb libxcb-xfixes0 libxcb-xinerama0 libxcb-shape0
-        echo "export DISPLAY=:99" >> $BASH_ENV
+        export DISPLAY=:99
         /sbin/start-stop-daemon --start --quiet --pidfile /tmp/custom_xvfb_99.pid --make-pidfile --background --exec /usr/bin/Xvfb -- :99 -screen 0 1400x200x24 -ac +extension GLX +render -noreset;
 
     - name: Install packages
@@ -38,6 +38,7 @@ jobs:
         pip install --upgrade pip wheel setuptools
         pip install -r requirements.txt
         pip install -r requirements/extra.txt
+        pip install -r requirements/example-requirements.txt
         pip install -r requirements/example.txt
         pip install -U -r requirements/doc.txt
         export CPLUS_INCLUDE_PATH=/usr/include/gdal
@@ -48,9 +49,7 @@ jobs:
 
     - name: Build docs
       run: |
-        make -C doc/ html
-        make -C doc/ latexpdf LATEXOPTS="-file-line-error -halt-on-error"
-        cp -a doc/build/latex/networkx_reference.pdf doc/build/html/_downloads/.
+        echo "To do"
 
     - name: Deploy docs
       run: |
diff --git a/.travis.yml b/.travis.yml
index 7e6bd2d34..607435f61 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -50,6 +50,7 @@ after_success:
       pip install --upgrade pip wheel setuptools;
       pip install -r requirements.txt;
       pip install -r requirements/extra.txt;
+      pip install -r requirements/example-requirements.txt;
       pip install -r requirements/example.txt;
       pip install -U -r requirements/doc.txt;
       export CPLUS_INCLUDE_PATH=/usr/include/gdal;
diff --git a/doc/developer/deprecations.rst b/doc/developer/deprecations.rst
index 22bbf5372..ad647a00a 100644
--- a/doc/developer/deprecations.rst
+++ b/doc/developer/deprecations.rst
@@ -59,8 +59,9 @@ Version 3.0
 * In ``linalg/algebraicconnectivity.py`` remove ``_CholeskySolver`` and related code.
 * In ``convert_matrix.py`` remove ``to_numpy_matrix`` and ``from_numpy_matrix``.
 * In ``readwrite/json_graph/cytoscape.py``, change function signature for
-  ``cytoscape_graph`` and ``cytoscape_data`` to replace the ``attrs`` keyword
+  ``cytoscape_graph`` and ``cytoscape_data`` to replace the ``attrs`` keyword.
   argument with explicit ``name`` and ``ident`` keyword args.
 * Remove ``networkx/readwrite/nx_yaml.py`` and related tests.
-* Remove ``networkx/readwrite/gpickle.py`` and related tests. 
-* Remove ``networkx/readwrite/nx_shp.py`` and related tests (add info in alternatives). 
+* Remove ``networkx/readwrite/gpickle.py`` and related tests.
+* Remove ``networkx/readwrite/nx_shp.py`` and related tests (add info in alternatives).
+* Remove ``copy`` method in the coreview Filtered-related classes and related tests.
diff --git a/doc/release/release_dev.rst b/doc/release/release_dev.rst
index 02ecea975..a62657a63 100644
--- a/doc/release/release_dev.rst
+++ b/doc/release/release_dev.rst
@@ -53,6 +53,9 @@ Deprecations
   Deprecate ``read_gpickle`` and ``write_gpickle``.
 - [`#4298 <https://github.com/networkx/networkx/pull/4298>`_]
   Deprecate ``read_shp``, ``edges_from_line``, and ``write_shp``.
+- [`#4355 <https://github.com/networkx/networkx/pull/4355>`_]
+  Deprecate ``copy`` method in the coreview Filtered-related classes.
+
 
 Contributors to this release
 ----------------------------
diff --git a/doc/tutorial.rst b/doc/tutorial.rst
index 1de851a7f..4d4fd2972 100644
--- a/doc/tutorial.rst
+++ b/doc/tutorial.rst
@@ -131,6 +131,24 @@ At this stage the graph ``G`` consists of 8 nodes and 3 edges, as can be seen by
     >>> G.number_of_edges()
     3
 
+.. note:: 
+   
+   The order of adjacency reporting (e.g., G.adj, G.successors,
+   G.predecessors) is the order of edge addition. However, 
+   the order of G.edges is the order of the adjacencies
+   which includes both the order of the nodes and each 
+   node's adjacencies. See example below:
+
+.. nbplot::
+
+    >>> G = nx.DiGraph()
+    >>> G.add_edge(2, 1)   # adds the nodes in order 2, 1
+    >>> G.add_edge(1, 3)
+    >>> G.add_edge(2, 4)
+    >>> G.add_edge(1, 2)
+    >>> assert list(G.successors(2)) == [1, 4]
+    >>> assert list(G.edges) == [(2, 1), (2, 4), (1, 3), (1, 2)]
+
 Examining elements of a graph
 -----------------------------
 
diff --git a/networkx/classes/coreviews.py b/networkx/classes/coreviews.py
index e22f6855a..f824e4539 100644
--- a/networkx/classes/coreviews.py
+++ b/networkx/classes/coreviews.py
@@ -1,5 +1,6 @@
 """
 """
+import warnings
 from collections.abc import Mapping
 
 __all__ = [
@@ -283,7 +284,17 @@ class FilterAtlas(Mapping):  # nodedict, nbrdict, keydict
             return self._atlas[key]
         raise KeyError(f"Key {key} not found")
 
+    # FIXME should this just be removed? we don't use it, but someone might
     def copy(self):
+        warnings.warn(
+            (
+                "FilterAtlas.copy is deprecated.\n"
+                "It will be removed in NetworkX 3.0.\n"
+                "Please open an Issue on https://github.com/networkx/networkx/issues\n"
+                "if you use this feature. We think that no one does use it."
+            ),
+            DeprecationWarning,
+        )
         try:  # check that NODE_OK has attr 'nodes'
             node_ok_shorter = 2 * len(self.NODE_OK.nodes) < len(self._atlas)
         except AttributeError:
@@ -326,7 +337,17 @@ class FilterAdjacency(Mapping):  # edgedict
             return FilterAtlas(self._atlas[node], new_node_ok)
         raise KeyError(f"Key {node} not found")
 
+    # FIXME should this just be removed? we don't use it, but someone might
     def copy(self):
+        warnings.warn(
+            (
+                "FilterAdjacency.copy is deprecated.\n"
+                "It will be removed in NetworkX 3.0.\n"
+                "Please open an Issue on https://github.com/networkx/networkx/issues\n"
+                "if you use this feature. We think that no one does use it."
+            ),
+            DeprecationWarning,
+        )
         try:  # check that NODE_OK has attr 'nodes'
             node_ok_shorter = 2 * len(self.NODE_OK.nodes) < len(self._atlas)
         except AttributeError:
@@ -384,7 +405,17 @@ class FilterMultiInner(FilterAdjacency):  # muliedge_seconddict
             return FilterAtlas(self._atlas[nbr], new_node_ok)
         raise KeyError(f"Key {nbr} not found")
 
+    # FIXME should this just be removed? we don't use it, but someone might
     def copy(self):
+        warnings.warn(
+            (
+                "FilterMultiInner.copy is deprecated.\n"
+                "It will be removed in NetworkX 3.0.\n"
+                "Please open an Issue on https://github.com/networkx/networkx/issues\n"
+                "if you use this feature. We think that no one does use it."
+            ),
+            DeprecationWarning,
+        )
         try:  # check that NODE_OK has attr 'nodes'
             node_ok_shorter = 2 * len(self.NODE_OK.nodes) < len(self._atlas)
         except AttributeError:
@@ -412,7 +443,17 @@ class FilterMultiAdjacency(FilterAdjacency):  # multiedgedict
             return FilterMultiInner(self._atlas[node], self.NODE_OK, edge_ok)
         raise KeyError(f"Key {node} not found")
 
+    # FIXME should this just be removed? we don't use it, but someone might
     def copy(self):
+        warnings.warn(
+            (
+                "FilterMultiAdjacency.copy is deprecated.\n"
+                "It will be removed in NetworkX 3.0.\n"
+                "Please open an Issue on https://github.com/networkx/networkx/issues\n"
+                "if you use this feature. We think that no one does use it."
+            ),
+            DeprecationWarning,
+        )
         try:  # check that NODE_OK has attr 'nodes'
             node_ok_shorter = 2 * len(self.NODE_OK.nodes) < len(self._atlas)
         except AttributeError:
diff --git a/networkx/utils/misc.py b/networkx/utils/misc.py
index 74cca6dd1..7011ce726 100644
--- a/networkx/utils/misc.py
+++ b/networkx/utils/misc.py
@@ -62,7 +62,7 @@ def flatten(obj, result=None):
             result.append(item)
         else:
             flatten(item, result)
-    return obj.__class__(result)
+    return tuple(result)
 
 
 def make_list_of_ints(sequence):
diff --git a/requirements/example-requirements.txt b/requirements/example-requirements.txt
new file mode 100644
index 000000000..a55fb87db
--- /dev/null
+++ b/requirements/example-requirements.txt
@@ -0,0 +1,3 @@
+# For mayavi
+vtk>=9.0
+pyqt5>=5.15
diff --git a/requirements/example.txt b/requirements/example.txt
index 107696620..a1118222f 100644
--- a/requirements/example.txt
+++ b/requirements/example.txt
@@ -8,6 +8,4 @@ geopandas>=0.8
 osmnx>=0.16
 pysal>=2.3
 # For mayavi
-vtk>=9.0
-pyqt5>=5.15
 mayavi>=4.7


Test patch:
diff --git a/networkx/algorithms/shortest_paths/generic.py b/networkx/algorithms/shortest_paths/generic.py
index 97d3a530e..5a277e363 100644
--- a/networkx/algorithms/shortest_paths/generic.py
+++ b/networkx/algorithms/shortest_paths/generic.py
@@ -159,7 +159,7 @@ def shortest_path(G, source=None, target=None, weight=None, method="dijkstra"):
             if method == "unweighted":
                 paths = nx.bidirectional_shortest_path(G, source, target)
             elif method == "dijkstra":
-                paths = nx.dijkstra_path(G, source, target, weight)
+                _, paths = nx.bidirectional_dijkstra(G, source, target, weight)
             else:  # method == 'bellman-ford':
                 paths = nx.bellman_ford_path(G, source, target, weight)
     return paths
diff --git a/networkx/classes/tests/test_coreviews.py b/networkx/classes/tests/test_coreviews.py
index c9b259a09..2d5fe82ee 100644
--- a/networkx/classes/tests/test_coreviews.py
+++ b/networkx/classes/tests/test_coreviews.py
@@ -315,10 +315,10 @@ class TestUnionMultiAdjacency(TestUnionAdjacency):
 class TestFilteredGraphs:
     def setup(self):
         self.Graphs = [nx.Graph, nx.DiGraph, nx.MultiGraph, nx.MultiDiGraph]
-        self.SubGraphs = [nx.graphviews.subgraph_view] * 4
 
     def test_hide_show_nodes(self):
-        for Graph, SubGraph in zip(self.Graphs, self.SubGraphs):
+        SubGraph = nx.graphviews.subgraph_view
+        for Graph in self.Graphs:
             G = nx.path_graph(4, Graph)
             SG = G.subgraph([2, 3])
             RG = SubGraph(G, nx.filters.hide_nodes([0, 1]))
@@ -330,7 +330,8 @@ class TestFilteredGraphs:
             assert SGC.edges == RGC.edges
 
     def test_str_repr(self):
-        for Graph, SubGraph in zip(self.Graphs, self.SubGraphs):
+        SubGraph = nx.graphviews.subgraph_view
+        for Graph in self.Graphs:
             G = nx.path_graph(4, Graph)
             SG = G.subgraph([2, 3])
             RG = SubGraph(G, nx.filters.hide_nodes([0, 1]))
@@ -344,13 +345,86 @@ class TestFilteredGraphs:
             repr(RG.adj[2])
 
     def test_copy(self):
-        for Graph, SubGraph in zip(self.Graphs, self.SubGraphs):
+        SubGraph = nx.graphviews.subgraph_view
+        for Graph in self.Graphs:
             G = nx.path_graph(4, Graph)
             SG = G.subgraph([2, 3])
             RG = SubGraph(G, nx.filters.hide_nodes([0, 1]))
+            RsG = SubGraph(G, nx.filters.show_nodes([2, 3]))
             assert G.adj.copy() == G.adj
             assert G.adj[2].copy() == G.adj[2]
             assert SG.adj.copy() == SG.adj
             assert SG.adj[2].copy() == SG.adj[2]
             assert RG.adj.copy() == RG.adj
             assert RG.adj[2].copy() == RG.adj[2]
+            assert RsG.adj.copy() == RsG.adj
+            assert RsG.adj[2].copy() == RsG.adj[2]
+
+    def test_filtered_copy(self):
+        # TODO: This function can be removed when filtered.copy()
+        # deprecation expires
+        SubGraph = nx.graphviews.subgraph_view
+        for Graph in self.Graphs:
+            G = nx.path_graph(4, Graph)
+            SG = G.subgraph([2, 3])
+            RG = SubGraph(G, nx.filters.hide_nodes([0, 1]))
+            RsG = SubGraph(G, nx.filters.show_nodes([2, 3]))
+            # test FilterAtlas & co in these subgraphs
+            assert SG._node.copy() == SG._node
+            assert SG.adj._atlas.copy() == SG.adj._atlas
+            assert SG.adj[2]._atlas.copy() == SG.adj[2]._atlas
+            assert SG.adj[2]._atlas[3].copy() == SG.adj[2]._atlas[3]
+            assert RG.adj._atlas.copy() == RG.adj._atlas
+            assert RG.adj[2]._atlas.copy() == RG.adj[2]._atlas
+            assert RG.adj[2]._atlas[3].copy() == RG.adj[2]._atlas[3]
+            assert RG._node.copy() == RG._node
+            assert RsG.adj._atlas.copy() == RsG.adj._atlas
+            assert RsG.adj[2]._atlas.copy() == RsG.adj[2]._atlas
+            assert RsG.adj[2]._atlas[3].copy() == RsG.adj[2]._atlas[3]
+            assert RsG._node.copy() == RsG._node
+            # test MultiFilterInner
+            if G.is_multigraph():
+                assert SG.adj[2]._atlas[3][0].copy() == SG.adj[2]._atlas[3][0]
+                assert RG.adj[2]._atlas[3][0].copy() == RG.adj[2]._atlas[3][0]
+                assert RsG.adj[2]._atlas[3][0].copy() == RsG.adj[2]._atlas[3][0]
+
+            # test deprecation
+            # FilterAtlas.copy()
+            pytest.deprecated_call(SG._node.copy)
+            # FilterAdjacency.copy()
+            pytest.deprecated_call(SG.adj._atlas.copy)
+            # FilterMultiAdjacency.copy()
+            if G.is_multigraph():
+                pytest.deprecated_call(SG.adj._atlas.copy)
+            # FilterMultiInner.copy()
+            if G.is_multigraph():
+                pytest.deprecated_call(SG.adj[2]._atlas.copy)
+
+            SSG = SG.subgraph([2])
+            assert list(SSG) == [2]
+
+            # check case when node_ok is small
+            G = nx.complete_graph(9, Graph)
+            SG = G.subgraph([2, 3])
+            RG = SubGraph(G, nx.filters.hide_nodes([0, 1]))
+            RsG = SubGraph(G, nx.filters.show_nodes([2, 3, 4, 5, 6, 7, 8]))
+            assert SG.adj._atlas.copy() == SG.adj._atlas
+            assert SG.adj[2]._atlas.copy() == SG.adj[2]._atlas
+            assert SG.adj[2]._atlas[3].copy() == SG.adj[2]._atlas[3]
+            assert SG._node.copy() == SG._node
+            assert RG.adj._atlas.copy() == RG.adj._atlas
+            assert RG.adj[2]._atlas.copy() == RG.adj[2]._atlas
+            assert RG.adj[2]._atlas[3].copy() == RG.adj[2]._atlas[3]
+            assert RG._node.copy() == RG._node
+            assert RsG.adj._atlas.copy() == RsG.adj._atlas
+            assert RsG.adj[2]._atlas.copy() == RsG.adj[2]._atlas
+            assert RsG.adj[2]._atlas[3].copy() == RsG.adj[2]._atlas[3]
+            assert RsG._node.copy() == RsG._node
+            # test MultiFilterInner
+            if G.is_multigraph():
+                assert SG.adj[2][3]._atlas.copy() == SG.adj[2][3]._atlas
+                assert RG.adj[2][3]._atlas.copy() == RG.adj[2][3]._atlas
+                assert RsG.adj[2][3]._atlas.copy() == RsG.adj[2][3]._atlas
+
+            SSG = SG.subgraph([2])
+            assert list(SSG) == [2]
diff --git a/networkx/utils/tests/test_misc.py b/networkx/utils/tests/test_misc.py
index 3ecf2ef0b..b20648cb1 100644
--- a/networkx/utils/tests/test_misc.py
+++ b/networkx/utils/tests/test_misc.py
@@ -1,3 +1,5 @@
+from copy import copy
+
 import pytest
 import networkx as nx
 import random
@@ -8,6 +10,7 @@ from networkx.utils import (
     dict_to_numpy_array,
     dict_to_numpy_array1,
     dict_to_numpy_array2,
+    flatten,
     is_string_like,
     iterable,
     groups,
@@ -19,6 +22,56 @@ from networkx.utils import (
     to_tuple,
 )
 
+nested_depth = (
+    1,
+    2,
+    (
+        3,
+        4,
+        (
+            (5, 6, (7,), (8, (9, 10), 11), (12, 13, (14, 15)), 16),
+            17,
+        ),
+        18,
+        19,
+    ),
+    20,
+)
+
+nested_set = {
+    (1, 2, 3, 4),
+    (5, 6, 7, 8, 9),
+    (10, 11, (12, 13, 14), (15, 16, 17, 18)),
+    19,
+    20,
+}
+
+nested_mixed = [
+    1,
+    (2, 3, {4, (5, 6), 7}, [8, 9]),
+    {10: "foo", 11: "bar", (12, 13): "baz"},
+    {(14, 15): "qwe", 16: "asd"},
+    (17, (18, "19"), 20),
+]
+
+
+@pytest.mark.parametrize("result", [None, [], ["existing"], ["existing1", "existing2"]])
+@pytest.mark.parametrize(
+    "nested",
+    [nested_depth, nested_mixed, nested_set],
+)
+def test_flatten(nested, result):
+    if result is None:
+        val = flatten(nested, result)
+        assert len(val) == 20
+    else:
+        _result = copy(result)  # because pytest passes parameters as is
+        nexisting = len(_result)
+        val = flatten(nested, _result)
+        assert len(val) == len(_result) == 20 + nexisting
+
+    assert issubclass(type(val), tuple)
+
 
 def test_is_string_like():
     assert is_string_like("aaaa")