Repository: networkx/networkx

Issue:
Steiner tree approximation does not iteratively remove nonterminal leaves
<!-- If you have a general question about NetworkX, please use the discussions tab to create a new discussion -->

<!--- Provide a general summary of the issue in the Title above -->
The last step in both steiner tree approximation algorithms ("mehlhorn and "kou" are effected) from [steinertree.py](https://github.com/networkx/networkx/blob/main/networkx/algorithms/approximation/steinertree.py) is to remove nonterminal leave nodes from the graph. It's implemented in the function `_remove_nonterminal_leaves`. Within `_remove_nonterminal_leaves` nonterminal leaves should be iteratively removed until no more nonterminal leaves exist. Currently only the nonterminal leaves are removed, but this might yield to further nonterminal leaves.

### Current Behavior

<!--- Tell us what happens instead of the expected behavior -->
The non terminal leaves are not removed iteratively, see implementation:

```python
def _remove_nonterminal_leaves(G, terminals):
    terminals_set = set(terminals)
    for n in list(G.nodes):
        if n not in terminals_set and G.degree(n) == 1:
            G.remove_node(n)
```

### Expected Behavior
The nonterminal leaves should be removed iteratively - not only once - e.g., in a loop.
An example implementation (maybe not the most efficient one) could be:

```python
def _remove_nonterminal_leaves_iteratively(G, terminals):
    terminals_set = set(terminals)
    while True:
        non_terminal_leaves = [n for n in G.nodes if n not in terminals_set and G.degree(n) == 1]
        if not non_terminal_leaves:
            break
        G.remove_nodes_from(non_terminal_leaves)
```

<!--- Tell us what should happen -->

### Steps to Reproduce

It's not obvious to reproduce this bug with a small example when calling the steiner_tree functions. I have huge graphs where this bug occurs quite often. But it's easy to trigger this when using the effected wrong implementation `_remove_nonterminal_leaves` directly.
  
<!--- Provide a minimal example that reproduces the bug -->

```python
import networkx as nx
from networkx.algorithms.approximation.steinertree import _remove_nonterminal_leaves

G = nx.Graph()
G.add_edges_from([(1,2),(2,3),(3,4),(4,5)], weight=1)
G.edges  # prints EdgeView([(1, 2), (2, 3), (3, 4), (4, 5)])

_remove_nonterminal_leaves(G, [1,2])
G.edges  # prints EdgeView([(1, 2), (2, 3), (3, 4)])

_remove_nonterminal_leaves(G, [1,2])
G.edges  # prints EdgeView([(1, 2), (2, 3)])

_remove_nonterminal_leaves(G, [1,2])
G.edges  # prints EdgeView([(1, 2)]) finally the correct result without further nonterminal leaves
```

### Environment

<!--- Please provide details about your local environment -->
This is a bug in the current latest source code (main or tag: networkx-3.1).
 
Python version: 3.11.4
NetworkX version: 3.1

### Additional context

<!--- Add any other context about the problem here, screenshots, etc. -->


Discussion:
rossbar: @OrionSehn there is already a PR open for this issue at #7136 with a fair bit of discussion - perhaps you could take a look at that one and weigh in there?
OrionSehn: > This approach makes sense to me and the test adequately demonstrates the problem with the current implementation (i.e. non-terminal nodes along a path become terminal with subsequent removals).
> 
> There are potential "gotchas" related to this approach implicitly assuming that leaf nodes have degree one. This may not always be true: two cases I can think of are 1) graphs with self-loop edges (see example) and 2) MultGraphs with multi-edges.
> 
> ```python
> # Desired behavior
> >>> G = nx.path_graph(10)
> >>> _remove_nonterminal_nodes(G, [4, 5, 6])
> >>> list(G)
> [4, 5, 6]
> >>> H = nx.path_graph(10)
> >>> H.add_edge(9, 9)  # self-loop on one terminal node
> >>> _remove_nonterminal_edges(G, [4, 5, 6])
> >>> list(G)
> [4, 5, 6, 7, 8, 9]
> ```
> 
> Since this function is only to be used in the context of the steiner_tree approximations, these may be fine - but it's worth double-checking how steiner_tree handles these cases to make sure the `_remove_nonterminal_leaves` gives consistent results for these cases!

Hey @rossbar, I was able to handle both of these cases that you've brought up! It does end up being a little slower than what I had written in April, but does handle both the self looped case and the multigraph case as expected. I've added a few extra tests to make it clear that this behaves successfully. Hopefully its sensible enough how this works just by looking at it. 

Thank you so much for your very thoughtful comments and contributions. 

Lemme know if there's other things we should consider.
OrionSehn-personal: I've revised my amendment thanks to dan's very good suggestions, thank you guys very much for taking the time to take a look at this. 

