Add negative cycle detection heuristic (#3879)

* ignore pytest cache

* add negative cycle detecting mechanism

* add initial tests for negative cycle detector

* fix notation

* refactor negative cycle heuristic

* enhance argument hanging indent

* add negative cycle consistency tests

* document parameters in docstring

* enhance pep-8 conformity

* increase pep-8 conformity

* add contributor

* decrease verbosity of the exception

* add comment, fix typo

* decrease indentation

* diversify random tests

* reduce memory footprint, provide more documentation

* change keyword name and tighten tests and comments

Co-authored-by: Dan Schult <dschult@colgate.edu>

4 files changed, 76 insertions, 5 deletions

diff --git a/.gitignore b/.gitignore
index 868f8c18..be9f1870 100644
--- a/.gitignore
+++ b/.gitignore
@@ -50,3 +50,6 @@ networkx.egg-info/
 
 # VS Code settings
 .vscode
+
+# PyTest Cache
+.pytest_cache
diff --git a/CONTRIBUTORS.rst b/CONTRIBUTORS.rst
index 47c89fca..ce4bf512 100644
--- a/CONTRIBUTORS.rst
+++ b/CONTRIBUTORS.rst
@@ -171,6 +171,7 @@ is partially historical, and now, mostly arbitrary.
 - Alessandro Luongo
 - Huston Hedinger
 - Oleguer Sagarra
+- Kazimierz Wojciechowski, GitHub `<https://github.com/kazimierz-256>`_, LinkedIn `<https://linkedin.com/in/wojciechowski-kazimierz/>`_
 - Gaetano Pietro Paolo Carpinato, Github `<https://github.com/Carghaez>`_, LinkedIn `<https://linkedin.com/in/gaetanocarpinato/>`_
 - Arun Nampally, GitHub `<https://github.com/arunwise>`_, LinkedIn `<https://www.linkedin.com/in/arun-nampally-b57845b7/>`_
 - Ryan Duve
diff --git a/networkx/algorithms/shortest_paths/tests/test_weighted.py b/networkx/algorithms/shortest_paths/tests/test_weighted.py
index 24d4c1cd..3df0ffd6 100644
--- a/networkx/algorithms/shortest_paths/tests/test_weighted.py
+++ b/networkx/algorithms/shortest_paths/tests/test_weighted.py
@@ -436,6 +436,34 @@ class TestBellmanFordAndGoldbergRadzik(WeightedTestBase):
             G = nx.path_graph(2)
             nx.goldberg_radzik(G, 3, 0)
 
+    def test_negative_weight_cycle_heuristic(self):
+        G = nx.DiGraph()
+        G.add_edge(0, 1, weight=-1)
+        G.add_edge(1, 2, weight=-1)
+        G.add_edge(2, 3, weight=-1)
+        G.add_edge(3, 0, weight=3)
+        assert not nx.negative_edge_cycle(G, heuristic=True)
+        G.add_edge(2, 0, weight=1.999)
+        assert nx.negative_edge_cycle(G, heuristic=True)
+        G.edges[2, 0]['weight'] = 2
+        assert not nx.negative_edge_cycle(G, heuristic=True)
+
+    def test_negative_weight_cycle_consistency(self):
+        import random
+        unif = random.uniform
+        for random_seed in range(2):  # range(20):
+            random.seed(random_seed)
+            for density in [.1, .9]:  # .3, .7, .9]:
+                for N in [1, 10, 20]:  # range(1, 60 - int(30 * density)):
+                    for max_cost in [1, 90]:  # [1, 10, 40, 90]:
+                        G = nx.binomial_graph(N, density, seed=4, directed=True)
+                        edges = ((u, v, unif(-1, max_cost)) for u, v in G.edges)
+                        G.add_weighted_edges_from(edges)
+
+                        no_heuristic = nx.negative_edge_cycle(G, heuristic=False)
+                        with_heuristic = nx.negative_edge_cycle(G, heuristic=True)
+                        assert no_heuristic == with_heuristic
+
     def test_negative_weight_cycle(self):
         G = nx.cycle_graph(5, create_using=nx.DiGraph())
         G.add_edge(1, 2, weight=-7)
diff --git a/networkx/algorithms/shortest_paths/weighted.py b/networkx/algorithms/shortest_paths/weighted.py
index ac5ddc2c..6f9aee86 100644
--- a/networkx/algorithms/shortest_paths/weighted.py
+++ b/networkx/algorithms/shortest_paths/weighted.py
@@ -1101,7 +1101,8 @@ def all_pairs_dijkstra_path(G, cutoff=None, weight='weight'):
 
 
 def bellman_ford_predecessor_and_distance(G, source, target=None,
-                                          weight='weight'):
+                                          weight='weight',
+                                          heuristic=False):
     """Compute shortest path lengths and predecessors on shortest paths
     in weighted graphs.
 
@@ -1131,6 +1132,10 @@ def bellman_ford_predecessor_and_distance(G, source, target=None,
        dictionary of edge attributes for that edge. The function must
        return a number.
 
+    heuristic : bool
+        Determines whether to use a heuristic to early detect negative
+        cycles at a hopefully negligible cost.
+
     Returns
     -------
     pred, dist : dictionaries
@@ -1201,12 +1206,13 @@ def bellman_ford_predecessor_and_distance(G, source, target=None,
     weight = _weight_function(G, weight)
 
     dist = _bellman_ford(G, [source], weight, pred=pred, dist=dist,
-                         target=target)
+                         target=target,
+                         heuristic=heuristic)
     return (pred, dist)
 
 
 def _bellman_ford(G, source, weight, pred=None, paths=None, dist=None,
-                  target=None):
+                  target=None, heuristic=True):
     """Relaxation loop for Bellman–Ford algorithm.
 
     This is an implementation of the SPFA variant.
