graph-v3

A modern C++20 graph library — header-only, descriptor-based, works with your containers.

---

Highlights

• Header-only — drop into any CMake project; no compiled components
• Works with your containers — std::vector<std::vector<int>> or std::map<int, std::vector<int>> are valid graphs out of the box
• 13 algorithms — Dijkstra, Bellman-Ford, BFS, DFS, topological sort, connected components, articulation points, biconnected components, MST, triangle counting, MIS, label propagation, Jaccard coefficient
• 7 lazy views — vertexlist, edgelist, incidence, neighbors, BFS, DFS, topological sort — all composable with range adaptors
• Customization Point Objects (CPOs) — adapt existing data structures without modifying them
• 3 containers, 26 trait combinations — dynamic_graph, compressed_graph, undirected_adjacency_list with mix-and-match vertex/edge storage
• 4261 tests passing — comprehensive Catch2 test suite

---

Quick Example — Dijkstra Shortest Paths

// (simplified — see examples/dijkstra_clrs_example.cpp for the full version)
#include "graph/graph.hpp"
#include "graph/algorithm/dijkstra_shortest_paths.hpp"
#include <vector>
#include <iostream>

int main() {
  // Weighted directed graph — edges are (target, weight) per vertex
  using G = std::vector<std::vector<std::pair<int,double>>>;
  G g{{{1, 10.0}, {2, 5.0}},   // vertex 0
      {{3, 1.0}},              // vertex 1
      {{1, 3.0}, {3, 9.0}},    // vertex 2
      {{4, 7.0}},              // vertex 3
      {}};                     // vertex 4

  std::vector<double>   distance(graph::num_vertices(g));
  std::vector<uint32_t> predecessor(graph::num_vertices(g));

  graph::dijkstra_shortest_paths(g, uint32_t(0), distance, predecessor);

  for (size_t v = 0; v < distance.size(); ++v)
    std::cout << "0 -> " << v << " : " << distance[v] << "\n";
}

---

Two Abstract Data Types

graph-v3 provides two peer abstractions — adjacency lists and edge lists — each first-class in the library.

ADT	Namespace	Primary Use
Adjacency list	graph::adj_list	Fast per-vertex edge traversal; required by most algorithms
Edge list	graph::edge_list	Compact edge-centric storage; ideal for Kruskal MST, bulk loading

Both share a common descriptor system and customization-point interface.

---

Feature Overview

Category	What's Included	Details
Algorithms	Dijkstra, Bellman-Ford, BFS, DFS, topological sort, connected components, articulation points, biconnected components, MST, triangle counting, MIS, label propagation, Jaccard	Algorithm reference
Views	vertexlist, edgelist, incidence, neighbors, BFS, DFS, topological sort	View reference
Containers	dynamic_graph (26 trait combos), compressed_graph (CSR), undirected_adjacency_list	Container reference
CPOs	19 customization point objects (vertices, edges, target_id, vertex_value, edge_value, …)	CPO reference
Concepts	9 graph concepts (edge, vertex, adjacency_list, …)	Concepts reference

---

Supported Compilers

Compiler	Version	Platform	Status
GCC	13 +	Linux	Tested
Clang	10 +	Linux, macOS	Tested
MSVC	2022 +	Windows	Tested

Requires CMake 3.20+ and a C++20-capable toolchain.

---

Installation

CMake FetchContent (recommended)

include(FetchContent)
FetchContent_Declare(
  graph3
  GIT_REPOSITORY https://github.com/pratzl/desc.git
  GIT_TAG        main
)
FetchContent_MakeAvailable(graph3)

target_link_libraries(your_target PRIVATE graph::graph3)

Manual / Subdirectory

add_subdirectory(path/to/graph-v3)
target_link_libraries(your_target PRIVATE graph::graph3)

System Install

cmake --preset linux-gcc-release
cmake --install build/linux-gcc-release --prefix /usr/local

Then in your project:

find_package(graph3 REQUIRED)
target_link_libraries(your_target PRIVATE graph::graph3)

---

How graph-v3 Compares to Boost.Graph

	graph-v3	Boost.Graph (BGL)
Language standard	C++20 (concepts, ranges)	C++98 / C++03
Property access	CPOs (vertex_value, edge_value)	Property maps
Graph types	Standard containers or library containers	Custom Boost types
Deployment	Header-only, single CMake target	Part of Boost (compiled components)

---

Documentation

The full documentation hub is at docs/index.md.

Quick links:

• Getting Started
• Migration from graph-v2
• FAQ
• Implementation Matrix
• Concepts Reference
• CPO Reference

---

Contributing

See CONTRIBUTING.md for build instructions, testing, code style, and PR guidelines.

---

License

Distributed under the Boost Software License 1.0.

---

Status: 4261 / 4261 tests passing · 13 algorithms · 7 views · 3 containers · 26 trait combinations · C++20 · BSL-1.0