Structural evolution since BGL?

[dabrahams]

I'm interested in generic graph libraries for Swift; there are several, but they don't seem to have learned from the Boost Graph Library; I might try to coax them along, or might try to write something myself. This library I know was written by people familiar with the BGL (hi @lums658!) and I assume newly-discovered truths have been incorporated—I don't mean things at the language level, obviously, but fundamental things about how to address the graph domain generically. I'd like to get an idea of what those new truths might be.

Thanks,
Dave

[lums658]

Hi Dave! There are some forthcoming C++ papers on our proposed graph library — D3126 (overview) and D3127 (terminology and conceptual background) will answer many of your questions I think. In some cases we made explicit what was implicit in BGL. In other cases we jettisoned some things — and also added some things. The feedback I have gathered over the years is that BGL is too complicated and too slow to be useful. A quick summary. One of the biggest revelations was that there is a difference between a graph and its representation. A graph has vertices and edges — whereas a representation of a graph encodes the structure of a graph in a form that is amenable to computation. One example of the difference between a graph and its representation is an adjacency matrix. While on would never use that for actual computation, it encodes the adjacency of vertices, based on an enumeration of the vertices — which is different from the vertices themselves. That is if you have a graph G = {V, E}, the elements in set V can be enumerated as { v0, v1, … } — the adjacency matrix is in terms of the numbers {0, 1, 2} rather than {v0, v1, …} — it doesn’t matter what the vs are, just that we have enumerated them. The adjacency matrix does not have the vertices or edges from the graph — in fact it doesn’t have vertices or edges at all. As is done in linear algebra, for efficiency we can represent the adjacency matrix in sparse form, either in coordinate form (COO) or in compressed form (ala CSR). In graph terms, the former is an edge list, while the latter is usually referred to as an adjacency. Since these representations are just compressed forms of the adjacency matrix, they also don’t contain vertices or edges per se. Now, given an enumeration, we can get the vertices and/or edges (and their properties) from a graph — though it is typically only the properties we are interested in. There may not be a materialized vertex or materialized edges anywhere at all. Another big thing was a change in emphasis on how the library is used. Rather than providing lots of machinery for creating a graph, working with its properties, and so forth — the new library is algorithm-centric arranged around a set of concepts and the assumption is that users will bring their own containers. Most importantly, compositions of standard library containers are suitable for use as a graph for most algorithms. That is, a vector of tuples (or a tuple of vectors) is an edge list representation and a vector of vectors is an adjacency list representation. There is no general-purpose graph generator. Conceptually, a graph representation is a range of ranges — in general a random-access range of forward ranges (depending on what algorithms require). We also accommodate “hyper sparse” graphs in the framework by allowing a map of ranges to be used for the graph. A hyper sparse graph representation is one for which the enumeration of vertices is not contiguous — this comes up a lot in real-world applications. We also don’t have property maps — the algorithms that require access to properties within an algorithm (and there aren’t that many that do) are parameterized with a property accessor function. Also, many things in graph algorithms are used for book-keeping in an algorithms, but aren’t properties per se. The black/grey/white map used by the CLRS form of BFS for example is simply an algorithm implementation detail (which is not at all needed for BFS — in fact the queue is not needed for BFS, but that is another story). There are many other examples of things that don’t need to be in the interface of a graph algorithm. We still have visitors, though much more accessible (we don’t require a complete callback structure be created when only one or a few of the callbacks are required). We experimented with using coroutines as a mechanism for visitors, which is really cool, but there was some overhead that probably would not be acceptable. There is a proposal for “const coroutines” which may eliminate that overhead however, so we may bring coroutines back for visitor functionality. We have views of graphs (and their constituents) to ease traversal — for instance there is a breadth-first view of a graph that can be iterated with a range-based for loop. I think we need to understand a bit better what you mean by memoization in your case, but I think we have a mechanism for that (currently called “descriptors”, which is a collision with BGL terminology that will need to be changed). OTOH, it sounds like this is a data structure issue rather than an algorithm issue so it may be orthogonal to our framework — meaning it is up to the user to provide a graph representation meeting the algorithm concepts in the library — the algorithms would not be concerned with memoizing — the graph data structure does that. To the algorithm, it just needs to behave according to the graph concepts. (We are planning a “CSR” graph as a separate proposal, but that is the only actual data structure being contemplated.) PS — We should have a zoom call to catch up on things. Send me an email and we can set up a time. Sincerely, Andrew Lumsdaine On Dec 24, 2024, at 2:28 PM, Dave Abrahams ***@***.***> wrote: I'm interested in generic graph libraries for Swift; there are several, but they don't seem to have learned from the Boost Graph Library; I might try to coax them along, or might try to write something myself. This library I know was written by people familiar with the BGL (hi @lums658<https://urldefense.com/v3/__https://github.com/lums658__;!!K-Hz7m0Vt54!i9L4uSW8UQG9-jHQQ-1PiAUxu_XXmEudlRHmBBIOElNy7biB3cZhMiIaRJTKwGvLFvsx4YBTcLfwsyAB-GZO9w$>!) and I assume newly-discovered truths have been incorporated—I don't mean things at the language level, obviously, but fundamental things about how to address the graph domain generically. I'd like to get an idea of what those new truths might be. Thanks, Dave — Reply to this email directly, view it on GitHub<https://urldefense.com/v3/__https://github.com/stdgraph/graph-v2/discussions/141__;!!K-Hz7m0Vt54!i9L4uSW8UQG9-jHQQ-1PiAUxu_XXmEudlRHmBBIOElNy7biB3cZhMiIaRJTKwGvLFvsx4YBTcLfwsyAT_JHycQ$>, or unsubscribe<https://urldefense.com/v3/__https://github.com/notifications/unsubscribe-auth/AGKPFDLWI5LKYMW24BGQ6XL2HHNZ5AVCNFSM6AAAAABUFHRVR2VHI2DSMVQWIX3LMV43ERDJONRXK43TNFXW4OZXG42DCNRRG4__;!!K-Hz7m0Vt54!i9L4uSW8UQG9-jHQQ-1PiAUxu_XXmEudlRHmBBIOElNy7biB3cZhMiIaRJTKwGvLFvsx4YBTcLfwsyAv8fLYhg$>. You are receiving this because you were mentioned.Message ID: ***@***.***>

[dabrahams]

There are some forthcoming C++ papers on our proposed graph library — D3126 (overview) and D3127 (terminology and conceptual background) will answer many of your questions I think.

Not so sure; I don't really know C++ anymore! Half true, at least.

In some cases we made explicit what was implicit in BGL. In other cases we jettisoned some things — and also added some things. The feedback I have gathered over the years is that BGL is too complicated and too slow to be useful.

Huh. I wonder where the slowness comes from?

A quick summary.

I'm going to apologize in advance because what follows here probably sounds challenging, but my conclusion is actually that I must obviously be missing something important.

One of the biggest revelations was that there is a difference between a graph and its representation.
A graph has vertices and edges — whereas a representation of a graph encodes the structure of a graph in a form that is amenable to computation.

? I thought BGL already reflected that understanding by allowing me to model a graph concept with arbitrary implementations. You must mean something very specific.

One example of the difference between a graph and its representation is an adjacency matrix. While on would never use that for actual computation, it encodes the adjacency of vertices, based on an enumeration of the vertices — which is different from the vertices themselves. That is if you have a graph G = {V, E}, the elements in set V can be enumerated as { v0, v1, … } — the adjacency matrix is in terms of the numbers {0, 1, 2} rather than {v0, v1, …} — it doesn’t matter what the vs are, just that we have enumerated them. The adjacency matrix does not have the vertices or edges from the graph — in fact it doesn’t have vertices or edges at all.

I don't think I understand what you mean here. The way I see it, matrix is a mathematical object, or a data structure (depending on the level you're viewing it) that doesn't have vertices or edges. The adjacency matrix is a graph with particular algebraic/performance properties and operations. It has vertices and edges because we say it does. It can be implemented using various data structures, including a matrix.

