Repository: networkx/networkx

Issue:
Dispatched nx-loopback tests performance degradation
This is something I noticed while investigating #7354. The test suite when run with the `nx-loopback` backend is significantly slower than when run without loopback. I'd expect it to be a little slower due to the extra conversion overhead, but AIUI that should be limited to adding a single attribute to the graph which should not be very expensive. The total performance degradation is signficantly greater than what I'd expect from additional call/conversion overhead.

For example, I've noticed that [`test_omega`](https://github.com/networkx/networkx/blob/fbb2d82dc7b69f104eedd4f8630c4ab6e1b6713e/networkx/algorithms/tests/test_smallworld.py#L51) is an order of magnitude slower with loopback enabled:

### Without loopback

```
pytest -k test_omega networkx/algorithms/tests/test_smallworld.py =========================================================== test session starts ===========================================================
platform linux -- Python 3.11.6, pytest-8.1.1, pluggy-1.4.0
Matplotlib: 3.8.3
Freetype: 2.6.1
configfile: pyproject.toml
plugins: mpl-0.17.0, cov-5.0.0, xdist-3.5.0
collected 6 items / 5 deselected / 1 selected                                                                                             

networkx/algorithms/tests/test_smallworld.py .                                                                                      [100%]

===================================================== 1 passed, 5 deselected in 2.07s =====================================================
```

### With loopback

```NETWORKX_TEST_BACKEND=nx-loopback pytest -k test_omega networkx/algorithms/tests/test_smallworld.py 
=========================================================== test session starts ===========================================================
platform linux -- Python 3.11.6, pytest-8.1.1, pluggy-1.4.0
Matplotlib: 3.8.3
Freetype: 2.6.1
configfile: pyproject.toml
plugins: mpl-0.17.0, cov-5.0.0, xdist-3.5.0
collected 6 items / 5 deselected / 1 selected                                                                                             

networkx/algorithms/tests/test_smallworld.py .                                                                                      [100%]

==================================================== 1 passed, 5 deselected in 36.31s =====================================================
```

I haven't done an exhaustive comparison to see which tests are most affected, but this is probably a good place to start looking as it's the worst offender (at least on my system).


Discussion:
dschult: If this copy code works for nx-loopback -- I think we should update the copy methods in the base classes to ensure that the neighbor/adjacency order is maintained when users do `G.copy()`.  It didn't matter when the order of the neighbors was arbitrary based on storage/reporting within a Python dict. But now that dicts have ordered keys, users might expect the order to be the same after a copy.

Would maintaining the adjacency order during `copy` be considered a breaking change? We didn't tell people the current reordering was a feature -- indeed, we said the order could be machine dependent. But it is possible that some people are counting on a specific order after a copy.  Still, my inclination is that implementing `copy` as maintaining neighbor order is not breaking any assurance. Your output may change from what it was, but now it has a defined pattern. Anyway, I'm open to a deprecation on that (still to be written) PR if/when we get to it.
dschult: The timing results I was getting are apparently a "feature" of my local testing environment. I would like some help in getting my environment set up better.

Running `NETWORKX_TEST_BACKEND=nx-loopback pytest --doctest-modules --durations=10 --pyargs networkx` from the base dir of my repo runs all the tests just fine **without** the loopback!!  I get the same results as running it without the environment variable set.  I can add an `assert False` to a test file in the repo and that test fails. So I am testing the correct files, just not with the loopback backend.  I have put `assert False` into the `loopback.convert_from_nx` function and it is never reached.

`NETWORKX_TEST_BACKEND=nx-loopback pytest --doctest-modules --durations=10 --pyargs networkx/classes` (or any other specific file or dir within the networkx repo) runs **with** the nx-loopback process. All the files and loopback functions are called as they should be.

I do not have networkx installed in this mamba environment. I have used `pip install -e .` to create the egg directory in the repo's home directory. Without that, the testing command leads to an error about nx-loopback not being a backend. And that error happens even when pointing to specific files/dirs to run the tests for.

