On Wed, Jun 12, 2024 at 12:27 AM Michael Wong <fraggamuffin@gmail.com> wrote:

Hi, this SG19 meeting will focus on Graph Michael Wong is inviting

you to a scheduled Zoom meeting.

Topic: SG19 monthly

Time: 2nd Thursdays 02:00 PM Eastern Time (US and Canada)

Every month on the Second Thu,

Join from PC, Mac, Linux, iOS or Android:

https://iso.zoom.us/j/93084591725?pwd=K3QxZjJlcnljaE13ZWU5cTlLNkx0Zz09

Password: 035530

Or iPhone one-tap :

US: +13017158592,,93084591725# or +13126266799,,93084591725#

Or Telephone:

Dial(for higher quality, dial a number based on your current location):

US: +1 301 715 8592 or +1 312 626 6799 or +1 346 248 7799 or +1

408 638 0968 or +1 646 876 9923 or +1 669 900 6833 or +1 253 215 8782

or 877 853 5247 (Toll Free)

Meeting ID: 930 8459 1725

Password: 035530

International numbers available: https://iso.zoom.us/u/agewu4X97

Or Skype for Business (Lync):

https://iso.zoom.us/skype/93084591725

Agenda:

1. Opening and introductions

The ISO Code of conduct:

https://www.iso.org/files/live/sites/isoorg/files/store/en/PUB100397.pdf

IEC Code of Conduct:

https://www.iec.ch/basecamp/iec-code-conduct-technical-work

ISO patent policy.

https://isotc.iso.org/livelink/livelink/fetch/2000/2122/3770791/Common_Policy.htm?nodeid=6344764&vernum=-2

The WG21 Practices and Procedures and Code of Conduct:

https://isocpp.org/std/standing-documents/sd-4-wg21-practices-and-procedures

1.1 Roll call of participants

Phil, Boguslaw, Guy, Oliver, Richard, Michael, ANdrew, Jens, Scott

1.2 Adopt agenda

1.3 Approve minutes from previous meeting, and approve publishing

previously approved minutes to ISOCPP.org

1.4 Action items from previous meetings

2. Main issues (125 min)

2.1 General logistics

Meeting plan, focus on one paper per meeting but does not preclude other

paper

updates.

2024 planning

C++23 and C++26 statusCPPCON 2024

Schedule for Graph to go out

June 24: St. Louis

July 11

Aug 15

Sept 12: exit vote

Sept 15-20 CPPCON meeting

OCt 10: exit vote, last chance

Nov 14: Not possible

else

2025-02-10 to 15: Hagenberg, Austria; University of Applied Sciences, Upper Austria

* Jan 11, 2024 02:00 PM ET: Graph DONE

* Feb 8, 2024 02:00 PM ET: Graph DONE

* Mar 14, 2024 02:00 PM ET: Cancelled due to Tokyo 3-18-23

* Apr 11, 2024 02:00 PM ET: Stats/Graph DONE

* May 9, 2024 02:00 PM ET: Graph DONE

* June 13, 2024 02:00 PM ET: Graph; St.louis 6-24-29

* July 11, 2024 02:00 PM ET: Stats

* Aug 15, 2024 02:00 PM ET: Graph

* Sep 12, 2024 02:00 PM ET: CPPCON Sept 15-20 so canceled

* Oct 10, 2024 02:00 PM ET: Stats

* Nov 14, 2024 02:00 PM ET: Cancelled Wroclaw F2F

* Dec 12, 2024 02:00 PM ET: Graph

ISO meeting status

future C++ Std meetings

2.2 Paper reviews

SG6 feedback pre-St.Louis 2024:

| 11:41 AM (2 hours ago) | |||

Hi Phil,

sorry for picking this back up only now. But I reviewed P3131 and P3130 again

and still don't see anything *in the papers* that requires review by SG6.

You mention CSR in P3131, but if I understand correctly, the paper only uses

it as an implementation detail, not as a library facility exposed to C++

users. There may well be topics that warrant discussion in SG6, but I don't

see them written up. If there are topics/questions related to your papers that

you want to raise in SG6, please put them in the paper(s). I find it

especially helpful if you paper points out the feedback you need and the

challenges that you believe need to be reviewed.

So for now I continue to believe that there is nothing for SG6 to review. And

I don't mean the topic in general — I mean the specific papers.

I hope this helps,

Matthias

On Dienstag, 19. März 2024 23:38:33 MESZ Phil Ratzloff wrote:

> compressed_graph (P3131) is an extended version of a CSR matrix. The purpose

> of the discussion is to see if this would be valuable in the context of

> numerics/mathematics. If so, someone would need to take that on and own it

> in collaboration with our effort.

>

> How it is presented would also need to be different than what I've done to

> date.

>

> compressed_graph extends the typical CSR matrix by supporting optional

> values for rows and the compressed_graph object itself. The API for the

> graph is defined as a set of functions that apply to all graphs, defined in

> P3130.

>

> I took this approach to minimize the public interface of compressed_graph,

