NWGraph: A Library of Generic Graph Algorithms and Data Structures in C++20
Join us for our upcoming Future Computing Seminar Series
Speaker: external page Dr. Andrew Lumsdaine, Pacific Northwest National Lab
Date: March 21st, 2023, 18:00 CET
Where: Online
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.
Speaker Bio:
Andrew Lumsdaine is a computer scientist and a Laboratory Fellow in the Advanced Computing, Mathematics, and Data Division at Pacific Northwest National Lab. He is also an Affiliate Professor of Computer Science in the Paul G. Allen School of Computer Science and Engineering at the University of Washington. Dr. Lumsdaine completed his PhD from the Massachusetts Institute of Technology and began his academic career as a faculty member at the University of Notre Dame. He later moved to Indiana University and joined PNNL/UW in 2016. He is currently on a temporary leave from PNNL and is working at TileDB, Inc., a database startup spun out from MIT. A unifying theme of his research has been on software construction and high-performance computing, focusing how researchers can make the most efficient and productive use of their computing systems, and developing tools to facilitate this process. His research agenda has included various efforts such as distributed-memory computing and the Message Passing Interface (MPI), generic programming and the C++ language standard, and scalable graph analytics and the (Parallel) Boost Graph Library.