So...  How do i run pytest on the whole repo using nx-loopback as my backend?
dschult: I've now found that I can get `nx-loopback` testing feature working while testing the whole library so long as I don't try to use the `--doctest-modules` option. :)  
```NETWORKX_TEST_BACKEND=nx-loopback pytest --doctest-modules --pyargs networkx```
doesn't convert using nx-loopback. But without the doctests it does. 
dschult: This change to keep edge order consistent during nx-loopback conversion is ready for review.
It should work to make #7398 pass the dispatch tests -- but I haven't tested that yet.

Patch:
diff --git a/networkx/algorithms/assortativity/pairs.py b/networkx/algorithms/assortativity/pairs.py
index 5a1d6f8e1..1b8c3460d 100644
--- a/networkx/algorithms/assortativity/pairs.py
+++ b/networkx/algorithms/assortativity/pairs.py
@@ -1,4 +1,4 @@
-"""Generators of  x-y pairs of node data."""
+"""Generators of x-y pairs of node data."""
 import networkx as nx
 
 __all__ = ["node_attribute_xy", "node_degree_xy"]
@@ -6,21 +6,25 @@ __all__ = ["node_attribute_xy", "node_degree_xy"]
 
 @nx._dispatchable(node_attrs="attribute")
 def node_attribute_xy(G, attribute, nodes=None):
-    """Returns iterator of node-attribute pairs for all edges in G.
+    """Yields 2-tuples of node attribute values for all edges in `G`.
+
+    This generator yields, for each edge in `G` incident to a node in `nodes`,
+    a 2-tuple of form ``(attribute value,  attribute value)`` for the parameter
+    specified node-attribute.
 
     Parameters
     ----------
     G: NetworkX graph
 
     attribute: key
-       The node attribute key.
+        The node attribute key.
 
     nodes: list or iterable (optional)
         Use only edges that are incident to specified nodes.
         The default is all nodes.
 
-    Returns
-    -------
+    Yields
+    ------
     (x, y): 2-tuple
         Generates 2-tuple of (attribute, attribute) values.
 
@@ -29,13 +33,14 @@ def node_attribute_xy(G, attribute, nodes=None):
     >>> G = nx.DiGraph()
     >>> G.add_node(1, color="red")
     >>> G.add_node(2, color="blue")
+    >>> G.add_node(3, color="green")
     >>> G.add_edge(1, 2)
     >>> list(nx.node_attribute_xy(G, "color"))
     [('red', 'blue')]
 
     Notes
     -----
-    For undirected graphs each edge is produced twice, once for each edge
+    For undirected graphs, each edge is produced twice, once for each edge
     representation (u, v) and (v, u), with the exception of self-loop edges
     which only appear once.
     """
@@ -61,7 +66,11 @@ def node_attribute_xy(G, attribute, nodes=None):
 
 @nx._dispatchable(edge_attrs="weight")
 def node_degree_xy(G, x="out", y="in", weight=None, nodes=None):
-    """Generate node degree-degree pairs for edges in G.
+    """Yields 2-tuples of ``(degree, degree)`` values for edges in `G`.
+
+    This generator yields, for each edge in `G` incident to a node in `nodes`,
+    a 2-tuple of form ``(degree, degree)``. The node degrees are weighted
+    when a `weight` attribute is specified.
 
     Parameters
     ----------
@@ -82,12 +91,11 @@ def node_degree_xy(G, x="out", y="in", weight=None, nodes=None):
         Use only edges that are adjacency to specified nodes.
         The default is all nodes.
 
-    Returns
-    -------
+    Yields
+    ------
     (x, y): 2-tuple
         Generates 2-tuple of (degree, degree) values.
 
-
     Examples
     --------
     >>> G = nx.DiGraph()
@@ -99,7 +107,7 @@ def node_degree_xy(G, x="out", y="in", weight=None, nodes=None):
 
     Notes
     -----
-    For undirected graphs each edge is produced twice, once for each edge
+    For undirected graphs, each edge is produced twice, once for each edge
     representation (u, v) and (v, u), with the exception of self-loop edges
     which only appear once.
     """
diff --git a/networkx/classes/digraph.py b/networkx/classes/digraph.py
index fc2374a2b..2547201f2 100644
--- a/networkx/classes/digraph.py
+++ b/networkx/classes/digraph.py
@@ -25,6 +25,9 @@ class _CachedPropertyResetterAdjAndSucc:
     are set to new objects. In addition, the attributes `_succ` and `_adj`
     are synced so these two names point to the same object.
 
