Quantize spacetime on your laptop.
This reproducible archival rendering is generated from a tracked triangulation fixture; see the viewer and visual-artifact contract.
Maintenance status
CDT++ v1.0.0-rc3 is the current C++23 release candidate. The repository remains maintained as an independent scientific reference and regression oracle for causal-triangulations, the supported Rust successor. New C++ work is limited to correctness, reproducibility, cross-implementation validation, the complete supported 2+1D move set, and work approved in project issues. The v1.0.0 release contract remains tracked by issue #90; making the GitHub repository read-only is a separate future lifecycle decision rather than an automatic consequence of that release. The local Python comparison harness orchestrates independent C++ and Rust executables and analyzes their declared outputs; it is not a second scientific implementation.
Table of contents
- CDT-plusplus
Introduction
For an introduction to Causal Dynamical Triangulations, including the foundations and recent results, please see the wiki.
Causal Dynamical Triangulations in C++ uses the Computational Geometry Algorithms Library, Boost, and TBB. Arbitrary-precision numbers and functions are by MPFR and GMP. Melissa E. O'Neill's Permuted Congruential Generators library provides high-quality RNGs that pass L'Ecuyer's TestU01 statistical tests. doctest provides BDD/TDD. vcpkg provides library management and building. Doxygen provides automated document generation. The supported C++ namespace and per-header contract are recorded in the C++ API boundary. The compiled C++ API quickstart demonstrates validated construction, ten reported Metropolis proposals with separate candidate-success and acceptance results, aggregate accounting, and a verified persistence round trip. The exact CGAL version, kernel, TDS, metadata, lifetime, TBB, benchmark, and upgrade policies are recorded in the CGAL 6.2 integration contract. The evidence and migration gates for replacing GMP/MPFR with Boost.Multiprecision are recorded in the arithmetic backend evaluation. The opt-in operations, ownership and synchronization rules, replayable stress inputs, sanitizer boundary, and matched scaling protocol are recorded in the multithreaded CGAL contract. {fmt} provides a safe and fast alternative to iostream. spdlog provides fast, multithreaded logging. Python and JSON Schema provide the local, offline cross-implementation comparison boundary.
Regression-oracle scope
The principal reason to preserve this implementation is its causality-filtering Delaunay construction path in include/Foliated_triangulation.hpp. find_invalid_timevalue_cells classifies cells from stored vertex time labels, has_valid_timevalues provides the predicate, find_bad_vertex selects a vertex responsible for an acausal local configuration, and fix_timevalues removes offending vertices through CGAL so the cavity is retriangulated until the foliation contract is satisfied.
The deterministic doctest scenario "Detecting and fixing problems with vertices and cells" in tests/Foliated_triangulation_test.cpp exercises this path with fixed points and time labels. Its inputs, detected bad vertex, final initialization state, cell counts, and causal classification are the first comparison fixture for causal-triangulations; exact Monte Carlo trajectories are not required to match.
The versioned, language-neutral fixtures, canonical C++ results, run manifests, raw outputs, and Rust consumption rules are published in the reference/ package.
After building, run that fixture directly with:
Usage
The supported build produces cdt and initialize in out/build/reference/src. Run the primary simulation through Just and pass its arguments after the recipe name:
For troubleshooting, the equivalent direct command is ./out/build/reference/src/cdt --help.
Use --no-output for batch, debugging, or scripted runs that should print results without writing checkpoint or final triangulation files:
With output enabled, every generated .off triangulation is accompanied by a .off.meta provenance manifest containing the effective seed, configuration, version/toolchain identity, transition-trace fingerprint, and payload checksum. Checkpoint files are validated snapshots, not resumable simulation states; see docs/reproducibility.md for the replay and persistence contract. Same-seed generation replays the random inputs, while exact transition replay requires an identical starting manifold; CDT++ does not alter its spherical construction to force CGAL to reproduce one of several valid cospherical tetrahedralizations.
- cdt-viewer is an opt-in macOS archival target. Build it with just viewer-build, regenerate the tracked hero image with just viewer-render, and see the viewer contract for its narrower support boundary.
- initialize is also used by the dependency-free local parameter sweep described under offline comparison.
See the command-line reference for every option. Build and dependency instructions begin at Quickstart.
Roadmap
- Cross-platform support on Linux, macOS (x64 & arm64), and Windows
- Cross-compiler support on gcc, clang, and MSVC
- Develop with literate programming using Doxygen
- Test using CTest
- Continuous integration by GitHub Actions on the leading edge
- 3D Simplex
- 3D Spherical triangulation
- 2+1 foliation
- S3 Bulk action
- 3D Ergodic moves
- High-quality Random Number Generation with M.E. O'Neill's PCG library
- Restore optional parallel triangulation with [TBB] (#74)
- Automated code analysis with CodeQL
- Build/debug with Visual Studio 2022
- Use {fmt} library (instead of iostream)
- 3D Metropolis algorithm
- Multithreaded logging with spdlog
- Restore optional visualization with [Qt] (#98)
- Initialize two masses
- The shortest path algorithm
- Einstein tensor
- Complete test coverage
- Complete documentation
- Quantize Spacetime!
Quickstart
From a fresh checkout, the primary supported headless build, dependency bootstrap, and test path is:
The build recipe uses the Release configuration and the pkgx launcher on Unix when pkgx is available, then delegates to scripts/build.sh on Unix or scripts/build.bat on Windows. Its first run creates an ignored .cache/vcpkg checkout at the exact builtin-baseline recorded in vcpkg.json, bootstraps vcpkg, installs the manifest dependencies, builds in out/build/reference, and runs the supported CTest smoke suite. The first dependency build can take several minutes; subsequent runs reuse both vcpkg dependencies and CMake/Ninja outputs, so an unchanged build is a no-op apart from configuration and tests.
For a production build with CDT++ assertions enabled, use the focused Debug workflow:
The Debug build preset compiles the cdt and initialize production targets, then the debug-cli test preset runs the 21 Debug-compatible CTest entries labeled integration. It defines CGAL_NDEBUG because supported move paths deliberately traverse invalid intermediate triangulations, while leaving CDT++'s own assertions enabled. The cdt and cdt-no-output simulation tests and the doctest unit suite are excluded because those paths trip project invariant assertions on the intermediate state. Release remains the canonical complete test configuration.
On Unix, compiler caching is optional. The pkgx launcher supplies the repository-pinned ccache binary when CDT_COMPILER_CACHE=ccache; leaving the variable unset or setting it to off preserves the uncached build:
Compiler caching covers project compilation; vcpkg binary caching remains responsible for reusing compiled third-party packages.
The optional pkgx entry point supplies the complete Unix developer-tool environment ephemerally and invokes the same build contract directly:
To expose the same dependency-build tools to an interactive shell, source the reusable environment script:
In CLion, open Settings | Build, Execution, Deployment | Toolchains, select the local toolchain, choose Add environment | From file, and select scripts/pkgx-env.sh. The script supplies the pkgx tool environment and points VCPKG_ROOT at the repository-owned .cache/vcpkg checkout while keeping CGAL and the other project libraries under vcpkg control.
pkgx does not install CGAL or any other project library; those remain owned by the pinned vcpkg manifest. The underlying ./scripts/build.sh and scripts\build.bat entry points remain available for troubleshooting and native Windows development.
Current reference-suite status
With the pinned baseline, the reference configuration and build succeed on macOS with AppleClang. The cross-platform just build command runs all 131 CTest registrations through scripts/build.sh on Unix and scripts/build.bat on Windows: 106 doctest scenarios, 23 CLI integration tests, one compiled C++ API example, and one arithmetic-backend correctness test. The same reference-smoke preset is the supported local and CI contract; there are no overlapping focused registrations that can pass while omitting another doctest suite. The current parallel preset also registers 129 tests: 103 ordinary doctest scenarios, one parallel launcher containing five scenarios, the same 23 CLI integration tests, the C++ API example, and the arithmetic correctness test. The parallel-enabled AddressSanitizer configuration exercises the same replayable stress contract.
Setup
This project uses CMake+Ninja to build C++23 sources and vcpkg manifest mode to manage C++ libraries. macOS with AppleClang is the primary v1.0.0-rc3 validation target; the remaining compiler and platform matrix will be recorded as it is verified.
Prerequisites
The smallest pkgx-assisted host setup is:
- Xcode Command Line Tools on macOS, or a C++23 compiler and base build environment on Linux
- pkgx
- Just, used by the recipes and scripts/pkgx-build.sh to resolve the repository's tool-version pins
- Python 3.14 for native dependency bootstrap, and uv when checking or running the Python support scripts
- Doxygen 1.16.1 and Graphviz 15.1.0 when checking or generating API documentation; pkgx can supply both
The pkgx build and documentation launchers supply their required tools ephemerally, including Git, Bash, CMake, Ninja, Python, Doxygen, Graphviz, M4, Autoconf, Autoconf Archive, Automake, GNU Libtool, Texinfo, and pkg-config. If pkgx is not installed, provide these tools conventionally through a package manager such as Homebrew or apt:
- Git
- Bash
- build-essential (Linux only)
- m4
- automake
- autoconf
- autoconf-archive
- libtool (macOS) or libtool-bin (Linux)
- pkg-config
- texinfo
- ninja (macOS) or ninja-build (Linux)
The build does not require a pre-existing personal vcpkg checkout, a fork, a submodule, Docker, or a hosted development environment.
Developer workflow
The repository-root Justfile provides the same small command vocabulary used by the related projects:
check covers repository-wide C++ formatting, Python formatting/lint/type checks, spelling, release metadata and citation fields, YAML, GitHub Actions syntax and security, whitespace, and CMake preset parsing. ci adds the pinact policy check and the supported build/test contract. Documentation validation remains available separately through just docs-check. The GitHub Actions Ubuntu GCC, Ubuntu Clang, macOS AppleClang, and Windows MSVC jobs all run just ci; the two Ubuntu jobs also run just build-parallel. The Ubuntu compiler jobs use the pinned pkgx ccache package with a compiler-specific persistent cache. Sanitizer builds use Release semantics with sanitizer-provided -O1 -g flags, while coverage uses Release semantics with coverage-provided -O0 -g flags; no duplicate full-suite Debug job is needed. Windows continues to compile with native MSVC; the locked Python environment supplies clang-format only as a source formatter. Install the developer tools with Homebrew, use equivalent system packages, or let pkgx supply the Unix environment ephemerally; pkgx remains optional. For example:
All configure paths require CMake 4.4.0 or newer. The Justfile owns the tested 4.4.1 toolchain pin: pkgx-backed recipes remain reproducible at that version, while direct configure paths accept newer compatible CMake releases. CI is pkgx-first; because pkgx does not currently publish its CMake and Ninja packages for Windows, that job uses the exact Justfile pins available as PyPI wheels through uv tool install --no-build.
pinact uses .pinact.yaml to retain immutable action SHAs, readable release comments, and a seven-day release cooldown. just update-actions uses an installed pinact, Go, or a pkgx-provided Go fallback, then requires yamllint, actionlint, and zizmor to pass. Direct third-party Python dependencies install only from locked wheels. The uv environment provides clang-format and yamllint; actionlint uses its pinned upstream version, and zizmor uses its pinned PyPI wheel through uvx.
vcpkg maintenance
vcpkg.json is the dependency source of truth. Its builtin-baseline pins the official microsoft/vcpkg registry commit used locally and in CI. The repository-local .cache/vcpkg checkout is disposable tool/cache infrastructure and must not be edited or committed. The native build entry points delegate checkout provenance, baseline, and executable-integrity validation directly to scripts/bootstrap_vcpkg.py, whose cross-platform fixtures run under just check.
To update dependencies intentionally, bootstrap the current checkout, run the vcpkg baseline updater, synchronize the independently reviewed tool pins, review both diffs, and then rerun the complete build:
just sync-vcpkg-tool-pins reads the new manifest baseline, fetches that exact upstream commit's tool metadata, downloads the official Windows amd64 and arm64 release assets, and atomically updates the release and SHA-256 pins in scripts/bootstrap_vcpkg.py. It leaves the existing pins unchanged if any input cannot be fetched or validated, and only writes when the rendered release and hash assignments differ from the bootstrap source.
On Windows, invoke the synchronizer with python.exe scripts\sync_vcpkg_tool_pins.py; scripts\build.bat and scripts\fast-build.bat already invoke the bootstrap implementation directly.
CI uses the repository's cached-vcpkg action, which derives the vcpkg checkout commit from the same manifest baseline, stores compiler-specific binary archives through actions/cache, and separately caches downloaded source archives. No separately maintained checkout SHA is required; the bootstrap script retains an independent tool release and Windows executable hashes as a supply-chain review gate.
CodeQL keeps third-party implementation findings out of CDT++ results through a two-phase manual build. just codeql-prepare configures the project, installs manifest dependencies before CodeQL starts tracing, and uses a build directory under the host temporary directory so installed headers are outside the checkout. After CodeQL initialization, just codeql-build compiles only the cdt and initialize production targets with tests disabled. The regular just build and just ci contracts continue to build and run the complete test suite.
Build
Run just build from the repository root. It delegates to ./scripts/build.sh on Unix and scripts\build.bat on Windows; either platform-specific script can itself be run from any working directory for troubleshooting. If VCPKG_ROOT already names the clean official checkout at the manifest baseline, the script respects it; otherwise it uses the pinned disposable checkout described above. Both scripts invoke the reference configure and build presets followed by the reference-smoke test preset; products and tests are isolated under out/build/reference, while scripts\fast-build.bat configures the same reference tree and builds only the primary cdt target. All entry points preserve a compatible CMake cache and refresh it only when the selected vcpkg toolchain path changes. Direct script invocations must expose CMake 4.4.0 or newer on PATH; the canonical pkgx-backed just recipes select the tested 4.4.1 toolchain automatically.
The archival Qt viewer is deliberately outside that cross-platform headless contract. On macOS, just viewer-build selects the separate viewer preset and vcpkg feature, builds cdt-viewer under out/build/viewer, and runs its noninteractive image smoke test. Qt and Eigen are installed only in that build tree. See docs/viewer.md for regeneration, version pins, and portability rules.
Project Layout
The project is similar to PitchFork Layout, as follows:
- .github - GitHub specific settings
- out/build/reference - Ephemeral supported headless build directory
- cmake - Cmake configurations
- docs - Documentation
- external - Includes submodules of external projects (none so far, all using vcpkg)
- include - Header files
- scripts - Build, test, and run scripts
- src - Source files
- tests - Unit tests
- viewer - Versioned archival render fixtures, manifests, and schemas
Command-line reference
CDT-plusplus uses program_options to parse options from the help message, and so understands long or short argument formats, provided the short argument given is an unambiguous match to a longer one. The help message should be instructive:
--threads is a maximum concurrency limit for CGAL/oneTBB bulk Delaunay operations. It defaults to 1. Zero and negative values are rejected. The canonical reference build accepts only 1; values greater than 1 require the parallel preset. This option does not parallelize Metropolis-Hastings, Pachner moves, persistence, or concurrent access to one manifold.
The dimensionality of the spacetime is such that each slice of spacetime is d-1-dimensional, so setting d=3 generates two spacelike dimensions and one timelike dimension, with a defined global time foliation. A d-dimensional simplex will have some d-1 sub-simplices that are purely spacelike (all on the same timeslice) as well as some that are timelike (span two timeslices). In CDT we actually care more about the timelike links (in 2+1 spacetime), and the timelike faces (in 3+1 spacetime).
Documentation
Online documentation is at https://adamgetchell.org/CDT-plusplus/.
The compiled C++ API quickstart is the canonical end-to-end public API example and is embedded verbatim in the generated site.
The scientific transition, proposal-ratio, geometry-delta, counter, and precision contracts are recorded in docs/metropolis-hastings.md. The cross-language schema, exact-versus-numerical comparison policy, and raw archival records are documented in reference/README.md. The literature-backed contracts, exact deltas, inverse relationships, and failure-atomicity rules for the complete 2+1D move set are recorded in docs/ergodic-moves.md. Seed replay, PCG stream ownership, checkpoint metadata, and the parallel stream policy are recorded in docs/reproducibility.md. The repository-wide scientific bibliography is maintained in REFERENCES.md.
Validate the generated API documentation without modifying the worktree:
To generate the same publishable output used by the documentation workflow, run just docs; it writes docs/html/ only after strict generation and generated-site validation succeed. Both recipes require Doxygen 1.16.1 and Graphviz 15.1.0 and use pkgx ephemerally when matching local tools are unavailable. Doxygen 1.16.1 is the archival pin because 1.17.0 duplicates linked labels, emits broken alphabetical-index fragments for this repository, and injects an unused Mermaid CDN dependency. scripts/validate_generated_site.py preserves that bounded workaround by checking the actual HTML, local links and fragments, duplicate IDs and link labels, and required assets. USE_MATHJAX allows MathJax to render LaTeX formulae, and HAVE_DOT enables GraphViz diagrams. Documentation validation is intentionally separate from the cross-platform just ci contract. The documentation workflow runs just docs on Ubuntu and publishes its output to the gh-pages branch.
Citing CDT++
If CDT++ contributes to published work, cite the software using CITATION.cff and cite the scientific methods relevant to the work from REFERENCES.md. The software citation records the current declared release, 1.0.0-rc3. Advance its version and release date together with the CMake, vcpkg, Python-tooling, Doxygen, and CLI metadata for subsequent releases.
Testing
Run just build; it selects scripts/build.sh on Unix or scripts\build.bat on Windows, builds the test target, and executes all 131 CTest entries: 106 doctest scenarios, 23 executable integration tests covering normal CLI use and invalid-boundary rejection, one compiled C++ API example, and one arithmetic-backend correctness test labeled scientific. The parallel-enabled AddressSanitizer and parallel configurations register 103 ordinary doctest scenarios, one launcher containing five scenarios labeled unit, parallel, and configuration, the same 23 integration tests, the C++ API example, and the arithmetic test, for 129 CTest entries. Every process-level test is labeled integration, and invalid-input tests also carry the cli-boundary subcategory. Run just ci for the complete local validation gate.
just check also runs the repository-owned Semgrep policy and its annotated fixtures. Use just semgrep-test while changing the rules and just semgrep to scan the real source tree for false positives.
The doctest executable can also be run directly:
To rerun the complete suite without rebuilding:
To run a specific test category, use:
In addition to the command line output, you can see detailed results in the out/build/reference/Testing directory generated by CTest.
Coverage
Coverage reporting is supported on Linux with GNU GCC and its matching gcov, CMake, Ninja, LCOV 2.5 or newer, and genhtml. Distribution packages may provide an older LCOV that cannot parse coverage from current GCC releases; use the upstream LCOV release when necessary. Generate the same reports used by Codecov with:
The command uses an isolated build/coverage CMake tree and writes the filtered LCOV tracefile to build/coverage.info and the browsable report to build/coverage-html/index.html. Only project-owned include/ and src/ paths are retained, consistently excluding tests, generated files, system headers, and vcpkg dependencies. Reports include line and branch coverage; function coverage is disabled because GCC can emit inconsistent function and line records for generated lambda bodies. The raw LCOV capture temporarily retains function records because LCOV 2.5 requires them while filtering GCC 16 data; the project-only extraction removes them from both published reports. If coverage collection fails, verify that g++ -dumpfullversion -dumpversion and gcov --version report the same major version.
GCC 16 also emits three known line-hit/branch-unhit records for templated assignments in Utilities.hpp. The coverage recipe keeps LCOV's warnings visible and requires that exact count during extraction and report generation; new or removed inconsistencies therefore fail the command for review.
The Codecov workflow runs this recipe, uploads only build/coverage.info with OIDC, and preserves both reports as a 14-day GitHub Actions artifact for local diagnosis. If report generation fails, the workflow also preserves the gcov inputs and CTest diagnostics for seven days. It does not rely on Codecov's automatic gcov discovery. Codecov retains the LCOV branch detail but counts an executed line with an uncovered branch as a line hit, keeping its project percentage comparable to LCOV's line rate; use the LCOV artifact for the separate branch-coverage rate.
Static Analysis
Python 3.14 is selected by .python-version, uv locks the environment in uv.lock, Ruff owns Python formatting and linting, and ty owns static type checking. Run just python-sync once and then use just python-check or just python-fix; both commands are also part of the repository-wide validation recipes.
This project follows the CppCore Guidelines as enforced by ClangTidy. The repository pins LLVM 22; run Clang-Tidy through its Just recipe:
(Or use your favorite linter plugin for your editor/IDE.)
Sanitizers
AddressSanitizer + UndefinedBehaviorSanitizer, LeakSanitizer, MemorySanitizer, and ThreadSanitizer share the repository-owned Linux driver and CMake presets. Run one locally with just sanitize asan, just sanitize lsan, just sanitize msan, or just sanitize tsan; the GitHub Actions workflows invoke the same commands. MemorySanitizer remains experimental because third-party dependencies are not instrumented. AddressSanitizer enables the optional CGAL/TBB path and its parallel contract; ThreadSanitizer exercises the default sequential configuration.
Offline Comparison
The cdt-compare command launches explicit CDT++ and causal-triangulations commands without a shell. Both receive copied versions of the #94 protocol, result schema, and reference manifest. The harness retains exact stdout, stderr, exit status, executable digest, command, working directory, process time, and host provenance. It first anchors the live C++ output to #94's committed canonical result, then compares exact fields and named tolerance-based fields with Rust. Any live C++ transition observations are independently anchored to the committed #94 protocol before becoming the Rust reference. It classifies implementation-specific and unsupported fields without interpreting either implementation as ground truth.
After building CDT++ and a compatible Rust fixture producer, run one bounded comparison and retain it locally:
Reproduce summary.json entirely from the stored raw artifacts, without running either executable:
The bundle under out/comparisons/run-1 is canonical and is published atomically only after analysis and manifest creation finish. Preserve its inputs/, raw/, manifest.json, and summary.json together. Python validates the complete artifact inventory and its digests, validates schemas, constructs commands, classifies comparisons, and renders a small text table; it does not implement topology, action, move-legality, or acceptance rules. See the comparison-harness contract for producer configuration, placeholders, artifact layout, failure records, and the C++ reference/Rust result boundary.
The retained cdt-optimize-initialize command is also entirely local and dependency-free. It writes one directory per parameter pair under out/experiments/initialize, including configuration JSON, raw stdout, a tab-separated volume profile, metrics, artifact digests, and source/executable provenance. Each invocation requires a nonexistent output path. Seed 92 is the default; use --seed and --output-directory for another replayable record. Fresh CGAL triangulations remain subject to the reproducibility contract.
Visualization
The restored Qt-based cdt-viewer is an opt-in macOS archival renderer. Its tracked OFF fixture, render manifest, noninteractive smoke test, exact canonical-image policy, and inventory of historical visuals are documented in the viewer and visual-artifact contract. The default build remains headless and does not install Qt or Eigen.
Contributing
Please see CONTRIBUTING.md and our CODE_OF_CONDUCT.md.
Your code should pass Continuous Integration:
- just fix for safe automatic formatting with the repository's .clang-format
- just clang-tidy to analyze C++ with the pinned LLVM 22 toolchain
- just check for fast, non-mutating source, documentation, YAML, workflow, and CMake validation
- just ci for the supported build and complete validation contract before pushing
The slower sanitizer workflows remain available through GitHub Actions and repository commands when relevant to a change:
Valgrind is intentionally unsupported: on x86/AMD64 its floating-point emulation does not honor the directed rounding required by CGAL's interval predicates. Disabling CGAL's rounding check would make geometric results untrustworthy, so memory diagnostics use the supported sanitizer workflows instead.
Optional:
- ClangTidy on all changed files
Issues
Current work and known limitations are tracked in the CDT++ GitHub issue tracker. The README does not duplicate a hardcoded issue list because tracker state changes independently of repository releases.
Generated by
1.16.1