# pgrouting/gsoc-pgrouting architecture

> Architecture diagram of the GitHub repository pgrouting/gsoc-pgrouting, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2026-05-23). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/pgrouting/gsoc-pgrouting
- Repository: https://github.com/pgrouting/gsoc-pgrouting

## Overview

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: [`src/cpp_common`](https://github.com/pgrouting/gsoc-pgrouting/tree/main/src/cpp_common) (C++ common), [`include/drivers`](https://github.com/pgrouting/gsoc-pgrouting/tree/main/include/drivers) (Drivers), [`pgtap`](https://github.com/pgrouting/gsoc-pgrouting/tree/main/pgtap) (Tests), [`CMakeLists.txt`](https://github.com/pgrouting/gsoc-pgrouting/blob/main/CMakeLists.txt) (Build system)

## Diagram (Mermaid)

```mermaid
flowchart TD

subgraph group_g1["SQL extension"]
  node_postgres[("PostgreSQL<br/>runtime boundary")]
  node_sql_common["SQL common<br/>sql helpers<br/>[pgrouting.control]"]
  node_sql_dijkstra["Shortest paths SQL<br/>function wrappers<br/>[dijkstra.sql]"]
  node_sql_trsp["TRSP SQL<br/>function wrappers<br/>[trsp.sql]"]
  node_sql_vrp["VRP SQL<br/>function wrappers<br/>[pickDeliver.sql]"]
  node_sql_version["Version SQL<br/>upgrade scripts<br/>[version.sql]"]
end

subgraph group_g2["Native engine"]
  node_common_cpp["C++ common<br/>shared runtime"]
  node_common_c["C common<br/>shared runtime"]
  node_types["Result types<br/>row models"]
  node_drivers["Drivers<br/>adapter layer"]
  node_process["Process layer<br/>pipeline stage"]
end

subgraph group_g3["Feature families"]
  node_shortest["Shortest paths<br/>algorithm family"]
  node_spanning["Spanning trees<br/>algorithm family"]
  node_flow["Flow problems<br/>algorithm family"]
  node_trsp["Turn restrictions<br/>feature family"]
  node_withpoints["With points<br/>feature family"]
  node_vrp["Pickup delivery<br/>optimization family"]
  node_contraction["Contraction<br/>graph reduction"]
end

subgraph group_g4["Support"]
  node_tests["Tests<br/>validation suite"]
  node_docs["Docs<br/>documentation pipeline"]
  node_build["Build system<br/>build orchestration<br/>[CMakeLists.txt]"]
  node_ci["CI / release<br/>automation<br/>[release.yml]"]
end

node_postgres -->|"loads"| node_sql_common
node_postgres -->|"calls"| node_sql_dijkstra
node_postgres -->|"calls"| node_sql_trsp
node_postgres -->|"calls"| node_sql_vrp
node_postgres -->|"upgrades"| node_sql_version
node_sql_dijkstra -->|"dispatches"| node_drivers
node_sql_trsp -->|"dispatches"| node_drivers
node_sql_vrp -->|"dispatches"| node_drivers
node_drivers -->|"orchestrates"| node_process
node_drivers -->|"uses"| node_common_cpp
node_drivers -->|"uses"| node_common_c
node_process -->|"emits"| node_types
node_common_cpp -->|"converts"| node_types
node_shortest -->|"depends on"| node_common_cpp
node_spanning -->|"depends on"| node_common_cpp
node_flow -->|"depends on"| node_common_cpp
node_trsp -->|"depends on"| node_common_cpp
node_withpoints -->|"depends on"| node_common_cpp
node_vrp -->|"depends on"| node_common_cpp
node_contraction -->|"depends on"| node_common_cpp
node_trsp -->|"adapts via"| node_drivers
node_withpoints -->|"adapts via"| node_drivers
node_tests -.->|"verifies"| node_sql_dijkstra
node_tests -.->|"verifies"| node_sql_trsp
node_tests -.->|"verifies"| node_sql_vrp
node_docs -.->|"documents"| node_sql_common
node_build -.->|"packages"| node_sql_common
node_build -.->|"compiles"| node_shortest
node_build -.->|"generates"| node_docs
node_ci -.->|"runs"| node_tests
node_ci -.->|"drives"| node_build

click node_sql_common "https://github.com/pgrouting/gsoc-pgrouting/blob/main/sql/common/pgrouting.control"
click node_sql_dijkstra "https://github.com/pgrouting/gsoc-pgrouting/blob/main/sql/dijkstra/dijkstra.sql"
click node_sql_trsp "https://github.com/pgrouting/gsoc-pgrouting/blob/main/sql/trsp/trsp.sql"
click node_sql_vrp "https://github.com/pgrouting/gsoc-pgrouting/blob/main/sql/pickDeliver/pickDeliver.sql"
click node_sql_version "https://github.com/pgrouting/gsoc-pgrouting/blob/main/sql/version/version.sql"
click node_common_cpp "https://github.com/pgrouting/gsoc-pgrouting/tree/main/src/cpp_common"
click node_common_c "https://github.com/pgrouting/gsoc-pgrouting/tree/main/src/common"
click node_types "https://github.com/pgrouting/gsoc-pgrouting/tree/main/include/c_types"
click node_drivers "https://github.com/pgrouting/gsoc-pgrouting/tree/main/include/drivers"
click node_process "https://github.com/pgrouting/gsoc-pgrouting/tree/main/include/process"
click node_shortest "https://github.com/pgrouting/gsoc-pgrouting/tree/main/src/dijkstra"
click node_spanning "https://github.com/pgrouting/gsoc-pgrouting/tree/main/src/spanningTree"
click node_flow "https://github.com/pgrouting/gsoc-pgrouting/tree/main/src/max_flow"
click node_trsp "https://github.com/pgrouting/gsoc-pgrouting/tree/main/src/trsp"
click node_withpoints "https://github.com/pgrouting/gsoc-pgrouting/tree/main/src/withPoints"
click node_vrp "https://github.com/pgrouting/gsoc-pgrouting/tree/main/src/pickDeliver"
click node_contraction "https://github.com/pgrouting/gsoc-pgrouting/tree/main/src/contraction"
click node_tests "https://github.com/pgrouting/gsoc-pgrouting/tree/main/pgtap"
click node_docs "https://github.com/pgrouting/gsoc-pgrouting/tree/main/doc"
click node_build "https://github.com/pgrouting/gsoc-pgrouting/blob/main/CMakeLists.txt"
click node_ci "https://github.com/pgrouting/gsoc-pgrouting/blob/main/.github/workflows/release.yml"

classDef toneNeutral fill:#f8fafc,stroke:#334155,stroke-width:1.5px,color:#0f172a
classDef toneBlue fill:#dbeafe,stroke:#2563eb,stroke-width:1.5px,color:#172554
classDef toneAmber fill:#fef3c7,stroke:#d97706,stroke-width:1.5px,color:#78350f
classDef toneMint fill:#dcfce7,stroke:#16a34a,stroke-width:1.5px,color:#14532d
classDef toneRose fill:#ffe4e6,stroke:#e11d48,stroke-width:1.5px,color:#881337
classDef toneIndigo fill:#e0e7ff,stroke:#4f46e5,stroke-width:1.5px,color:#312e81
classDef toneTeal fill:#ccfbf1,stroke:#0f766e,stroke-width:1.5px,color:#134e4a
class node_postgres,node_sql_common,node_sql_dijkstra,node_sql_trsp,node_sql_vrp,node_sql_version toneBlue
class node_common_cpp,node_common_c,node_types,node_drivers,node_process toneAmber
class node_shortest,node_spanning,node_flow,node_trsp,node_withpoints,node_vrp,node_contraction toneMint
class node_tests,node_docs,node_build,node_ci toneRose
```

## Components

### SQL extension

Database-facing API and install/upgrade definitions

- **PostgreSQL**: runtime boundary · Host database server that loads and executes the extension
- [SQL common](https://github.com/pgrouting/gsoc-pgrouting/blob/main/sql/common/pgrouting.control): sql helpers · Shared SQL-side checks and extension bootstrap logic · `sql/common/pgrouting.control`
- [Shortest paths SQL](https://github.com/pgrouting/gsoc-pgrouting/blob/main/sql/dijkstra/dijkstra.sql): function wrappers · SQL wrappers for Dijkstra and related routing functions · `sql/dijkstra/dijkstra.sql`
- [TRSP SQL](https://github.com/pgrouting/gsoc-pgrouting/blob/main/sql/trsp/trsp.sql): function wrappers · SQL wrappers for turn-restricted routing functions · `sql/trsp/trsp.sql`
- [VRP SQL](https://github.com/pgrouting/gsoc-pgrouting/blob/main/sql/pickDeliver/pickDeliver.sql): function wrappers · SQL wrappers for pickup-delivery and vehicle-routing features · `sql/pickDeliver/pickDeliver.sql`
- [Version SQL](https://github.com/pgrouting/gsoc-pgrouting/blob/main/sql/version/version.sql): upgrade scripts · Versioning and extension upgrade scripts · `sql/version/version.sql`

### Native engine

C/C++ execution layer and shared infrastructure

- [C++ common](https://github.com/pgrouting/gsoc-pgrouting/tree/main/src/cpp_common): shared runtime · Shared graph, memory, and PostgreSQL-to-native utilities · `src/cpp_common`
- [C common](https://github.com/pgrouting/gsoc-pgrouting/tree/main/src/common): shared runtime · PostgreSQL connection, parameter checks, and error/report helpers · `src/common`
- [Result types](https://github.com/pgrouting/gsoc-pgrouting/tree/main/include/c_types): row models · Internal type definitions for edges, paths, tours, flows, and specialized results · `include/c_types`
- [Drivers](https://github.com/pgrouting/gsoc-pgrouting/tree/main/include/drivers): adapter layer · Entry-point adapters that turn SQL inputs into internal graph objects · `include/drivers`
- [Process layer](https://github.com/pgrouting/gsoc-pgrouting/tree/main/include/process): pipeline stage · Common orchestration for parsing, execution, and result shaping · `include/process`

### Feature families

Major algorithm and problem-domain subsystems

- [Shortest paths](https://github.com/pgrouting/gsoc-pgrouting/tree/main/src/dijkstra): algorithm family · Core routing algorithms such as Dijkstra, A*, Bellman-Ford, and variants · `src/dijkstra`
- [Spanning trees](https://github.com/pgrouting/gsoc-pgrouting/tree/main/src/spanningTree): algorithm family · Minimum spanning tree algorithms and variants · `src/spanningTree`
- [Flow problems](https://github.com/pgrouting/gsoc-pgrouting/tree/main/src/max_flow): algorithm family · Maximum flow, min-cost flow, matching, and min-cut algorithms · `src/max_flow`
- [Turn restrictions](https://github.com/pgrouting/gsoc-pgrouting/tree/main/src/trsp): feature family · Routing with turn penalties or restrictions · `src/trsp`
- [With points](https://github.com/pgrouting/gsoc-pgrouting/tree/main/src/withPoints): feature family · Routing that interpolates points on edges before solving · `src/withPoints`
- [Pickup delivery](https://github.com/pgrouting/gsoc-pgrouting/tree/main/src/pickDeliver): optimization family · VRP-style pickup-delivery and depot-based scheduling · `src/pickDeliver`
- [Contraction](https://github.com/pgrouting/gsoc-pgrouting/tree/main/src/contraction): graph reduction · Graph reduction and contraction-hierarchy support · `src/contraction`

### Support

Docs, tests, build, and release tooling

- [Tests](https://github.com/pgrouting/gsoc-pgrouting/tree/main/pgtap): validation suite · PGTAP and docquery regression surfaces · `pgtap`
- [Docs](https://github.com/pgrouting/gsoc-pgrouting/tree/main/doc): documentation pipeline · Sphinx and Doxygen documentation sources · `doc`
- [Build system](https://github.com/pgrouting/gsoc-pgrouting/blob/main/CMakeLists.txt): build orchestration · CMake and packaging configuration · `CMakeLists.txt`
- [CI / release](https://github.com/pgrouting/gsoc-pgrouting/blob/main/.github/workflows/release.yml): automation · Workflows, release scripts, and environment-specific runners · `.github/workflows/release.yml`

## Connections

- 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