@@ -1243,6 +1249,10 @@ def _bellman_ford(G, source, weight, pred=None, paths=None, dist=None,
         Ending node for path. Path lengths to other destinations may (and
         probably will) be incorrect.
 
+    heuristic : bool
+        Determines whether to use a heuristic to early detect negative
+        cycles at a hopefully negligible cost.
+
     Returns
     -------
     Returns a dict keyed by node to the distance from the source.
@@ -1269,6 +1279,11 @@ def _bellman_ford(G, source, weight, pred=None, paths=None, dist=None,
     if dist is None:
         dist = {v: 0 for v in source}
 
+    # Heuristic Storage setup. Note: use None because nodes cannot be None
+    nonexistent_edge = (None, None)
+    pred_edge = {v: None for v in source}
+    recent_update = {v: nonexistent_edge for v in source}
+
     G_succ = G.succ if G.is_directed() else G.adj
     inf = float('inf')
     n = len(G)
@@ -1287,6 +1302,24 @@ def _bellman_ford(G, source, weight, pred=None, paths=None, dist=None,
                 dist_v = dist_u + weight(u, v, e)
 
                 if dist_v < dist.get(v, inf):
+                    # In this conditional branch we are updating the path with v.
+                    # If it happens that some earlier update also added node v
+                    # that implies the existence of a negative cycle since
+                    # after the update node v would lie on the update path twice.
+                    # The update path is stored up to one of the source nodes,
+                    # therefore u is always in the dict recent_update
+                    if heuristic:
+                        if v in recent_update[u]:
+                            raise nx.NetworkXUnbounded("Negative cost cycle detected.")
+                        # Transfer the recent update info from u to v if the
+                        # same source node is the head of the update path.
+                        # If the source node is responsible for the cost update,
+                        # then clear the history and use it instead.
+                        if v in pred_edge and pred_edge[v] == u:
+                            recent_update[v] = recent_update[u]
+                        else:
+                            recent_update[v] = (u, v)
+
                     if v not in in_q:
                         q.append(v)
                         in_q.add(v)
@@ -1297,6 +1330,7 @@ def _bellman_ford(G, source, weight, pred=None, paths=None, dist=None,
                         count[v] = count_v
                     dist[v] = dist_v
                     pred[v] = [u]
+                    pred_edge[v] = u
 
                 elif dist.get(v) is not None and dist_v == dist.get(v):
                     pred[v].append(u)
@@ -1859,7 +1893,7 @@ def goldberg_radzik(G, source, weight='weight'):
     return pred, d
 
 
-def negative_edge_cycle(G, weight='weight'):
+def negative_edge_cycle(G, weight='weight', heuristic=True):
     """Returns True if there exists a negative edge cycle anywhere in G.
 
     Parameters
@@ -1879,6 +1913,11 @@ def negative_edge_cycle(G, weight='weight'):
        dictionary of edge attributes for that edge. The function must
        return a number.
 
+    heuristic : bool
+        Determines whether to use a heuristic to early detect negative
+        cycles at a negligible cost. In case of graphs with a negative cycle,
+        the performance of detection increases by at least an order of magnitude.
+
     Returns
     -------
     negative_cycle : bool
@@ -1908,7 +1947,7 @@ def negative_edge_cycle(G, weight='weight'):
     G.add_edges_from([(newnode, n) for n in G])
 
     try:
-        bellman_ford_predecessor_and_distance(G, newnode, weight)
+        bellman_ford_predecessor_and_distance(G, newnode, weight, heuristic=heuristic)
     except nx.NetworkXUnbounded:
         return True
     finally: