# cyang-kth/fmm architecture

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

- Interactive diagram: https://gitdiagram.com/cyang-kth/fmm
- Repository: https://github.com/cyang-kth/fmm

## Overview

1. **What this repository is**
   - This is a C++ map-matching framework for noisy GPS trajectories.
   - The core product is a library plus multiple front ends: command-line apps, Python bindings, notebooks, and a web demo.
   - The architecture centers on turning GPS observations and a road network into matched paths, with an optional precomputation layer for faster routing.

2. **Top-level layering**
   - The code is organized from low-level primitives up to applications:
     - `src/core` for shared geometry/GPS types.
     - `src/network` for graph and routing structures.
     - `src/mm` for map-matching algorithms and app-level orchestration.
     - `src/io` for reading GPS input and writing match results.
     - `src/config` for configuration parsing and validation.
     - `src/app` for executable entry points.
   - This separation is important: algorithms do not directly own file formats or CLI concerns.

3. **Core domain model**
   - `src/core/gps.hpp` and `src/core/geometry.*` define the basic observation and geometry abstractions used throughout.
   - The system works with trajectories, points, network edges, and matched outputs rather than a single app-specific DTO.
   - These types are the boundary between input parsing, graph computation, and output formatting.

4. **Network and routing subsystem**
   - `src/network` implements the road-network representation and routing support:
     - `network_graph`, `bidirectional_network_graph`, `graph`, `heap`, and `rtree`.
   - The routing layer is built for fast nearest-edge and path queries, which are central to candidate generation and shortest-path calculations.
   - The presence of an R-tree indicates spatial indexing is used to prune candidate search around GPS points.

5. **Map-matching algorithms**
   - `src/mm/fmm` contains the “Fast Map Matching” implementation, which combines hidden Markov model logic with precomputed routing information.
   - `src/mm/stmatch` contains the STMatch algorithm, likely used when precomputation is not desired or for large networks.
   - `src/mm/h3mm` adds a hexagon-based matching mode using Uber’s H3 indexing system.
   - `src/mm/transition_graph.cpp` and `src/mm/composite_graph.cpp` suggest the framework builds intermediate graphs to model transitions between candidate states.

6. **Precomputation path: UBODT**
   - The major architectural distinction in this repo is the UBODT pipeline:
     - `src/mm/fmm/ubodt_gen_*` generates the Upper Bounded Origin-Destination Table.
     - `src/mm/fmm/ubodt.*` reads and queries the precomputed table.
   - This precomputation is what makes FMM scale well: shortest-path work is shifted from runtime matching into an offline preparation step.
   - In diagrams, UBODT should be shown as a reusable cache between network data and the FMM matcher.

7. **Application entry points**
   - `src/app/fmm.cpp`, `stmatch.cpp`, `ubodt_gen_app.cpp`, and `h3mm.cpp` are the CLI executables.
   - The app layer wires together config parsing, data loading, algorithm selection, execution, and result writing.
   - The README confirms these build into separate binaries: `fmm`, `stmatch`, and `ubodt_gen`.

8. **Input/output boundary**
   - `src/io/gps_reader.*` handles GPS ingestion in the supported formats.
   - `src/io/mm_writer.*` serializes matched results, including rich outputs such as path geometry, offsets, errors, and traversed edges.
   - Network input is handled through configuration and lower-level network loading code, with shapefile and related geospatial formats emphasized in the docs.
   - This I/O layer is a clean boundary: algorithms consume in-memory structures, not raw files.

9. **Configuration boundary**
   - `src/config` contains separate config models for GPS, network, and result output.
   - The app layer likely binds these configs to CLI arguments or XML/JSON files, as shown by the example configs in `example/command_line_example` and `example/web_demo`.
   - This keeps runtime behavior declarative and makes the same algorithm usable from CLI, Python, and web contexts.

10. **Python integration**
    - `src/python/pyfmm.hpp` and `python/fmm.i` expose the C++ engine to Python via SWIG.
    - The Python side is thin: it wraps the compiled core rather than reimplementing matching logic.
    - This is why notebooks and the web demo can reuse the exact same matching engine as the CLI tools.

