Repository: networkx/networkx

Issue:
lowest_common_ancestor for multigraph
Hello,
I am working with a multigraph and would like to find the lowest common ancestor for nodes. It looks like there's no implementation for multigraph. Can you please help me with this?

Discussion:

Patch:
diff --git a/doc/developer/about_us.rst b/doc/developer/about_us.rst
index b785cf2e3..a96a68948 100644
--- a/doc/developer/about_us.rst
+++ b/doc/developer/about_us.rst
@@ -145,6 +145,7 @@ to add your name to the bottom of the list.
 - Philip Boalch
 - Matt Schwennesen, Github: `mjschwenne <https://github.com/mjschwenne>`_
 - Andrew Knyazev, Github: `lobpcg <https://github.com/lobpcg>`_, LinkedIn: `andrew-knyazev <https://www.linkedin.com/in/andrew-knyazev>`_
+- Sultan Orazbayev, GitHub: `link <https://github.com/SultanOrazbayev>`_, LinkedIn: `link <https://www.linkedin.com/in/sultan-orazbayev/>`_
 
 A supplementary (but still incomplete) list of contributors is given by the
 list of names that have commits in ``networkx``'s
diff --git a/doc/release/contribs.py b/doc/release/contribs.py
index 55ccacc40..6d2f26b2d 100644
--- a/doc/release/contribs.py
+++ b/doc/release/contribs.py
@@ -5,11 +5,17 @@ import sys
 import string
 import shlex
 
-if len(sys.argv) != 2:
-    print("Usage: ./contributors.py tag-of-previous-release")
+if len(sys.argv) < 2 or len(sys.argv) > 3:
+    print(
+        "Usage: ./contributors.py tag-of-previous-release tag-of-newer-release (optional)"
+    )
     sys.exit(-1)
 
 tag = sys.argv[1]
+if len(sys.argv) < 3:
+    compare_tag = None
+else:
+    compare_tag = sys.argv[2]
 
 
 def call(cmd):
@@ -17,19 +23,42 @@ def call(cmd):
 
 
 tag_date = call(f"git log -n1 --format='%ci' {tag}")[0]
+if compare_tag:
+    compare_tag_date = call(f"git log -n1 --format='%ci' {compare_tag}")[0]
+
 print(f"Release {tag} was on {tag_date}\n")
 
-merges = call(f"git log --since='{tag_date}' --merges --format='>>>%B' --reverse")
+if compare_tag:
+    merges = call(
+        f"git log --since='{tag_date}' --until='{compare_tag_date}' --merges --format='>>>%B' --reverse"
+    )
+else:
+    merges = call(f"git log --since='{tag_date}' --merges --format='>>>%B' --reverse")
 merges = [m for m in merges if m.strip()]
 merges = "\n".join(merges).split(">>>")
 merges = [m.split("\n")[:2] for m in merges]
 merges = [m for m in merges if len(m) == 2 and m[1].strip()]
 
-num_commits = call(f"git rev-list {tag}..HEAD --count")[0]
+if compare_tag:
+    num_commits = call(f"git rev-list {tag}..{compare_tag} --count")[0]
+else:
+    num_commits = call(f"git rev-list {tag}..HEAD --count")[0]
+
 print(f"A total of {num_commits} changes have been committed.\n")
 
 # Use filter to remove empty strings
-commits = filter(None, call(f"git log --since='{tag_date}' --pretty=%s --reverse"))
+if compare_tag:
+    commits = filter(
+        None,
+        call(
+            f"git log --since='{tag_date}' --until='{compare_tag_date}' --pretty=%s --reverse"
+        ),
+    )
+else:
+    commits = filter(
+        None,
+        call(f"git log --since='{tag_date}' --pretty=%s --reverse"),
+    )
 for c in commits:
     print("- " + c)
 
@@ -44,12 +73,17 @@ for (merge, message) in merges:
 
 print("\nMade by the following committers [alphabetical by last name]:\n")
 
-authors = call(f"git log --since='{tag_date}' --format=%aN")
+if compare_tag:
+    authors = call(
+        f"git log --since='{tag_date}' --until='{compare_tag_date}' --format=%aN"
+    )
+else:
+    authors = call(f"git log --since='{tag_date}' --format=%aN")
 authors = [a.strip() for a in authors if a.strip()]
 
 
 def key(author):
-    author = [v for v in author.split() if v[0] in string.ascii_letters]
+    author = [v for v in author.split()]
     if len(author) > 0:
         return author[-1]
 
diff --git a/doc/release/index.rst b/doc/release/index.rst
index a0b592be0..7ab33c988 100644
--- a/doc/release/index.rst
+++ b/doc/release/index.rst
@@ -15,6 +15,9 @@ period.
    :maxdepth: 2
 
    release_dev
+   release_2.8.8
+   release_2.8.7
+   release_2.8.6
    release_2.8.5
    release_2.8.4
    release_2.8.3
