pgr_dijkstraVia throws std::bad_alloc when a node does not exist

[claudiadragoste]

Problem

When using pgr_dijkstraVia, if one of the input nodes does not exist in the graph, the function throws the following error instead of handling the case gracefully.

SQL Error [XX000]: ERROR: std::bad_alloc
Hint:
from 170576 to 1
Where: SQL function "pgr_dijkstravia" statement 1

To Reproduce

SELECT * FROM pgr_dijkstraVia(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
    ARRAY[170576, 1]
);

Where node 170576 does not exist in the graph.

Expectation

The function should return an empty result but should not throw std::bad_alloc.

Sample Data

Platform/versions

POSTGIS="3.5.3 3.5.3" [EXTENSION] PGSQL="160" GEOS="3.13.1-CAPI-1.19.2" PROJ="8.2.1 NETWORK_ENABLED=OFF URL_ENDPOINT=https://cdn.proj.org USER_WRITABLE_DIRECTORY=C:\WINDOWS\ServiceProfiles\NetworkService\AppData\Local/proj DATABASE_PATH=C:\Program Files\PostgreSQL\16\share\contrib\postgis-3.5\proj\proj.db" (compiled against PROJ 8.2.1) GDAL="GDAL 3.9.2, released 2024/08/13" LIBXML="2.12.5" LIBJSON="0.12" LIBPROTOBUF="1.2.1" WAGYU="0.5.0 (Internal)" TOPOLOGY RASTER

[ayushjariyal]

@claudiadragoste, I want to work on this issue. May I proceed?

[claudiadragoste]

Thank you for the aswer. I wasn't sure if this is the place to report the error.

[cvvergara]

Hi @claudiadragoste

I wonder if you can give me the data set where you are getting the error.
Sorry I did not notice your issue before, I have been busy.

[claudiadragoste]

Hola @cvvergara

I validate the behavior of pgr_dijkstraVia by using a minimal graph defined explicitly in the query:

SELECT *
FROM pgr_dijkstraVia(
    '
    SELECT *
    FROM (
        VALUES
            (100, 1, 2, 1, 1),
            (101, 2, 3, 1, 1),
            (102, 3, 4, 1, 1)
    ) AS edge_table(id, source, target, cost, reverse_cost)
    ',
    ARRAY[1, 3, 4]
);

This query executes successfully because all vertices specified in the input array (1, 3, and 4) exist in the graph. In addition, there is a valid path connecting them: 1 → 2 → 3 → 4.

The following query fails:

SELECT *
FROM pgr_dijkstraVia(
    '
    SELECT *
    FROM (
        VALUES
            (100, 1, 2, 1, 1),
            (101, 2, 3, 1, 1),
            (102, 3, 4, 1, 1)
    ) AS edge_table(id, source, target, cost, reverse_cost)
    ',
    ARRAY[1, 3, 5]
);

In this case, pgr_dijkstraVia returns the following error:

SQL Error [XX000]: ERROR: std::bad_alloc

The input graph only contains vertices 1, 2, 3, and 4. Vertex 5 is not present in the graph, but it is included in the input array ARRAY[1, 3, 5].

Therefore, the failure is triggered when one of the requested via vertices does not exist in the graph.

[claudiadragoste]

For comparison, pgr_dijkstra behaves differently when the start or end vertex does not exist in the graph.

SELECT *
FROM pgr_dijkstra(
    '
    SELECT *
    FROM (
        VALUES
            (100, 1, 2, 1, 1),
            (101, 2, 3, 1, 1),
            (102, 3, 4, 1, 1)
    ) AS edge_table(id, source, target, cost, reverse_cost)
    ',
    1,
    5
);

In this example, vertex 5 does not exist in the graph. However, pgr_dijkstra does not raise an error. Instead, it returns an empty result set because no path can be computed to the requested destination vertex.

[cvvergara]

I think I found the bug:
here
I am not guarding against an emtpy result causing undefined behavior (the std::bad_alloc)