2026-07-23T21:52:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16259 2024-03-12T12:00:43Z ddc:004 open_access

NWGraph: A Library of Generic Graph Algorithms and Data Structures in C++20 Lumsdaine, Andrew D'Alessandro, Luke Deweese, Kevin Firoz, Jesun Liu, Xu Tony McMillan, Scott Ratzloff, John Phillip Zalewski, Marcin Graph library generic programming graph algorithms The C++ Standard Library is a valuable collection of generic algorithms and data structures that improves the usability and reliability of C++ software. Graph algorithms and data structures are notably absent from the standard library, and previous attempts to fill this gap have not gained widespread adoption. In this paper we show that the richness of graph algorithms and data structures can in fact be captured by straightforward composition of existing C++ mechanisms. Generic programming is algorithm-oriented. Accordingly, we apply a systematic approach to analyzing a broad set of graph algorithms, "lift" unnecessary constraints from them, and organize the resulting set of minimal common type requirements, i.e., concepts, for defining their interfaces. By using the newly available ranges and concepts in C++20, the type requirements for generic graph algorithms can be succinctly expressed. The generic algorithms and data structures resulting from our analysis are realized in NWGraph, a modern, composable, and extensible C++ library. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrew Lumsdaine and Luke D'Alessandro and Kevin Deweese and Jesun Firoz and Xu Tony Liu and Scott McMillan and John Phillip Ratzloff and Marcin Zalewski 2022 Is Part Of LIPIcs, Volume 222, 36th European Conference on Object-Oriented Programming (ECOOP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ECOOP.2022.31 urn:nbn:de:0030-drops-162592 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2022.31 eng https://creativecommons.org/licenses/by/4.0/legalcode