11. **Example surfaces**
    - `example/notebook`, `example/python`, `example/cpp-api`, `example/web_demo`, and `example/osmnx_example` show different integration surfaces over the same core engine.
    - The web demo adds a small Python server, static assets, and JSON configs, but still depends on the underlying matching binaries/bindings.
    - The notebooks and examples are not separate products; they are usage layers that demonstrate the same backend architecture.

12. **External dependencies that shape the design**
    - GDAL is a major dependency for geospatial file I/O and geometry handling.
    - Boost Graph/Geometry/Serialization support routing, spatial operations, and UBODT serialization.
    - OpenMP is used for parallelism, which matters for large trajectory batches.
    - H3 is bundled for the hexagon-matching mode.
    - `spdlog`, `cxxopts`, `catch2`, and `fiboheap` are embedded third-party libraries for logging, CLI parsing, tests, and heap operations.

13. **Testing and validation**
    - `test/` contains focused unit/integration tests for algorithms, network behavior, and FMM behavior.
    - The test data mirrors the real runtime shapes: network files, trajectories, UBODT tables, and matching outputs.
    - This indicates the architecture is intended to validate both graph logic and end-to-end matching workflows.

14. **Build and packaging**
    - The repo is CMake-driven (`CMakeLists.txt`, `python/CMakeLists.txt`, `test/CMakeLists.txt`), with platform support for Linux/macOS/Windows.
    - Docker and CI configs exist for reproducible builds, but they do not change the runtime architecture.
    - In an architecture diagram, the build system should be treated as an outer concern around the compiled C++ core, not a runtime subsystem.

15. **Primary data flow**
    - Typical FMM flow: road network + GPS observations → spatial indexing/candidate generation → optional UBODT-based shortest-path lookup → HMM-based state/transition evaluation → matched path output.
    - STMatch follows a similar input/output shape but without the precomputed UBODT dependency.
    - H3MM replaces the road-network path with hexagon indexing and interpolation logic for a different target domain.

16. **How to diagram the boundaries**
    - Draw the core C++ library in the middle, with three main inbound data sources: network files, GPS trajectories, and precomputed UBODT.
    - Show the algorithm layer split into FMM, STMatch, and H3MM.
    - Put I/O/config as the outer shell around all algorithms.
    - Attach Python, CLI, notebook, and web demo as separate consumers of the same compiled core, rather than separate implementations.