> as I know containers can take a long time to get through the Committee.

>

> If it were to be used for math-oriented features, I imagine there might need

> to be member functions added, as well as mathematical algorithms that use

> it.

sorry for picking this back up only now. But I reviewed P3131 and P3130 again

and still don't see anything *in the papers* that requires review by SG6.

You mention CSR in P3131, but if I understand correctly, the paper only uses

it as an implementation detail, not as a library facility exposed to C++

users. There may well be topics that warrant discussion in SG6, but I don't

see them written up. If there are topics/questions related to your papers that

you want to raise in SG6, please put them in the paper(s). I find it

especially helpful if you paper points out the feedback you need and the

challenges that you believe need to be reviewed.

So for now I continue to believe that there is nothing for SG6 to review. And

I don't mean the topic in general — I mean the specific papers.

I hope this helps,

Matthias

On Dienstag, 19. März 2024 23:38:33 MESZ Phil Ratzloff wrote:

> compressed_graph (P3131) is an extended version of a CSR matrix. The purpose

> of the discussion is to see if this would be valuable in the context of

> numerics/mathematics. If so, someone would need to take that on and own it

> in collaboration with our effort.

>

> How it is presented would also need to be different than what I've done to

> date.

>

> compressed_graph extends the typical CSR matrix by supporting optional

> values for rows and the compressed_graph object itself. The API for the

> graph is defined as a set of functions that apply to all graphs, defined in

> P3130.

>

> I took this approach to minimize the public interface of compressed_graph,

> as I know containers can take a long time to get through the Committee.

>

> If it were to be used for math-oriented features, I imagine there might need

> to be member functions added, as well as mathematical algorithms that use

> it.

Review BSI Graph feedback:

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.

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?

2.2.1: ML topics

2.2.1.1 Graph Proposal Phil Ratsloff et al

D3127 terminology

Andrew presenting

pg 3: terminology can we claw back

4: rarely a distinction between graph and graph terminology

8: OR: add multiple edges (pair of nodes connected by 2 or more edges)

Figure 3 mentions instagram

This is an R1: should add a table of what is delta with R0

10: JM: partition graph: V should add vn1-1 looks wrong, so its 2 level of subscripting so need to fix the latex

11: typo

12: OR: represent currents, flow networks, circuits, deserves mention of direction of current or if it is positive or negative; library needs to support it because it is difficult; not scope creep, but fundamental; representing them is subtle

JM: disagree, can do route finding without flow network, is enough

AL+OR: need to work through examples to get the building blocks

JM: different dimension of design, flow network is not a good example to explain these terms, use something else; do the flow network in another paper

OR: disagree, the necessity of these terms is revealed by this paper; how to categorize a structure for flow network

AL: we call it multigraph for flow network, not structural, cant enforce at compile time

OR: direct representation vs adjacency lists should be separate, not conflated; section 10. should not have adjacency list

JM: dont introduce arc now

OR: Pure connectivity has no representation; OK

AL: will remove circuit

Appendix:

OR: data to graph do we need this at all

AL: like to avoid the property map dependency; JM: not sure what the abstraction layer is for Djkstra

PR: current abstraction is a concept of property on a graph, edge, vertex, so tuple is property on the edge, inside algo there are multiple values, caller to Djkstra knows which graph and provides a function to extract the correct distance

AL: add a djkstra example

OR: start with vertex, list of edges, tuple of properties

what is the property referring to?

AL: property represents circuit element, the current, the conductance, that is associated with the edge

PR: to make this compile, need a second argument on the vector

AL: yes I see

JM: vertex needs a template argument

OR dont like direct representation, it will be templated on vertex and edge weight, vertex should not know edge weight; its not the cleanest design

AL: template on edge type? OK

JM: should this be super generic graph data structure

PR:P3131 has a definition for compressed graph

JM: template on edge and vertex wright and everyhting else is impl detail

PR: can reduce internal size of graph

OR: cover vector of vector

AL: should pass that into Djkstra

PR: now you can

OR: adjacency lists is unstructured, but there are large patches that are structured, use template param to optimize these structures through customization

PR: depends on who is creating the data structure; have range of ranges and how you represent that range is upto you

impl is in P3131 and it is a CSR but there could be additional

PR: how customizable should it be; want to have 1 thats good, then more can come later

JM: containers are complex to get through LEWG; how detail should the spec be, or impl leeway

it should support all the algorithms in the paper but not arbitrary

PR: design to adapt existing containers

I am just providing are constructors, everything else use public interface

P303 are all CPO public fns, gives back a range

your own graph datastructure can override the CPOs

What about negative edges, cycles, DAG

contains the list of issues at bottom

Agree on a graph DS but does not preclude other algo; needs to be trimmed down

another paper needed: Comparison of BGL with our Graph

Latest paper:

Here’s a link to the paper (different than the previous paper reviewed).

There are some additional updates I’m planning on making before the meeting.

