The last step in both steiner tree approximation algorithms ("mehlhorn and "kou" are effected) from 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

The non terminal leaves are not removed iteratively, see implementation:

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:

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)

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.

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

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