Generic Graph Libraries in C++20
summary
Claims that the C++ Standard Library already supplies the primitives to write generic graph algorithms, using C++20 concepts and ranges and customization point objects, and shows line-for-line BFS and Dijkstra implementations that take a range-of-ranges graph interface. Provides concrete builders and adapters (including a nwgraph compressed-sparse-row implementation), runs the Kevin Bacon BFS example, and treats billion-vertex scale as a goal. A standards proposal p1709 r3d proposal exists in SG19; it is a working proof of concept, not yet standardized.
AI-written summary · about
chapters (16)
- 0:00Start
- 1:00Phil Ratzloff
- 9:57Review of Generic Programming and Graph Terminology
- 11:30Genetic Programming
- 14:19Are We Including Network Flow Algorithms and How Do You Decide Which Algorithms To Support
- 17:18Iterator
- 20:26Graph Terminology
- 23:18Traversal
- 29:03Breadth First Search
- 31:23Requirements
- 33:57Relaxation Step
- 40:00Compressed Sparse Storage
- 45:23Adapters and Construction
- 48:08Graph Construction
- 50:55Six Degrees of Kevin Bacon Example
- 53:59Bipartite Graphs
related talks
31mExtending CRuby with native Graph data type
01h 00mGraph Mastery to AI
41mGraphGen: Conducting Graph Analytics over Relational Databases
55mA Practical Guide to Graph Databases
29mA New Era for Graph Queries: ISO/IEC 39075 GQL
20mPre-Select Static Caching and Neighborhood Ordering for BFS-like Algorithms on Disk-based Graph Engines
37mGraph Computing at Scale
29mThinking in Graphs – An Intro to Graph Databases & Applications