https://docs.google.com/document/d/1OpH-xxRri7tJTtJJIZTYmSHkkrZJkdBwm9zJ7LqolfQ/edit?usp=sharing

P1709R3:

https://docs.google.com/document/d/1kLHhbSTX7j0tPeTYECQFSNx3R35Mu3xO5_dyYdRy4dM/edit?usp=sharing

https://docs.google.com/document/d/1QkfDzGyfNQKs86y053M0YHOLP6frzhTJqzg1Ug_vkkE/edit?usp=sharing

<http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p2119r0.html>

<

https://docs.google.com/document/d/175wIm8o4BNGti0WLq8U6uZORegKVjmnpfc-_E8PoGS0/edit?ts=5fff27cd#heading=h.9ogkehmdmtel

*>*

Array copy semantics:

array copy-semantics paper P1997 "Relaxing Restrictions on Arrays",

https://wg21.link/p1997

Stats feedback:

P1708:

Added ISO references

OR: Erroneous instead of unspecified as another alternative is more specific and less ambiguous

P2376R0

<http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p2376r0.pdf>

Comments

on Simple Statistical Functions (p1708r4): Contracts, Exceptions and

Special cases Johan Lundberg

2.2.1.2 Reinforcement Learning Larry Lewis Jorge Silva

Reinforcement Learning proposal:

2.2.1.3 Differential Calculus:

https://docs.google.com/document/d/175wIm8o4BNGti0WLq8U6uZORegKVjmnpfc-_E8PoGS0/edit?ts=5fff27cd#heading=h.9ogkehmdmtel

2.2.1.4: Stats paper

P2681R0

<https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p2681r0.pdf> More

Stats Functions Richard Dosselmann, Michael Wong

Current github

https://github.com/cplusplus/papers/issues/475

https://github.com/cplusplus/papers/issues/979

Stats review Richard Dosselman et al

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p1708r4.pdf

Feedback from Johan Lundberg and Oleksandr Korval

https://isocpp.org/files/papers/D2376R0.pdf

P1708R3: Math proposal for Machine Learning: 3rd review

PXXXX: combinatorics: 1st Review

*> std.org/jtc1/sc22/wg21/docs/papers/2020/p1708r2

<http://std.org/jtc1/sc22/wg21/docs/papers/2020/p1708r2>*

*> above is the stats paper that was reviewed in Prague*

*> http://wiki.edg.com/bin/view/Wg21prague/P1708R2SG19

<http://wiki.edg.com/bin/view/Wg21prague/P1708R2SG19>*

*>*

*> Review Jolanta Polish feedback.*

*> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p2119r0.html

<http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p2119r0.html>*

2.2.1.4: Matrix paper

2.2.3 any other proposal for reviews?

2.3 Other Papers and proposals

P1416R1: SG19 - Linear Algebra for Data Science and Machine Learning

https://docs.google.com/document/d/1IKUNiUhBgRURW-UkspK7fAAyIhfXuMxjk7xKikK4Yp8/edit#heading=h.tj9hitg7dbtr

P1415: Machine Learning Layered list

https://docs.google.com/document/d/1elNFdIXWoetbxjO1OKol_Wj8fyi4Z4hogfj5tLVSj64/edit#heading=h.tj9hitg7dbtr

2.2.2 SG14 Linear Algebra progress:

Different layers of proposal

https://docs.google.com/document/d/1poXfr7mUPovJC9ZQ5SDVM_1Nb6oYAXlK_d0ljdUAtSQ/edit

2.5 Future F2F meetings:

2.6 future C++ Standard meetings:

https://isocpp.org/std/meetings-and-participation/upcoming-meetings

None

3. Any other business

New reflector

http://lists.isocpp.org/mailman/listinfo.cgi/sg19

Old Reflector

https://groups.google.com/a/isocpp.org/forum/#!newtopic/sg19

<https://groups.google.com/a/isocpp.org/forum/?fromgroups=#!forum/sg14>

Code and proposal Staging area

4. Review

4.1 Review and approve resolutions and issues [e.g., changes to SG's

working draft]

4.2 Review action items (5 min)

5. Closing process

5.1 Establish next agenda

5.2 Future meeting

* Jan 11, 2024 02:00 PM ET: Graph DONE

* Feb 8, 2024 02:00 PM ET: Graph DONE

* Mar 14, 2024 02:00 PM ET: Cancelled due to Tokyo 3-18-23

* Apr 11, 2024 02:00 PM ET: Stats/Graph DONE

* May 9, 2024 02:00 PM ET: Graph DONE

* June 13, 2024 02:00 PM ET: Graph; St.louis 6-24-29

* July 11, 2024 02:00 PM ET: Stats

* Aug 15, 2024 02:00 PM ET: Graph

* Sep 12, 2024 02:00 PM ET: CPPCON Sept 15-20 so cancelled

* Oct 10, 2024 02:00 PM ET: Stats

* Nov 14, 2024 02:00 PM ET: Cancelled Wroclaw F2F

* Dec 12, 2024 02:00 PM ET: Graph