+    Warning: most of the time, when ``G._adj`` is set, ``G._pred`` should also
+    be set to maintain a valid data structure. They share datadicts.
+
     This object sits on a class and ensures that any instance of that
     class clears its cached properties "succ" and "adj" whenever the
     underlying instance attributes "_succ" or "_adj" are set to a new object.
@@ -39,10 +42,18 @@ class _CachedPropertyResetterAdjAndSucc:
         od["_adj"] = value
         od["_succ"] = value
         # reset cached properties
-        if "adj" in od:
-            del od["adj"]
-        if "succ" in od:
-            del od["succ"]
+        props = [
+            "adj",
+            "succ",
+            "edges",
+            "out_edges",
+            "degree",
+            "out_degree",
+            "in_degree",
+        ]
+        for prop in props:
+            if prop in od:
+                del od[prop]
 
 
 class _CachedPropertyResetterPred:
@@ -51,6 +62,9 @@ class _CachedPropertyResetterPred:
     This assumes that the ``cached_property`` ``G.pred`` should be reset whenever
     ``G._pred`` is set to a new value.
 
+    Warning: most of the time, when ``G._pred`` is set, ``G._adj`` should also
+    be set to maintain a valid data structure. They share datadicts.
+
     This object sits on a class and ensures that any instance of that
     class clears its cached property "pred" whenever the underlying
     instance attribute "_pred" is set to a new object. It only affects
@@ -63,8 +77,11 @@ class _CachedPropertyResetterPred:
     def __set__(self, obj, value):
         od = obj.__dict__
         od["_pred"] = value
-        if "pred" in od:
-            del od["pred"]
+        # reset cached properties
+        props = ["pred", "in_edges", "degree", "out_degree", "in_degree"]
+        for prop in props:
+            if prop in od:
+                del od[prop]
 
 
 class DiGraph(Graph):
diff --git a/networkx/classes/graph.py b/networkx/classes/graph.py
index bf628ed62..ae11d1b08 100644
--- a/networkx/classes/graph.py
+++ b/networkx/classes/graph.py
@@ -37,8 +37,11 @@ class _CachedPropertyResetterAdj:
     def __set__(self, obj, value):
         od = obj.__dict__
         od["_adj"] = value
-        if "adj" in od:
-            del od["adj"]
+        # reset cached properties
+        props = ["adj", "edges", "degree"]
+        for prop in props:
+            if prop in od:
+                del od[prop]
 
 
 class _CachedPropertyResetterNode:
@@ -59,6 +62,7 @@ class _CachedPropertyResetterNode:
     def __set__(self, obj, value):
         od = obj.__dict__
         od["_node"] = value
+        # reset cached properties
         if "nodes" in od:
             del od["nodes"]
 
