pgr_bdastar doesn't return the same result as pgr_astar

Open
  • Is something wrong?
#1,885 3 comments 0 reactions 0 assignees View on GitHub

Maintainers usually reply within 3 days

Nobody has claimed this yet.

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
45/100
Issue type
Bug
Clarity
Clearly specified
Activity status
Stale
Tech stack
postgresql
Domain
backend, databases

Research direction

The issue is in the pgRouting library's bidirectional A* algorithm (pgr_bdastar) returning a different path than the unidirectional A* (pgr_astar). Start by examining the test data in edge_min_repro.zip to understand the graph structure. Look at the source code for both algorithms, likely in src/astar/ or similar directories. Compare the heuristics and bidirectional search logic. Run the provided queries on the sample data to reproduce the discrepancy. 'Done' is when both algorithms return identical paths and aggregate costs for the given input.

Written by the indexing model from the issue text.

Description

Documentation

Problem

pgr_bdastar doesn't return the same result as pgr_astar

To Reproduce

Using pgRouting docker image, import the following data:

edge_min_repro.zip

Then run the following queries:

SELECT 
seq, path_seq AS "pathSeq", node, edge, pgr.cost, agg_cost AS "aggCost"
FROM pgr_bdastar('SELECT * FROM edge', 1153548005, 558255664, true) as pgr
ORDER BY seq;

which returns:

1 1 1153548005 54256 0.000379723504336132 0
2 2 558255704 54146 0.000304523536838747 0.000379723504336132
3 3 558255705 54149 0.00138401927422877 0.00068424704117488
4 4 558255703 54142 0.000341445410931827 0.00206826631540365
5 5 558255702 54141 0.00148219733407846 0.00240971172633548
6 6 558255664 -1 0 0.00389190906041394

and

SELECT 
seq, path_seq AS "pathSeq", node, edge, pgr.cost, agg_cost AS "aggCost"
FROM pgr_astar('SELECT * FROM edge', 1153548005, 558255664, true) as pgr
ORDER BY seq;

which returns:

1 1 1153548005 54256 0.00037972350433613237 0
2 2 558255704 54147 0.00027403899672301315 0.00037972350433613237
3 3 1037080644 54145 0.0002883815801048997 0.0006537625010591456
4 4 1037086594 54144 0.0005431804623754474 0.0009421440811640453
5 5 1037074188 54143 0.0003132688487491818 0.0014853245435394926
6 6 558255702 54141 0.001482197334078463 0.0017985933922886744
7 7 558255664 -1 0 0.0032807907263671375

Expectation

Result should be the same, with the same sequence and the same aggCost.

Sample Data

Uploaded above.

Platform/versions

docker images 11-2.5-2.6.2 or 12-3.0-3.1.0 or 13-3.1-3.1.3

Dominant language
C++
Stars
1.4k
Forks
397
Avg merge
2d 16h
Merged PRs (30d)
8

Getting set up

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from pgRouting/pgrouting

All issues in pgRouting/pgrouting

Similar issues

More C++ issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.