Goldberg-Radzik Algorithm Reports Negative Cycle Outside Connected Components

[iany0]

Current Behavior

The goldberg_radzik identifies a negative cycle in situations where there is an isolated component with a negative cycle, and the specified source node for the algorithm is not part of that isolated component. According to the goldberg_radzik documentation, "In the case where the (di)graph is not connected, if a component not containing the source contains a negative (di)cycle, it will not be detected". However, this negative cycle is reported regardless of the source node's connectivity to the component.

Steps to Reproduce

G = nx.DiGraph()
for i in range(7):
    G.add_node(i)
edges_data = [
    (0, 1, 2), (1, 2, 3), (2, 3, 2), (3, 0, 1),
    (4, 5, 1), (5, 5, -1), (5, 6, 1), (6, 4, 1)
]
for u, v, w in edges_data:
    G.add_edge(u, v, weight=w)

pred, dist = nx.goldberg_radzik(G, 1)

Environment

Python version: 3.9
NetworkX version: 3.2.1

[amandesai01]

Can you provide link to the documentation you are referring?

[dschult]

This does raise for a negatively weighted selfloop edge. If an edge between two distinct nodes has negative weight it will only cause an error to be raised if it is in the same component as the source. But if that edge is a self-loop, it does get reported whether that is in the same component or not.

@iany0 can you explain your use case and how this impacts you? Perhaps there is a workaround.
The long term fix is either to change the doc_string to explain that behavior is different for negatively weighted self-loops, or to change how we are looking for negative cycles. I'm afraid that this issue exists with many of the shortest_path functions. How it affects you might help us decide how to fix it.

Thanks!