License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECOOP.2022.31
URN: urn:nbn:de:0030-drops-162592
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16259/
Lumsdaine, Andrew ;
D'Alessandro, Luke ;
Deweese, Kevin ;
Firoz, Jesun ;
Liu, Xu Tony ;
McMillan, Scott ;
Ratzloff, John Phillip ;
Zalewski, Marcin
NWGraph: A Library of Generic Graph Algorithms and Data Structures in C++20
Abstract
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.
BibTeX - Entry
@InProceedings{lumsdaine_et_al:LIPIcs.ECOOP.2022.31,
author = {Lumsdaine, Andrew and D'Alessandro, Luke and Deweese, Kevin and Firoz, Jesun and Liu, Xu Tony and McMillan, Scott and Ratzloff, John Phillip and Zalewski, Marcin},
title = {{NWGraph: A Library of Generic Graph Algorithms and Data Structures in C++20}},
booktitle = {36th European Conference on Object-Oriented Programming (ECOOP 2022)},
pages = {31:1--31:28},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-225-9},
ISSN = {1868-8969},
year = {2022},
volume = {222},
editor = {Ali, Karim and Vitek, Jan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16259},
URN = {urn:nbn:de:0030-drops-162592},
doi = {10.4230/LIPIcs.ECOOP.2022.31},
annote = {Keywords: Graph library, generic programming, graph algorithms}
}
