Repository: networkx/networkx
Pull request: Add dfs_labeled_edges reporting of reverse edges due to depth_limit.
Fixes #6239

The new reporting of edges labels them as "reverse-depth_limit" rather than simply "reverse" to make clear that they exist due to cutting off the exploration due to reaching the depth_limit.


Problem statement:
nx.dfs_labeled_edges does not return last visited edge if depth_limit is specified
`nx.dfs_labeled_edges` does not return last (deepest) visited edge when traversing backwards if **depth_limit** is specified.

### Current Behavior
```
graph = nx.path_graph(5, nx.DiGraph)
list(nx.dfs_labeled_edges(graph, source=0))

[(0, 0, 'forward'),
 (0, 1, 'forward'),
 (1, 2, 'forward'),
 (2, 3, 'forward'),
 (3, 4, 'forward'),
 (3, 4, 'reverse'),
 (2, 3, 'reverse'),
 (1, 2, 'reverse'),
 (0, 1, 'reverse'),
 (0, 0, 'reverse')]

list(nx.dfs_labeled_edges(graph, source=0, depth_limit=4))

[(0, 0, 'forward'),
 (0, 1, 'forward'),
 (1, 2, 'forward'),
 (2, 3, 'forward'),
 (3, 4, 'forward'),
 (2, 3, 'reverse'),
 (1, 2, 'reverse'),
 (0, 1, 'reverse'),
 (0, 0, 'reverse')]
```
Note that edge  `(3, 4, 'reverse')` is missing.

### Expected Behavior
```
graph = nx.path_graph(5, nx.DiGraph)
list(nx.dfs_labeled_edges(graph, source=0, depth_limit=4))

[(0, 0, 'forward'),
 (0, 1, 'forward'),
 (1, 2, 'forward'),
 (2, 3, 'forward'),
 (3, 4, 'forward'),
 (3, 4, 'reverse'),
 (2, 3, 'reverse'),
 (1, 2, 'reverse'),
 (0, 1, 'reverse'),
 (0, 0, 'reverse')]
```
### Environment
Python version: 3.10
NetworkX version: 2.8.8 and 3.0rc1

Hints from issue discussion:
I can verify that there is a bug in `dfs_labeled_edges` for the reporting of reverse edges at the requested `depth_level`. The fix is to add an else clause for the check on `depth_now > 1`. And there are almost no tests currently for "reverse" edge reporting in the test suite. So we should add those. 
This may not be a bug afterall...  more like a question about the definition of a "reverse" edge.

A "reverse" edge is one in which both u and v have been visited and the edge is in the DFS tree. But with the depth_limit, we don't actually visit node v when we move forward along (u, v)... we reach the depth limit and stop that branch.  Because we haven't visited that node, some people could argue that we shouldn't report the "reverse" edge. 

One result is that for a fixed depth_limit, the preorder of nodes reports one depth more of nodes than the post-order.

But we can define the labeled DFS edges in either manner. For depth_limit 2, we could report the forward and reverse edges that we would-have-seen without a depth_limit for the edges that we touch.  Or we could report the reverse edges only if we actually visit the node at the far end of the edge. I can't find any good definition of what constitutes a reverse edge (also called a back-edge) when there is a depth_limit to the traversal.

@ikarsokolov can you describe the application you are working with and why you expect there to be a reverse edge for each forward edge when the depth_limit is set?  

I can see an advantage to ensuring that "reverse" edge is reported for each "forward" edge. You gain information about when you stopped looking at a node -- but you don't have information about whether the DFS had finished visiting that node or you reached the depth_limit. We can easily limit the impact of this change to just this function. What is the right thing to report?
@dschult thanks for quick and detailed responses!

> can you describe the application you are working with and why you expect there to be a reverse edge for each forward edge when the depth_limit is set?

Simple example:
I have tree and want to do DFS from the root. I also have blacklist of nodes that should be excluded from DFS result with their complete subtrees. Something like "I want filtered iterator over tree without these particular nodes and all their children".