In graph terms, the former is an edge list, while the latter is usually referred to as an adjacency.

As is done in linear algebra, for efficiency we can represent the adjacency matrix in sparse form, either in coordinate form (COO) or in compressed form (ala CSR).

Strictly speaking, neither of those (especially the first) would have the big-O performance characteristics I associate with adjacency matrix. Now it may be that no real large graphs are dense enough to make adjacency matrix a win, even if you use a bitset for underlying storage…

Since these representations are just compressed forms of the adjacency matrix,

If you can say that, you can say an adjacency list is also a compressed form of the adjacency matrix.

they also don’t contain vertices or edges per se. Now, given an enumeration, we can get the vertices and/or edges (and their properties) from a graph — though it is typically only the properties we are interested in. There may not be a materialized vertex or materialized edges anywhere at all.

I don't really know what you mean by "contain" here. The whole point of BGL's vertex and edge descriptors is that vertices are just identities and edges are just relationships between those vertices (and have identity of their own). There's not necessarily any place to "store" a vertex or an edge—the storage often associated with those things would be in property maps. Surely I'm not telling you anything you don't know. But the fact that I have to say it goes to show just how little I understand what you're suggesting… it sounds like you're talking about BGL's fundamental design, not something new. The BGL already works with graphs having no materialized representation. IIRC the book has an N-queens example. Divisibility of integers is a relationship I could use to easily make a BGL adjacency matrix, for aother example.