Please do continue to give any further suggestions if you can think of improvements!
OrionSehn: @rossbar 

Thank you for your review, your code is much much more readable. I added an extra few words to clarify the problem this resolves slightly further. 

I also fixed a super minor style issue with your submission

Thanks for all your help on this.

Orion 
OrionSehn: Happy to help! Glad we could get her sorted!

Patch:
diff --git a/networkx/algorithms/approximation/steinertree.py b/networkx/algorithms/approximation/steinertree.py
index c6c834f42..f4840effd 100644
--- a/networkx/algorithms/approximation/steinertree.py
+++ b/networkx/algorithms/approximation/steinertree.py
@@ -113,10 +113,21 @@ def _kou_steiner_tree(G, terminal_nodes, weight):
 
 
 def _remove_nonterminal_leaves(G, terminals):
-    terminals_set = set(terminals)
-    for n in list(G.nodes):
-        if n not in terminals_set and G.degree(n) == 1:
-            G.remove_node(n)
+    terminal_set = set(terminals)
+    leaves = {n for n in G if len(set(G[n]) - {n}) == 1}
+    nonterminal_leaves = leaves - terminal_set
+
+    while nonterminal_leaves:
+        # Removing a node may create new non-terminal leaves, so we limit
+        # search for candidate non-terminal nodes to neighbors of current
+        # non-terminal nodes
+        candidate_leaves = set.union(*(set(G[n]) for n in nonterminal_leaves))
+        candidate_leaves -= nonterminal_leaves | terminal_set
+        # Remove current set of non-terminal nodes
+        G.remove_nodes_from(nonterminal_leaves)
+        # Find any new non-terminal nodes from the set of candidates
+        leaves = {n for n in candidate_leaves if len(set(G[n]) - {n}) == 1}
+        nonterminal_leaves = leaves - terminal_set
 
 
 ALGORITHMS = {


Test patch:
diff --git a/networkx/algorithms/approximation/tests/test_steinertree.py b/networkx/algorithms/approximation/tests/test_steinertree.py
index 23c3193e4..1b074757c 100644
--- a/networkx/algorithms/approximation/tests/test_steinertree.py
+++ b/networkx/algorithms/approximation/tests/test_steinertree.py
@@ -1,7 +1,11 @@
 import pytest
 
 import networkx as nx
-from networkx.algorithms.approximation.steinertree import metric_closure, steiner_tree
+from networkx.algorithms.approximation.steinertree import (
+    _remove_nonterminal_leaves,
+    metric_closure,
+    steiner_tree,
+)
 from networkx.utils import edges_equal
 
 
@@ -190,6 +194,12 @@ class TestSteinerTree:
             S = steiner_tree(G, terminal_nodes, method=method)
             assert edges_equal(S.edges(data=True, keys=True), expected_edges)
 
+    def test_remove_nonterminal_leaves(self):
+        G = nx.path_graph(10)
+        _remove_nonterminal_leaves(G, [4, 5, 6])
+
+        assert list(G) == [4, 5, 6]  # only the terminal nodes are left
+
 
 @pytest.mark.parametrize("method", ("kou", "mehlhorn"))
 def test_steiner_tree_weight_attribute(method):
@@ -224,3 +234,32 @@ def test_steiner_tree_method_invalid():
         ValueError, match="invalid_method is not a valid choice for an algorithm."
     ):
         nx.approximation.steiner_tree(G, terminal_nodes=[1, 3], method="invalid_method")
+
+
+def test_steiner_tree_remove_non_terminal_leaves_self_loop_edges():
+    # To verify that the last step of the steiner tree approximation
+    # behaves in the case where a non-terminal leaf has a self loop edge
+    G = nx.path_graph(10)
+
+    # Add self loops to the terminal nodes
+    G.add_edges_from([(2, 2), (3, 3), (4, 4), (7, 7), (8, 8)])
+
+    # Remove non-terminal leaves
+    _remove_nonterminal_leaves(G, [4, 5, 6, 7])
+
+    # The terminal nodes should be left
+    assert list(G) == [4, 5, 6, 7]  # only the terminal nodes are left
+
+
+def test_steiner_tree_non_terminal_leaves_multigraph_self_loop_edges():
+    # To verify that the last step of the steiner tree approximation
+    # behaves in the case where a non-terminal leaf has a self loop edge
+    G = nx.MultiGraph()
+    G.add_edges_from([(i, i + 1) for i in range(10)])
+    G.add_edges_from([(2, 2), (3, 3), (4, 4), (4, 4), (7, 7)])
+
+    # Remove non-terminal leaves
+    _remove_nonterminal_leaves(G, [4, 5, 6, 7])
+
+    # Only the terminal nodes should be left
+    assert list(G) == [4, 5, 6, 7]