# UNDF: UNDF-2026-000000566
# valhalla-0001: linkclassification.cc — IsSlipLane() nested linear scan O(F×R)

## File
`src/mjolnir/linkclassification.cc`

## Severity
**MEDIUM**

## Lines Affected
- Lines 658–662: `std::find(forward_nodes.begin(), forward_nodes.end(), node)` inside
  `for (auto node : reverse_nodes)` loop

## Defective Code

```cpp
// IsSlipLane() — lines 648–673
bool IsSlipLane(Data& data, SlipLaneInput input, double traverse_threshold) {
  auto forward_nodes =
      GoTowardsIntersection(input.first_node, input.fork_edge, true, traverse_threshold, data);
  auto reverse_nodes =
      GoTowardsIntersection(input.last_node, input.merge_edge, false, traverse_threshold, data);

  // O(R × F) — for each of R reverse nodes, linear scan over F forward nodes
  std::optional<uint32_t> intersection_node;
  for (auto node : reverse_nodes) {
    if (std::find(forward_nodes.begin(), forward_nodes.end(), node) != forward_nodes.end()) {
      intersection_node = node;
      break;
    }
  }
  return intersection_node != std::nullopt;
}
```

`forward_nodes` and `reverse_nodes` are `std::vector<uint32_t>`. For each node in
`reverse_nodes` (up to R nodes), `std::find` does a linear scan over `forward_nodes`
(up to F nodes). Total work: O(R × F).

Note: `GoTowardsIntersection` already uses an `std::unordered_set<size_t>` for its own
visited tracking, so visited tracking is O(1) there — but the intersection check reverts
to O(N²).

`IsSlipLane` is called during graph tile building (`mjolnir`) for every candidate link edge
in the OSM road network. Dense urban areas may have thousands of slip lane candidates, and
the traverse threshold controls path lengths. At high thresholds both vectors can reach
hundreds of nodes.

## Complexity Analysis
| Path | Per intersection check | Call frequency | Overall |
|------|----------------------|----------------|---------|
| Slow (std::find on vector) | O(F × R) | per link edge | **O(L × F × R)** |
| Fast (unordered_set lookup) | O(R) | per link edge | **O(L × R)** |

Where L = number of link edges, F = forward path length, R = reverse path length.
At traverse_threshold = 200m and urban density, F and R can each reach ~50 nodes,
giving 2500× overhead per link check vs O(R).

## Fixed Code

```cpp
bool IsSlipLane(Data& data, SlipLaneInput input, double traverse_threshold) {
  auto forward_nodes =
      GoTowardsIntersection(input.first_node, input.fork_edge, true, traverse_threshold, data);
  auto reverse_nodes =
      GoTowardsIntersection(input.last_node, input.merge_edge, false, traverse_threshold, data);

  // Build O(1) lookup set from forward_nodes
  std::unordered_set<uint32_t> forward_set(forward_nodes.begin(), forward_nodes.end());

  std::optional<uint32_t> intersection_node;
  for (auto node : reverse_nodes) {
    if (forward_set.count(node)) {   // O(1) instead of O(F)
      intersection_node = node;
      break;
    }
  }
  return intersection_node != std::nullopt;
}
```
