Skip to content

CLAUDE.md

Latest commit

 

History

History
107 lines (78 loc) · 5.16 KB

CLAUDE.md

File metadata and controls

107 lines (78 loc) · 5.16 KB
Raw

CLAUDE.md

This file provides guidance to Claude Code (claude.ai/code) when working with code in this repository.

Project Overview

Wardrop User Equilibrium (UE) traffic assignment solver for the Chicago-Regional benchmark network using the Bi-Conjugate Frank-Wolfe (BFW) algorithm family. Solves the Beckmann convex minimization formulation with exact Newton–bisection line search.

Release 0.1 — single-file C++ program src/oba_assignment.cpp producing oba_assignment.exe.

Build & Run

Requires C++17 + OpenMP. This workspace uses MSYS2 MinGW64 g++ (C:/msys64/mingw64/bin/g++.exe).

# Build (from bash — Claude Code shell)
make                # uses Makefile
# or: powershell.exe -File build.ps1

# Run with defaults (BFW, conv=1e-4, paths+turns enabled)
./oba_assignment.exe

# Override algorithm
OBA_ALGO=3FW ./oba_assignment.exe

# Fast solver-only (skip large output files)
OBA_ENABLE_PATHS=0 OBA_ENABLE_TURNS=0 ./oba_assignment.exe

# CLI overrides
./oba_assignment.exe --data-dir ./chicago-regional --out-dir ./output --conv 1e-4

Compiler flags: -std=c++17 -O3 -fopenmp -march=native

Code Layout

Single-file program: src/oba_assignment.cpp (~1700 lines). Pipeline: parse → build network → solve → post-process → output.

Key functions (approximate line numbers):

Function Line Role
Config::from_env ~67 Read env vars into config
parse_network ~151 TNTP link file parser
parse_trips ~194 TNTP OD demand parser
parse_nodes ~236 TNTP node coordinate parser
build_network ~260 Construct Network struct from raw parsed data
build_csr / update_csr_costs ~346 CSR adjacency graph for Dijkstra
dijkstra_single ~398 Single-origin shortest path
aon_parallel ~431 OpenMP parallel Dijkstra + subtree AON loading
line_search ~659 Newton-bisection on Beckmann objective
compute_direction ~764 FW/CFW/BFW/3FW conjugate direction
run_solver ~1015 Main iteration loop
extract_final_paths ~1108 Post-convergence path reconstruction
save_turning_movements ~1248 Turning volume computation and CSV export
save_link_metrics_csv ~1438 Per-link metrics export
decompose_and_save_paths ~1483 Multi-path decomposition and export
main ~1637 Entry point, CLI parsing, orchestration

Architecture

  1. Parsers (parse_network, parse_trips, parse_nodes): Read TNTP-format files from chicago-regional/.
  2. Network struct: Link-indexed arrays (flow, cost, capacity, fftt, BPR params). update_costs() applies BPR formula + generalized cost (distance/toll weights).
  3. CSRGraph: Compressed sparse row adjacency for shortest paths. Built once, costs updated each iteration.
  4. Solver loop (run_solver): Parallel Dijkstra + subtree AON, Newton-bisection line search, N-conjugate direction for FW/CFW/BFW/3FW. When OBA_ENABLE_PATHS=1, switches to FW for path-flow tracking.
  5. Post-processing: Path reconstruction, turning movements, and link metrics CSV export.

Configuration (environment variables)

Variable Default Purpose
OBA_THREADS min(omp_get_max_threads(), 8) Parallel Dijkstra workers
OBA_ALGO BFW Algorithm: FW, CFW, BFW, or 3FW
OBA_CONV 1e-4 Convergence gap target (RelGap)
OBA_MAX_ITER 500 Maximum iterations
OBA_ENABLE_PATHS 1 0 to skip paths.csv
OBA_MULTIPATH 0 1 for iterative multi-path tracking (slower, forces FW)
OBA_ENABLE_TURNS 1 0 to skip turning movements
OBA_ENABLE_SHP 0 Reserved (not implemented)
OBA_PATH_FLOW_EPS 1e-3 Prune threshold for tiny path flows

CLI arguments: --data-dir <path>, --out-dir <path>, --conv <value> (overrides OBA_CONV).

In-code constants: DIST_WEIGHT=0.04 (min/mile), TOLL_WEIGHT=0.02 (min/cent).

Output Files (in output/)

File Content
convergence.csv Per-iteration: iter, rel_gap, tstt, sptt, alpha, timings
paths.csv Single-path per OD (when OBA_ENABLE_PATHS=1)
turning_movements.csv junction_node, from_node, to_node, volume
link_metrics.csv Per-link: flow, vc_ratio, travel_time, generalized_cost + base attributes

Note: paths.csv can reach GB scale on full Chicago-Regional.

Dataset

Chicago-Regional (in chicago-regional/): 12,982 nodes, 1,790 zones, 39,018 links, 1.36M trips. TNTP format. CRS: NAD83 / Illinois State Plane East (US survey feet).

Important Implementation Details

  • Parallel Dijkstra+AON: each OpenMP thread solves shortest paths for assigned origin chunks and performs subtree demand loading.
  • CSR row scan for edge-to-link lookup keeps predecessor-link mapping simple and cache-friendly.
  • Newton-bisection line search avoids unstable fixed step sizes; operates on Beckmann objective slope.
  • 3FW (tri-conjugate Frank-Wolfe): 3 previous directions, 3×3 linear system per iteration with fallback chain if singular.
  • RelGap = (TSTT − SPTT) / SPTT, where TSTT is total system travel time and SPTT is sum of minimum OD costs from the AON pass.