diff --git a/networkx/convert_matrix.py b/networkx/convert_matrix.py
index d4c924a85..12017fe26 100644
--- a/networkx/convert_matrix.py
+++ b/networkx/convert_matrix.py
@@ -348,7 +348,7 @@ def from_pandas_edgelist(
     edge_attr : str or int, iterable, True, or None
         A valid column name (str or int) or iterable of column names that are
         used to retrieve items and add them to the graph as edge attributes.
-        If `True`, all of the remaining columns will be added.
+        If `True`, all columns will be added except `source`, `target` and `edge_key`.
         If `None`, no edge attributes are added to the graph.
 
     create_using : NetworkX graph constructor, optional (default=nx.Graph)
@@ -436,6 +436,8 @@ def from_pandas_edgelist(
         return g
 
     reserved_columns = [source, target]
+    if g.is_multigraph() and edge_key is not None:
+        reserved_columns.append(edge_key)
 
     # Additional columns requested
     attr_col_headings = []
diff --git a/networkx/generators/trees.py b/networkx/generators/trees.py
index c1b0d7935..1651a036a 100644
--- a/networkx/generators/trees.py
+++ b/networkx/generators/trees.py
@@ -452,6 +452,24 @@ def random_labeled_tree(n, *, seed=None):
     ------
     NetworkXPointlessConcept
         If `n` is zero (because the null graph is not a tree).
+
+    Examples
+    --------
+    >>> G = nx.random_labeled_tree(5, seed=42)
+    >>> nx.is_tree(G)
+    True
+    >>> G.edges
+    EdgeView([(0, 1), (0, 3), (0, 2), (2, 4)])
+
+    A tree with *arbitrarily directed* edges can be created by assigning
+    generated edges to a ``DiGraph``:
+
+    >>> DG = nx.DiGraph()
+    >>> DG.add_edges_from(G.edges)
+    >>> nx.is_tree(DG)
+    True
+    >>> DG.edges
+    OutEdgeView([(0, 1), (0, 3), (0, 2), (2, 4)])
     """
     # Cannot create a Prüfer sequence unless `n` is at least two.
     if n == 0:
diff --git a/networkx/utils/backends.py b/networkx/utils/backends.py
index b48798d80..1472e7768 100644
--- a/networkx/utils/backends.py
+++ b/networkx/utils/backends.py
@@ -1059,15 +1059,13 @@ class _dispatchable:
             # node_attrs: dict | None
             # preserve_edge_attrs: bool (False if edge_attrs is not None)
             # preserve_node_attrs: bool (False if node_attrs is not None)
-            # preserve_graph_attrs: bool
-            key = edge_key, node_key, graph_key = (
+            key = edge_key, node_key = (
                 frozenset(edge_attrs.items())
                 if edge_attrs is not None
                 else preserve_edge_attrs,
                 frozenset(node_attrs.items())
                 if node_attrs is not None
                 else preserve_node_attrs,
-                preserve_graph_attrs,
             )
             if cache:
                 warning_message = (
@@ -1085,8 +1083,8 @@ class _dispatchable:
                     "will correctly clear the cache to keep it consistent. "
                     "You may also use `G.__networkx_cache__.clear()` to "
                     "manually clear the cache, or set `G.__networkx_cache__` "
-                    "to None to disable caching for G. Enable or disable "
-                    "caching via `nx.config.cache_converted_graphs` config."
+                    "to None to disable caching for G. Enable or disable caching "
+                    "globally via `nx.config.cache_converted_graphs` config."
                 )
                 # Do a simple search for a cached graph with compatible data.
                 # For example, if we need a single attribute, then it's okay
@@ -1095,7 +1093,6 @@ class _dispatchable:
                 for compat_key in itertools.product(
                     (edge_key, True) if edge_key is not True else (True,),
                     (node_key, True) if node_key is not True else (True,),
-                    (graph_key, True) if graph_key is not True else (True,),
                 ):
                     if (rv := cache.get(compat_key)) is not None:
                         warnings.warn(warning_message)
@@ -1106,25 +1103,23 @@ class _dispatchable:
                     # with any edge attribute will suffice. We use the same logic
                     # below (but switched) to clear unnecessary items from the cache.
                     # Use `list(cache.items())` to be thread-safe.
-                    for (ekey, nkey, gkey), val in list(cache.items()):
+                    for (ekey, nkey), val in list(cache.items()):
                         if edge_key is False or ekey is True:
-                            pass
+                            pass  # Cache works for edge data!
                         elif (
                             edge_key is True
                             or ekey is False
                             or not edge_key.issubset(ekey)
                         ):
-                            continue
+                            continue  # Cache missing required edge data; does not work
                         if node_key is False or nkey is True:
-                            pass
+                            pass  # Cache works for node data!
                         elif (
                             node_key is True
                             or nkey is False
                             or not node_key.issubset(nkey)
                         ):
-                            continue
-                        if graph_key and not gkey:
-                            continue
+                            continue  # Cache missing required node data; does not work
                         warnings.warn(warning_message)
                         return val
 
@@ -1135,7 +1130,10 @@ class _dispatchable:
             node_attrs=node_attrs,
             preserve_edge_attrs=preserve_edge_attrs,
             preserve_node_attrs=preserve_node_attrs,
-            preserve_graph_attrs=preserve_graph_attrs,
+            # Always preserve graph attrs when we are caching b/c this should be
+            # cheap and may help prevent extra (unnecessary) conversions. Because
+            # we do this, we don't need `preserve_graph_attrs` in the cache key.
+            preserve_graph_attrs=preserve_graph_attrs or use_cache,
             name=self.name,
             graph_name=graph_name,
         )
@@ -1147,7 +1145,7 @@ class _dispatchable:
             for cur_key in list(cache):
                 if cur_key == key:
                     continue
-                ekey, nkey, gkey = cur_key
+                ekey, nkey = cur_key
                 if ekey is False or edge_key is True:
                     pass
                 elif ekey is True or edge_key is False or not ekey.issubset(edge_key):
@@ -1156,8 +1154,6 @@ class _dispatchable:
                     pass
                 elif nkey is True or node_key is False or not nkey.issubset(node_key):
                     continue
-                if gkey and not graph_key:
-                    continue
                 cache.pop(cur_key, None)  # Use pop instead of del to be thread-safe
 
         return rv
@@ -1368,6 +1364,8 @@ class _dispatchable:
                 G1 = backend.convert_to_nx(bound.arguments["G"])
                 G2 = bound2.arguments["G"]
                 G2._adj = G1._adj
+                if G2.is_directed():
+                    G2._pred = G1._pred
                 nx._clear_cache(G2)
             elif self.name == "edmonds_karp":
                 R1 = backend.convert_to_nx(bound.arguments["residual"])
diff --git a/pyproject.toml b/pyproject.toml
index 39d760349..a7759cfed 100644
--- a/pyproject.toml
+++ b/pyproject.toml
@@ -77,7 +77,7 @@ doc = [
 ]
 extra = [
     'lxml>=4.6',
-    'pygraphviz>=1.12',
+    'pygraphviz>=1.13',
     'pydot>=2.0',
     'sympy>=1.10',
 ]
diff --git a/requirements/extra.txt b/requirements/extra.txt
index ad08057f4..e21b8bfce 100644
--- a/requirements/extra.txt
+++ b/requirements/extra.txt
@@ -1,6 +1,6 @@
 # Generated via tools/generate_requirements.py and pre-commit hook.
 # Do not edit this file; modify pyproject.toml instead.
 lxml>=4.6
-pygraphviz>=1.12
+pygraphviz>=1.13
 pydot>=2.0
 sympy>=1.10


Test patch:
diff --git a/networkx/classes/tests/dispatch_interface.py b/networkx/classes/tests/dispatch_interface.py
index 96c363b93..57aaa13bc 100644
--- a/networkx/classes/tests/dispatch_interface.py
+++ b/networkx/classes/tests/dispatch_interface.py
@@ -69,12 +69,11 @@ class LoopbackDispatcher:
         graph_name=None,
     ):
         if name in {
-            # Raise if input graph changes
+            # Raise if input graph changes. See test_dag.py::test_topological_sort6
             "lexicographical_topological_sort",
             "topological_generations",
             "topological_sort",
-            # Sensitive tests (iteration order matters)
-            "dfs_labeled_edges",
+            # Would be nice to some day avoid these cutoffs of full testing
         }:
             return graph
         if isinstance(graph, NodeView):
@@ -98,7 +97,7 @@ class LoopbackDispatcher:
         elif graph.__class__ in {PlanarEmbedding, LoopbackPlanarEmbedding}:
             G = LoopbackDiGraph()  # or LoopbackPlanarEmbedding
         else:
-            # It would be nice to be able to convert _AntiGraph to a regular Graph
+            # Would be nice to handle these better some day
             # nx.algorithms.approximation.kcomponents._AntiGraph
             # nx.algorithms.tree.branchings.MultiDiGraph_EdgeKey
             # nx.classes.tests.test_multidigraph.MultiDiGraphSubClass
@@ -108,71 +107,64 @@ class LoopbackDispatcher:
         if preserve_graph_attrs:
             G.graph.update(graph.graph)
 
+        # add nodes
+        G.add_nodes_from(graph)
         if preserve_node_attrs:
-            G.add_nodes_from(graph.nodes(data=True))
+            for n, dd in G._node.items():
+                dd.update(graph.nodes[n])
         elif node_attrs:
-            G.add_nodes_from(
-                (
-                    node,
-                    {
-                        k: datadict.get(k, default)
-                        for k, default in node_attrs.items()
-                        if default is not None or k in datadict
-                    },
+            for n, dd in G._node.items():
+                dd.update(
+                    (attr, graph._node[n].get(attr, default))
+                    for attr, default in node_attrs.items()
+                    if default is not None or attr in graph._node[n]
                 )
-                for node, datadict in graph.nodes(data=True)
-            )
-        else:
-            G.add_nodes_from(graph)
-
-        if graph.is_multigraph():
-            if preserve_edge_attrs:
-                G.add_edges_from(
-                    (u, v, key, datadict)
-                    for u, nbrs in graph._adj.items()
-                    for v, keydict in nbrs.items()
-                    for key, datadict in keydict.items()
-                )
-            elif edge_attrs:
-                G.add_edges_from(
-                    (
-                        u,
-                        v,
-                        key,
-                        {
-                            k: datadict.get(k, default)
-                            for k, default in edge_attrs.items()
-                            if default is not None or k in datadict
-                        },
-                    )
-                    for u, nbrs in graph._adj.items()
-                    for v, keydict in nbrs.items()
-                    for key, datadict in keydict.items()
-                )
-            else:
-                G.add_edges_from(
-                    (u, v, key, {})
-                    for u, nbrs in graph._adj.items()
-                    for v, keydict in nbrs.items()
-                    for key, datadict in keydict.items()
-                )
-        elif preserve_edge_attrs:
-            G.add_edges_from(graph.edges(data=True))
+
+        # tools to build datadict and keydict
+        if preserve_edge_attrs:
+
+            def G_new_datadict(old_dd):
+                return G.edge_attr_dict_factory(old_dd)
         elif edge_attrs:
-            G.add_edges_from(
-                (
-                    u,
-                    v,
-                    {
-                        k: datadict.get(k, default)
-                        for k, default in edge_attrs.items()
-                        if default is not None or k in datadict
-                    },
+
+            def G_new_datadict(old_dd):
+                return G.edge_attr_dict_factory(
+                    (attr, old_dd.get(attr, default))
+                    for attr, default in edge_attrs.items()
+                    if default is not None or attr in old_dd
                 )
-                for u, v, datadict in graph.edges(data=True)
-            )
         else:
-            G.add_edges_from(graph.edges)
+
+            def G_new_datadict(old_dd):
+                return G.edge_attr_dict_factory()
+
+        if G.is_multigraph():
+
+            def G_new_inner(keydict):
+                kd = G.adjlist_inner_dict_factory(
+                    (k, G_new_datadict(dd)) for k, dd in keydict.items()
+                )
+                return kd
+        else:
+            G_new_inner = G_new_datadict
+
+        # add edges keeping the same order in _adj and _pred
+        G_adj = G._adj
+        if G.is_directed():
+            for n, nbrs in graph._adj.items():
+                G_adj[n].update((nbr, G_new_inner(dd)) for nbr, dd in nbrs.items())
+            # ensure same datadict for pred and adj; and pred order of graph._pred
+            G_pred = G._pred
+            for n, nbrs in graph._pred.items():
+                G_pred[n].update((nbr, G_adj[nbr][n]) for nbr in nbrs)
+        else:  # undirected
+            for n, nbrs in graph._adj.items():
+                # ensure same datadict for both ways; and adj order of graph._adj
+                G_adj[n].update(
+                    (nbr, G_adj[nbr][n] if n in G_adj[nbr] else G_new_inner(dd))
+                    for nbr, dd in nbrs.items()
+                )
+
         return G
 
     @staticmethod
diff --git a/networkx/tests/test_convert_pandas.py b/networkx/tests/test_convert_pandas.py
index 7076eb57a..594fcab7d 100644
--- a/networkx/tests/test_convert_pandas.py
+++ b/networkx/tests/test_convert_pandas.py
@@ -241,7 +241,8 @@ class TestConvertPandas:
         df = nx.to_pandas_adjacency(G, dtype=np.intp)
         pd.testing.assert_frame_equal(df, dftrue)
 
-    def test_edgekey_with_multigraph(self):
+    @pytest.mark.parametrize("edge_attr", [["attr2", "attr3"], True])
+    def test_edgekey_with_multigraph(self, edge_attr):
         df = pd.DataFrame(
             {
                 "source": {"A": "N1", "B": "N2", "C": "N1", "D": "N1"},
@@ -264,7 +265,7 @@ class TestConvertPandas:
             df,
             source="source",
             target="target",
-            edge_attr=["attr2", "attr3"],
+            edge_attr=edge_attr,
             edge_key="attr1",
             create_using=nx.MultiGraph(),
         )