An "adjacency slice" graph library along with implementations of a few path coloring algorithms for plane graphs.

The header-only graph library is contained in the include directory. The majority of the library depends only on a couple files from the simple libaven header-only library, which is vendored in the deps directory.

The */geometry.h files define functions to construct vector geometry for graph visualization and depend on the headers from libavengl. The libavengl library draws 2D vector graphics using the OpenGL ES 2.0 API. The provided visualization uses GLFW for window creation. The GLFW and libavengl libraries and the headers for X11, xkbcommon, and Wayland are vendored in deps.

The visualization should build with no system dependencies other than a C compiler on most modern Windows or Linux systems.

To build the build system:

make

or

cc -o build build.c

where cc is your favorite C compiler that supports C99 or later ¹.

To build the algorithm visualization run:

./build

The resulting executables will be in the build_out directory.

For a release build using clang or gcc run:

  ./build -ccflags "-O3 -ffast-math" -glfw-ccflags "-O3 -DNDEBUG"

To build and run the visualization in "watch mode" you may run:

  ./build watch

The build system will watch for changes to files in visualization/. If a file in visualization/game/ is modified, then the changes will be compiled into a dynamic library and hot loaded into the running application. If a file in the root of visualization/ is changed, then the application will close, compile, and run.

A couple rudimentary programs were written to find and draw algorithm examples as a series of Tikz drawings. To build these exectuables, run:

./build tikz

To build and run the algorithm benchmarks you will need ~13GB of unused available system RAM and a C compiler that supports C11 atomics. An example run command with gcc or clang on Linux would be:

./build bench -ccflags "-std=c11 -O3 -march=native"

The benchmarks may take up to a few hours to complete.

Here are the latest results from my Linux system with x86_64 Intel N100 processor, compiled using Clang 19.1.7:

Threaded results for p3color :

Threaded results for p3choose :

Pyramid graph p3color scaling comparison:

To clean all build artifacts:

./build clean

The visualization compiled with Emscripten is available online.

The copyright Aven Bross 2024 and the license provided in LICENSE.MIT apply to each text file that does not contain its own separate license and copyright.