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