Main entry points: [`src/app/fmm.cpp`](https://github.com/cyang-kth/fmm/blob/master/src/app/fmm.cpp) (CLI apps), [`src/network/network.hpp`](https://github.com/cyang-kth/fmm/blob/master/src/network/network.hpp) (Network model), [`src/core/geometry.hpp`](https://github.com/cyang-kth/fmm/blob/master/src/core/geometry.hpp) (Geometry), [`src/mm/fmm/fmm_algorithm.hpp`](https://github.com/cyang-kth/fmm/blob/master/src/mm/fmm/fmm_algorithm.hpp) (FMM engine)

## Diagram (Mermaid)

```mermaid
flowchart TD

subgraph group_core["Core types"]
  node_core_gps["GPS types<br/>domain types<br/>[gps.hpp]"]
  node_core_geometry["Geometry<br/>[geometry.hpp]"]
end

subgraph group_network["Network layer"]
  node_network_graph["Network graph<br/>road graph<br/>[network_graph.hpp]"]
  node_network_bidirectional["Bidir graph<br/>routing graph"]
  node_network_rtree{{"R-tree<br/>spatial index<br/>[rtree.hpp]"}}
  node_network_heap["Heap<br/>priority queue<br/>[heap.hpp]"]
  node_network_network["Network model<br/>network facade<br/>[network.hpp]"]
end

subgraph group_matching["Matching engines"]
  node_mm_transition{{"Transition graph<br/>state graph"}}
  node_mm_composite{{"Composite graph<br/>state graph"}}
  node_fmm_alg["FMM engine<br/>map matching<br/>[fmm_algorithm.hpp]"]
  node_ubodt[("UBODT<br/>precomputed route cache<br/>[ubodt.hpp]")]
  node_ubodt_gen["UBODT gen<br/>offline builder"]
  node_stmatch_alg["STMatch<br/>map matching"]
  node_h3mm{{"H3MM<br/>hex matching<br/>[h3mm.hpp]"}}
end

subgraph group_interfaces["Front ends"]
  node_gps_reader["GPS reader<br/>input adapter<br/>[gps_reader.hpp]"]
  node_mm_writer["Result writer<br/>output adapter<br/>[mm_writer.hpp]"]
  node_config_models["Configs<br/>runtime config<br/>[gps_config.hpp]"]
  node_pyfmm["Python binding<br/>swig wrapper<br/>[pyfmm.hpp]"]
  node_cli_apps["CLI apps<br/>executables<br/>[fmm.cpp]"]
end

subgraph group_examples["Examples"]
  node_cpp_example["C++ example<br/>example client<br/>[main.cpp]"]
  node_web_demo["Web demo<br/>demo app<br/>[web_demo.py]"]
  node_notebooks["Notebooks<br/>analysis client<br/>[fmm_example.ipynb]"]
end

node_core_gps -->|"parsed by"| node_gps_reader
node_core_geometry -->|"supports"| node_network_graph
node_core_geometry -->|"used by"| node_mm_transition
node_network_network -->|"wraps"| node_network_graph
node_network_network -->|"indexes"| node_network_rtree
node_network_network -->|"routes via"| node_network_heap
node_network_bidirectional -->|"extends"| node_network_graph
node_gps_reader -->|"configured by"| node_config_models
node_cli_apps -->|"loads"| node_config_models
node_cli_apps -->|"consumes"| node_gps_reader
node_cli_apps -->|"writes"| node_mm_writer
node_cli_apps -->|"runs"| node_fmm_alg
node_cli_apps -->|"runs"| node_stmatch_alg
node_cli_apps -->|"runs"| node_ubodt_gen
node_cli_apps -->|"runs"| node_h3mm
node_fmm_alg -->|"builds"| node_mm_transition
node_fmm_alg -->|"queries"| node_ubodt
node_ubodt_gen -->|"reads network"| node_network_network
node_stmatch_alg -->|"queries"| node_network_network
node_h3mm -->|"uses"| node_core_geometry
node_pyfmm -->|"wraps"| node_fmm_alg
node_cpp_example -.->|"illustrates"| node_pyfmm
node_web_demo -->|"calls"| node_pyfmm
node_notebooks -.->|"explores"| node_pyfmm
node_mm_writer -->|"serializes"| node_core_geometry
node_ubodt -.->|"accelerates"| node_network_heap

click node_core_gps "https://github.com/cyang-kth/fmm/blob/master/src/core/gps.hpp"
click node_core_geometry "https://github.com/cyang-kth/fmm/blob/master/src/core/geometry.hpp"
click node_network_graph "https://github.com/cyang-kth/fmm/blob/master/src/network/network_graph.hpp"
click node_network_bidirectional "https://github.com/cyang-kth/fmm/blob/master/src/network/bidirectional_network_graph.hpp"
click node_network_rtree "https://github.com/cyang-kth/fmm/blob/master/src/network/rtree.hpp"
click node_network_heap "https://github.com/cyang-kth/fmm/blob/master/src/network/heap.hpp"
click node_network_network "https://github.com/cyang-kth/fmm/blob/master/src/network/network.hpp"
click node_mm_transition "https://github.com/cyang-kth/fmm/blob/master/src/mm/transition_graph.hpp"
click node_mm_composite "https://github.com/cyang-kth/fmm/blob/master/src/mm/composite_graph.hpp"
click node_fmm_alg "https://github.com/cyang-kth/fmm/blob/master/src/mm/fmm/fmm_algorithm.hpp"
click node_ubodt "https://github.com/cyang-kth/fmm/blob/master/src/mm/fmm/ubodt.hpp"
click node_ubodt_gen "https://github.com/cyang-kth/fmm/blob/master/src/mm/fmm/ubodt_gen_algorithm.hpp"
click node_stmatch_alg "https://github.com/cyang-kth/fmm/blob/master/src/mm/stmatch/stmatch_algorithm.hpp"
click node_h3mm "https://github.com/cyang-kth/fmm/blob/master/src/mm/h3mm/h3mm.hpp"
click node_gps_reader "https://github.com/cyang-kth/fmm/blob/master/src/io/gps_reader.hpp"
click node_mm_writer "https://github.com/cyang-kth/fmm/blob/master/src/io/mm_writer.hpp"
click node_config_models "https://github.com/cyang-kth/fmm/blob/master/src/config/gps_config.hpp"
click node_pyfmm "https://github.com/cyang-kth/fmm/blob/master/src/python/pyfmm.hpp"
click node_cli_apps "https://github.com/cyang-kth/fmm/blob/master/src/app/fmm.cpp"
click node_cpp_example "https://github.com/cyang-kth/fmm/blob/master/example/cpp-api/main.cpp"
click node_web_demo "https://github.com/cyang-kth/fmm/blob/master/example/web_demo/web_demo.py"
click node_notebooks "https://github.com/cyang-kth/fmm/blob/master/example/notebook/fmm_example.ipynb"

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_core_gps,node_core_geometry toneBlue
class node_network_graph,node_network_bidirectional,node_network_rtree,node_network_heap,node_network_network toneAmber
class node_mm_transition,node_mm_composite,node_fmm_alg,node_ubodt,node_ubodt_gen,node_stmatch_alg,node_h3mm toneMint
class node_gps_reader,node_mm_writer,node_config_models,node_pyfmm,node_cli_apps toneRose
class node_cpp_example,node_web_demo,node_notebooks toneIndigo
```

## Components

### Core types

Shared geometry and GPS domain primitives used across the library.

- [GPS types](https://github.com/cyang-kth/fmm/blob/master/src/core/gps.hpp): domain types · Trajectory, observation, and GPS-related shared types. · `src/core/gps.hpp`
- [Geometry](https://github.com/cyang-kth/fmm/blob/master/src/core/geometry.hpp): geometry core · Core geometric primitives and helpers. · `src/core/geometry.hpp`

### Network layer

Road graph, spatial indexing, and routing primitives.

- [Network graph](https://github.com/cyang-kth/fmm/blob/master/src/network/network_graph.hpp): road graph · Base graph and network model for road topology. · `src/network/network_graph.hpp`
- [Bidir graph](https://github.com/cyang-kth/fmm/blob/master/src/network/bidirectional_network_graph.hpp): routing graph · Bidirectional graph variant used for routing queries. · `src/network/bidirectional_network_graph.hpp`
- [R-tree](https://github.com/cyang-kth/fmm/blob/master/src/network/rtree.hpp): spatial index · Spatial index for nearby-edge candidate search. · `src/network/rtree.hpp`
- [Heap](https://github.com/cyang-kth/fmm/blob/master/src/network/heap.hpp): priority queue · Routing heap implementation used by shortest-path search. · `src/network/heap.hpp`
- [Network model](https://github.com/cyang-kth/fmm/blob/master/src/network/network.hpp): network facade · Higher-level network wrapper and loaders around the road graph. · `src/network/network.hpp`

### Matching engines

Algorithm families and their intermediate graph structures.

- [Transition graph](https://github.com/cyang-kth/fmm/blob/master/src/mm/transition_graph.hpp): state graph · Intermediate graph for candidate transitions in matching. · `src/mm/transition_graph.hpp`
- [Composite graph](https://github.com/cyang-kth/fmm/blob/master/src/mm/composite_graph.hpp): state graph · Composite structure used to assemble matching state spaces. · `src/mm/composite_graph.hpp`
- [FMM engine](https://github.com/cyang-kth/fmm/blob/master/src/mm/fmm/fmm_algorithm.hpp): map matching · Fast map matching algorithm and HMM-based orchestration. · `src/mm/fmm/fmm_algorithm.hpp`
- [UBODT](https://github.com/cyang-kth/fmm/blob/master/src/mm/fmm/ubodt.hpp): precomputed route cache · Upper Bounded Origin-Destination Table reader and query layer. · `src/mm/fmm/ubodt.hpp`
- [UBODT gen](https://github.com/cyang-kth/fmm/blob/master/src/mm/fmm/ubodt_gen_algorithm.hpp): offline builder · Offline generation pipeline for the UBODT cache. · `src/mm/fmm/ubodt_gen_algorithm.hpp`
- [STMatch](https://github.com/cyang-kth/fmm/blob/master/src/mm/stmatch/stmatch_algorithm.hpp): map matching · Alternative matching algorithm without the UBODT dependency. · `src/mm/stmatch/stmatch_algorithm.hpp`
- [H3MM](https://github.com/cyang-kth/fmm/blob/master/src/mm/h3mm/h3mm.hpp): hex matching · Hexagon-based matching mode built on H3 indexing. · `src/mm/h3mm/h3mm.hpp`

### Front ends

CLI entry points, Python bindings, and I/O/config boundaries.

- [GPS reader](https://github.com/cyang-kth/fmm/blob/master/src/io/gps_reader.hpp): input adapter · Reads GPS trajectories from supported input formats. · `src/io/gps_reader.hpp`
- [Result writer](https://github.com/cyang-kth/fmm/blob/master/src/io/mm_writer.hpp): output adapter · Serializes matched paths, offsets, errors, and traversed edges. · `src/io/mm_writer.hpp`
- [Configs](https://github.com/cyang-kth/fmm/blob/master/src/config/gps_config.hpp): runtime config · GPS, network, and result configuration models. · `src/config/gps_config.hpp`
- [Python binding](https://github.com/cyang-kth/fmm/blob/master/src/python/pyfmm.hpp): swig wrapper · Thin SWIG-facing wrapper around the compiled matching engine. · `src/python/pyfmm.hpp`
- [CLI apps](https://github.com/cyang-kth/fmm/blob/master/src/app/fmm.cpp): executables · Command-line entry points for FMM, STMatch, H3MM, and UBODT generation. · `src/app/fmm.cpp`

### Examples

Representative usage surfaces built on top of the compiled core.

- [C++ example](https://github.com/cyang-kth/fmm/blob/master/example/cpp-api/main.cpp): example client · Standalone C++ API example that consumes the library. · `example/cpp-api/main.cpp`
- [Web demo](https://github.com/cyang-kth/fmm/blob/master/example/web_demo/web_demo.py): demo app · Python-backed web demo using the same matching core. · `example/web_demo/web_demo.py`
- [Notebooks](https://github.com/cyang-kth/fmm/blob/master/example/notebook/fmm_example.ipynb): analysis client · Notebook examples for FMM, STMatch, and post-processing. · `example/notebook/fmm_example.ipynb`

## Connections

- GPS types → GPS reader: parsed by · GPS observations enter through the I/O boundary.
- Geometry → Network graph: supports · Geometry primitives underpin road-network representation.
- Geometry → Transition graph: used by · Geometry helps build candidate and transition structures.
- Network model → Network graph: wraps · Network facade builds on the base graph representation.
- Network model → R-tree: indexes · Spatial index supports nearby-edge lookups.
- Network model → Heap: routes via · Priority queue supports shortest-path search.
- Bidir graph → Network graph: extends · Bidirectional variant is a specialized routing graph.
- GPS reader → Configs: configured by · Input parsing is driven by runtime config.
- CLI apps → Configs: loads · CLI executables bind config to runtime behavior.
- CLI apps → GPS reader: consumes · Apps load trajectory input through the reader layer.
- CLI apps → Result writer: writes · Apps emit matched outputs through the writer layer.
- CLI apps → FMM engine: runs · FMM executable orchestrates the main matcher.
- CLI apps → STMatch: runs · STMatch executable orchestrates the alternative matcher.
- CLI apps → UBODT gen: runs · Dedicated executable builds the offline cache.
- CLI apps → H3MM: runs · H3MM executable exposes hex-based matching.
- FMM engine → Transition graph: builds · FMM constructs transition/state graphs.
- FMM engine → UBODT: queries · Runtime matching uses the precomputed route cache.
- UBODT gen → Network model: reads network · UBODT generation depends on the road network.
- STMatch → Network model: queries · STMatch uses routing and candidate queries against the network.
- H3MM → Geometry: uses · Hex matching still depends on shared geometry utilities.
- Python binding → FMM engine: wraps · Python bindings expose the compiled core engine.
- C++ example → Python binding: illustrates · Example surface shows library consumption patterns.
- Web demo → Python binding: calls · Web demo reuses the same binding layer.
- Notebooks → Python binding: explores · Notebook workflows exercise the same core engine interactively.
- Result writer → Geometry: serializes · Output includes path geometry and related measurements.
- UBODT → Heap: accelerates · Precomputed routes reduce runtime shortest-path work.
