pgr_drivingDistance: get_depth() is O(reached × V) and dominates runtime on large graphs

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

Maintainers usually reply within 3 days

@jflangenbach-casageo is already working on this.

Since Oct 28, 2026.

  • #3177 by @jflangenbach-casageo — open

Assessment

Difficulty
3/5
Estimated time
1-2 days
Newbie friendliness
62/100
Issue type
Bug
Clarity
Clearly specified
Activity status
Active
Tech stack
cpp, postgresql
Domain
backend, performance

Research direction

Start in detail::get_depth() in include/dijkstra/drivingDist.hpp, which scans every vertex for each reached vertex; the proposed replacement memoizes depth in one O(V) pass and keeps the remove_details() handling. Reproduce with the chain-graph queries in the issue and compare the returned rows against the original build. Done when the depth output matches the old version on the grid tests and the pgTAP suite passes.

Written by the indexing model from the issue text.

Description

bug

Title: pgr_drivingDistance: get_depth() is O(reached × V) and dominates runtime on large graphs

Problem

Since 3.6.0, pgr_drivingDistance (and pgr_withPointsDD) compute the depth column in detail::get_depth() (include/dijkstra/drivingDist.hpp). For every vertex found on the current depth level, the function scans all vertices of the graph to find its children:

for (const auto v : vertices) {
    for (V p = 0; p < graph.num_vertices() ; ++p) {
        ...
        if (!(predecessors[p] == v)) continue;

This makes the cost O(reached vertices × all vertices in the graph). The Dijkstra search itself stops at distance and is cheap. But get_depth() also iterates over every vertex that was loaded and never reached. Typical isochrone queries load a bounding area that is much larger than the reachable part, so get_depth() takes almost all of the runtime.

The loop also has no CHECK_FOR_INTERRUPTS(), so the query cannot be cancelled while it runs.

The code is unchanged from 3.6.0 through 4.0.2 and is the same on main and develop.

Versions

  • pgRouting 4.0.1 (pgr_full_version(): 4.0.1, Release, ..., Boost 1.83.0)
  • PostgreSQL 18, Ubuntu 24.04, PGDG packages

Minimal reproduction

A chain graph. The search always reaches the same 20,001 vertices. Only the number of loaded, unreachable vertices changes:

CREATE TEMP TABLE edges AS
SELECT g AS id, g AS source, g + 1 AS target, 1.0::float8 AS cost, -1.0::float8 AS reverse_cost
FROM generate_series(1, 2000000) g;

SELECT count(*) FROM pgr_drivingDistance('SELECT * FROM edges WHERE id <= 100000', 1, 20000);
SELECT count(*) FROM pgr_drivingDistance('SELECT * FROM edges WHERE id <= 1000000', 1, 20000);
SELECT count(*) FROM pgr_drivingDistance('SELECT * FROM edges', 1, 20000);
-- graph building only (start vertex does not exist)
SELECT count(*) FROM pgr_drivingDistance('SELECT * FROM edges', -1, 20000);
Vertices in graph Result rows Time
100,000 20,001 2.1 s
1,000,000 20,001 19.2 s
2,000,000 20,001 40.5 s
2,000,000, building only – 1.7 s

The result stays the same, but the runtime grows linearly with the number of unreachable vertices.

Real-world impact

These numbers come from a road network (car, cost in seconds, one start vertex):

Isochrone Vertices loaded Vertices reached Time total Time loading + graph building
10 min 607,779 15,783 10.4 s 0.7 s
30 min 1,685,400 247,916 9 min 26 s not measured

More than 90 % of the time is spent in get_depth(). The depth column is not used in these queries, but it cannot be switched off.

With the fix proposed below, the same 30-minute isochrone (Hamburg main station as start point) runs much faster. The times below are for our complete application functions, end to end. Each function selects the edges, calls pgr_drivingDistance once and builds the output geometry:

30 min isochrone, complete function pgRouting 4.0.1, unchanged with the fix below
Isochrone polygon 9 min 6 s 13 s
Catchment area as grid cells 9 min 4 s 11 s

So in practice almost the whole runtime of these queries was spent in get_depth().

Proposed fix

Compute the depth in a single pass over the predecessors, depth(v) = depth(pred(v)) + 1, and memoize the results. This is O(V) and gives the same result, including the remove_details() handling for details = false:

template <typename G, typename V>
std::map<int64_t, int64_t> get_depth(
        const G &graph,
        V root,
        const std::vector<double>& distances,
        std::vector<V>& predecessors,
        double distance,
        bool details) {
    std::map<int64_t, int64_t> depth;
    if (predecessors.empty()) return depth;
    if (predecessors.size() != distances.size()) return depth;

    if (!details) {
        remove_details(graph, distances, predecessors);
    }

    const int64_t UNKNOWN = -2;
    const int64_t NOT_IN_TREE = -1;
    std::vector<int64_t> d(predecessors.size(), UNKNOWN);
    d[root] = 0;

    std::vector<V> chain;
    for (V v = 0; v < predecessors.size(); ++v) {
        if (d[v] != UNKNOWN) continue;
        if (v % 100000 == 0) CHECK_FOR_INTERRUPTS();

        /* walk up the tree until a vertex with known depth is found */
        chain.clear();
        V u = v;
        while (d[u] == UNKNOWN) {
            if (predecessors[u] == u || !(distances[u] <= distance)) {
                d[u] = NOT_IN_TREE;
                break;
            }
            chain.push_back(u);
            u = predecessors[u];
        }

        /* assign depths back down the chain */
        int64_t current = d[u];
        for (auto it = chain.rbegin(); it != chain.rend(); ++it) {
            current = (current == NOT_IN_TREE) ? NOT_IN_TREE : current + 1;
            d[*it] = current;
        }
    }

    for (V v = 0; v < d.size(); ++v) {
        if (d[v] >= 0) depth[graph[v].id] = d[v];
    }
    return depth;
}

The function above is a drop-in replacement for detail::get_depth() in include/dijkstra/drivingDist.hpp (v4.0.1). No other file or signature changes.

How we tested it

  1. Standalone harness: We compared the original and the new function on 300 random shortest-path trees, with and without details, with points (negative ids) and with a distance limit. The returned maps and the modified predecessor vectors were identical in all cases. For a tree with 600,000 vertices and 15,783 reached, the original took 4.9 s and the new version 0.006 s.
  2. Full build: We built pgRouting 4.0.1 with the change (Release, Ubuntu 24.04, PostgreSQL 18, Boost 1.83) and compared the complete result rows of the original and the patched library on a 300 × 300 grid with random costs and one-way edges:
Query Rows Differences
pgr_drivingDistance, one start vertex 2,441 0
pgr_drivingDistance, several start vertices 3,608 0
pgr_drivingDistance, several start vertices, equicost 3,608 0
pgr_drivingDistance, undirected 2,972 0
pgr_withPointsDD, details => true 2,803 0
pgr_withPointsDD, details => false 2,800 0
pgr_withPointsDD, details => false, equicost 2,790 0

In the same build, the chain reproduction above (2,000,000 vertices) dropped from 40.9 s to 2.2 s.

We have not run the pgTAP suite with this change.

Everything needed is contained in this issue. Please feel free to use the code above under the project's license.

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.