This repo contains a refactoring of the BITSCAN and GRAPH libraries for efficient operations with bitsets and graphs in modern C++. The BITSCAN library is devoted to bitset manipulation. The GRAPH library is dedicated to efficient graph operations and uses BITSCAN to represent graphs in memory. The repo contains additional utilities (library UTILS) and many tests and examples.
The C++ BITSCAN and GRAPH libraries result from more than 20 years of research in combinatorial optimization. They are at the core of many exact state-of-the-art algorithms for hard combinatorial problems and their applications, such as:
-
CliSAT: A new exact algorithm for hard maximum clique problems, 2023.
-
A new branch-and-filter exact algorithm for binary constraint satisfaction problems, 2022.
-
A new combinatorial branch-and-bound algorithm for the Knapsack Problem with Conflicts, 2021.
-
A branch-and-cut algorithm for the Edge Interdiction Clique Problem, 2021.
-
A new branch-and-bound algorithm for the maximum edge-weighted clique problem, 2019.
-
A new branch-and-bound algorithm for the Maximum Weighted Clique Problem, 2019.
-
Efficiently enumerating all maximal cliques with bit-parallelism, 2018.
-
A new exact maximum clique algorithm for large and massive sparse graphs, 2016.
-
A novel clique formulation for the visual feature matching problem,2015.
-
A new DSATUR-based algorithm for exact vertex coloring, 2012.
-
An exact bit-parallel algorithm for the maximum clique problem, 2011.
and many others.
The repository has been tested on Linux (24.x.x) and Windows 10 OS.
The latest release, v1.4.2 (March 2026), remains compatible with C++14.
This research has been partially funded by the Spanish Ministry of Economy and Competitiveness (MINECO), national grants DPI 2010-21247-C02-01, DPI 2014-53525-C3-1-R and DPI2017-86915-C3-3-R.