CDT-plusplus

Quantize spacetime on your laptop.

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, TBB, and Eigen. Arbitrary-precision numbers and functions are by MPFR and GMP. Docopt provides a beautiful command-line interface. Melissa E. O'Neill's Permuted Congruential Generators library provides high-quality RNGs that pass L'Ecuyer's TestU01 statistical tests. Catch provides BDD/TDD. vcpkg provides library management and building. Doxygen provides automated document generation. {fmt} provides a safe and fast alternative to iostream. spdlog provides fast, multithreaded logging. PVS-Studio and LGTM provide commercial-grade static analysis and security checks. CometML provides machine learning for model building.

Goals

• Cross-platform support on Linux, macOS (x64 & arm64), and Windows
• Cross-compiler support on gcc, clang, and MSVC
• Develop with literate programming using Doxygen
• Efficient Pure Functional Programming in C++ Using Move Semantics
• Test using CTest
• Develop using Behavior-driven development (BDD) with Catch
• Continuous integration by Travis-CI on macOS and Linux with gcc/Clang
• Continuous integration by AppVeyor on Windows with MSVC
• Continuous integration by Github Actions on the leading edge
• 3D Simplex
• 3D Spherical triangulation
• 2+1 foliation
• Integrate Docopt CLI
• S3 Bulk action
• 3D Ergodic moves
• High-quality Random Number Generation with M.E. O'Neill's PCG library
• Multithreading via TBB
• Automated code analysis with LGTM
• Build/debug with Visual Studio 2019
• Use {fmt} library (instead of iostream)
• Static code analysis with PVS-Studio
• 3D Metropolis algorithm
• Multithreaded logging with spdlog
• Output via HDF5
• A Surface mesh manifold of 3D Triangulation
• 4D Simplex
• 4D Spherical triangulation
• 3+1 foliation
• S4 Bulk action
• 4D Ergodic moves
• Initialize two masses
• The shortest path algorithm
• Einstein tensor
• Complete test coverage
• Complete documentation
• Quantize Spacetime!

Quickstart

Setup

This project uses CMake+Ninja to build and vcpkg to manage C++ libraries. Using C++20 features, it successfully builds with AppleClang, gcc-10, clang-10, and Visual Studio 2019.

Short

If you use Docker:

docker pull acgetchell/cdt-plusplus
docker run -it --name cdt cdt-plusplus

Binaries will be in /CDT-plusplus/build/src. Proceed to Use.

Long

On macOS or Linux, you will first need to install some prerequisites using your favorite package manager (e.g. homebrew or apt):

• build-essential (Linux only)
• automake
• autoconf
• autoconf-archive
• libtool (macOS) or libtool-bin (Linux)
• pkg-config
• texinfo
• yasm
• ninja (macOS) or ninja-build (Linux)

Next, install vcpkg:

git clone https://github.com/Microsoft/vcpkg.git
cd vcpkg
./bootstrap-vcpkg.sh -useSystemBinaries
./vcpkg integrate install

vcpkg is then invoked by CMake in vcpkg manifest mode and install the project dependencies listed in vcpkg.json into a local vcpkg_installed directory.

Build

Clone the repo:

git clone https://github.com/acgetchell/CDT-plusplus.git

To get CMake and the build scripts to run correctly, you'll need to set $VCPKG_ROOT to wherever you cloned vcpkg, e.g.

export VCPKG_ROOT="$HOME/vcpkg"

This will set the CMAKE_TOOLCHAIN_FILE option for CMake.

You can optionally pre-build the project dependencies (100+ packages) by running at the top level of the project:

vcpkg install --feature-flags=manifests

Project Layout

The project is similar to PitchFork Layout, as follows:

• .github - GitHub specific settings
• build - Ephemeral out-of-source 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

Run

If you want to get started right away, run fast-build.sh or fast-build.bat, depending on your operating system, from scripts. This will compile the appropriate executables in RELEASE mode with no tests.

This should result in the main program executable, cdt in build/src or build\Debug, along with several others.

• cdt-opt is a simplified version with hard-coded inputs, mainly useful for debugging and scripting
• initialize is used by CometML to run parameter optimization

Use

CDT-plusplus uses Docopt 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:

./build/src/cdt --help
cdt started at 2021-08-08.20:18:58PDT
Causal Dynamical Triangulations in C++ using CGAL.

Copyright (c) 2014-2021 Adam Getchell

A program that generates d-dimensional triangulated spacetimes
with a defined causal structure and evolves them according
to the Metropolis algorithm. Specify the number of passes to control
how much evolution is desired. Each pass attempts a number of ergodic
moves equal to the number of simplices in the simulation.

