DROPS

Document

DOI: 10.4230/LIPIcs.ECOOP.2022.31

NWGraph: A Library of Generic Graph Algorithms and Data Structures in C++20

Authors: Andrew Lumsdaine, Luke D'Alessandro, Kevin Deweese, Jesun Firoz, Xu Tony Liu, Scott McMillan, John Phillip Ratzloff, and Marcin Zalewski

Published in: LIPIcs, Volume 222, 36th European Conference on Object-Oriented Programming (ECOOP 2022)

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.

Cite as

Andrew Lumsdaine, Luke D'Alessandro, Kevin Deweese, Jesun Firoz, Xu Tony Liu, Scott McMillan, John Phillip Ratzloff, and Marcin Zalewski. NWGraph: A Library of Generic Graph Algorithms and Data Structures in C++20. In 36th European Conference on Object-Oriented Programming (ECOOP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 222, pp. 31:1-31:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ECOOP.2022.31},
  URN =		{urn:nbn:de:0030-drops-162592},
  doi =		{10.4230/LIPIcs.ECOOP.2022.31},
  annote =	{Keywords: Graph library, generic programming, graph algorithms}
}

Search Results

Documents authored by Zalewski, Marcin

NWGraph: A Library of Generic Graph Algorithms and Data Structures in C++20

Abstract

Cite as

Thanks for your feedback!

Could not send message