You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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:
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:
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.
importnetworkxasnxfromnetworkx.algorithms.approximation.steinertreeimport_remove_nonterminal_leavesG=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
The text was updated successfully, but these errors were encountered:
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:
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:
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.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
The text was updated successfully, but these errors were encountered: