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]>
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]> 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”
>> 1. Need clarification.
>> 2. "Very hard to follow" mentioned 2x.
>> 1. It’s presented as a series of layers in the library. Need
>> clarification on what makes it difficult.
>> 3. 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?
>> 1. We never had any comparisons to BGL.
>> 2. Andrew is planning on adding a new paper to compare graph-v2
>> with BGL.
>> 4. “We need to add a mathematical perspective to the paper.”
>> 1. P3127 was created from the Background chapter in P1709 and was
>> intended for the mathematical background.
>> 2. Andrew is planning extending P3127 to include a more rigorous
>> mathematical description. We would like to have an independent review when
>> it’s ready.
>> 5. “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.”
>> 1. 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.
>> 6. The electrical circuit example has issues in P3127, section 6.1.
>> 1. Andrew has acknowledged this and will replace it with a better
>> example.
>> 7. A concern is that the DFS and BFS functionality isn’t flexible
>> enough, especially when compared to boost::graph’s visitors.
>> 1. We’ve agreed to provide more flexible versions of BFS & DFS.
>> 2. 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.
>>
>> 8. “I'm not convinced by the load api.”
>> 1. 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”
>> 1. 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]
>> https://lists.isocpp.org/mailman/listinfo.cgi/sg19
>>
> --
> SG19 mailing list
> SG19_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/sg19
>