Usage:./cdt (--spherical | --toroidal) -n SIMPLICES -t TIMESLICES [-d DIM]
            [--init INITIAL] [--foliate FOLIATION] -k K --alpha ALPHA
            --lambda LAMBDA [-p PASSES] [-c CHECKPOINT]

Examples:
./cdt --spherical -n 32000 -t 11 --alpha 0.6 -k 1.1 --lambda 0.1 --passes 1000
./cdt --s -n32000 -t11 -a.6 -k1.1 -l.1 -p1000

Options:
  -h --help                   Show this message
  --version                   Show program version
  -n SIMPLICES                Approximate number of simplices
  -t TIMESLICES               Number of timeslices
  -d DIM                      Dimensionality [default: 3]
  -i --init INITIAL           Initial radius [default: 1]
  --foliate FOLIATION         Foliation spacing between timeslices [default: 1]
  -a --alpha ALPHA            Negative squared geodesic length of 1-d
                              timelike edges
  -k K                        K = 1/(8*pi*G_newton)
  -l --lambda LAMBDA          K * Cosmological constant
  -p --passes PASSES          Number of passes [default: 100]
  -c --checkpoint CHECKPOINT  Checkpoint every n passes [default: 10]

The dimensionality of the spacetime is such that each slice of spacetime is d-1-dimensional, so setting d=3 generates 2 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).

Document

Online documentation is at https://adamgetchell.org/CDT-plusplus/ automatically generated by Travis-CI.

If you have Doxygen installed you can generate the same information locally using the configuration file in docs\Doxyfile by simply typing at the top level directory (Doxygen will recursively search):

doxygen ./docs/Doxyfile

This will generate a docs/html/ directory containing documentation generated from CDT++ source files. USE_MATHJAX has been enabled in Doxyfile so that the LaTeX formulae can be rendered in the html documentation using MathJax. HAVE_DOT is set to YES which allows various graphs to be autogenerated by Doxygen using GraphViz. If you do not have GraphViz installed, set this option to NO (along with UML_LOOK).

Test

In the scripts directory, run build.sh or build.bat depending on your operating system.

Unit tests run (in build/tests or build\tests\Debug) via CDT_test, the Catch executable:

./CDT_test

or (Windows):

CDT_test.exe

You can also run both CTest integration and Catch unit tests in the build directory with:

cmake --build . --target test

or (Windows):

ctest -C Debug

In addition to the command line output, you can see detailed results in the build/Testing directory which is generated thereby.

Deactivate Unit tests with -D ENABLE_TESTING:BOOL=FALSE, e.g. scripts/fast-build.sh.

Static Analysis

This project follows the CppCore Guidelines as enforced by ClangTidy, which you can install and then run using the clang-tidy.sh script:

sudo apt-get install clang-tidy
cd scripts
./clang-tidy.sh

(Or use your favorite linter plugin for your editor/IDE.)

The cppcheck.sh script runs a quick static analysis using cppcheck.

brew install cppcheck
cd scripts
./cppcheck-build.sh

Clang comes with scan-build which can run a much more thorough, but slower static analysis integrated with CMake and Ninja.

./scan.sh

Sanitizers

AddressSanitizer + UndefinedBehaviorSanitizer, LeakSanitizer, MemorySanitizer, and ThreadSanitizer are run with scripts/asan.sh, scripts/lsan.sh, scripts/msan.sh, and scripts/tsan.sh. They are also checked by Travis-CI during commits.

Optimize Parameters

CometML is used to record Experiments which conduct Model Optimization. The script to do this is optimize-initialize.py. In order for this to work, you must install the following into your Python virtual environment.

pip install tensorflow
pip install comet-ml

You can then run experiments and look at results on https://www.comet.ml!

Visualize

Currently, looking for a good visualization library. GeomView has been deprecated and the interface with CGAL is not maintained.

Contribute

Please see CONTRIBUTING.md and our CODE_OF_CONDUCT.md.

Your code should pass Continuous Integration:

• Whitespace formatting (git diff --check HEAD^)

• clang-format with project settings (.clang-format)

• cppcheck test with cppcheck.sh

• Valgrind be sure to look at the results to ensure you're not leaking memory

• AddressSanitizer and UndefinedBehaviorSanitizer; test with asan.sh

• LeakSanitizer (if supported by your platform); test with lsan.sh

• MemorySanitizer (if supported by your platform); test with msan.sh

• ThreadSanitizer test with tsan.sh

• LGTM check to ensure you haven't introduced a security vulnerability. Look at the query console for more details.

• Sonarcloud provides a lot of good suggestions.

Optional:

• ClangTidy on all changed files

• PVS-Studio using pvs-studio.sh if you have it installed

Issues