A set of integers is a string of bits. A graph is a table of such sets. BitGraph is a C++ library that turns neighbourhood intersections, overlap tests and candidate counting into a handful of machine-word operations.
Row v of the adjacency matrix is a bitset holding the neighbours of v. Common neighbours, induced subgraphs and candidate filtering reduce to AND, OR and AND NOT, touching 64 vertices per word.
Forward and reverse, destructive or not, through small scanner objects or independent views that each carry their own cursor.
bitarray and ugraph store every block. sparse_bitarray and sparse_ugraph store only non-empty ones, so huge, sparse graphs stay small.
Vertex- and edge-weighted graphs, with DIMACS, Matrix Market and edge-list readers and writers and automatic format detection.
Degree and degeneracy orderings, reversible vertex relabelling, classic graphs and uniform random graphs.
Click bits to edit the two neighbourhoods. The result is a single bitwise operation, exactly what g.neighbors(u) &= g.neighbors(v) does on 64 vertices at a time.
Born from more than 20 years of research in exact algorithms for maximum clique, graph colouring and constraint satisfaction.
Algorithm code reads the same on a set and on a graph row.
#include "BitGraph/graph/graph.h" using namespace bitgraph; ugraph g(6); g.add_edge(0, 1); g.add_edge(0, 2); g.add_edge(0, 3); g.add_edge(1, 2); g.add_edge(1, 3); g.add_edge(3, 4); // common neighbours: one AND bitarray common = g.neighbors(0); common &= g.neighbors(1); bitarray::scan scan(common); for (int v = scan.next_bit(); v != BBObject::noBit; v = scan.next_bit()) std::cout << v << ' '; // 2 3
#include "BitGraph/bitscan/bitscan.h" using namespace bitgraph; // 10M elements, few set: stays small sparse_bitarray big(10000000); big.set_bit(0); big.set_bit(900000); big.set_bit(9999999); sparse_bitarray::scan scan(big); for (int b = scan.next_bit(); b != BBObject::noBit; b = scan.next_bit()) std::cout << b << ' '; // 0 900000 9999999
Measured on a Xeon Gold 6342, GCC 13 -O3, 100,000-bit sets. Dense bitsets match std::bitset on bulk operations; scanning and sparse storage are where BitGraph wins.
&= vs std::bitset at 1% occupancycount() vs std::bitset at 1%_Find_nextGRAPH has no direct counterpart library, so no speedup is claimed for it; its speed comes from the BITSCAN operations on adjacency rows. Full tables, method and caveats: benchmarks.
Two small, header-only projects that show the library in real algorithms. Both build on BitGraph v2.0.0 and use CMake.
Computes the coreness of every vertex in O(|E|) with the Batagelj-Zaversnik bin-sort algorithm, plus degeneracy orderings and greedy clique heuristics.
psanse/seq_coloringSEQ and ISEQ vertex coloring heuristics on bitset rows. ISEQ is the upper bound used in exact maximum clique algorithms such as CliSAT.
CMake 3.14+ and a C++14 compiler.
git clone https://github.com/psanse/BitGraph.git cd BitGraph cmake -S . -B build -DCMAKE_BUILD_TYPE=Release cmake --build build cmake --install build
# your CMakeLists.txt
find_package(BitGraph CONFIG REQUIRED)
target_link_libraries(my_app PRIVATE
BitGraph::graph BitGraph::bitscan BitGraph::utils)
| Toolchain | Status |
|---|---|
| GCC 13.3, Ubuntu 24.04 | build, tests, examples, installed-package check pass |
| MSVC 19.5 (VS 2026), Windows | build, tests, examples, installed-package check pass |
v2.0.0 (October 2026) is not source-compatible with 1.x. See the changelog and migration table.
BITSCAN and GRAPH sit at the core of many exact algorithms.
A new exact algorithm for hard maximum clique problems, 2023
Clique-based robust point cloud registration, 2025
Exact maximum clique for large sparse graphs, 2016
The 2011 paper where BITSCAN originated
More in the README. To cite BitGraph, see CITATION.cff.