bug : Bellman-Ford/DAG ignore negative costs despite documented support — base_graph filtering

Aperta
  • Qualcosa non va?
#3,148 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 2 giorni

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
3/5
Tempo stimato
1-2 giorni
Idoneità per principianti
65/100
Tipo di issue
Bug
Chiarezza
Specificata chiaramente
Stato di attività
Attiva
Stack tecnologico
cpp, postgresql
Ambito
backend, databases

Direzione di ricerca

The issue is in src/dijkstra/shortestPath_driver.cpp and include/cpp_common/base_graph.hpp. Start by examining the graph_add_edge function (lines 732-761) that filters negative costs. Look at the driver's insert_edges call (line 240, 268) and the Which enum in include/c_common/enums.h to identify the algorithm types. The fix requires adding a new insertion function that allows negatives and routing Bellman-Ford, EdwardMoore, and DAGSP through it. Run the provided SQL queries to verify the bug and test the fix.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

bug Looks AI

Problem

The documented negative-cost support for pgr_bellmanFord, pgr_edwardMoore, and pgr_dagShortestPath does not actually work.

doc/bellman_ford/pgr_bellmanFord.rst:42,47 states some edge weights may be negative and the process is valid for edges with both positive and negative weights. The algorithm wrappers (include/bellman_ford/bellman_ford.hpp:132 boost::bellman_ford_shortest_paths, include/bellman_ford/edwardMoore.hpp:180 queue relaxation, and include/dagShortestPath/dagShortestPath.hpp:131 boost::dag_shortest_paths) all handle negatives.

However, every call goes through src/dijkstra/shortestPath_driver.cpp:240,268 (digraph.insert_edges(edges)) → include/cpp_common/base_graph.hpp:732-761 (graph_add_edge), where edges are guarded with if(cost>=0) and if(reverse>=0). Negatives are dropped before the algorithms ever receive them. This matches the Dijkstra contract (doc/src/pgRouting-concepts.rst:85,108 and doc/dijkstra/dijkstra-family.rst:57-59), but directly contradicts the Bellman and DAG contracts. The sibling helper base_graph.hpp:815-850 (graph_add_neg_edge) converts negative costs via (-0.5) * cost with a TODO at line 816, so it cannot be reused as-is.

To Reproduce

-- Bellman: negative middle edge should be used
SELECT * FROM pgr_bellmanFord(
  'SELECT * FROM (VALUES (1,1,2,5),(2,2,3,-4),(3,1,3,10)) AS t(id,source,target,cost)',
  1, 3, true);
-- Expected Bellman: path 1->2->3, agg_cost = 1
-- Actual today: path 1->3, agg_cost = 10 (the -4 edge was filtered out)

-- Bellman: negative reverse_cost on undirected graph
SELECT * FROM pgr_bellmanFord(
  'SELECT * FROM (VALUES (1,1,2,5,2),(2,2,3,10,-3)) AS t(id,source,target,cost,reverse_cost)',
  1, 3, false);
-- Expected: reverse edge with negative cost is traversed; Actual today: ignored

-- DAG: negative on an acyclic graph should be used
SELECT * FROM pgr_dagShortestPath(
  'SELECT * FROM (VALUES (1,1,2,-2),(2,2,3,1),(3,1,3,5)) AS t(id,source,target,cost)',
  1, 3);
-- Expected: path 1->2->3, agg_cost = -1
-- Actual today: path 1->3, agg_cost = 5

-- Dijkstra on identical data should preserve current behavior (negative = edge does not exist)
SELECT * FROM pgr_dijkstra(
  'SELECT * FROM (VALUES (1,1,2,5),(2,2,3,-4),(3,1,3,10)) AS t(id,source,target,cost)',
  1, 3, true);
-- Expected & Actual: path 1->3, agg_cost = 10 (filtering preserved)

Expectation

  • pgr_bellmanFord/pgr_edwardMoore (directed and undirected) and pgr_dagShortestPath (directed) include both negative cost and reverse_cost values in the graph so underlying solvers (boost::bellman_ford_shortest_paths, edwardMoore, dag_shortest_paths) can route through them.
  • pgr_dijkstra, pgr_bdDijkstra, pgr_aStar, and pgr_bdAstar preserve their current filter (cost < 0 implies the edge does not exist).
  • No changes to public SQL signatures or empty-SQL query checks (ERROR: Empty edges SQL at shortestPath_driver.cpp:145-148).

Sample Data

The inline VALUES queries above reproduce the issue directly. Alternatively, using the standard sample dataset:

INSERT INTO edges(id, source, target, cost) VALUES (-1, 1, 2, -4);

Platform/versions

SELECT version();            -- PostgreSQL 17.x (affects 13-18, logic is in the C++ graph layer)
SELECT postgis_full_version();
SELECT pgr_version();        -- 4.1.0-dev, develop @ 350b1e533
  • OS: Ubuntu 24.04 (platform-independent C++ graph logic)

Proposed approach
Minimal two-file fix without changing SQL signatures:

  1. Add insert_edges_allow_negative / graph_add_edge_allow_negative to include/cpp_common/base_graph.hpp (a non-filtering variant that stores cost and reverse_cost as-is, unlike graph_add_edge at lines 732–761).
  2. Route BELLMANFORD, EDWARDMOORE, and DAGSP through this new insertion path in src/dijkstra/shortestPath_driver.cpp:239-292 by matching on Which (include/c_common/enums.h:34-36), ensuring DAG applies only to directed calls.
  3. Keep Dijkstra/BDD/A*/BFS/WITHPOINTS on the existing filtered path.
  4. Add pgTAP regression tests covering negative cost and reverse_cost for Bellman-Ford and DAG.

Happy to follow ur direction ! :)

Lingua principale
C++
Stelle
1.4k
Fork
397
Merge medio
2g 2h
PR unite (30g)
4

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di pgRouting/pgrouting

Tutte le issue di pgRouting/pgrouting

Issue simili

Altre issue su C++

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.