How cyang-kth/fmm works
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: fmm.cpp CLI apps · network.hpp Network model · geometry.hpp Geometry · fmm_algorithm.hpp FMM engine
Components 22
Core types
Shared geometry and GPS domain primitives used across the library.
Network layer
Road graph, spatial indexing, and routing primitives.
- Network graph · Base graph and network model for road topology.
src/network/network_graph.hpp - Bidir graph · Bidirectional graph variant used for routing queries.
src/network/bidirectional_network_graph.hpp - R-tree · Spatial index for nearby-edge candidate search.
src/network/rtree.hpp - Heap · Routing heap implementation used by shortest-path search.
src/network/heap.hpp - Network model · 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 · Intermediate graph for candidate transitions in matching.
src/mm/transition_graph.hpp - Composite graph · Composite structure used to assemble matching state spaces.
src/mm/composite_graph.hpp - FMM engine · Fast map matching algorithm and HMM-based orchestration.
src/mm/fmm/fmm_algorithm.hpp - UBODT · Upper Bounded Origin-Destination Table reader and query layer.
src/mm/fmm/ubodt.hpp - UBODT gen · Offline generation pipeline for the UBODT cache.
src/mm/fmm/ubodt_gen_algorithm.hpp - STMatch · Alternative matching algorithm without the UBODT dependency.
src/mm/stmatch/stmatch_algorithm.hpp - H3MM · 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 · Reads GPS trajectories from supported input formats.
src/io/gps_reader.hpp - Result writer · Serializes matched paths, offsets, errors, and traversed edges.
src/io/mm_writer.hpp - Configs · GPS, network, and result configuration models.
src/config/gps_config.hpp - Python binding · Thin SWIG-facing wrapper around the compiled matching engine.
src/python/pyfmm.hpp - CLI apps · 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 · Standalone C++ API example that consumes the library.
example/cpp-api/main.cpp - Web demo · Python-backed web demo using the same matching core.
example/web_demo/web_demo.py - Notebooks · Notebook examples for FMM, STMatch, and post-processing.
example/notebook/fmm_example.ipynb
Connections 26
- 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.