Date: Tue, 9 Jan 2024 17:50:52 +0000

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.

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.

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.

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.

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!

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) eminently.

>>

>> Best wishes,

>> Roger.

>>

> --

> SG19 mailing list

> SG19_at_[hidden]

> https://lists.isocpp.org/mailman/listinfo.cgi/sg19

>

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.

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.

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.

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.

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!

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) eminently.

>>

>> Best wishes,

>> Roger.

>>

> --

> SG19 mailing list

> SG19_at_[hidden]

> https://lists.isocpp.org/mailman/listinfo.cgi/sg19

>

Received on 2024-01-09 17:51:05