Dynamic Programming on Chain Graphs

Implementation of dynamic programming on chain graphs on an arbitrary semiring using C++23.

Check out the following Medium stories to know more about this project:

• Dynamic Programming on Chain Graphs. Part 1: The Problem;
• Dynamic Programming on Chain Graphs. Part 2: The Solution;
• Dynamic Programming on Chain Graphs. Part 3: Preparing for Implementation;
• Dynamic Programming on Chain Graphs. Part 4: The Implementation.
• Dynamic Programming on Chain Graphs. Part 5: Testing.

A writing about the binocular stereo vision example:

• Scanline Stereo Vision.

Build Requirements

The project contains a Dockerfile with all needed dependencies included. You can build it in Linux terminal by executing the following command from the root directory of this project:

docker build -t ubuntu-clang:18 .

It is based on Ubuntu 24.04 LTS. Below is the explanation of the contents of the Docker image.

The project requires a compiler and a standard library compatible with some C++20 and C++23 features, including but not limited to the following:

• C++20 modules;
• deducing this;
• multidimensional operator[];
• std::mdspan.

As of April 2024, it is clang 18 and libc++ 18. Also, it needs a compatible build system: CMake 3.28 or newer and Ninja 1.10 or newer.

Building the Project

Shell

You can set up the project using

cmake \
  -S . \
  -B build \
  -G Ninja \
  -DCMAKE_BUILD_TYPE=Release \
  -DCMAKE_CXX_COMPILER=clang++-18 \
  -DCMAKE_CXX_FLAGS='-stdlib=libc++ -Wall -Wextra -pedantic'

Then, build it with

cmake --build build

You may see warnings about assume attribute not being supported, which is okay at the moment. Let us wait for Clang 19 to be included in an Ubuntu repository.

Docker

To set up and build the project in Docker container, I recommend you using your current user id and directory to avoid root-owned files and keep you absolute paths right:

docker run --rm -u ${UID}:${UID} -v $(pwd):$(pwd) ubuntu-clang:18 bash -c " \
  cd $(pwd) && \
  cmake \
    -S . \
    -B build \
    -G Ninja \
    -DCMAKE_BUILD_TYPE=Release \
    -DCMAKE_CXX_COMPILER=clang++-18 \
    -DCMAKE_CXX_FLAGS='-stdlib=libc++ -Wall -Wextra -pedantic' && \
  cmake --build build \
"

IDE

Those using JetBrains CLion can set up a Docker toolchain by specifying:

• CMake: Docker CMake;
• Build Tool: /usr/bin/ninja;
• C Compiler: clang-18;
• C++ Compiler clang++-18;
• Debugger: lldb-18.

Running Tests

The project uses doctest — a lightweight testing framework compatible with C++23.

Configure the project

cmake \
  -S . \
  -B build \
  -G Ninja \
  -DCMAKE_BUILD_TYPE=Release \
  -DCMAKE_CXX_COMPILER=clang++-18 \
  -DCMAKE_CXX_FLAGS='-stdlib=libc++ -Wall -Wextra -pedantic'

Build tests

cmake --build build --target tests

Run the tests

./build/tests/tests

You can do this in Docker container:

docker run --rm -u ${UID}:${UID} -v $(pwd):$(pwd) ubuntu-clang:18 bash -c " \
  cd $(pwd) && \
  cmake \
    -S . \
    -B build \
    -G Ninja \
    -DCMAKE_BUILD_TYPE=Release \
    -DCMAKE_CXX_COMPILER=clang++-18 \
    -DCMAKE_CXX_FLAGS='-stdlib=libc++ -Wall -Wextra -pedantic' && \
  cmake --build build --target tests && \
  build/tests/tests \
"

Using the Project

Configure the project

cmake \
  -S . \
  -B build \
  -G Ninja \
  -DCMAKE_BUILD_TYPE=Release \
  -DCMAKE_CXX_COMPILER=clang++-18 \
  -DCMAKE_CXX_FLAGS='-stdlib=libc++ -Wall -Wextra -pedantic'

Scanline Stereo Vision Example

You can get the example inputs from the Middlebury Stereo Datasets.

Build the example

cmake --build build --target scanline_stereo_vision

Run the example using view0.png as the left image and view1.png as the right image. Use the maximum disparity 50 and smoothness weight 25. Compute the disparity map using the "compact" algorithm and write the resulting disparity map into out.png.

./build/examples/scanline_stereo_vision view0.png view1.png out.png 50 25 compact

You can do this in Docker container:

docker run --rm -u ${UID}:${UID} -v $(pwd):$(pwd) ubuntu-clang:18 bash -c " \
  cd $(pwd) && \
  cmake \
    -S . \
    -B build \
    -G Ninja \
    -DCMAKE_BUILD_TYPE=Release \
    -DCMAKE_CXX_COMPILER=clang++-18 \
    -DCMAKE_CXX_FLAGS='-stdlib=libc++ -Wall -Wextra -pedantic' && \
  cmake --build build --target scanline_stereo_vision && \
  build/examples/scanline_stereo_vision view0.png view1.png out.png 50 25 compact \
"

Licensing

This project includes the CImg library. It is provided "as is" under the CeCILL license. You can find more information about the CImg library and its licensing terms in the third_party/CImg directory. Please refer to the third_party/CImg/Licence_CeCILL_V2-en.txt for the full license text.

The other project parts (the files outside the third_party directory) are licensed under the MIT license, so you can freely use the source code in pet projects, commercial projects, and home assignments. You can also modify it, distribute it, and sell it. Note that the project is provided "as is," so the author is not responsible for your usage of it. See the LICENSE file for more details.