I listen to traversal events:

- "forward" edge pointed to blacklisted node => blacklisted subtree traversal is started, subsequent nodes should be dropped from the result.
- Matching "reverse" edge => exit from blacklisted node, subtree traversal is finished, subsequent nodes should be kept in the result.

If depth_limit is set and blacklisted node happens to be one level above limit I will never receive signal that node + it's subtree traversal is complete.

> A "reverse" edge is one in which both u and v have been visited and the edge is in the DFS tree. But with the depth_limit, we don't actually visit node v when we move forward along (u, v)... we reach the depth limit and stop that branch. Because we haven't visited that node, some people could argue that we shouldn't report the "reverse" edge.

I see your point. I think in this case we should have another label besides "forward". Something like "examine".
See how this is done in [boost graph](https://www.boost.org/doc/libs/1_80_0/libs/graph/doc/depth_first_search.html) library.
They handled traversal with visitor pattern but the principle is the same.
```
vis.examine_edge(e, g) is invoked on every out-edge of each vertex after it is discovered.
vis.tree_edge(e, g) is invoked on each edge as it becomes a member of the edges that form the search tree. If you wish to record predecessors, do so at this event point.
vis.back_edge(e, g) is invoked on the back edges in the graph.
```
`examine_edge` is missing label in NetworkX implementation.

The only drawback I see here is wasted computational power. "Examined" nodes on last depth level will not be included in final result. At least on my naive implementation. My graph has about ~1M nodes so a lot of nodes can be enumerated here,
With our code, you can get the "examine" trait of an edges by looking for `etype in ("forward", "nontree")`. So, I'm not sure it helps all that much. The difference I see is that the boost code has a "finish_vertex" moment. That's really what you are looking for: a point when you can be sure the tree from that node has been explored completely. That's what we use "reverse" to indicate. 

But we have to figure out whether we consider the subtree-from-that-node to have been fully explored when the depth_limit stopped the exploration. Currently, we don't indicate that we stopped exploring the tree-from-that-node. I think it would be good to report the edge as "reverse-depth_limit" to make a note that a reverse edge should be indicated (we are done exploring that node), but that it isn't the same as a normal "reverse" edge. I'll put together a PR for this.

In the meantime, a workaround is for you to track the depth yourself, and when a "forward" edge reaches the depth_limit, the corresponding "reverse" edge is guaranteed to immediately follow that "forward" edge. So, you don't have to enter blacklisted mode at all. You know that no subtree nodes will be reported.
Something like: 
```python
if etype == "forward":
    if v in excluded_nodes:
        if depth < depth_limit:  # no need to blacklist the subtree if depth == depth_limit
            blacklisted_subtree = True
```
@dschult I tried your patch and it works exactly like I wanted.
Thanks.

Commit message: Minor docstring touchups.

Patch to review:
diff --git a/networkx/algorithms/traversal/depth_first_search.py b/networkx/algorithms/traversal/depth_first_search.py
index 0ccca4ff971..c250787bf00 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/algorithms/traversal/tests/test_dfs.py b/networkx/algorithms/traversal/tests/test_dfs.py
index 765280954d7..3490134d29b 100644
--- a/networkx/algorithms/traversal/tests/test_dfs.py
+++ b/networkx/algorithms/traversal/tests/test_dfs.py
@@ -59,11 +59,43 @@ def test_dfs_labeled_edges(self):
         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 @@ def test_dls_edges(self):
         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-6239
+        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"),
+        ]


Code review comments:
diff_hunk: @@ -141,12 +173,79 @@ def test_dls_edges(self):
         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-6239
path: networkx/algorithms/traversal/tests/test_dfs.py
text: @user1:
```suggestion
        # Note: reverse-depth_limit edge types were not reported before gh-6240
```

Just a tiny nit pick, #6239 is the issue, 6240 is where this behavior will be added.