C++ Logo

sg19

Advanced search

Re: [isocpp-sg19] SG19 June 13 2024 Monthly call

From: Michael Wong <fraggamuffin_at_[hidden]>
Date: Thu, 13 Jun 2024 15:57:01 -0400
On Wed, Jun 12, 2024 at 12:27 AM Michael Wong <fraggamuffin_at_[hidden]>
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 status
> CPPCON 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

2024-11-18 to 23: Wrocław, Poland
<https://isocpp.org/files/papers/N4974.pdf>; Nokia
else
2025-02-10 to 15: Hagenberg, Austria
<https://isocpp.org/files/papers/N4979.pdf>; 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:
Matthias Kretz
11:41 AM (2 hours ago)
to Phil, me, Lisa
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.


>
> 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

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3126r1.pdf
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
>

Received on 2024-06-13 19:57:18