Another big thing was a change in emphasis on how the library is used. Rather than providing lots of machinery for creating a graph, working with its properties, and so forth
— the new library is algorithm-centric arranged around a set of concepts and the assumption is that users will bring their own containers.

Yeah, again sounds like you're talking about BGL: that adjacency_list generative programming thing may get a lot of attention from newcomers I suppose, but that was never the focus of the BGL as far as I was concerned. And that kind of TMP nonsense doesn't translate to languages with real (separately-checked) generics. I suppose you could use macros in Swift or Rust. Anyway, I used the BGL algorithms with my own data structures all the time! So, still confused here.

Most importantly, compositions of standard library containers are suitable for use as a graph for most algorithms.

Again, sounds like BGL. You might need to provide a few additional concept requirements; I don't remember. Maybe you're saying that those are available OOTB, but if so that is not a very fundamental difference and might only be more practical because of cleaner-looking SFINAE (cough) in C++20.

Conceptually, a graph representation is a range of ranges — in general a random-access range of forward ranges (depending on what algorithms require).

Presumably the inner ranges' elements are neighbor vertex IDs?

That sounds like an adjacency list, but not an edge list or adjacency matrix, as I understand them, so not a generalized graph. Also doesn't sound like it supports bidirectional traversal, or various other thiings the BGL concepts accommodate. What am I missing here?

We also accommodate “hyper sparse” graphs in the framework by allowing a map of ranges to be used for the graph. A hyper sparse graph representation is one for which the enumeration of vertices is not contiguous — this comes up a lot in real-world applications.

Also doesn't sound new…

We also don’t have property maps — the algorithms that require access to properties within an algorithm (and there aren’t that many that do) are parameterized with a property accessor function.

How is that not just a property map with different syntax?

Also, many things in graph algorithms are used for book-keeping in an algorithms, but aren’t properties per se. The black/grey/white map used by the CLRS form of BFS for example is simply an algorithm implementation detail (which is not at all needed for BFS

…right, so by parameterizing on the property map, the BGL lets you use a dummy map, the writing of which is a no-op.

— in fact the queue is not needed for BFS, but that is another story). There are many other examples of things that don’t need to be in the interface of a graph algorithm.

Yes, the BGL interfaces were too complex, that's for sure. Overloads are bad for usability, and more should have been done to reduce the sizes of the parameter lists.

What I'm hearing so far sounds like a nicer face on a conceptual structure that is not fundamentally different from the BGL, presented as though the BGL is completely different from what I understand it to be. So I must really be missing something important.

I think we need to understand a bit better what you mean by memoization in your case… the algorithms would not be concerned with memoizing — the graph data structure does that.

Where did I express that concern? Not in this thread—I do have a concern about it but I don't think it has anything to do with graphs; it's more a fundamental issue with systems that enforce pure mutable value semantics. These systems don't have anything like C++'s mutable keyword, so in a non-mutating algorithm on a graph, the graph can't be updated and therefore can't "handle the memoization" because there are no references (unless you do something to make them safe like locking around shared data structures). We've worked out several approaches for Hylo. In C++ you can of course do all the not-really constant-const maneuvers you want ;-).