UNDF: UNDF-2026-000000407

graphhopper-0001: AlternativeRouteCH — IntArrayList.contains() O(P) inside edge loop

File

core/src/main/java/com/graphhopper/routing/AlternativeRouteCH.java

Severity

HIGH

Lines Affected

Line 174: alternatives.get(0).nodes.contains() × 2 — inside per-edge loop
Lines 182–187: nodesInCurrentAlternativeSetContains() — O(A×P) per edge call

Defective Code

// Line 159–168 — sharedDistance() — O(E × A × P) total
private double sharedDistance(Path path) {
    double sharedDistance = 0.0;
    List<EdgeIteratorState> edges = path.calcEdges();
    for (EdgeIteratorState edge : edges) {
        if (nodesInCurrentAlternativeSetContains(edge.getBaseNode()) && nodesInCurrentAlternativeSetContains(edge.getAdjNode())) {
            sharedDistance += edge.getDistance();
        }
    }
    return sharedDistance;
}

// Line 170–178 — sharedDistanceWithShortest() — O(E × P) total
private double sharedDistanceWithShortest(Path path) {
    double sharedDistance = 0.0;
    List<EdgeIteratorState> edges = path.calcEdges();
    for (EdgeIteratorState edge : edges) {
        if (alternatives.get(0).nodes.contains(edge.getBaseNode()) && alternatives.get(0).nodes.contains(edge.getAdjNode())) {
            sharedDistance += edge.getDistance();
        }
    }
    return sharedDistance;
}

// Line 181–188 — nodesInCurrentAlternativeSetContains() — O(A × P) per call
private boolean nodesInCurrentAlternativeSetContains(int v) {
    for (AlternativeInfo alternative : alternatives) {
        if (alternative.nodes.contains(v)) {   // IntArrayList.contains() = O(P) linear scan
            return true;
        }
    }
    return false;
}

AlternativeInfo.nodes is assigned from path.calcNodes() which returns an IntArrayList (HPPC). IntArrayList.contains() is a linear scan over the node list — O(P) per call where P = path length (number of nodes on the path).

Root Cause

Path.calcNodes() returns IntArrayList (an indexed array list), not a hash set. AlternativeInfo stores the result as IntIndexedContainer — the declared interface — which does not prevent linear-scan contains(). Every edge shared-distance calculation performs O(P) membership tests, called O(E) times per path evaluation, with up to A alternatives.

Complexity Analysis

Path	Per-call	Total calls	Overall
Slow (IntArrayList.contains)	O(P)	O(E × A)	O(E × A × P)
Fast (IntScatterSet.contains)	O(1)	O(E × A)	O(E × A)

For a 1000-edge route with paths of 800 nodes and 3 alternatives: slow = 2,400,000 comparisons vs fast = 3,000 comparisons — 800× speedup.

Fixed Code

import com.carrotsearch.hppc.IntScatterSet;
import com.carrotsearch.hppc.IntSet;

// In AlternativeInfo inner class — store node set alongside node list:
public static class AlternativeInfo {
    final double shareWeight;
    final Path path;
    final IntIndexedContainer nodes;
    final IntSet nodeSet;   // ADD: O(1) lookup set

    AlternativeInfo(Path path, double shareWeight) {
        this.path = path;
        this.shareWeight = shareWeight;
        this.nodes = path.calcNodes();
        // Build O(1) lookup set from the node list
        IntScatterSet set = new IntScatterSet(nodes.size());
        for (int i = 0; i < nodes.size(); i++) {
            set.add(nodes.get(i));
        }
        this.nodeSet = set;
    }
}

// sharedDistanceWithShortest — use nodeSet instead of nodes
private double sharedDistanceWithShortest(Path path) {
    double sharedDistance = 0.0;
    List<EdgeIteratorState> edges = path.calcEdges();
    for (EdgeIteratorState edge : edges) {
        if (alternatives.get(0).nodeSet.contains(edge.getBaseNode())
                && alternatives.get(0).nodeSet.contains(edge.getAdjNode())) {
            sharedDistance += edge.getDistance();
        }
    }
    return sharedDistance;
}

// nodesInCurrentAlternativeSetContains — use nodeSet
private boolean nodesInCurrentAlternativeSetContains(int v) {
    for (AlternativeInfo alternative : alternatives) {
        if (alternative.nodeSet.contains(v)) {   // O(1) hash lookup
            return true;
        }
    }
    return false;
}

4.2 KiB Raw Permalink Blame History Unescape Escape