How pgrouting/gsoc-pgrouting works
1. Repository purpose and system boundary
pgRouting is a PostgreSQL/PostGIS extension that adds routing and network-analysis functions directly inside the database. The main runtime boundary is the PostgreSQL server: users call SQL functions, PostgreSQL loads the extension, and the extension executes graph algorithms on data already stored in tables.
2. Public API layer: SQL extension files
The sql/ tree is the database-facing API. It contains the extension install scripts, per-function SQL wrappers, versioned upgrade files, and pgrouting.control. This layer defines what PostgreSQL sees as extension functions such as pgr_dijkstra, pgr_astar, pgr_ksp, pgr_tsp, pgr_trsp, and many others.
3. Native execution layer: C/C++ algorithms
The actual algorithms live in src/ and include/. Most function families have a C implementation for the core algorithm and C++ helper code for data handling, graph structures, and result conversion. This is the computational engine of the extension.
4. Common infrastructure shared by all algorithms
Shared utilities are concentrated in include/cpp_common, include/c_common, and matching src/common / src/cpp_common sources. These handle PostgreSQL connection and parameter checks, memory helpers, graph and path types, identifier handling, and conversion of C++ results back into PostgreSQL rowsets. This shared layer is the main dependency used by almost every algorithm family.
5. Driver/process pattern
Many features are split into algorithm core plus a driver layer. The include/drivers/ headers and src/*/*_driver.cpp files adapt PostgreSQL inputs into internal graph objects, call the algorithm, and serialize results. Some families also have process sources in src/*/*_process.cpp and matching headers in include/process/, which provide a consistent execution pipeline for query parsing and result shaping.
6. Algorithm families
The code is organized by graph problem domain: shortest paths, all-pairs, A*/bidirectional variants, spanning tree, connected components, max flow/min cut, TSP, turn-restricted routing, withPoints routing, driving distance, planar checks, graph coloring, contraction hierarchies, traversal, and utilities. Each family has a matching presence across include/, src/, sql/, doc/, and test data, which makes the repo organized around feature families rather than one monolithic engine.
7. Data flow for a typical function call
A PostgreSQL client calls an extension function; SQL wrappers route the call to native code; the driver parses SQL arguments and fetches graph rows from tables; the algorithm builds an in-memory graph; the result is converted into PostgreSQL tuples and returned as a set of rows. This “SQL → driver → algorithm → result conversion → SQL result set” flow is the core runtime architecture.
8. Result and type modeling
The include/c_types/ headers define the row and result shapes returned to PostgreSQL, such as edges, paths, routes, tours, and specialized outputs for flow, contraction, or line-graph features. These types are the contract between internal computation and the SQL API, and are important for diagramming where algorithm output becomes database-visible rows.
9. Feature-specific data preparation
Some features need specialized preprocessing layers. Examples include withPoints and driving_distance for interpolating points on edges, trsp for turn restrictions, pickDeliver for VRP-style pickup/delivery optimization, and contraction for graph reduction. These subsystems sit between raw table data and the core routing algorithms.
10. Testing architecture
The repo has two major test surfaces: docqueries/ contains example SQL queries and expected results used for documentation validation, and pgtap/ contains PostgreSQL TAP tests for regression, edge cases, type checks, and crash safety. There are also helper scripts in tools/testers/ and CI workflow definitions that execute these suites across environments.
11. Documentation pipeline
Documentation is a first-class subsystem under doc/ and doxygen/. Sphinx-based docs generate the user and developer docs, while Doxygen config documents C++ internals. The locale/ tree supports translated docs, and docqueries/ doubles as executable documentation for function behavior.
12. Build and packaging pipeline
The project uses CMake as the build orchestrator, with custom CMake modules in cmake/ for PostgreSQL, Sphinx, and version handling. The build emits a PostgreSQL extension package from SQL scripts plus compiled native code. CI and release automation are in .github/workflows/, ci/, and tools/release-scripts/.
13. External dependencies and runtime environment
The primary runtime dependency is PostgreSQL with PostGIS available in the database. Build-time dependencies include C/C++ compilers, Boost Graph Library, CMake, Perl, and optionally Sphinx for docs. These materially affect how the extension is compiled, installed, and loaded by PostgreSQL.
14. How to draw the architecture diagram
A useful diagram would place PostgreSQL at the center, with SQL extension definitions feeding into native algorithm modules. Around that, show shared common libraries, specialized feature families, and output row types. Add separate support lanes for tests (pgtap, docqueries), docs (doc, doxygen, locale), and build/release tooling (CMake, ci, .github, tools).
Main entry points: cpp_common C++ common · drivers Drivers · pgtap Tests · CMakeLists.txt Build system
Components 22
SQL extension
Database-facing API and install/upgrade definitions
- PostgreSQL · Host database server that loads and executes the extension
- SQL common · Shared SQL-side checks and extension bootstrap logic
sql/common/pgrouting.control - Shortest paths SQL · SQL wrappers for Dijkstra and related routing functions
sql/dijkstra/dijkstra.sql - TRSP SQL · SQL wrappers for turn-restricted routing functions
sql/trsp/trsp.sql - VRP SQL · SQL wrappers for pickup-delivery and vehicle-routing features
sql/pickDeliver/pickDeliver.sql - Version SQL · Versioning and extension upgrade scripts
sql/version/version.sql
Native engine
C/C++ execution layer and shared infrastructure
- C++ common · Shared graph, memory, and PostgreSQL-to-native utilities
src/cpp_common - C common · PostgreSQL connection, parameter checks, and error/report helpers
src/common - Result types · Internal type definitions for edges, paths, tours, flows, and specialized results
include/c_types - Drivers · Entry-point adapters that turn SQL inputs into internal graph objects
include/drivers - Process layer · Common orchestration for parsing, execution, and result shaping
include/process
Feature families
Major algorithm and problem-domain subsystems
- Shortest paths · Core routing algorithms such as Dijkstra, A*, Bellman-Ford, and variants
src/dijkstra - Spanning trees · Minimum spanning tree algorithms and variants
src/spanningTree - Flow problems · Maximum flow, min-cost flow, matching, and min-cut algorithms
src/max_flow - Turn restrictions · Routing with turn penalties or restrictions
src/trsp - With points · Routing that interpolates points on edges before solving
src/withPoints - Pickup delivery · VRP-style pickup-delivery and depot-based scheduling
src/pickDeliver - Contraction · Graph reduction and contraction-hierarchy support
src/contraction
Support
Docs, tests, build, and release tooling
- Tests · PGTAP and docquery regression surfaces
pgtap - Docs · Sphinx and Doxygen documentation sources
doc - Build system · CMake and packaging configuration
CMakeLists.txt - CI / release · Workflows, release scripts, and environment-specific runners
.github/workflows/release.yml
Connections 31
- PostgreSQL → SQL common: loads · PostgreSQL installs extension definitions and common SQL helpers
- PostgreSQL → Shortest paths SQL: calls · Client SQL invokes routing functions through extension wrappers
- PostgreSQL → TRSP SQL: calls · Client SQL invokes turn-restricted functions through extension wrappers
- PostgreSQL → VRP SQL: calls · Client SQL invokes pickup-delivery functions through extension wrappers
- PostgreSQL → Version SQL: upgrades · Extension versioning and upgrade scripts are executed by PostgreSQL
- Shortest paths SQL → Drivers: dispatches · SQL wrappers route requests into native driver entry points
- TRSP SQL → Drivers: dispatches · TRSP SQL wrappers route requests into native driver entry points
- VRP SQL → Drivers: dispatches · VRP SQL wrappers route requests into native driver entry points
- Drivers → Process layer: orchestrates · Drivers pass parsed inputs into shared process pipelines where used
- Drivers → C++ common: uses · Adapters rely on common graph and conversion utilities
- Drivers → C common: uses · Adapters rely on shared PostgreSQL-side helpers
- Process layer → Result types: emits · Process stages shape native results into PostgreSQL-visible row types
- C++ common → Result types: converts · Shared C++ utilities marshal algorithm outputs into result records
- Shortest paths → C++ common: depends on · Routing algorithms build on shared graph and data-handling primitives
- Spanning trees → C++ common: depends on · MST implementations use the shared graph layer
- Flow problems → C++ common: depends on · Flow and matching algorithms use common graph structures
- Turn restrictions → C++ common: depends on · Turn-restricted routing uses shared path and restriction primitives
- With points → C++ common: depends on · Point-on-edge routing uses shared geometry and graph primitives
- Pickup delivery → C++ common: depends on · VRP logic uses common data and conversion utilities
- Contraction → C++ common: depends on · Contraction hierarchies build on shared graph primitives
- Turn restrictions → Drivers: adapts via · TRSP-specific drivers bridge SQL to the restricted-routing engine
- With points → Drivers: adapts via · With-points drivers bridge SQL to the interpolated-routing engine
- Tests → Shortest paths SQL: verifies · Regression suites exercise exposed SQL behavior
- Tests → TRSP SQL: verifies · Regression suites exercise restricted-routing SQL behavior
- Tests → VRP SQL: verifies · Regression suites exercise VRP SQL behavior
- Docs → SQL common: documents · User docs mirror the extension-facing API and concepts
- Build system → SQL common: packages · CMake assembles SQL scripts and compiled code into the extension
- Build system → Shortest paths: compiles · Build system compiles the native algorithm modules
- Build system → Docs: generates · Build system can generate documentation outputs
- CI / release → Tests: runs · Automation executes regression suites across environments
- CI / release → Build system: drives · CI and release jobs build, package, and validate the extension