Date: Thu, 11 Jan 2024 22:17:07 +0000
Sorry shared edges --> shared edge weights
I did experiment with shared edges at some point but abandoned it as a bad
idea :)
On Thu, 11 Jan 2024 at 22:16, Oliver Rosten <oliver.rosten_at_[hidden]>
wrote:
> Hi Andrew,
>
> The use case has to do with undirected edges with a mutable property.
>> With adjacency-based graph representations, an undirected edge gets split
>> into two directed edges (since the representation is of adjacencies —
>> partial edges, essentially). If there are edges with properties, those are
>> shared, and then how to handle that becomes interesting — and leads (iiuc)
>> to your diagram.
>
>
> That's not quite what I'm getting at (at least if I've understood you
> correctly). The end-point data, 'a' and 'b' have nothing to do with the
> handling of shared edges. For that I've implemented a couple of strategies:
>
> 1. Literally share the weight, using a shared pointer.
> 2. Store it separately for each edge. For mutations, employ a sentinel
> which deals with the case of an exception being thrown when one weight has
> been changed, but not the other.
>
> There are a couple of ways to think about 'a' and 'b'. One would be to say
> that the edge weights are actually completely independent, say W and W'.
> Alternatively, you say that there is one component of the edge weight that
> is always shared - call it W - and a freedom to differ held by 'a' and 'b'.
> You can use 'a' and 'b' to establish an orientation for the edges. A bit
> like saying you've drawn a mark on your resistor, indicating the back and
> front for the purposes of establishing a positive current convention. (With
> W holding the value of the resistance.)
>
> Note that you could choose 'a' and 'b' such that you could interpret your
> graph as a directed graph with incident edges recorded. But I think the
> structure is more flexible than this.
>
> Oliver
>
> PS My history includez implementing a 1D fluid flow network, which is of
> course very similar to electrical circuits. (I actually simulated some of
> the latter as part of my testing, since the code is generic.) I then
> reimplemented all of this and much more besides in a library of mine up on
> github. In terms of the algorithms available, it's nothing like as mature
> as BGL. But you can do some cool things like topological sorting at compile
> time.
>
> On Thu, 11 Jan 2024 at 21:51, Andrew Lumsdaine <al75_at_[hidden]> wrote:
>
>> Oh — hah — yes. Very familiar with that case. At least the way we have
>> seen it come up is more in the context of implementation than as an
>> abstraction per se (though there of course may be a corresponding
>> abstraction). The use case has to do with undirected edges with a mutable
>> property. With adjacency-based graph representations, an undirected edge
>> gets split into two directed edges (since the representation is of
>> adjacencies — partial edges, essentially). If there are edges with
>> properties, those are shared, and then how to handle that becomes
>> interesting — and leads (iiuc) to your diagram.
>>
>> I am also looking for names for certain other things like the thing we
>> are calling a “structurally bipartite graph” (or more informally, a
>> “rectangular graph”).
>>
>> I did approach a mathematician about some of these things before the
>> holidays. He initially wanted to express it all in terms of category
>> theory. It wasn’t quite what I was hoping for.
>>
>> (The reason that hypergraphs came to mind is that hypergraphs have
>> generalized edges — i.e., the “edges” of the graph are arbitrary subsets of
>> vertices, rather than just being subsets of size 2. That includes subsets
>> of size 1. If one tries to interpret that in the usual sense of a graph
>> edge as having a source and a target — it’s an edge with a source but no
>> target — an edge to nowhere :-)).
>>
>> Best Regards,
>> Andrew Lumsdaine
>>
>> PS — Interestingly, the genesis of my work in graphs came from circuit
>> simulation (way back). My first task as a new PhD student was to implement
>> RCM for the sparse solver in a circuit simulator. Reimplementing it 12
>> years later led to BGL.
>>
>>
>> On Jan 9, 2024, at 11:25 PM, Oliver Rosten <oliver.rosten_at_[hidden]>
>> wrote:
>>
>> This Message Is From an Untrusted Sender
>> You have not previously corresponded with this sender.
>> See https://itconnect.uw.edu/email-tags for additional information.
>> Please contact the UW-IT Service Center, help_at_[hidden] 206.221.5000, for
>> assistance.
>> Hi Andrew,
>>
>> Thanks for such a detailed reply. Re. the circuit diagram, it's not a
>> hypergraph I'm thinking of. It's a structure like this:
>>
>> a---W--->
>> <---W---b
>>
>> Every edge comes as a pair of partial edges. They have a shared weight,
>> W, as you'd expect from an undirected graph. But they also have independent
>> end-point data, labelled a, b). This is sufficient to properly model things
>> like electrical circuits. So this is a directed graph but with a particular
>> restriction that all edges come in pairs, but holding data such that I
>> don't think it's right to call it undirected (but it almost is!). I don't
>> know the right name for this structure, but I suspect a mathematician
>> would! This is part of my broader point: I really think we would benefit
>> from finding a willing participant from the mathematics community to keep
>> us on the straight and narrow!
>>
>> I completely take your point about the origin of the STL. I certainly
>> don't desire an explicit coupling between something like unstructured span
>> and the graph library. However, I also have little doubt that knowing the
>> shape of unstructured span would greatly help the design of graph. It think
>> it's reasonable for development of these two things to happen concurrently.
>> Indeed, I've cc'd the first 4 authors of the mdspan paper (apologies if
>> I've not carried on far enough down the author list!).
>>
>> Re. merging information from your two papers, I think this might help if
>> done judiciously. I find P1709 very hard to follow, despite having spent a
>> lot of time working with graphs!
>>
>> Oliver
>>
>> On Tue, 9 Jan 2024 at 22:04, Andrew Lumsdaine <al75_at_[hidden]> wrote:
>>
>>> Hi — Thanks for your comments. My responses in-line below.
>>>
>>> Cheers,
>>> Andrew Lumsdaine
>>>
>>> On Jan 9, 2024, at 9:50 AM, Oliver Rosten via SG19 <
>>> sg19_at_[hidden]> wrote:
>>>
>>> Some other things to add:
>>>
>>> 1. The electrical circuit example needs more explanation, and I think
>>> this will highlight some deep issues around representing things which are
>>> seemingly trivially graphs, as graphs in practice. In what sense is a
>>> bog-standard resistor directed? I assume the reason that the graph is
>>> directed is because current has a sign and in an undirected graph it
>>> becomes ambiguous which way the current is flowing (also you may want
>>> components like diodes). But the directed representation also has issues:
>>> "can current flow from 'Vdd' to 'n0'?" should be immediately answerable
>>> from the properties of Vdd and its edges. There are other ways to represent
>>> an electrical circuit. One is as a directed graph but with incident edges
>>> recorded - but iiuc, this is excluded from the latest version of the paper.
>>> Alternatively, one could have a mathematical object, the name of which I
>>> actually don't know: it looks like an undirected graph, but where each
>>> partial edge has additional, unique, end-point data, as well as the common
>>> weight. Things like this are the reason why I think we need a broader group
>>> to look at this proposal (i.e. beyond SG19) and if we possibly can we
>>> should involve someone from the mathematics community. Otherwise there's a
>>> real danger we end up missing important insights.
>>>
>>>
>>> The circuit example might not be the best one to illustrate an
>>> undirected graph. The connectivity structure is in fact undirected. When
>>> one starts assigning values to elements and computing currents and
>>> voltages, then directivity is required. What kind of graph you get also
>>> depends on what kind of formulation / analysis you want to do. And, in
>>> fact, if you are using a modified nodal analysis (which is what I had in
>>> mind), you can’t really model a circuit element (simply) as a single edge.
>>> In the case of a diode you have two properties, the conductance in the
>>> forward direction and the conductance in the reverse direction - you have
>>> either two properties on one edge or two edges in opposite directions. (If
>>> one makes the analogy between a sparse matrix and a graph, the latter is
>>> probably more correct.)
>>>
>>> I think you may be thinking of a hypergraph (that is certainly another
>>> generalization of a graph — although hypergraphs can generally be reduced
>>> to bipartite graphs).
>>>
>>> Our thinking for this paper was to go lighter on the mathematics and
>>> exposit at a more practical level. I have a more mathematical paper that
>>> we could perhaps provide as a complement to this one. I would need to
>>> merge some of P1709R5 back into that paper however, as well as expand a few
>>> things. It’s about ten pages at the moment. A revision would maybe grow
>>> it by a couple of pages.
>>>
>>> As far as the definition of a graph goes, I was very careful to be quite
>>> precise, to make all terms well-defined, and to differentiate
>>> representation (which is useful - and which is used for describing and
>>> implementing algorithms) and the G={V, E} (which is less useful). The
>>> complementary paper I mentioned above has almost a page describing how
>>> imprecise even the math literature is about these things. Among other
>>> things, the literature is almost universally sloppy about graph vs graph
>>> representation and about vertex vs vertex enumeration. I deliberately used
>>> a somewhat different exposition than the one you always see just to hammer
>>> that point home.
>>>
>>>
>>> 2. My comment about the structure of the paper changing was a reference
>>> to previous comparisons with boost::graph. I'm sure these were in an
>>> earlier version, or am I misremembering? Either way, it would be very
>>> helpful to have a proper discussion of e.g. the move away from visitors.
>>>
>>>
>>> We had decided not to include direct comparisons with BGL or GraphBLAS
>>> in the interest of space, but we have contributors to BGL and GraphBLAS as
>>> authors of this paper, so we can definitely include such comparisons.
>>>
>>> I don’t think I am saying anything I haven’t said to the GraphBLAS
>>> community directly when I say GraphBLAS should be considered dangerous. (I
>>> have an open challenge to the community to prove me wrong. It’s been unmet
>>> for 6+ years.)
>>>
>>>
>>> 3. Re. the definition of a graph, there needs to be a proper discussion
>>> about whether the paper's definition of graph is what some authors call a
>>> multigraph and whether it does/does not include loops. These things are
>>> mentioned, in passing, when introducing algorithms, but terminology needs
>>> to be properly established.
>>>
>>>
>>> Agreed. These are run-time properties of a graph and the preconditions
>>> for the algorithms would need to properly account for them. With our
>>> formulation being based on the adjacency matrix representation, there is*kind
>>> of* an assumption that these are not multigraphs. Of course, anyone
>>> can make a graph with multiple edges between the same two vertices once you
>>> have moved away from the dense adjacency matrix representation and are
>>> using an edge list or an adjacency list. But yes, this needs to be called
>>> out in the algorithm preconditions.
>>>
>>> Alternatively (or in addition to) preconditions, some algorithms could
>>> probably still be used with multigraphs, but properties associated with
>>> edges could perhaps have some kind of property combiner (if it makes sense
>>> in the context of the algorithm and what the graph is modeling). In the
>>> case of the Kevin Bacon example, there are lots of edges between actors,
>>> one for each movie in which they have costarred. When doing breadth-first
>>> search, do we just traverse one edge and record a single property? Do we
>>> traverse all edges and record all the properties? Pick the one
>>> lexicograpically first? Etc.
>>>
>>> Along these same lines we need to describe requirements on connectivity
>>> vis-a-vis computed results.
>>>
>>>
>>> 4. I think we're trying to do too much in one go in this paper. I think
>>> a great first step would be to build on mdspan and try to standardize (or
>>> at least understand) what might reasonably be called an unstructured span.
>>> This could be represented as a vector of vectors or as a vector with some
>>> auxiliary storage indicating where the partitions fall. The point is that
>>> an unstructured span, with the right invariants, is an adjacency list. If
>>> we can understand unstructured span and its desirable api, I think this
>>> will be incredibly valuable guidance for what a standardized graph
>>> container might look like.
>>>
>>>
>>> I agree that unstructured mdspan would be super-useful in this context.
>>> We were somewhat reluctant to dive into that as some of the original
>>> thoughts about that (or closely related) go back to the dawn of generic
>>> programming: Matt Austern’s Segmented Iterators and Hierarchical
>>> Algorithms, Rene Rivera’s Hierarchical Data Structures and Related
>>> Concepts, and I am sure there are more. We didn’t want to have
>>> unstructured mdspan as a dependency since it could be several cycles before
>>> it might come into existence.
>>>
>>> I think it would be quite useful to co-develop graphs and unstructured
>>> mdspan. The latter cuts across other SGs I think (ranges comes to mind —
>>> though linear algebra would obviously be interested in it for sparse
>>> matrices).
>>>
>>>
>>> 5. IIUC, this paper excludes pure connectivity graphs. These are
>>> incredibly helpful and, if I've understood correctly that they are not
>>> supported, would be a major omission. Another good reason, imo, to start
>>> with unstructured span!
>>>
>>>
>>> Pure connectivity graphs are WIP. I had hoped to have something done by
>>> this mailing but ran out of time. Besides just the exposition of this kind
>>> of representation, we need to relax the requirements for some of the
>>> algorithms, with the current requirements either a specialization or an
>>> overload of the connectivity graphs.
>>>
>>>
>>>
>>> 6. I'm not convinced by the load api. We don't have a load api for
>>> vector etc. Moreover, would it not be preferable to have appropriate
>>> constructors?
>>>
>>>
>>>
>>> I could probably go on but I think this is sufficient for now. Having
>>> graphs and associated algorithms in the standard would be fantastic. But I
>>> think we need to take a step back, involve people from the right
>>> communities, and figure out how to do this step-by-step.
>>>
>>> Oliver
>>>
>>> On Tue, 9 Jan 2024 at 17:18, Michael Wong via SG19 <
>>> sg19_at_[hidden]> wrote:
>>>
>>>> Roger and BSI, Thanks for the great feedback. We SG19 will look at this
>>>> feedback this Thursday on our regular call at 2-4 pm ET. Cheers.
>>>>
>>>> On Mon, Jan 8, 2024 at 5:20 PM Roger Orr <rogero_at_[hidden]> wrote:
>>>>
>>>>> Hello Michael,
>>>>> as you will see from the minutes, the BSI briefly discussed P1709R4
>>>>> "Graph Library" today.
>>>>> You are listed as an author, so we are directing our feedback to you
>>>>> in the first instance!
>>>>>
>>>>> As Oliver (Rosten) said "The basic premise is important, and it would
>>>>> be fantastic to have support for graphs in the standard."
>>>>>
>>>>> The main items identified were:
>>>>> Oliver:
>>>>> - This paper is long and incomplete, it has lots of details which I
>>>>> think to be irrelevant, however things that are definitely relevant are
>>>>> missing from the paper - for example definition of graph - since people
>>>>> have different ideas. We need to add a mathematical perspective to the
>>>>> paper.
>>>>>
>>>>> - The structure of the paper completely changed in the new revision,
>>>>> so now it’s hard to understand what and why they have done
>>>>>
>>>>> - Another missing part is discussion of graph invariants
>>>>>
>>>>> Tom (Deakin): There’s a big missing part in “Prior art” part,
>>>>> GraphBLAS (https://graphblas.org
>>>>> <https://urldefense.com/v3/__https://graphblas.org__;!!K-Hz7m0Vt54!lEMnRbkdjKfReFDkvhwE2zDloIG-JEOwnu8lyeH-nsfm4K0in2mS-TkcBdVd2CoVCH3WLh8DX360WQc$>)
>>>>> eminently.
>>>>>
>>>>> Best wishes,
>>>>> Roger.
>>>>>
>>>> --
>>>> SG19 mailing list
>>>> SG19_at_[hidden]
>>>> https://lists.isocpp.org/mailman/listinfo.cgi/sg19
>>>> <https://urldefense.com/v3/__https://lists.isocpp.org/mailman/listinfo.cgi/sg19__;!!K-Hz7m0Vt54!lEMnRbkdjKfReFDkvhwE2zDloIG-JEOwnu8lyeH-nsfm4K0in2mS-TkcBdVd2CoVCH3WLh8DGEl61LA$>
>>>>
>>> --
>>> SG19 mailing list
>>> SG19_at_[hidden]
>>>
>>> https://urldefense.com/v3/__https://lists.isocpp.org/mailman/listinfo.cgi/sg19__;!!K-Hz7m0Vt54!lEMnRbkdjKfReFDkvhwE2zDloIG-JEOwnu8lyeH-nsfm4K0in2mS-TkcBdVd2CoVCH3WLh8DGEl61LA$
>>>
>>>
>>
I did experiment with shared edges at some point but abandoned it as a bad
idea :)
On Thu, 11 Jan 2024 at 22:16, Oliver Rosten <oliver.rosten_at_[hidden]>
wrote:
> Hi Andrew,
>
> The use case has to do with undirected edges with a mutable property.
>> With adjacency-based graph representations, an undirected edge gets split
>> into two directed edges (since the representation is of adjacencies —
>> partial edges, essentially). If there are edges with properties, those are
>> shared, and then how to handle that becomes interesting — and leads (iiuc)
>> to your diagram.
>
>
> That's not quite what I'm getting at (at least if I've understood you
> correctly). The end-point data, 'a' and 'b' have nothing to do with the
> handling of shared edges. For that I've implemented a couple of strategies:
>
> 1. Literally share the weight, using a shared pointer.
> 2. Store it separately for each edge. For mutations, employ a sentinel
> which deals with the case of an exception being thrown when one weight has
> been changed, but not the other.
>
> There are a couple of ways to think about 'a' and 'b'. One would be to say
> that the edge weights are actually completely independent, say W and W'.
> Alternatively, you say that there is one component of the edge weight that
> is always shared - call it W - and a freedom to differ held by 'a' and 'b'.
> You can use 'a' and 'b' to establish an orientation for the edges. A bit
> like saying you've drawn a mark on your resistor, indicating the back and
> front for the purposes of establishing a positive current convention. (With
> W holding the value of the resistance.)
>
> Note that you could choose 'a' and 'b' such that you could interpret your
> graph as a directed graph with incident edges recorded. But I think the
> structure is more flexible than this.
>
> Oliver
>
> PS My history includez implementing a 1D fluid flow network, which is of
> course very similar to electrical circuits. (I actually simulated some of
> the latter as part of my testing, since the code is generic.) I then
> reimplemented all of this and much more besides in a library of mine up on
> github. In terms of the algorithms available, it's nothing like as mature
> as BGL. But you can do some cool things like topological sorting at compile
> time.
>
> On Thu, 11 Jan 2024 at 21:51, Andrew Lumsdaine <al75_at_[hidden]> wrote:
>
>> Oh — hah — yes. Very familiar with that case. At least the way we have
>> seen it come up is more in the context of implementation than as an
>> abstraction per se (though there of course may be a corresponding
>> abstraction). The use case has to do with undirected edges with a mutable
>> property. With adjacency-based graph representations, an undirected edge
>> gets split into two directed edges (since the representation is of
>> adjacencies — partial edges, essentially). If there are edges with
>> properties, those are shared, and then how to handle that becomes
>> interesting — and leads (iiuc) to your diagram.
>>
>> I am also looking for names for certain other things like the thing we
>> are calling a “structurally bipartite graph” (or more informally, a
>> “rectangular graph”).
>>
>> I did approach a mathematician about some of these things before the
>> holidays. He initially wanted to express it all in terms of category
>> theory. It wasn’t quite what I was hoping for.
>>
>> (The reason that hypergraphs came to mind is that hypergraphs have
>> generalized edges — i.e., the “edges” of the graph are arbitrary subsets of
>> vertices, rather than just being subsets of size 2. That includes subsets
>> of size 1. If one tries to interpret that in the usual sense of a graph
>> edge as having a source and a target — it’s an edge with a source but no
>> target — an edge to nowhere :-)).
>>
>> Best Regards,
>> Andrew Lumsdaine
>>
>> PS — Interestingly, the genesis of my work in graphs came from circuit
>> simulation (way back). My first task as a new PhD student was to implement
>> RCM for the sparse solver in a circuit simulator. Reimplementing it 12
>> years later led to BGL.
>>
>>
>> On Jan 9, 2024, at 11:25 PM, Oliver Rosten <oliver.rosten_at_[hidden]>
>> wrote:
>>
>> This Message Is From an Untrusted Sender
>> You have not previously corresponded with this sender.
>> See https://itconnect.uw.edu/email-tags for additional information.
>> Please contact the UW-IT Service Center, help_at_[hidden] 206.221.5000, for
>> assistance.
>> Hi Andrew,
>>
>> Thanks for such a detailed reply. Re. the circuit diagram, it's not a
>> hypergraph I'm thinking of. It's a structure like this:
>>
>> a---W--->
>> <---W---b
>>
>> Every edge comes as a pair of partial edges. They have a shared weight,
>> W, as you'd expect from an undirected graph. But they also have independent
>> end-point data, labelled a, b). This is sufficient to properly model things
>> like electrical circuits. So this is a directed graph but with a particular
>> restriction that all edges come in pairs, but holding data such that I
>> don't think it's right to call it undirected (but it almost is!). I don't
>> know the right name for this structure, but I suspect a mathematician
>> would! This is part of my broader point: I really think we would benefit
>> from finding a willing participant from the mathematics community to keep
>> us on the straight and narrow!
>>
>> I completely take your point about the origin of the STL. I certainly
>> don't desire an explicit coupling between something like unstructured span
>> and the graph library. However, I also have little doubt that knowing the
>> shape of unstructured span would greatly help the design of graph. It think
>> it's reasonable for development of these two things to happen concurrently.
>> Indeed, I've cc'd the first 4 authors of the mdspan paper (apologies if
>> I've not carried on far enough down the author list!).
>>
>> Re. merging information from your two papers, I think this might help if
>> done judiciously. I find P1709 very hard to follow, despite having spent a
>> lot of time working with graphs!
>>
>> Oliver
>>
>> On Tue, 9 Jan 2024 at 22:04, Andrew Lumsdaine <al75_at_[hidden]> wrote:
>>
>>> Hi — Thanks for your comments. My responses in-line below.
>>>
>>> Cheers,
>>> Andrew Lumsdaine
>>>
>>> On Jan 9, 2024, at 9:50 AM, Oliver Rosten via SG19 <
>>> sg19_at_[hidden]> wrote:
>>>
>>> Some other things to add:
>>>
>>> 1. The electrical circuit example needs more explanation, and I think
>>> this will highlight some deep issues around representing things which are
>>> seemingly trivially graphs, as graphs in practice. In what sense is a
>>> bog-standard resistor directed? I assume the reason that the graph is
>>> directed is because current has a sign and in an undirected graph it
>>> becomes ambiguous which way the current is flowing (also you may want
>>> components like diodes). But the directed representation also has issues:
>>> "can current flow from 'Vdd' to 'n0'?" should be immediately answerable
>>> from the properties of Vdd and its edges. There are other ways to represent
>>> an electrical circuit. One is as a directed graph but with incident edges
>>> recorded - but iiuc, this is excluded from the latest version of the paper.
>>> Alternatively, one could have a mathematical object, the name of which I
>>> actually don't know: it looks like an undirected graph, but where each
>>> partial edge has additional, unique, end-point data, as well as the common
>>> weight. Things like this are the reason why I think we need a broader group
>>> to look at this proposal (i.e. beyond SG19) and if we possibly can we
>>> should involve someone from the mathematics community. Otherwise there's a
>>> real danger we end up missing important insights.
>>>
>>>
>>> The circuit example might not be the best one to illustrate an
>>> undirected graph. The connectivity structure is in fact undirected. When
>>> one starts assigning values to elements and computing currents and
>>> voltages, then directivity is required. What kind of graph you get also
>>> depends on what kind of formulation / analysis you want to do. And, in
>>> fact, if you are using a modified nodal analysis (which is what I had in
>>> mind), you can’t really model a circuit element (simply) as a single edge.
>>> In the case of a diode you have two properties, the conductance in the
>>> forward direction and the conductance in the reverse direction - you have
>>> either two properties on one edge or two edges in opposite directions. (If
>>> one makes the analogy between a sparse matrix and a graph, the latter is
>>> probably more correct.)
>>>
>>> I think you may be thinking of a hypergraph (that is certainly another
>>> generalization of a graph — although hypergraphs can generally be reduced
>>> to bipartite graphs).
>>>
>>> Our thinking for this paper was to go lighter on the mathematics and
>>> exposit at a more practical level. I have a more mathematical paper that
>>> we could perhaps provide as a complement to this one. I would need to
>>> merge some of P1709R5 back into that paper however, as well as expand a few
>>> things. It’s about ten pages at the moment. A revision would maybe grow
>>> it by a couple of pages.
>>>
>>> As far as the definition of a graph goes, I was very careful to be quite
>>> precise, to make all terms well-defined, and to differentiate
>>> representation (which is useful - and which is used for describing and
>>> implementing algorithms) and the G={V, E} (which is less useful). The
>>> complementary paper I mentioned above has almost a page describing how
>>> imprecise even the math literature is about these things. Among other
>>> things, the literature is almost universally sloppy about graph vs graph
>>> representation and about vertex vs vertex enumeration. I deliberately used
>>> a somewhat different exposition than the one you always see just to hammer
>>> that point home.
>>>
>>>
>>> 2. My comment about the structure of the paper changing was a reference
>>> to previous comparisons with boost::graph. I'm sure these were in an
>>> earlier version, or am I misremembering? Either way, it would be very
>>> helpful to have a proper discussion of e.g. the move away from visitors.
>>>
>>>
>>> We had decided not to include direct comparisons with BGL or GraphBLAS
>>> in the interest of space, but we have contributors to BGL and GraphBLAS as
>>> authors of this paper, so we can definitely include such comparisons.
>>>
>>> I don’t think I am saying anything I haven’t said to the GraphBLAS
>>> community directly when I say GraphBLAS should be considered dangerous. (I
>>> have an open challenge to the community to prove me wrong. It’s been unmet
>>> for 6+ years.)
>>>
>>>
>>> 3. Re. the definition of a graph, there needs to be a proper discussion
>>> about whether the paper's definition of graph is what some authors call a
>>> multigraph and whether it does/does not include loops. These things are
>>> mentioned, in passing, when introducing algorithms, but terminology needs
>>> to be properly established.
>>>
>>>
>>> Agreed. These are run-time properties of a graph and the preconditions
>>> for the algorithms would need to properly account for them. With our
>>> formulation being based on the adjacency matrix representation, there is*kind
>>> of* an assumption that these are not multigraphs. Of course, anyone
>>> can make a graph with multiple edges between the same two vertices once you
>>> have moved away from the dense adjacency matrix representation and are
>>> using an edge list or an adjacency list. But yes, this needs to be called
>>> out in the algorithm preconditions.
>>>
>>> Alternatively (or in addition to) preconditions, some algorithms could
>>> probably still be used with multigraphs, but properties associated with
>>> edges could perhaps have some kind of property combiner (if it makes sense
>>> in the context of the algorithm and what the graph is modeling). In the
>>> case of the Kevin Bacon example, there are lots of edges between actors,
>>> one for each movie in which they have costarred. When doing breadth-first
>>> search, do we just traverse one edge and record a single property? Do we
>>> traverse all edges and record all the properties? Pick the one
>>> lexicograpically first? Etc.
>>>
>>> Along these same lines we need to describe requirements on connectivity
>>> vis-a-vis computed results.
>>>
>>>
>>> 4. I think we're trying to do too much in one go in this paper. I think
>>> a great first step would be to build on mdspan and try to standardize (or
>>> at least understand) what might reasonably be called an unstructured span.
>>> This could be represented as a vector of vectors or as a vector with some
>>> auxiliary storage indicating where the partitions fall. The point is that
>>> an unstructured span, with the right invariants, is an adjacency list. If
>>> we can understand unstructured span and its desirable api, I think this
>>> will be incredibly valuable guidance for what a standardized graph
>>> container might look like.
>>>
>>>
>>> I agree that unstructured mdspan would be super-useful in this context.
>>> We were somewhat reluctant to dive into that as some of the original
>>> thoughts about that (or closely related) go back to the dawn of generic
>>> programming: Matt Austern’s Segmented Iterators and Hierarchical
>>> Algorithms, Rene Rivera’s Hierarchical Data Structures and Related
>>> Concepts, and I am sure there are more. We didn’t want to have
>>> unstructured mdspan as a dependency since it could be several cycles before
>>> it might come into existence.
>>>
>>> I think it would be quite useful to co-develop graphs and unstructured
>>> mdspan. The latter cuts across other SGs I think (ranges comes to mind —
>>> though linear algebra would obviously be interested in it for sparse
>>> matrices).
>>>
>>>
>>> 5. IIUC, this paper excludes pure connectivity graphs. These are
>>> incredibly helpful and, if I've understood correctly that they are not
>>> supported, would be a major omission. Another good reason, imo, to start
>>> with unstructured span!
>>>
>>>
>>> Pure connectivity graphs are WIP. I had hoped to have something done by
>>> this mailing but ran out of time. Besides just the exposition of this kind
>>> of representation, we need to relax the requirements for some of the
>>> algorithms, with the current requirements either a specialization or an
>>> overload of the connectivity graphs.
>>>
>>>
>>>
>>> 6. I'm not convinced by the load api. We don't have a load api for
>>> vector etc. Moreover, would it not be preferable to have appropriate
>>> constructors?
>>>
>>>
>>>
>>> I could probably go on but I think this is sufficient for now. Having
>>> graphs and associated algorithms in the standard would be fantastic. But I
>>> think we need to take a step back, involve people from the right
>>> communities, and figure out how to do this step-by-step.
>>>
>>> Oliver
>>>
>>> On Tue, 9 Jan 2024 at 17:18, Michael Wong via SG19 <
>>> sg19_at_[hidden]> wrote:
>>>
>>>> Roger and BSI, Thanks for the great feedback. We SG19 will look at this
>>>> feedback this Thursday on our regular call at 2-4 pm ET. Cheers.
>>>>
>>>> On Mon, Jan 8, 2024 at 5:20 PM Roger Orr <rogero_at_[hidden]> wrote:
>>>>
>>>>> Hello Michael,
>>>>> as you will see from the minutes, the BSI briefly discussed P1709R4
>>>>> "Graph Library" today.
>>>>> You are listed as an author, so we are directing our feedback to you
>>>>> in the first instance!
>>>>>
>>>>> As Oliver (Rosten) said "The basic premise is important, and it would
>>>>> be fantastic to have support for graphs in the standard."
>>>>>
>>>>> The main items identified were:
>>>>> Oliver:
>>>>> - This paper is long and incomplete, it has lots of details which I
>>>>> think to be irrelevant, however things that are definitely relevant are
>>>>> missing from the paper - for example definition of graph - since people
>>>>> have different ideas. We need to add a mathematical perspective to the
>>>>> paper.
>>>>>
>>>>> - The structure of the paper completely changed in the new revision,
>>>>> so now it’s hard to understand what and why they have done
>>>>>
>>>>> - Another missing part is discussion of graph invariants
>>>>>
>>>>> Tom (Deakin): There’s a big missing part in “Prior art” part,
>>>>> GraphBLAS (https://graphblas.org
>>>>> <https://urldefense.com/v3/__https://graphblas.org__;!!K-Hz7m0Vt54!lEMnRbkdjKfReFDkvhwE2zDloIG-JEOwnu8lyeH-nsfm4K0in2mS-TkcBdVd2CoVCH3WLh8DX360WQc$>)
>>>>> eminently.
>>>>>
>>>>> Best wishes,
>>>>> Roger.
>>>>>
>>>> --
>>>> SG19 mailing list
>>>> SG19_at_[hidden]
>>>> https://lists.isocpp.org/mailman/listinfo.cgi/sg19
>>>> <https://urldefense.com/v3/__https://lists.isocpp.org/mailman/listinfo.cgi/sg19__;!!K-Hz7m0Vt54!lEMnRbkdjKfReFDkvhwE2zDloIG-JEOwnu8lyeH-nsfm4K0in2mS-TkcBdVd2CoVCH3WLh8DGEl61LA$>
>>>>
>>> --
>>> SG19 mailing list
>>> SG19_at_[hidden]
>>>
>>> https://urldefense.com/v3/__https://lists.isocpp.org/mailman/listinfo.cgi/sg19__;!!K-Hz7m0Vt54!lEMnRbkdjKfReFDkvhwE2zDloIG-JEOwnu8lyeH-nsfm4K0in2mS-TkcBdVd2CoVCH3WLh8DGEl61LA$
>>>
>>>
>>
Received on 2024-01-11 22:17:20