Date: Fri, 10 May 2024 13:34:12 +0000
In yesterday’s SG19 meeting Michael asked that I collect our comments into the P3126 Overview paper. This will help us keep track of the open issues and give more visibility to a wider audience. That will come out in the next mailing after May 22.
I think many of the comments apply to the P3127 Background and Terminology paper. I haven’t seen any changes to that yet and don’t know if it will be updated for the mailing.
It also gives me a chance to respond to one of your comments:
>>> I don't think I expressed myself very well here. I completely take your point about not assuming that vertices are in a random-access range. But what I'm trying to get at is as follows. Suppose someone standardizes unstructured span, as a natural extension of mdspan. What could we learn from its api that may be relevant for graphs? In both cases, we will presumably have a method which allows iteration over the ith partition (or edges of a given node, for graphs). Consistency of the stl may mean we want these to have the same look/feel.
That’s making more sense to me. I think the unstructured span would have the best application for an adjacency list. Is there anything you can point me to for an example?
I think a big part of those designs are support for operator[] and there’s been some debate on that internally. We might be able to create an interface on top of the existing design to provide something that’s more like an unstructured span (if I understand it correctly). We could even do that for vertices stored in map, and if the caller attempts to access an id that doesn’t exist we’d through an exception rather than adding a new element.
I would take that approach rather than trying to use that as the underlying fundamental data model described in P3130 Graph Container Interface because I’m concerned it wouldn’t support existing features. The features that come to mind right away are supporting properties on vertices, or being able to easily adapt to pre-existing graph data structures outside of the standard. There may be others features I haven’t thought of.
I can also look at mdspan for inspiration. If you have any other specific things in mind, please share.
This is a lower priority for me compared to the other things we’ve discussed.
From: SG19 <sg19-bounces_at_[hidden]> On Behalf Of Oliver Rosten via SG19
Sent: Tuesday, April 16, 2024 4:43 PM
To: sg19_at_[hidden]cpp.org
Cc: Oliver Rosten <oliver.rosten_at_[hidden]>
Subject: Re: [SG19] Graph library open issues
EXTERNAL
Hi Phil,
Here are some additional thoughts:
1. I don't find the discussion about adjacency matrices helpful, but rather a distraction. It's not that it shouldn't be there in some form, but at the moment it has a prominence which I don't think is commensurate with its importance to the paper, perhaps exacerbated by the fact that the paper lacks many salient details (see point 2).
2. As it stands, the paper lacks a discussion of the authors' standpoint on graph terminology, defining features (e.g. self loops, multi-edges) and the sort of trade-offs you get by allowing/not allowing them. Put another way, I think the paper would be easier to follow if there's a technical narrative that reveals the way the authors are thinking about this huge area. I like the style of the motivation in R5; if this could be greatly extended to include the mathematical background that Andrew is working on, this would be really helpful. And beyond the mathematical background, as discussion of the computational tradeoffs for both graph implementations and the associated algorithms, given certain choice, would be great to have.
3. Fine
4. Fine
5. The summary tables for the algorithms are necessary but not sufficient.
a. There needs to be a discussion of these aspects for graph implementations themselves. Various graph operations may be more efficient if the graph structure is more constrained. However, not allowing e.g. multiple edges between pairs of nodes prohibits representing many useful systems. There are trade-offs and these need to be discussed.
b. A justification of the choices made for the algorithms may be helpful.
6. I think it's very valuable to include electrical circuits in addition to a simpler example. As we've discussed, electrical circuits are surprisingly subtle to represent using graphs, but I think users of a graph library should rightly expect that it can be elegantly done. I think signs of a good design for std::graph is that people can do this. So I think electrical circuits should stay in, in all their glory, but complemented by something less subtle.
7. Fine
8. Fine
Resolved issues:
I don't think I expressed myself very well here. I completely take your point about not assuming that vertices are in a random-access range. But what I'm trying to get at is as follows. Suppose someone standardizes unstructured span, as a natural extension of mdspan. What could we learn from its api that may be relevant for graphs? In both cases, we will presumably have a method which allows iteration over the ith partition (or edges of a given node, for graphs). Consistency of the stl may mean we want these to have the same look/feel.
Oliver
On Wed, 10 Apr 2024 at 18:52, Michael Wong via SG19 <sg19_at_[hidden]<mailto:sg19_at_[hidden]>> wrote:
Thank you, I actually also want the list of issues from Andrew as well, whether there is a solution or not, its best to list it out. Please.
On Wed, Apr 10, 2024 at 1:39 PM Phil Ratzloff via SG19 <sg19_at_[hidden]<mailto:sg19_at_[hidden]>> wrote:
Michael suggested I list the issues identified by Oliver, which I’ve identified below.
In addition to the items listed, we also know we need to refine the definition of the edgelist concepts.
Oliver indicated there may be more things, so this will likely be an incremental process to refine the proposal.
Since the original comments, P1709 has been split into multiple papers numbered P3126..P3131 consecutively. They follow the same structure as P1709 with the chapters being made individual papers.
Open Issues
1. “[P1709] has lots of details which I think to be irrelevant”
* Need clarification.
1. "Very hard to follow" mentioned 2x.
* It’s presented as a series of layers in the library. Need clarification on what makes it difficult.
1. 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?
* We never had any comparisons to BGL.
* Andrew is planning on adding a new paper to compare graph-v2 with BGL.
1. “We need to add a mathematical perspective to the paper.”
* P3127 was created from the Background chapter in P1709 and was intended for the mathematical background.
* Andrew is planning extending P3127 to include a more rigorous mathematical description. We would like to have an independent review when it’s ready.
1. “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.”
* The current version of P3128 Algorithms has a summary table for each algorithm that includes Complexity, Directed?, Multi-edge?, Cycles?, Self-loops?, and Throws?. We still need to make a pass through the algorithms to assure the values are correct.
1. The electrical circuit example has issues in P3127, section 6.1.
* Andrew has acknowledged this and will replace it with a better example.
1. A concern is that the DFS and BFS functionality isn’t flexible enough, especially when compared to boost::graph’s visitors.
* We’ve agreed to provide more flexible versions of BFS & DFS.
* Phil is researching coroutines as an alternative.
i. Oliver likes the examples I’ve shown but has also pointed out coroutines can’t be constexpr. Because of that, he would also like visitors included.
ii. Guy said that coroutines might raise concerns as a “novel” approach by LEWG.
iii. There are open questions about performance differences between the use of coroutines vs. visitors we will be investigating.
1. “I'm not convinced by the load api.”
* Phil: I’m not either. I’ll re-examine this to see if I can expand the list of constructors in compressed_graph so the load functions can be removed.
Resolved Issues
1. “build on mdspan and try to standardize (or at least understand) what might reasonably be called an unstructured span”
* Assumes vertices are in a random-access range and prevents the use of bi-directed ranges like std::map, which could be used for sparse vertex ids. The existing design should be able to adept easily to mdspan, so there’s no reason to pursue this.
--
SG19 mailing list
SG19_at_[hidden]<mailto:SG19_at_[hidden]>
https://lists.isocpp.org/mailman/listinfo.cgi/sg19<https://protect.checkpoint.com/v2/___https://lists.isocpp.org/mailman/listinfo.cgi/sg19___.YzJ1OnNhc2luc3RpdHV0ZTpjOm86NDExYzlhYzU4ZWZiZTJkNzZmYjQwNGMxOTVhYTc4OTI6NjplYmEwOmE1MmFiYWVkOTU2ZDU2MmZkODJhNzEwZTEyNzJjYTAxYjE1Y2Y5YmE5MWZmNjFiNGVhM2VjZWFiYjZkNTQxMGQ6aDpU>
--
SG19 mailing list
SG19_at_[hidden]<mailto:SG19_at_[hidden]>
https://lists.isocpp.org/mailman/listinfo.cgi/sg19<https://protect.checkpoint.com/v2/___https://lists.isocpp.org/mailman/listinfo.cgi/sg19___.YzJ1OnNhc2luc3RpdHV0ZTpjOm86NDExYzlhYzU4ZWZiZTJkNzZmYjQwNGMxOTVhYTc4OTI6NjoyN2U2OjRiNzI1NzMzMTIxODEwNDBjNWE2OTA4OGMwNmU3YjIzMTVkZWQyNzA2MzMzOTgwNDNkMWMyZWQ4ODNiYTM5ODc6aDpU>
I think many of the comments apply to the P3127 Background and Terminology paper. I haven’t seen any changes to that yet and don’t know if it will be updated for the mailing.
It also gives me a chance to respond to one of your comments:
>>> I don't think I expressed myself very well here. I completely take your point about not assuming that vertices are in a random-access range. But what I'm trying to get at is as follows. Suppose someone standardizes unstructured span, as a natural extension of mdspan. What could we learn from its api that may be relevant for graphs? In both cases, we will presumably have a method which allows iteration over the ith partition (or edges of a given node, for graphs). Consistency of the stl may mean we want these to have the same look/feel.
That’s making more sense to me. I think the unstructured span would have the best application for an adjacency list. Is there anything you can point me to for an example?
I think a big part of those designs are support for operator[] and there’s been some debate on that internally. We might be able to create an interface on top of the existing design to provide something that’s more like an unstructured span (if I understand it correctly). We could even do that for vertices stored in map, and if the caller attempts to access an id that doesn’t exist we’d through an exception rather than adding a new element.
I would take that approach rather than trying to use that as the underlying fundamental data model described in P3130 Graph Container Interface because I’m concerned it wouldn’t support existing features. The features that come to mind right away are supporting properties on vertices, or being able to easily adapt to pre-existing graph data structures outside of the standard. There may be others features I haven’t thought of.
I can also look at mdspan for inspiration. If you have any other specific things in mind, please share.
This is a lower priority for me compared to the other things we’ve discussed.
From: SG19 <sg19-bounces_at_[hidden]> On Behalf Of Oliver Rosten via SG19
Sent: Tuesday, April 16, 2024 4:43 PM
To: sg19_at_[hidden]cpp.org
Cc: Oliver Rosten <oliver.rosten_at_[hidden]>
Subject: Re: [SG19] Graph library open issues
EXTERNAL
Hi Phil,
Here are some additional thoughts:
1. I don't find the discussion about adjacency matrices helpful, but rather a distraction. It's not that it shouldn't be there in some form, but at the moment it has a prominence which I don't think is commensurate with its importance to the paper, perhaps exacerbated by the fact that the paper lacks many salient details (see point 2).
2. As it stands, the paper lacks a discussion of the authors' standpoint on graph terminology, defining features (e.g. self loops, multi-edges) and the sort of trade-offs you get by allowing/not allowing them. Put another way, I think the paper would be easier to follow if there's a technical narrative that reveals the way the authors are thinking about this huge area. I like the style of the motivation in R5; if this could be greatly extended to include the mathematical background that Andrew is working on, this would be really helpful. And beyond the mathematical background, as discussion of the computational tradeoffs for both graph implementations and the associated algorithms, given certain choice, would be great to have.
3. Fine
4. Fine
5. The summary tables for the algorithms are necessary but not sufficient.
a. There needs to be a discussion of these aspects for graph implementations themselves. Various graph operations may be more efficient if the graph structure is more constrained. However, not allowing e.g. multiple edges between pairs of nodes prohibits representing many useful systems. There are trade-offs and these need to be discussed.
b. A justification of the choices made for the algorithms may be helpful.
6. I think it's very valuable to include electrical circuits in addition to a simpler example. As we've discussed, electrical circuits are surprisingly subtle to represent using graphs, but I think users of a graph library should rightly expect that it can be elegantly done. I think signs of a good design for std::graph is that people can do this. So I think electrical circuits should stay in, in all their glory, but complemented by something less subtle.
7. Fine
8. Fine
Resolved issues:
I don't think I expressed myself very well here. I completely take your point about not assuming that vertices are in a random-access range. But what I'm trying to get at is as follows. Suppose someone standardizes unstructured span, as a natural extension of mdspan. What could we learn from its api that may be relevant for graphs? In both cases, we will presumably have a method which allows iteration over the ith partition (or edges of a given node, for graphs). Consistency of the stl may mean we want these to have the same look/feel.
Oliver
On Wed, 10 Apr 2024 at 18:52, Michael Wong via SG19 <sg19_at_[hidden]<mailto:sg19_at_[hidden]>> wrote:
Thank you, I actually also want the list of issues from Andrew as well, whether there is a solution or not, its best to list it out. Please.
On Wed, Apr 10, 2024 at 1:39 PM Phil Ratzloff via SG19 <sg19_at_[hidden]<mailto:sg19_at_[hidden]>> wrote:
Michael suggested I list the issues identified by Oliver, which I’ve identified below.
In addition to the items listed, we also know we need to refine the definition of the edgelist concepts.
Oliver indicated there may be more things, so this will likely be an incremental process to refine the proposal.
Since the original comments, P1709 has been split into multiple papers numbered P3126..P3131 consecutively. They follow the same structure as P1709 with the chapters being made individual papers.
Open Issues
1. “[P1709] has lots of details which I think to be irrelevant”
* Need clarification.
1. "Very hard to follow" mentioned 2x.
* It’s presented as a series of layers in the library. Need clarification on what makes it difficult.
1. 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?
* We never had any comparisons to BGL.
* Andrew is planning on adding a new paper to compare graph-v2 with BGL.
1. “We need to add a mathematical perspective to the paper.”
* P3127 was created from the Background chapter in P1709 and was intended for the mathematical background.
* Andrew is planning extending P3127 to include a more rigorous mathematical description. We would like to have an independent review when it’s ready.
1. “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.”
* The current version of P3128 Algorithms has a summary table for each algorithm that includes Complexity, Directed?, Multi-edge?, Cycles?, Self-loops?, and Throws?. We still need to make a pass through the algorithms to assure the values are correct.
1. The electrical circuit example has issues in P3127, section 6.1.
* Andrew has acknowledged this and will replace it with a better example.
1. A concern is that the DFS and BFS functionality isn’t flexible enough, especially when compared to boost::graph’s visitors.
* We’ve agreed to provide more flexible versions of BFS & DFS.
* Phil is researching coroutines as an alternative.
i. Oliver likes the examples I’ve shown but has also pointed out coroutines can’t be constexpr. Because of that, he would also like visitors included.
ii. Guy said that coroutines might raise concerns as a “novel” approach by LEWG.
iii. There are open questions about performance differences between the use of coroutines vs. visitors we will be investigating.
1. “I'm not convinced by the load api.”
* Phil: I’m not either. I’ll re-examine this to see if I can expand the list of constructors in compressed_graph so the load functions can be removed.
Resolved Issues
1. “build on mdspan and try to standardize (or at least understand) what might reasonably be called an unstructured span”
* Assumes vertices are in a random-access range and prevents the use of bi-directed ranges like std::map, which could be used for sparse vertex ids. The existing design should be able to adept easily to mdspan, so there’s no reason to pursue this.
--
SG19 mailing list
SG19_at_[hidden]<mailto:SG19_at_[hidden]>
https://lists.isocpp.org/mailman/listinfo.cgi/sg19<https://protect.checkpoint.com/v2/___https://lists.isocpp.org/mailman/listinfo.cgi/sg19___.YzJ1OnNhc2luc3RpdHV0ZTpjOm86NDExYzlhYzU4ZWZiZTJkNzZmYjQwNGMxOTVhYTc4OTI6NjplYmEwOmE1MmFiYWVkOTU2ZDU2MmZkODJhNzEwZTEyNzJjYTAxYjE1Y2Y5YmE5MWZmNjFiNGVhM2VjZWFiYjZkNTQxMGQ6aDpU>
--
SG19 mailing list
SG19_at_[hidden]<mailto:SG19_at_[hidden]>
https://lists.isocpp.org/mailman/listinfo.cgi/sg19<https://protect.checkpoint.com/v2/___https://lists.isocpp.org/mailman/listinfo.cgi/sg19___.YzJ1OnNhc2luc3RpdHV0ZTpjOm86NDExYzlhYzU4ZWZiZTJkNzZmYjQwNGMxOTVhYTc4OTI6NjoyN2U2OjRiNzI1NzMzMTIxODEwNDBjNWE2OTA4OGMwNmU3YjIzMTVkZWQyNzA2MzMzOTgwNDNkMWMyZWQ4ODNiYTM5ODc6aDpU>
Received on 2024-05-10 13:34:19