Graph Algorithms and Data Structures in C++20 - Phil Ratzloff & Andrew Lumsdaine - CppCon 2022

cppcon.org/
---
Graph Algorithms and Data Structures in C++20 - Phil Ratzloff, Andrew Lumsdaine - CppCon 2022
github.com/CppCon/CppCon2022
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.
This session presents an approach for expressing graph algorithms in a modern, composable, and extensible, aka generic, fashion. Concepts provide a means for a systematic organization of the type requirements for graph algorithms to operate correctly and efficiently. Remarkably, these type requirements can be expressed not in graph-specific terms, but rather in terms of existing sets of requirements already in place for basic containers in C++, i.e., ranges. Using this conceptual framework, we develop several generic algorithms and concrete data structures as well as the emerging proposal for a standard graph library.
---
Phil Ratzloff
Phil Ratzloff is a Distinguished Software Developer and C++ advocate at SAS Institute. He has used C++ for 27 years on applications using graphs for business cost analysis and fraud detection.
---
Andrew Lumsdaine
Andrew Lumsdaine is an internationally recognized expert in the area of high-performance computing who has made important contributions in many of the constitutive areas of HPC, including systems, programming languages, software libraries, and performance modeling. His work in HPC has been motivated by data-driven problems (e.g., large-scale graph analytics), as well as more traditional computational science problems. He has been an active participant in multiple standardization efforts, including the MPI Forum, the BLAS Technical Forum, the ISO C++ standardization committee, the oneAPI Technical Advisory Board, and the SYCL Advisory Panel. Open source software projects resulting from his work include the Matrix Template Library, the Boost Graph Library, and Open MPI.
---
Videos Filmed & Edited by Bash Films: www.BashFilms.com
TH-cam Channel Managed by Digital Medium Ltd events.digital-medium.co.uk
#cppcon #algorithms #datastructures

[@scbtripwire]

I used the Boost.Graph library at my previous job until I left in 2013. Great library. 🙂

[@ondrejsebek9092]

This would be really nice for Advent of Code :D I was thinking about A* and dijkstra the whole time.

[@JoseSilva-gt6zj]

Question: When should we use "A* algorithm" or "Dijkstra Algorithm" ? Thank y'all !

[@NomoregoodnamesD8]

The primary difference between A* and Dijkstra is that A* uses a heuristic distance to a single goal node.
If you intend to find only one path between nodes A and B, and you have a good heuristic, A* may be the better choice.
If you want to find paths to *all* other nodes from node A, use Dijkstra's.

[@blenm3]

@@NomoregoodnamesD8 A* has a few additional limitations - the heuristic needs to be

[@pesto801]

58:36 In the end what's the answer to Bjarne's question?

[@Jceek]

This data structure seems to have the same limitations that boost graph has. Immutable graphs are a corner case. With a vector you get dense vertex indices for free but things break when adding, removing vertices. Inversely, sparse data structures do not provide indices in the first place, so typical graph algorithms are not applicable directly, without providing any form of aux. index. Similarly for edges. Then there is the problem of initializing and mapping aux. data that serve algos for state management but should otherwise not be part of the graph itself (flags, flows, colors, etc ) And then there is the problem of cache inefficiency by storing vertex/edge labels next to or in adjacency lists. Column store makes a whole lot sense. Hopefully it doesn't make it into the standard as - unfortunately - it seems to be just yet another incomplete approach and people will continue to handcraft to get anything done in the real world

[@echosystemd]

Great comments. Do you know any graph library that solve the problems you mentioned?

[@Jceek]

@@echosystemd unfortunately, there seems to be none which is generic and efficient. I came to the conclusion that trying to solve the problem by composition of existing standard data structures is not the way to go.

[@ilieschamkar6767]

@@Jceek is there somewhere where I can discuss more about graphs implementation, if I'm not bothering you?

[@llothar68]

@@ilieschamkar6767 Every advanced algorithm book explains the normal graph algorithms.

[@llothar68]

The magic of graph performance is that you never should build a full graph but just dynamically redefine it with more details when needed. Just like 3D models reduce detail levels. And this kind of library is too complex and large for a general purpose language library. Like adding widgets, or even 2d drawing its better put into a special project.

[@mykolarabchevskiy8948]

There are other ways of representing graphs convenient for applications that the authors probably have yet to encounter. For example:
Graph := Map< Vertex, Set< Vertex > >
This representation allows you to define high-level functions that operate on sets of vertices (including searching for sets of vertices).

[@minciNashu]

I'm curious, why are you saying that's not a common way to represent a graph ? Because most graph study materials use this or the matrix variant.

[@ABaumstumpf]

What is this "Frankfürt" that is mentioned on the slides?

[@NoNameAtAll2]

where?

[@xl000]

15:58
For those who wonder, it's because there is an extra umlaut on Frankfürt - should be Frankfurt.
In his defence, half of the cities with the letter u somewhere also have an umlaut. And he's probably not fluent in German.

[@pawello87]

Any benchmarks? If it's comparable to boost::graph then what's the point of another graph impl?

[@pesto801]

incoming...