diff --git a/doc/release/release_2.8.6.rst b/doc/release/release_2.8.6.rst
new file mode 100644
index 000000000..fbc43f2a4
--- /dev/null
+++ b/doc/release/release_2.8.6.rst
@@ -0,0 +1,74 @@
+NetworkX 2.8.6
+==============
+
+Release date: 22 August 2022
+
+Supports Python 3.8, 3.9, and 3.10.
+
+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 :ref:`gallery of examples <examples_gallery>`.
+Please send comments and questions to the `networkx-discuss mailing list
+<http://groups.google.com/group/networkx-discuss>`_.
+
+Highlights
+----------
+
+Minor documentation and bug fixes.
+
+Merged PRs
+----------
+
+- Add random_spanning_tree to documentation (#5810)
+- DOC: Switch to enumerated list in quotient_graph docstring (#5837)
+- Add warning to nx_agraph about layout nondeterminism. (#5832)
+- Update docs to include description of the `return_seen` kwarg (#5891)
+- Add cache reset for when G._node is changed (#5894)
+- Allow classes to relabel nodes -- casting (#5903)
+- Update lattice.py (#5914)
+- Add to about_us.rst (#5919)
+- Update precommit hooks (#5923)
+- Remove old Appveyor cruft (#5924)
+- signature change for `node_link` functions: for issue #5787 (#5899)
+- Allow unsortable nodes in approximation.treewidth functions (#5921)
+- Fix Louvain_partitions by yielding a copy of the sets in the partition gh-5901 (#5902)
+- Adds ```nx.bfs_layers``` method (#5879)
+- Add function bfs_layers to docs (#5932)
+- Propose to make new node_link arguments keyword only. (#5928)
+- Bump nodelink args deprecation expiration to v3.2 (#5933)
+- Add examples to lowest common ancestors algorithms (#5531)
+- Naive lowest common ancestor implementation (#5736)
+- Add examples for the condensation function (#5452)
+- Minor doc fixups (#5868)
+- update all_pairs_lca docstrings (#5876)
+- Improve LCA input validation (#5877)
+- Replace LCA with naive implementations (#5883)
+- Update release notes
+- docstring update to lexicographical_topological_sort issue 5681 (#5930)
+- Support matplotlb 3.6rc1 failure (#5937)
+
+Improvements
+------------
+
+- [`#5883 <https://github.com/networkx/networkx/pull/5883>`_]
+  Replace the implementation of ``lowest_common_ancestor`` and
+  ``all_pairs_lowest_common_ancestor`` with a "naive" algorithm to fix
+  several bugs and improve performance.
+
+Contributors
+------------
+
+- Tanmay Aeron
+- Ross Barnowski
+- Kevin Brown
+- Matthias Bussonnier
+- Tigran Khachatryan
+- Dhaval Kumar
+- Jarrod Millman
+- Sultan Orazbayev
+- Dan Schult
+- Matt Schwennesen
+- Dilara Tekinoglu
+- kpetridis
diff --git a/doc/release/release_2.8.7.rst b/doc/release/release_2.8.7.rst
new file mode 100644
index 000000000..71b5aec32
--- /dev/null
+++ b/doc/release/release_2.8.7.rst
@@ -0,0 +1,52 @@
+NetworkX 2.8.7
+==============
+
+Release date: 1 October 2022
+
+Supports Python 3.8, 3.9, and 3.10.
+
+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 :ref:`gallery of examples <examples_gallery>`.
+Please send comments and questions to the `networkx-discuss mailing list
+<http://groups.google.com/group/networkx-discuss>`_.
+
+Highlights
+----------
+
+Minor documentation and bug fixes.
+
+Merged PRs
+----------
+
+- Bump release version
+- Fixed unused root argument in has_bridges (#5846)
+- docstring updates for `union`, `disjoint_union`, and `compose` (#5892)
+- Updated networkx/classes/function.py . Solves Issue #5463 (#5474)
+- Improved documentation for all_simple_paths (#5944)
+- Change is_path to return False when node not in G instead of raising exception (#5943)
+- Minor docstring touchups and test refactor for `is_path` (#5967)
+- Update documentation header links for latest pydata-sphinx-theme (#5966)
+- Fix failing example due to mpl 3.6 colorbar. (#5994)
+- Add Tidelift security vulnerability link (#6001)
+- Update linters (#6006)
+
+Improvements
+------------
+
+- [`#5943 <https://github.com/networkx/networkx/pull/5943>`_]
+  ``is_path`` used to raise a `KeyError` when the ``path`` argument contained
+  a node that was not in the Graph. The behavior has been updated so that
+  ``is_path`` returns `False` in this case rather than raising the exception.
+
+Contributors
+------------
+
+- Juanita Gomez
+- Kevin Brown
+- 0ddoes
+- pmlpm1986
+- Dan Schult
+- Jarrod Millman
diff --git a/doc/release/release_2.8.8.rst b/doc/release/release_2.8.8.rst
new file mode 100644
index 000000000..750230fbf
--- /dev/null
+++ b/doc/release/release_2.8.8.rst
@@ -0,0 +1,70 @@
+NetworkX 2.8.7
+==============
+
+Release date: 1 November 2022
+
+Supports Python 3.8, 3.9, 3.10, and 3.11.
+
+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 :ref:`gallery of examples <examples_gallery>`.
+Please send comments and questions to the `networkx-discuss mailing list
+<http://groups.google.com/group/networkx-discuss>`_.
+
+Highlights
+----------
+
+Minor documentation and bug fixes.
+
+Merged PRs
+----------
+
+- Bump release version
+- Fix warnings from running tests in randomized order (#6014)
+- Update pydata-sphinx-theme (#6012)
+- update secutiry link to tidelift (#6019)
+- Update numpydoc (#6022)
+- Support Python 3.11 (#6023)
+- Update linters (#6024)
+- Minor updates to expanders generator tests (#6027)
+- Add missing asserts to tests (#6039)
+- fixes #6036 (#6080)
+- Improve test coverage expanders line graph generators solved (PR for issue #6034) (#6071)
+- Replace .A call with .toarray for sparse array in example. (#6106)
+- Improve test coverage for algorithms/richclub.py (#6089)
+- Tested boykov_kolmogorov and dinitz with cutoff (#6104)
+- Improve test coverage for multigraph class (#6101)
+- Improve test coverage for algorithms in dominating_set.py (PR for issue 6032) (#6068)
+- Improve test coverage for graph class (#6105)
+- added coverage in generators/tree.py (#6082)
+- DOC: Specifically branch off main, instead of current branch (#6127)
+- Improve test coverage for multidigraph class (#6131)
+- Improve test coverage for digraph class (#6130)
+- Improve test coverage for algorithms in dispersion.py (#6100)
+- Test on Python 3.11 (#6159)
+- Improve test coverage in algorithms shortest paths unweighted.py (#6121)
+- Increased test coverage algorithms/matching.py (#6095)
+- Renamed test functions in test_lowest_common_ancestors (#6110)
+- Increase covering coverage (#6099)
+- Add example for fiedler_vector (#6155)
+- Improve test coverage for cycles.py (#6152)
+- Added an example in all_pairs_node_connectivity  (#6126)
+- Amount of nodes and edges have mistakes when reading adjlist file (#6132)
+- Update pytest (#6165)
+
+Contributors
+------------
+
+- Ross Barnowski
+- Paula Pérez Bianchi
+- DiamondJoseph
+- Jarrod Millman
+- Mjh9122
+- Alimi Qudirah
+- Okite chimaobi Samuel
+- Jefter Santiago
+- Dan Schult
+- Mridul Seth
+- Tindi Sommers
diff --git a/doc/release/release_dev.rst b/doc/release/release_dev.rst
index 735bd9d3f..94b62794b 100644
--- a/doc/release/release_dev.rst
+++ b/doc/release/release_dev.rst
@@ -16,8 +16,9 @@ Please send comments and questions to the `networkx-discuss mailing list
 Highlights
 ----------
 
-This release is the result of X of work with over X pull requests by
-X contributors. Highlights include:
+This release is the result of 4 months of work with over 217 pull requests by
+37 contributors. We also have a :ref:`guide for people moving from NetworkX 2.X
+to NetworkX 3.0 <migration_guide_from_2.x_to_3.0>`. Highlights include:
 
 - Better syncing between G._succ and G._adj for directed G.
   And slightly better speed from all the core adjacency data structures.
@@ -38,6 +39,11 @@ X contributors. Highlights include:
   are checking might be a class rather than an instance. We suggest you check
   for attribute `_adj` to verify it is like a NetworkX graph object or type and
   then `type(obj) is type` to check if it is a class.
+- We have added an experimental plugin feature which let users choose alternate
+  backends like GraphBLAS, CuGraph for computation. This is an opt-in feature and
+  may change in future releases.
+- Improved integration with the general Scientific Python ecosystem: <link to
+  the migration guide section?>
 
 Improvements
 ------------
@@ -69,18 +75,187 @@ Improvements
 API Changes
 -----------
 
+- [`#5899 <https://github.com/networkx/networkx/pull/5899>`_]
+  The `attrs` keyword argument will be replaced with keyword only arguments
+  `source`, `target`, `name`, `key` and `link` for `json_graph/node_link` functions.
 
 Deprecations
 ------------
 
+- [`#5723 <https://github.com/networkx/networkx/issues/5723>`_]
+  ``nx.nx_pydot.*`` will be deprecated in the future if pydot isn't being
+  actively maintained. Users are recommended to use pygraphviz instead. 
+- [`#5899 <https://github.com/networkx/networkx/pull/5899>`_]
+  The `attrs` keyword argument will be replaced with keyword only arguments
+  `source`, `target`, `name`, `key` and `link` for `json_graph/node_link` functions.
 
 Merged PRs
 ----------
 
-<output of contribs.py>
+A total of 217 changes have been committed.
+
+- Add 2.8.5 release notes
+- update all_pairs_lca docstrings (#5876)
+- Improve LCA input validation (#5877)
+- strategy_saturation_largest_first now accepts partial colorings (#5888)
+- Fixed unused root argument in has_bridges (#5846)
+- Update docs to include description of the `return_seen` kwarg (#5891)
+- Add cache reset for when G._node is changed (#5894)
+- Add weight distance metrics (#5305)
+- Allow classes to relabel nodes -- casting (#5903)
+- Update lattice.py (#5914)
+- docstring updates for `union`, `disjoint_union`, and `compose` (#5892)
+- Adds ```nx.bfs_layers``` method (#5879)
+- Add to about_us.rst (#5919)
+- Update precommit hooks (#5923)
+- Remove old Appveyor cruft (#5924)
+- signature change for `node_link` functions: for issue #5787 (#5899)
+- Allow unsortable nodes in approximation.treewidth functions (#5921)
+- Fix Louvain_partitions by yielding a copy of the sets in the partition gh-5901 (#5902)
+- Replace LCA with naive implementations (#5883)
+- Add function bfs_layers to docs (#5932)
+- Bump nodelink args deprecation expiration to v3.2 (#5933)
+- Update mapping logic in `relabel_nodes` (#5912)
+- Propose to make new node_link arguments keyword only. (#5928)
+- docstring update to lexicographical_topological_sort issue 5681 (#5930)
+- Update pygraphviz (#5934)
+- See matplotlb 3.6rc1 failure (#5937)
+- Further improvements to strategy_saturation_largest_first (#5935)
+- Arf layout (#5910)
+- [ENH] Find and verify a minimal D-separating set in DAG (#5898)
+- Add Mehlhorn Steiner approximations (#5629)
+- Updated networkx/classes/function.py . Solves Issue #5463 (#5474)
+- Improved documentation for all_simple_paths (#5944)
+- Change is_path to return False when node not in G instead of raising exception (#5943)
+- Preliminary VF2++ Implementation (#5788)
+- Minor docstring touchups and test refactor for `is_path` (#5967)
+- Update documentation header links for latest pydata-sphinx-theme (#5966)
+- Switch to relative import for vf2pp_helpers. (#5973)
+- Add vf2pp_helpers subpackage to wheel (#5975)
+- Enhance biconnected components to avoid indexing (#5974)
+- Update mentored projects list (#5985)
+- Add concurrency hook to cancel jobs on new push. (#5986)
+- Make all.py generator friendly (#5984)
+- Fix failing example due to mpl 3.6 colorbar. (#5994)
+- Only run scheduled pytest-randomly job in main repo. (#5993)
+- Fix steiner tree test (#5999)
+- Add Tidelift security vulnerability link (#6001)
+- Update linters (#6006)
+- Update doc requirements (#6008)
+- VF2++ for Directed Graphs (#5972)
+- Fix defect and update docs for MappedQueue, related to gh-5681 (#5939)
+- Fix warnings from running tests in randomized order (#6014)
+- Update pydata-sphinx-theme (#6012)
+- update security link to tidelift (#6019)
+- Update numpydoc (#6022)
+- Support Python 3.11 (#6023)
+- Update linters (#6024)
+- Fixed test for average shortest path in the case of directed graphs (#6003)
+- Minor updates to expanders generator tests (#6027)
+- Update deprecations after 3.0 dep sprint (#6031)
+- Use scipy.sparse array datastructure (#6037)
+- Designate 3.0b1 release
+- Bump release version
+- Use org funding.yml
+- Add missing asserts to tests (#6039)
+- improve test coverage for algorithms in load centrality (#6080)
+- Improve test coverage expanders line graph generators solved (PR for issue #6034) (#6071)
+- Update which flow functions support the cutoff argument (#6085)
+- Update GML parsing/writing to allow empty lists/tuples as node attributes (#6093)
+- Replace .A call with .toarray for sparse array in example. (#6106)
+- Improve test coverage for algorithms/richclub.py (#6089)
+- Tested boykov_kolmogorov and dinitz with cutoff (#6104)
+- Improve test coverage for multigraph class (#6101)
+- Improve test coverage for algorithms in dominating_set.py (PR for issue 6032) (#6068)
+- Warn on unused visualization kwargs that only apply to FancyArrowPatch edges (#6098)
+- Improve test coverage for graph class (#6105)
+- Fix weighted MultiDiGraphs in DAG longest path algorithms + add additional tests (#5988)
+- added coverage in generators/tree.py (#6082)
+- DOC: Specifically branch off main, instead of current branch (#6127)
+- Circular center node layout (#6114)
+- Improve test coverage for multidigraph class (#6131)
+- Improve test coverage for digraph class (#6130)
+- Improve test coverage for algorithms in dispersion.py (#6100)
+- Fix doc inconsistencies related to cutoff in connectivity.py and disjoint_paths.py (#6113)
+- Remove deprecated maxcardinality parameter from min_weight_matching (#6146)
+- Remove deprecated `find_cores` (#6139)
+- Remove deprecated project function from bipartite package. (#6147)
+- Test on Python 3.11 (#6159)
+- Improve test coverage in algorithms shortest paths unweighted.py (#6121)
+- Increased test coverage algorithms/matching.py (#6095)
+- Renamed test functions in test_lowest_common_ancestors (#6110)
+- Increase covering coverage (#6099)
+- Add example for fiedler_vector (#6155)
+- Improve test coverage for cycles.py (#6152)
+- Added an example in all_pairs_node_connectivity  (#6126)
+- Amount of nodes and edges have mistakes when reading adjlist file (#6132)
+- Update pytest to v7.2 (#6165)
+- Improve test coverage for voterank algorithm (#6161)
+- plugin based backend infrastructure to use multiple computation backends (#6000)
+- Undocumented parameters in dispersion (#6183)
+- improve swap.py test coverage  (#6176)
+- Improve test coverage for current_flow_betweenness module (#6143)
+- Completed Testing in community.py resolves issue #6184 (#6185)
+- Added an example to algebraic_connectivity (#6153)
+- Add ThinGraph example to Multi*Graph doc_strings (#6160)
+- Fix defect in eulerize, replace reciprocal edge weights (#6145)
+- For issue #6030 Add test coverage for algorithms in beamsearch.py (#6087)
+- Improve test coverage expanders stochastic graph generators (#6073)
+- Update developer requirements  (#6194)
+- Designate 3.0rc1 release
+- Bump release version
+- Tests added in test_centrality.py (#6200)
+- add laplacian_spectrum example (#6169)
+- PR for issue #6033 Improve test coverage for algorithms in betweenness_subset.py #6033 (#6083)
+- Di graph edges doc fix (#6108)
+- Improve coverage for core.py (#6116)
+- Add clear_edges() method to the list of methods to be frozen by nx.freeze() (#6190)
+- Adds LCA test case for self-ancestors from gh-4458. (#6218)
+- Minor Python 2 cleanup (#6219)
+- Add example laplacian matrix  (#6168)
+- Revert 6219 and delete comment. (#6222)
+- fix wording in error message (#6228)
+- Rm incorrect test case for connected edge swap (#6223)
 
 
 Contributors
 ------------
+Made by the following committers [alphabetical by last name]:
 
-<output of contribs.py>
+- 0ddoe_s
+- Tanmay Aeron
+- Guy Aglionby
+- Douglas K. G. Araujo
+- Ross Barnowski
+- Paula Pérez Bianchi
+- Kevin Brown
+- DiamondJoseph
+- Casper van Elteren
+- Radoslav Fulek
+- Juanita Gomez
+- Michael Holtz
+- Abangma Jessika
+- Tigran Khachatryan
+- Dhaval Kumar
+- Adam Li
+- Lucas H. McCabe
+- Jarrod Millman
+- Mjh9122
+- Sultan Orazbayev
+- Konstantinos Petridis
+- Alimi Qudirah
+- Adam Richardson
+- Okite chimaobi Samuel
+- Jefter Santiago
+- Dan Schult
+- Mridul Seth
+- Tindi Sommers
+- Morrison Turnansky
+- Sebastiano Vigna
+- George Watkins
+- Isaac Western
+- ddelange
+- ladykkk
+- nsengaw4c
+- pmlpm1986
+- stevenstrickler
diff --git a/examples/geospatial/fix_plot_delaunay.py b/examples/geospatial/plot_delaunay.py
similarity index 100%
rename from examples/geospatial/fix_plot_delaunay.py
rename to examples/geospatial/plot_delaunay.py
diff --git a/examples/geospatial/fix_plot_lines.py b/examples/geospatial/plot_lines.py
similarity index 100%
rename from examples/geospatial/fix_plot_lines.py
rename to examples/geospatial/plot_lines.py
diff --git a/examples/geospatial/fix_plot_points.py b/examples/geospatial/plot_points.py
similarity index 100%
rename from examples/geospatial/fix_plot_points.py
rename to examples/geospatial/plot_points.py
diff --git a/examples/geospatial/fix_plot_polygons.py b/examples/geospatial/plot_polygons.py
similarity index 100%
rename from examples/geospatial/fix_plot_polygons.py
rename to examples/geospatial/plot_polygons.py
diff --git a/networkx/algorithms/lowest_common_ancestors.py b/networkx/algorithms/lowest_common_ancestors.py
index 68aaf7d3f..9c40758f8 100644
--- a/networkx/algorithms/lowest_common_ancestors.py
+++ b/networkx/algorithms/lowest_common_ancestors.py
@@ -14,7 +14,6 @@ __all__ = [
 
 
 @not_implemented_for("undirected")
-@not_implemented_for("multigraph")
 def all_pairs_lowest_common_ancestor(G, pairs=None):
     """Return the lowest common ancestor of all pairs or the provided pairs
 
@@ -112,7 +111,6 @@ def all_pairs_lowest_common_ancestor(G, pairs=None):
 
 
 @not_implemented_for("undirected")
-@not_implemented_for("multigraph")
 def lowest_common_ancestor(G, node1, node2, default=None):
     """Compute the lowest common ancestor of the given pair of nodes.
 
@@ -150,7 +148,6 @@ def lowest_common_ancestor(G, node1, node2, default=None):
 
 
 @not_implemented_for("undirected")
-@not_implemented_for("multigraph")
 def tree_all_pairs_lowest_common_ancestor(G, root=None, pairs=None):
     r"""Yield the lowest common ancestor for sets of pairs in a tree.
 
@@ -237,7 +234,8 @@ def tree_all_pairs_lowest_common_ancestor(G, root=None, pairs=None):
                     msg = "No root specified and tree has multiple sources."
                     raise nx.NetworkXError(msg)
                 root = n
-            elif deg > 1:
+            # checking deg>1 is not sufficient for MultiDiGraphs
+            elif deg > 1 and len(G.pred[n]) > 1:
                 msg = "Tree LCA only defined on trees; use DAG routine."
                 raise nx.NetworkXError(msg)
     if root is None:
diff --git a/networkx/algorithms/swap.py b/networkx/algorithms/swap.py
index abba51817..9b2f06db6 100644
--- a/networkx/algorithms/swap.py
+++ b/networkx/algorithms/swap.py
@@ -350,7 +350,7 @@ def connected_double_edge_swap(G, nswap=1, _window_threshold=3, seed=None):
             while wcount < window and n < nswap:
                 # Pick two random edges without creating the edge list. Choose
                 # source nodes from the discrete degree distribution.
-                (ui, xi) = nx.utils.discrete_sequence(2, cdistribution=cdf)
+                (ui, xi) = discrete_sequence(2, cdistribution=cdf, seed=seed)
                 # If the source nodes are the same, skip this pair.
                 if ui == xi:
                     continue
diff --git a/networkx/algorithms/traversal/depth_first_search.py b/networkx/algorithms/traversal/depth_first_search.py
index 0ccca4ff9..c250787bf 100644
--- a/networkx/algorithms/traversal/depth_first_search.py
+++ b/networkx/algorithms/traversal/depth_first_search.py
@@ -364,12 +364,15 @@ def dfs_labeled_edges(G, source=None, depth_limit=None):
     edges: generator
        A generator of triples of the form (*u*, *v*, *d*), where (*u*,
        *v*) is the edge being explored in the depth-first search and *d*
-       is one of the strings 'forward', 'nontree', or 'reverse'. A
-       'forward' edge is one in which *u* has been visited but *v* has
+       is one of the strings 'forward', 'nontree', 'reverse', or 'reverse-depth_limit'.
+       A 'forward' edge is one in which *u* has been visited but *v* has
        not. A 'nontree' edge is one in which both *u* and *v* have been
        visited but the edge is not in the DFS tree. A 'reverse' edge is
-       on in which both *u* and *v* have been visited and the edge is in
-       the DFS tree.
+       one in which both *u* and *v* have been visited and the edge is in
+       the DFS tree. When the `depth_limit` is reached via a 'forward' edge,
+       a 'reverse' edge is immediately generated rather than the subtree
+       being explored. To indicate this flavor of 'reverse' edge, the string
+       yielded is 'reverse-depth_limit'.
 
     Examples
     --------
@@ -436,6 +439,8 @@ def dfs_labeled_edges(G, source=None, depth_limit=None):
                     visited.add(child)
                     if depth_now > 1:
                         stack.append((child, depth_now - 1, iter(G[child])))
+                    else:
+                        yield parent, child, "reverse-depth_limit"
             except StopIteration:
                 stack.pop()
                 if stack:
diff --git a/networkx/drawing/nx_pylab.py b/networkx/drawing/nx_pylab.py
index 674c28a45..61030b1aa 100644
--- a/networkx/drawing/nx_pylab.py
+++ b/networkx/drawing/nx_pylab.py
@@ -522,8 +522,11 @@ def draw_networkx_edges(
         Also, `(offset, onoffseq)` tuples can be used as style instead of a strings.
         (See `matplotlib.patches.FancyArrowPatch`: `linestyle`)
 
-    alpha : float or None (default=None)
-        The edge transparency
+    alpha : float or array of floats (default=None)
+        The edge transparency.  This can be a single alpha value,
+        in which case it will be applied to all specified edges. Otherwise,
+        if it is an array, the elements of alpha will be applied to the colors
+        in order (cycling through alpha multiple times if necessary).
 
     edge_cmap : Matplotlib colormap, optional
         Colormap for mapping intensities of edges
diff --git a/networkx/generators/classic.py b/networkx/generators/classic.py
index d83062af3..3971eb985 100644
--- a/networkx/generators/classic.py
+++ b/networkx/generators/classic.py
@@ -233,6 +233,8 @@ def complete_graph(n, create_using=None):
     n : int or iterable container of nodes
         If n is an integer, nodes are from range(n).
         If n is a container of nodes, those nodes appear in the graph.
+        Warning: n is not checked for duplicates and if present the
+        resulting graph may not be as desired. Make sure you have no duplicates.
     create_using : NetworkX graph constructor, optional (default=nx.Graph)
        Graph type to create. If graph instance, then cleared before populated.
 
@@ -360,6 +362,8 @@ def cycle_graph(n, create_using=None):
     n : int or iterable container of nodes
         If n is an integer, nodes are from `range(n)`.
         If n is a container of nodes, those nodes appear in the graph.
+        Warning: n is not checked for duplicates and if present the
+        resulting graph may not be as desired. Make sure you have no duplicates.
     create_using : NetworkX graph constructor, optional (default=nx.Graph)
        Graph type to create. If graph instance, then cleared before populated.
 
@@ -523,7 +527,9 @@ def lollipop_graph(m, n, create_using=None):
     ----------
     m, n : int or iterable container of nodes (default = 0)
         If an integer, nodes are from `range(m)` and `range(m,m+n)`.
-        If a container, the entries are the coordinate of the node.
+        If a container of nodes, those nodes appear in the graph.
+        Warning: m and n are not checked for duplicates and if present the
+        resulting graph may not be as desired. Make sure you have no duplicates.
 
         The nodes for m appear in the complete graph $K_m$ and the nodes
         for n appear in the path $P_n$
@@ -587,6 +593,8 @@ def path_graph(n, create_using=None):
     n : int or iterable
         If an integer, nodes are 0 to n - 1.
         If an iterable of nodes, in the order they appear in the path.
+        Warning: n is not checked for duplicates and if present the
+        resulting graph may not be as desired. Make sure you have no duplicates.
     create_using : NetworkX graph constructor, optional (default=nx.Graph)
        Graph type to create. If graph instance, then cleared before populated.
 
@@ -608,6 +616,8 @@ def star_graph(n, create_using=None):
     n : int or iterable
         If an integer, node labels are 0 to n with center 0.
         If an iterable of nodes, the center is the first.
+        Warning: n is not checked for duplicates and if present the
+        resulting graph may not be as desired. Make sure you have no duplicates.
     create_using : NetworkX graph constructor, optional (default=nx.Graph)
        Graph type to create. If graph instance, then cleared before populated.
 
@@ -679,6 +689,8 @@ def wheel_graph(n, create_using=None):
     n : int or iterable
         If an integer, node labels are 0 to n with center 0.
         If an iterable of nodes, the center is the first.
+        Warning: n is not checked for duplicates and if present the
+        resulting graph may not be as desired. Make sure you have no duplicates.
     create_using : NetworkX graph constructor, optional (default=nx.Graph)
        Graph type to create. If graph instance, then cleared before populated.
 
diff --git a/requirements/example.txt b/requirements/example.txt
index a256fbd88..935087971 100644
--- a/requirements/example.txt
+++ b/requirements/example.txt
@@ -1,6 +1,6 @@
-osmnx>=1.1
+osmnx>=1.2
 momepy>=0.5
 contextily>=1.2
-seaborn>=0.11
-cairocffi>=1.3
-igraph>=0.9.8
+seaborn>=0.12
+cairocffi>=1.4
+igraph>=0.10


Test patch:
diff --git a/networkx/algorithms/shortest_paths/astar.py b/networkx/algorithms/shortest_paths/astar.py
index 5d5a84791..6f0e442ec 100644
--- a/networkx/algorithms/shortest_paths/astar.py
+++ b/networkx/algorithms/shortest_paths/astar.py
@@ -46,7 +46,7 @@ def astar_path(G, source, target, heuristic=None, weight="weight"):
        returned by the function. The function must accept exactly three
        positional arguments: the two endpoints of an edge and the
        dictionary of edge attributes for that edge. The function must
-       return a number.
+       return a number or None to indicate a hidden edge.
 
     Raises
     ------
@@ -67,6 +67,14 @@ def astar_path(G, source, target, heuristic=None, weight="weight"):
     >>> print(nx.astar_path(G, (0, 0), (2, 2), heuristic=dist, weight="cost"))
     [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]
 
+    Notes
+    -----
+    Edge weight attributes must be numerical.
+    Distances are calculated as sums of weighted edges traversed.
+
+    The weight function can be used to hide edges by returning None.
+    So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
+    will find the shortest red path.
 
     See Also
     --------
@@ -127,7 +135,10 @@ def astar_path(G, source, target, heuristic=None, weight="weight"):
         explored[curnode] = parent
 
         for neighbor, w in G[curnode].items():
-            ncost = dist + weight(curnode, neighbor, w)
+            cost = weight(curnode, neighbor, w)
+            if cost is None:
+                continue
+            ncost = dist + cost
             if neighbor in enqueued:
                 qcost, h = enqueued[neighbor]
                 # if qcost <= ncost, a less costly path from the
@@ -179,7 +190,7 @@ def astar_path_length(G, source, target, heuristic=None, weight="weight"):
        returned by the function. The function must accept exactly three
        positional arguments: the two endpoints of an edge and the
        dictionary of edge attributes for that edge. The function must
-       return a number.
+       return a number or None to indicate a hidden edge.
     Raises
     ------
     NetworkXNoPath
diff --git a/networkx/algorithms/shortest_paths/tests/test_astar.py b/networkx/algorithms/shortest_paths/tests/test_astar.py
index e622502b4..3cc4050b9 100644
--- a/networkx/algorithms/shortest_paths/tests/test_astar.py
+++ b/networkx/algorithms/shortest_paths/tests/test_astar.py
@@ -44,6 +44,25 @@ class TestAStar:
         assert nx.astar_path(self.XG, "s", "v") == ["s", "x", "u", "v"]
         assert nx.astar_path_length(self.XG, "s", "v") == 9
 
+    def test_astar_directed_weight_function(self):
+        w1 = lambda u, v, d: d["weight"]
+        assert nx.astar_path(self.XG, "x", "u", weight=w1) == ["x", "u"]
+        assert nx.astar_path_length(self.XG, "x", "u", weight=w1) == 3
+        assert nx.astar_path(self.XG, "s", "v", weight=w1) == ["s", "x", "u", "v"]
+        assert nx.astar_path_length(self.XG, "s", "v", weight=w1) == 9
+
+        w2 = lambda u, v, d: None if (u, v) == ("x", "u") else d["weight"]
+        assert nx.astar_path(self.XG, "x", "u", weight=w2) == ["x", "y", "s", "u"]
+        assert nx.astar_path_length(self.XG, "x", "u", weight=w2) == 19
+        assert nx.astar_path(self.XG, "s", "v", weight=w2) == ["s", "x", "v"]
+        assert nx.astar_path_length(self.XG, "s", "v", weight=w2) == 10
+
+        w3 = lambda u, v, d: d["weight"] + 10
+        assert nx.astar_path(self.XG, "x", "u", weight=w3) == ["x", "u"]
+        assert nx.astar_path_length(self.XG, "x", "u", weight=w3) == 13
+        assert nx.astar_path(self.XG, "s", "v", weight=w3) == ["s", "x", "v"]
+        assert nx.astar_path_length(self.XG, "s", "v", weight=w3) == 30
+
     def test_astar_multigraph(self):
         G = nx.MultiDiGraph(self.XG)
         G.add_weighted_edges_from((u, v, 1000) for (u, v) in list(G.edges()))
diff --git a/networkx/algorithms/shortest_paths/weighted.py b/networkx/algorithms/shortest_paths/weighted.py
index ef0ee635d..e131d49b8 100644
--- a/networkx/algorithms/shortest_paths/weighted.py
+++ b/networkx/algorithms/shortest_paths/weighted.py
@@ -105,7 +105,7 @@ def dijkstra_path(G, source, target, weight="weight"):
         returned by the function. The function must accept exactly three
         positional arguments: the two endpoints of an edge and the
         dictionary of edge attributes for that edge. The function must
-        return a number.
+        return a number or None to indicate a hidden edge.
 
     Returns
     -------
@@ -186,7 +186,7 @@ def dijkstra_path_length(G, source, target, weight="weight"):
         returned by the function. The function must accept exactly three
         positional arguments: the two endpoints of an edge and the
         dictionary of edge attributes for that edge. The function must
-        return a number.
+        return a number or None to indicate a hidden edge.
 
     Returns
     -------
@@ -266,7 +266,7 @@ def single_source_dijkstra_path(G, source, cutoff=None, weight="weight"):
         returned by the function. The function must accept exactly three
         positional arguments: the two endpoints of an edge and the
         dictionary of edge attributes for that edge. The function must
-        return a number.
+        return a number or None to indicate a hidden edge.
 
     Returns
     -------
@@ -330,7 +330,7 @@ def single_source_dijkstra_path_length(G, source, cutoff=None, weight="weight"):
         returned by the function. The function must accept exactly three
         positional arguments: the two endpoints of an edge and the
         dictionary of edge attributes for that edge. The function must
-        return a number.
+        return a number or None to indicate a hidden edge.
 
     Returns
     -------
@@ -408,7 +408,7 @@ def single_source_dijkstra(G, source, target=None, cutoff=None, weight="weight")
         returned by the function. The function must accept exactly three
         positional arguments: the two endpoints of an edge and the
         dictionary of edge attributes for that edge. The function must
-        return a number.
+        return a number or None to indicate a hidden edge.
 
     Returns
     -------
@@ -506,7 +506,7 @@ def multi_source_dijkstra_path(G, sources, cutoff=None, weight="weight"):
         returned by the function. The function must accept exactly three
         positional arguments: the two endpoints of an edge and the
         dictionary of edge attributes for that edge. The function must
-        return a number.
+        return a number or None to indicate a hidden edge.
 
     Returns
     -------
@@ -579,7 +579,7 @@ def multi_source_dijkstra_path_length(G, sources, cutoff=None, weight="weight"):
         returned by the function. The function must accept exactly three
         positional arguments: the two endpoints of an edge and the
         dictionary of edge attributes for that edge. The function must
-        return a number.
+        return a number or None to indicate a hidden edge.
 
     Returns
     -------
@@ -664,7 +664,7 @@ def multi_source_dijkstra(G, sources, target=None, cutoff=None, weight="weight")
         returned by the function. The function must accept exactly three
         positional arguments: the two endpoints of an edge and the
         dictionary of edge attributes for that edge. The function must
-        return a number.
+        return a number or None to indicate a hidden edge.
 
     Returns
     -------
@@ -778,7 +778,8 @@ def _dijkstra_multisource(
         nodes.
 
     weight: function
-        Function with (u, v, data) input that returns that edges weight
+        Function with (u, v, data) input that returns that edge's weight
+        or None to indicate a hidden edge
 
     pred: dict of lists, optional(default=None)
         dict to store a list of predecessors keyed by that node
@@ -892,7 +893,7 @@ def dijkstra_predecessor_and_distance(G, source, cutoff=None, weight="weight"):
         returned by the function. The function must accept exactly three
         positional arguments: the two endpoints of an edge and the
         dictionary of edge attributes for that edge. The function must
-        return a number.
+        return a number or None to indicate a hidden edge.
 
     Returns
     -------
@@ -957,7 +958,7 @@ def all_pairs_dijkstra(G, cutoff=None, weight="weight"):
         returned by the function. The function must accept exactly three
         positional arguments: the two endpoints of an edge and the
         dictionary of edge attributes for that edge. The function must
-        return a number.
+        return a number or None to indicate a hidden edge.
 
     Yields
     ------
@@ -1025,7 +1026,7 @@ def all_pairs_dijkstra_path_length(G, cutoff=None, weight="weight"):
         returned by the function. The function must accept exactly three
         positional arguments: the two endpoints of an edge and the
         dictionary of edge attributes for that edge. The function must
-        return a number.
+        return a number or None to indicate a hidden edge.
 
     Returns
     -------
@@ -1083,7 +1084,7 @@ def all_pairs_dijkstra_path(G, cutoff=None, weight="weight"):
         returned by the function. The function must accept exactly three
         positional arguments: the two endpoints of an edge and the
         dictionary of edge attributes for that edge. The function must
-        return a number.
+        return a number or None to indicate a hidden edge.
 
     Returns
     -------
@@ -2251,7 +2252,7 @@ def bidirectional_dijkstra(G, source, target, weight="weight"):
         returned by the function. The function must accept exactly three
         positional arguments: the two endpoints of an edge and the
         dictionary of edge attributes for that edge. The function must
-        return a number.
+        return a number or None to indicate a hidden edge.
 
     Returns
     -------
diff --git a/networkx/algorithms/tests/test_lowest_common_ancestors.py b/networkx/algorithms/tests/test_lowest_common_ancestors.py
index fac31403e..1a8fd03c8 100644
--- a/networkx/algorithms/tests/test_lowest_common_ancestors.py
+++ b/networkx/algorithms/tests/test_lowest_common_ancestors.py
@@ -136,12 +136,6 @@ class TestTreeLCA:
         with pytest.raises(NNI):
             next(all_pairs_lca(G))
         pytest.raises(NNI, nx.lowest_common_ancestor, G, 0, 1)
-        G = nx.MultiDiGraph([(0, 1)])
-        with pytest.raises(NNI):
-            next(tree_all_pairs_lca(G))
-        with pytest.raises(NNI):
-            next(all_pairs_lca(G))
-        pytest.raises(NNI, nx.lowest_common_ancestor, G, 0, 1)
 
     def test_tree_all_pairs_lca_trees_without_LCAs(self):
         G = nx.DiGraph()
@@ -150,6 +144,41 @@ class TestTreeLCA:
         assert ans == [((3, 3), 3)]
 
 
+class TestMultiTreeLCA(TestTreeLCA):
+    @classmethod
+    def setup_class(cls):
+        cls.DG = nx.MultiDiGraph()
+        edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)]
+        cls.DG.add_edges_from(edges)
+        cls.ans = dict(tree_all_pairs_lca(cls.DG, 0))
+        # add multiedges
+        cls.DG.add_edges_from(edges)
+
+        gold = {(n, n): n for n in cls.DG}
+        gold.update({(0, i): 0 for i in range(1, 7)})
+        gold.update(
+            {
+                (1, 2): 0,
+                (1, 3): 1,
+                (1, 4): 1,
+                (1, 5): 0,
+                (1, 6): 0,
+                (2, 3): 0,
+                (2, 4): 0,
+                (2, 5): 2,
+                (2, 6): 2,
+                (3, 4): 1,
+                (3, 5): 0,
+                (3, 6): 0,
+                (4, 5): 0,
+                (4, 6): 0,
+                (5, 6): 2,
+            }
+        )
+
+        cls.gold = gold
+
+
 class TestDAGLCA:
     @classmethod
     def setup_class(cls):
@@ -326,6 +355,62 @@ class TestDAGLCA:
         assert nx.lowest_common_ancestor(G, 1, 3) == 2
 
 
+class TestMultiDiGraph_DAGLCA(TestDAGLCA):
+    @classmethod
+    def setup_class(cls):
+        cls.DG = nx.MultiDiGraph()
+        nx.add_path(cls.DG, (0, 1, 2, 3))
+        # add multiedges
+        nx.add_path(cls.DG, (0, 1, 2, 3))
+        nx.add_path(cls.DG, (0, 4, 3))
+        nx.add_path(cls.DG, (0, 5, 6, 8, 3))
+        nx.add_path(cls.DG, (5, 7, 8))
+        cls.DG.add_edge(6, 2)
+        cls.DG.add_edge(7, 2)
+
+        cls.root_distance = nx.shortest_path_length(cls.DG, source=0)
+
+        cls.gold = {
+            (1, 1): 1,
+            (1, 2): 1,
+            (1, 3): 1,
+            (1, 4): 0,
+            (1, 5): 0,
+            (1, 6): 0,
+            (1, 7): 0,
+            (1, 8): 0,
+            (2, 2): 2,
+            (2, 3): 2,
+            (2, 4): 0,
+            (2, 5): 5,
+            (2, 6): 6,
+            (2, 7): 7,
+            (2, 8): 7,
+            (3, 3): 3,
+            (3, 4): 4,
+            (3, 5): 5,
+            (3, 6): 6,
+            (3, 7): 7,
+            (3, 8): 8,
+            (4, 4): 4,
+            (4, 5): 0,
+            (4, 6): 0,
+            (4, 7): 0,
+            (4, 8): 0,
+            (5, 5): 5,
+            (5, 6): 5,
+            (5, 7): 5,
+            (5, 8): 5,
+            (6, 6): 6,
+            (6, 7): 5,
+            (6, 8): 6,
+            (7, 7): 7,
+            (7, 8): 7,
+            (8, 8): 8,
+        }
+        cls.gold.update(((0, n), 0) for n in cls.DG)
+
+
 def test_all_pairs_lca_self_ancestors():
     """Self-ancestors should always be the node itself, i.e. lca of (0, 0) is 0.
     See gh-4458."""
@@ -334,6 +419,9 @@ def test_all_pairs_lca_self_ancestors():
     G.add_nodes_from(range(5))
     G.add_edges_from([(1, 0), (2, 0), (3, 2), (4, 1), (4, 3)])
 
-    assert all(
-        u == v == a for (u, v), a in nx.all_pairs_lowest_common_ancestor(G) if u == v
-    )
+    ap_lca = nx.all_pairs_lowest_common_ancestor
+    assert all(u == v == a for (u, v), a in ap_lca(G) if u == v)
+    MG = nx.MultiDiGraph(G)
+    assert all(u == v == a for (u, v), a in ap_lca(MG) if u == v)
+    MG.add_edges_from([(1, 0), (2, 0)])
+    assert all(u == v == a for (u, v), a in ap_lca(MG) if u == v)
diff --git a/networkx/algorithms/traversal/tests/test_dfs.py b/networkx/algorithms/traversal/tests/test_dfs.py
index 765280954..0eb698b0f 100644
--- a/networkx/algorithms/traversal/tests/test_dfs.py
+++ b/networkx/algorithms/traversal/tests/test_dfs.py
@@ -59,11 +59,43 @@ class TestDFS:
         edges = list(nx.dfs_labeled_edges(self.G, source=0))
         forward = [(u, v) for (u, v, d) in edges if d == "forward"]
         assert forward == [(0, 0), (0, 1), (1, 2), (2, 4), (1, 3)]
+        assert edges == [
+            (0, 0, "forward"),
+            (0, 1, "forward"),
+            (1, 0, "nontree"),
+            (1, 2, "forward"),
+            (2, 1, "nontree"),
+            (2, 4, "forward"),
+            (4, 2, "nontree"),
+            (4, 0, "nontree"),
+            (2, 4, "reverse"),
+            (1, 2, "reverse"),
+            (1, 3, "forward"),
+            (3, 1, "nontree"),
+            (3, 0, "nontree"),
+            (1, 3, "reverse"),
+            (0, 1, "reverse"),
+            (0, 3, "nontree"),
+            (0, 4, "nontree"),
+            (0, 0, "reverse"),
+        ]
 
     def test_dfs_labeled_disconnected_edges(self):
         edges = list(nx.dfs_labeled_edges(self.D))
         forward = [(u, v) for (u, v, d) in edges if d == "forward"]
         assert forward == [(0, 0), (0, 1), (2, 2), (2, 3)]
+        assert edges == [
+            (0, 0, "forward"),
+            (0, 1, "forward"),
+            (1, 0, "nontree"),
+            (0, 1, "reverse"),
+            (0, 0, "reverse"),
+            (2, 2, "forward"),
+            (2, 3, "forward"),
+            (3, 2, "nontree"),
+            (2, 3, "reverse"),
+            (2, 2, "reverse"),
+        ]
 
     def test_dfs_tree_isolates(self):
         G = nx.Graph()
@@ -141,12 +173,79 @@ class TestDepthLimitedSearch:
         edges = nx.dfs_edges(self.G, source=9, depth_limit=4)
         assert list(edges) == [(9, 8), (8, 7), (7, 2), (2, 1), (2, 3), (9, 10)]
 
-    def test_dls_labeled_edges(self):
+    def test_dls_labeled_edges_depth_1(self):
         edges = list(nx.dfs_labeled_edges(self.G, source=5, depth_limit=1))
         forward = [(u, v) for (u, v, d) in edges if d == "forward"]
         assert forward == [(5, 5), (5, 4), (5, 6)]
+        # Note: reverse-depth_limit edge types were not reported before gh-6240
+        assert edges == [
+            (5, 5, "forward"),
+            (5, 4, "forward"),
+            (5, 4, "reverse-depth_limit"),
+            (5, 6, "forward"),
+            (5, 6, "reverse-depth_limit"),
+            (5, 5, "reverse"),
+        ]
 
-    def test_dls_labeled_disconnected_edges(self):
+    def test_dls_labeled_edges_depth_2(self):
         edges = list(nx.dfs_labeled_edges(self.G, source=6, depth_limit=2))
         forward = [(u, v) for (u, v, d) in edges if d == "forward"]
         assert forward == [(6, 6), (6, 5), (5, 4)]
+        assert edges == [
+            (6, 6, "forward"),
+            (6, 5, "forward"),
+            (5, 4, "forward"),
+            (5, 4, "reverse-depth_limit"),
+            (5, 6, "nontree"),
+            (6, 5, "reverse"),
+            (6, 6, "reverse"),
+        ]
+
+    def test_dls_labeled_disconnected_edges(self):
+        edges = list(nx.dfs_labeled_edges(self.D, depth_limit=1))
+        assert edges == [
+            (0, 0, "forward"),
+            (0, 1, "forward"),
+            (0, 1, "reverse-depth_limit"),
+            (0, 0, "reverse"),
+            (2, 2, "forward"),
+            (2, 3, "forward"),
+            (2, 3, "reverse-depth_limit"),
+            (2, 7, "forward"),
+            (2, 7, "reverse-depth_limit"),
+            (2, 2, "reverse"),
+            (8, 8, "forward"),
+            (8, 7, "nontree"),
+            (8, 9, "forward"),
+            (8, 9, "reverse-depth_limit"),
+            (8, 8, "reverse"),
+            (10, 10, "forward"),
+            (10, 9, "nontree"),
+            (10, 10, "reverse"),
+        ]
+        # large depth_limit has no impact
+        edges = list(nx.dfs_labeled_edges(self.D, depth_limit=19))
+        assert edges == [
+            (0, 0, "forward"),
+            (0, 1, "forward"),
+            (1, 0, "nontree"),
+            (0, 1, "reverse"),
+            (0, 0, "reverse"),
+            (2, 2, "forward"),
+            (2, 3, "forward"),
+            (3, 2, "nontree"),
+            (2, 3, "reverse"),
+            (2, 7, "forward"),
+            (7, 2, "nontree"),
+            (7, 8, "forward"),
+            (8, 7, "nontree"),
+            (8, 9, "forward"),
+            (9, 8, "nontree"),
+            (9, 10, "forward"),
+            (10, 9, "nontree"),
+            (9, 10, "reverse"),
+            (8, 9, "reverse"),
+            (7, 8, "reverse"),
+            (2, 7, "reverse"),
+            (2, 2, "reverse"),
+        ]