Date: Mon, 12 May 2025 12:40:38 -0400
On Tue, May 6, 2025 at 11:44 AM Michael Wong <fraggamuffin_at_[hidden]> wrote:
> Hi all, from the notes to the Apr 10th meeting now that all papers have
> been published in the April mailing. We wishes to take a vote on these
> papers to exit SG19 to head to LEWG. Please prepare accordingly. Thank you.
>
> The group reviewed updates to five papers, focusing on descriptors in
> graph algorithms, which reduce interface complexity and improve
> performance. They also discussed the implementation of accumulator objects
> for statistical functions, considering compile-time configuration to avoid
> runtime overhead. The need for further experimentation and potential delay
> of the accumulator to a second paper was suggested. The meeting concluded
> with plans to publish updated papers by April 15 for a potential vote in
> May.
> Action Items
>
> - [ ] Publish the updated papers by this weekend so they can be
> reviewed before the next meeting.
> - [ ] Perform a final review to ensure any internal comments are
> removed from the published papers.
> - [ ] Provide the updated paper versions to the group for further
> review and feedback.
> - [ ] We intend to put these papers to a vote to exit SG19 in the May
> 8th SG19 meeting based on the updated papers from updates for the
> graph proposal that have been added to the 2025-04 mailing (ISO/IEC
> JTC1/SC22/WG21 - Papers 2025
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/>). Feedback
> welcome.
> -
> P3126R3
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3126r3.pdf> Graph
> Library: Overview Phil Ratzloff, Andrew Lumsdaine 2025-04-13 2025-04
> P3126R2
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3126r2.pdf> SG14
> Low Latency,SG19 Machine Learning
> P3127R1
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3127r1.pdf> Graph
> Library: Background and Terminology Phil Ratzloff, Andrew Lumsdaine
> 2025-04-13 2025-04 P3127R0
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3127r0.pdf> SG14
> Low Latency,SG19 Machine Learning
> P3128R3
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3128r3.pdf> Graph
> Library: Algorithms Phil Ratzloff, Andrew Lumsdaine 2025-04-13 2025-04
> P3128R2
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3128r2.pdf> SG14
> Low Latency,SG19 Machine Learning
> P3129R1
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3129r1.pdf> Graph
> Library: Views Phil Ratzloff, Andrew Lumsdaine 2025-04-13 2025-04
> P3129R0
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3129r0.pdf> SG14
> Low Latency,SG19 Machine Learning
> P3130R3
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3130r3.pdf> Graph
> Library: Graph Container Interface Phil Ratzloff, Andrew Lumsdaine
> 2025-04-13 2025-04 P3130R2
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3130r2.pdf> SG14
> Low Latency,SG19 Machine Learning
> P3131R3
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3131r3.pdf> Graph
> Library: Graph Containers Phil Ratzloff, Andrew Lumsdaine 2025-04-13
> 2025-04 P3131R2
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3131r2.pdf> SG14
> Low Latency,SG19 Machine Learning
>
>
> 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
>
Richard, Oliver, Andrew, Scott, Jens, Andrzej, Michael, Michael L
>
>
> 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
>
>
>
>
> * Jan 9, 2025 02:00 PM ET: Cancelled
> * Feb 13, 2025 02:00 PM ET: Hagenberg F2F; Cancelled
> * Mar 13, 2025 02:00 PM ET: Graph
> * Apr 10, 2025 02:00 PM ET: Stats
> * May 8, 2025 02:00 PM ET: Graph
> * June 12, 2025 02:00 PM ET: Stats
> * July 10, 2025 02:00 PM ET: Graphs
> * Aug 14, 2025 02:00 PM ET: Stats
> * Sep 11, 2025 02:00 PM ET: Graph, CPPCON
> * Oct 9, 2025 02:00 PM ET: Stats
> * Nov 13, 2025 02:00 PM ET: Graph
> * Dec 11, 2025 02:00 PM ET: Stats
>
>
> ISO meeting status
>
> future C++ Std meetings
>
> 2.2 Paper reviews
>
Action Items
- [ ] Address the list of comments and issues raised on the terminology
paper.
- [ ] Clarify the definition of "graph" and the assumptions/requirements
around self-loops, multi-graphs, etc.
- [ ] Revisit the design of the "edge info" struct to simplify it and
ensure the concepts match the actual usage.
- [ ] Provide more rationale for the flexibility and generality of the
"edge info" design.
- [ ] Review the remaining papers (algorithms, views, containers) in
detail and provide feedback.
- [ ] Determine the appropriate path forward for gaining broader
community feedback and implementation experience, such as a Technical
Specification or a White Paper.
OutlineGraph Library Overview and Design Principles
- Phil introduces the concept of the shortest path algorithm as a
representative example of an algorithm.
- Andrew presents the background and terminology of the graph library,
emphasizing its lightweight design and compatibility with existing standard
library containers.
- The graph library aims to leverage existing algorithms and concepts
from C++20 and C++23, including algorithms, concepts, graph interface API,
and views.
- Andrew discusses the motivation behind views, which were developed
to modernize and clean up the Boost Graph Library (BGL), making it more
accessible to users.
Graph Library Algorithms and Parallelism
- Andrew explains the tension between graph problems and algorithms,
noting that different algorithms are used depending on the situation.
- The graph library focuses on commonly used and requested algorithms,
such as the Six Degrees of Kevin Bacon example, which uses a breadth-first
search (BFS) view.
- Michael interrupts to correct the example code, which uses a practical
search instead of BFS, and clarifies that the edges represent costar
relationships.
- Oliver suggests adding a diagram to help uninitiated people understand
the example better.
- Andrew provides a brief history of the Six Degrees of Kevin Bacon
concept, explaining its connection to the Milgram experiment.
Graph Library Standardization and Related Standards
- Andrew mentions the impact of the graph library on the standard and
its relationship with NW graph, BGL, and GraphLaws.
- Oliver raises concerns about the introduction section, suggesting it
needs to convey the unstructured nature of general case graphs more clearly.
- Michael points out a missing section reference and other minor errors
in the document.
- Michael suggests addressing the issues and sending detailed comments
for further review.
Terminology Paper and Graph Representation
- Andrew introduces the terminology paper, aiming to define consistent
vocabulary for graph representations and algorithms.
- The paper differentiates between a graph and its representations, such
as adjacency lists, and explains the runtime properties of directedness and
undirectedness.
- Oliver questions the distinction between directedness and
undirectedness, suggesting that it should be clarified in the paper.
- Andrew explains the transition from vertices and edges to indices in
adjacency lists and the importance of constant or logarithmic time indexing.
- The paper also covers definitions for directed and undirected edges,
neighbors, paths, self-loops, isolated vertices, multi-graphs, and
hypergraphs.
Direct Representation and Electrical Circuits
- Andrew discusses the direct representation, which allows users to
pass graphs directly into algorithms without converting them to other
representations.
- Oliver raises concerns about the representation of electrical
circuits, noting the subtlety of defining positive currents in undirected
graphs.
- Andrew explains that the direct representation does not depend on
the direction of currents, focusing on the topological properties of the
circuit.
- Oliver insists that the paper needs to address the implications of
directedness on representations and solver accuracy.
- Michael Wong agrees that the paper should clearly state how directed
and undirected representations impact solver accuracy and flow analysis.
Visitor Concepts and Algorithms
- Phil introduces the concept of descriptors, which simplify the
interface by consolidating specializations for algorithms.
- The descriptors replace the need for IDs and references, reducing the
number of concepts and views.
- Phil explains the impact of descriptors on the algorithms,
particularly the vertex ID function, which now takes a descriptor instead
of an iterator.
- The paper also includes visitor concepts, which were requested by
Oliver and are similar to those in Boost Graph Library.
- Jens suggests using italics and hyphens for exposition-only concepts
to improve readability and clarity.
Visitor Implementation and Repetition
- Phil discusses the implementation of visitor concepts, which are
taken directly from Boost Graph Library.
- Jens points out the repetition in the vertex info and edge info
structures, suggesting the creation of aliases for common patterns.
- Phil agrees that the repetition could be reduced by defining aliases
for vertex info and edge info.
- Oliver questions the use of void as a value type for vertices,
suggesting that it should be consistent with the graph's definition.
- Phil explains that void is used to allow for flexibility in extracting
values from vertices, but agrees to consider using vertex descriptors
instead.
Future Directions and Implementation Experience
- Phil mentions the potential for getting implementation experience
from a company that plans to use the graph library.
- Oliver expresses concerns about the paper's current state,
suggesting that it needs more time to bed down and gain broader experience.
- Michael Wong proposes the idea of a technical specification (TS) or a
white paper to gain broader feedback and implementation experience.
- Jens suggests that the paper should be presented to the Library
Evolution Working Group (LEWG) for further review and feedback.
- The group agrees to continue iterating on the paper, addressing
comments, and preparing it for a final vote.
Discussion on Design Rationale and Concerns
- Oliver points out that the design has issues with the edge info
struct, which doesn't seem to work as intended, especially with the void
concept.
Problems with Edge Info Struct and Concepts
- Jens explains that the concepts don't check certain configurations of
edge infos, which is a separate concern from the aesthetics of the design.
- agrees that this is a deep concern and mentions that they have
eliminated similar issues for the vertex info.
- Jens notes that they haven't seen actual use of the concepts, so it's
unclear if the problem exists for all edge info constellations.
- inquires if the node case has been solved, and confirms that a single
vertex ID is passed into the function.
Visitor Function and Data Model
- Oliver asks if the visitor expects to have access to the value on the
node, and Jens clarifies that the visitor can use value lookup functions
with the vertex ID.
- agrees that this approach makes sense and suggests passing around the
necessary data instead of passing around the entire struct.
- Phil introduces the concept of the edge info describing the data
model, including source and target IDs, edge descriptors, and optional edge
values.
- Phil explains that the edge info is used throughout the design, in
views, algorithms, and for defining external data loaded into the graph.
Challenges with Edge Value Storage
- questions the necessity of storing edge weights and node weights in
both the edge info struct and the data structures representing the graph.
- Phil suggests that the edge value can be a reference or a pointer,
which doesn't need to be copied in.
- Michael mentions that the next meeting is unlikely to happen next
month due to a face-to-face meeting and encourages online reviews.
- Phil notes that minimal changes are needed for the containers paper,
focusing more on algorithms and views for better understanding.
Conclusion and Next Steps
- Phil agrees and expresses readiness to focus on algorithms and views.
>
>
> For graph, we have a new draft of P3337 Comparison paper that compares the
> library in performance against boost::graph and NWGraph.
>
> If Andrew is able to attend, he should be able to review the changes he's
> made to P3126 and P3127.
>
>
> P3495 from Oliver/Mark
>
> >From Phil: There are updates to the P3126 Overview and P3127 Background
> and
> Terminology papers for the Graph Library. They haven’t been published yet,
> but it would be helpful to get input on them before they’re published.
>
>
>
> Since the changes are a response to Oliver’s concerns, I think Oliver and
> Andrew would need to attend to make it useful to have a session for the
> Graph Library. Unless they want to do that, I think we can send draft
> versions to the reflector, unless there’s a better idea.
>
>
> 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
>
> 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:
>
> 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 9, 2025 02:00 PM ET: Cancelled
> * Feb 13, 2025 02:00 PM ET: Hagenberg F2F; Cancelled
> * Mar 13, 2025 02:00 PM ET: Graph
> * Apr 10, 2025 02:00 PM ET: Stats
> * May 8, 2025 02:00 PM ET: Graph
> * June 12, 2025 02:00 PM ET: Stats
> * July 10, 2025 02:00 PM ET: Graphs
> * Aug 14, 2025 02:00 PM ET: Stats
> * Sep 11, 2025 02:00 PM ET: Graph, CPPCON
> * Oct 9, 2025 02:00 PM ET: Stats
> * Nov 13, 2025 02:00 PM ET: Graph
> * Dec 11, 2025 02:00 PM ET: Stats
>
> Hi all, from the notes to the Apr 10th meeting now that all papers have
> been published in the April mailing. We wishes to take a vote on these
> papers to exit SG19 to head to LEWG. Please prepare accordingly. Thank you.
>
> The group reviewed updates to five papers, focusing on descriptors in
> graph algorithms, which reduce interface complexity and improve
> performance. They also discussed the implementation of accumulator objects
> for statistical functions, considering compile-time configuration to avoid
> runtime overhead. The need for further experimentation and potential delay
> of the accumulator to a second paper was suggested. The meeting concluded
> with plans to publish updated papers by April 15 for a potential vote in
> May.
> Action Items
>
> - [ ] Publish the updated papers by this weekend so they can be
> reviewed before the next meeting.
> - [ ] Perform a final review to ensure any internal comments are
> removed from the published papers.
> - [ ] Provide the updated paper versions to the group for further
> review and feedback.
> - [ ] We intend to put these papers to a vote to exit SG19 in the May
> 8th SG19 meeting based on the updated papers from updates for the
> graph proposal that have been added to the 2025-04 mailing (ISO/IEC
> JTC1/SC22/WG21 - Papers 2025
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/>). Feedback
> welcome.
> -
> P3126R3
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3126r3.pdf> Graph
> Library: Overview Phil Ratzloff, Andrew Lumsdaine 2025-04-13 2025-04
> P3126R2
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3126r2.pdf> SG14
> Low Latency,SG19 Machine Learning
> P3127R1
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3127r1.pdf> Graph
> Library: Background and Terminology Phil Ratzloff, Andrew Lumsdaine
> 2025-04-13 2025-04 P3127R0
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3127r0.pdf> SG14
> Low Latency,SG19 Machine Learning
> P3128R3
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3128r3.pdf> Graph
> Library: Algorithms Phil Ratzloff, Andrew Lumsdaine 2025-04-13 2025-04
> P3128R2
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3128r2.pdf> SG14
> Low Latency,SG19 Machine Learning
> P3129R1
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3129r1.pdf> Graph
> Library: Views Phil Ratzloff, Andrew Lumsdaine 2025-04-13 2025-04
> P3129R0
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3129r0.pdf> SG14
> Low Latency,SG19 Machine Learning
> P3130R3
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3130r3.pdf> Graph
> Library: Graph Container Interface Phil Ratzloff, Andrew Lumsdaine
> 2025-04-13 2025-04 P3130R2
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3130r2.pdf> SG14
> Low Latency,SG19 Machine Learning
> P3131R3
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3131r3.pdf> Graph
> Library: Graph Containers Phil Ratzloff, Andrew Lumsdaine 2025-04-13
> 2025-04 P3131R2
> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3131r2.pdf> SG14
> Low Latency,SG19 Machine Learning
>
>
> 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
>
Richard, Oliver, Andrew, Scott, Jens, Andrzej, Michael, Michael L
>
>
> 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
>
>
>
>
> * Jan 9, 2025 02:00 PM ET: Cancelled
> * Feb 13, 2025 02:00 PM ET: Hagenberg F2F; Cancelled
> * Mar 13, 2025 02:00 PM ET: Graph
> * Apr 10, 2025 02:00 PM ET: Stats
> * May 8, 2025 02:00 PM ET: Graph
> * June 12, 2025 02:00 PM ET: Stats
> * July 10, 2025 02:00 PM ET: Graphs
> * Aug 14, 2025 02:00 PM ET: Stats
> * Sep 11, 2025 02:00 PM ET: Graph, CPPCON
> * Oct 9, 2025 02:00 PM ET: Stats
> * Nov 13, 2025 02:00 PM ET: Graph
> * Dec 11, 2025 02:00 PM ET: Stats
>
>
> ISO meeting status
>
> future C++ Std meetings
>
> 2.2 Paper reviews
>
Action Items
- [ ] Address the list of comments and issues raised on the terminology
paper.
- [ ] Clarify the definition of "graph" and the assumptions/requirements
around self-loops, multi-graphs, etc.
- [ ] Revisit the design of the "edge info" struct to simplify it and
ensure the concepts match the actual usage.
- [ ] Provide more rationale for the flexibility and generality of the
"edge info" design.
- [ ] Review the remaining papers (algorithms, views, containers) in
detail and provide feedback.
- [ ] Determine the appropriate path forward for gaining broader
community feedback and implementation experience, such as a Technical
Specification or a White Paper.
OutlineGraph Library Overview and Design Principles
- Phil introduces the concept of the shortest path algorithm as a
representative example of an algorithm.
- Andrew presents the background and terminology of the graph library,
emphasizing its lightweight design and compatibility with existing standard
library containers.
- The graph library aims to leverage existing algorithms and concepts
from C++20 and C++23, including algorithms, concepts, graph interface API,
and views.
- Andrew discusses the motivation behind views, which were developed
to modernize and clean up the Boost Graph Library (BGL), making it more
accessible to users.
Graph Library Algorithms and Parallelism
- Andrew explains the tension between graph problems and algorithms,
noting that different algorithms are used depending on the situation.
- The graph library focuses on commonly used and requested algorithms,
such as the Six Degrees of Kevin Bacon example, which uses a breadth-first
search (BFS) view.
- Michael interrupts to correct the example code, which uses a practical
search instead of BFS, and clarifies that the edges represent costar
relationships.
- Oliver suggests adding a diagram to help uninitiated people understand
the example better.
- Andrew provides a brief history of the Six Degrees of Kevin Bacon
concept, explaining its connection to the Milgram experiment.
Graph Library Standardization and Related Standards
- Andrew mentions the impact of the graph library on the standard and
its relationship with NW graph, BGL, and GraphLaws.
- Oliver raises concerns about the introduction section, suggesting it
needs to convey the unstructured nature of general case graphs more clearly.
- Michael points out a missing section reference and other minor errors
in the document.
- Michael suggests addressing the issues and sending detailed comments
for further review.
Terminology Paper and Graph Representation
- Andrew introduces the terminology paper, aiming to define consistent
vocabulary for graph representations and algorithms.
- The paper differentiates between a graph and its representations, such
as adjacency lists, and explains the runtime properties of directedness and
undirectedness.
- Oliver questions the distinction between directedness and
undirectedness, suggesting that it should be clarified in the paper.
- Andrew explains the transition from vertices and edges to indices in
adjacency lists and the importance of constant or logarithmic time indexing.
- The paper also covers definitions for directed and undirected edges,
neighbors, paths, self-loops, isolated vertices, multi-graphs, and
hypergraphs.
Direct Representation and Electrical Circuits
- Andrew discusses the direct representation, which allows users to
pass graphs directly into algorithms without converting them to other
representations.
- Oliver raises concerns about the representation of electrical
circuits, noting the subtlety of defining positive currents in undirected
graphs.
- Andrew explains that the direct representation does not depend on
the direction of currents, focusing on the topological properties of the
circuit.
- Oliver insists that the paper needs to address the implications of
directedness on representations and solver accuracy.
- Michael Wong agrees that the paper should clearly state how directed
and undirected representations impact solver accuracy and flow analysis.
Visitor Concepts and Algorithms
- Phil introduces the concept of descriptors, which simplify the
interface by consolidating specializations for algorithms.
- The descriptors replace the need for IDs and references, reducing the
number of concepts and views.
- Phil explains the impact of descriptors on the algorithms,
particularly the vertex ID function, which now takes a descriptor instead
of an iterator.
- The paper also includes visitor concepts, which were requested by
Oliver and are similar to those in Boost Graph Library.
- Jens suggests using italics and hyphens for exposition-only concepts
to improve readability and clarity.
Visitor Implementation and Repetition
- Phil discusses the implementation of visitor concepts, which are
taken directly from Boost Graph Library.
- Jens points out the repetition in the vertex info and edge info
structures, suggesting the creation of aliases for common patterns.
- Phil agrees that the repetition could be reduced by defining aliases
for vertex info and edge info.
- Oliver questions the use of void as a value type for vertices,
suggesting that it should be consistent with the graph's definition.
- Phil explains that void is used to allow for flexibility in extracting
values from vertices, but agrees to consider using vertex descriptors
instead.
Future Directions and Implementation Experience
- Phil mentions the potential for getting implementation experience
from a company that plans to use the graph library.
- Oliver expresses concerns about the paper's current state,
suggesting that it needs more time to bed down and gain broader experience.
- Michael Wong proposes the idea of a technical specification (TS) or a
white paper to gain broader feedback and implementation experience.
- Jens suggests that the paper should be presented to the Library
Evolution Working Group (LEWG) for further review and feedback.
- The group agrees to continue iterating on the paper, addressing
comments, and preparing it for a final vote.
Discussion on Design Rationale and Concerns
- Oliver points out that the design has issues with the edge info
struct, which doesn't seem to work as intended, especially with the void
concept.
Problems with Edge Info Struct and Concepts
- Jens explains that the concepts don't check certain configurations of
edge infos, which is a separate concern from the aesthetics of the design.
- agrees that this is a deep concern and mentions that they have
eliminated similar issues for the vertex info.
- Jens notes that they haven't seen actual use of the concepts, so it's
unclear if the problem exists for all edge info constellations.
- inquires if the node case has been solved, and confirms that a single
vertex ID is passed into the function.
Visitor Function and Data Model
- Oliver asks if the visitor expects to have access to the value on the
node, and Jens clarifies that the visitor can use value lookup functions
with the vertex ID.
- agrees that this approach makes sense and suggests passing around the
necessary data instead of passing around the entire struct.
- Phil introduces the concept of the edge info describing the data
model, including source and target IDs, edge descriptors, and optional edge
values.
- Phil explains that the edge info is used throughout the design, in
views, algorithms, and for defining external data loaded into the graph.
Challenges with Edge Value Storage
- questions the necessity of storing edge weights and node weights in
both the edge info struct and the data structures representing the graph.
- Phil suggests that the edge value can be a reference or a pointer,
which doesn't need to be copied in.
- Michael mentions that the next meeting is unlikely to happen next
month due to a face-to-face meeting and encourages online reviews.
- Phil notes that minimal changes are needed for the containers paper,
focusing more on algorithms and views for better understanding.
Conclusion and Next Steps
- Phil agrees and expresses readiness to focus on algorithms and views.
>
>
> For graph, we have a new draft of P3337 Comparison paper that compares the
> library in performance against boost::graph and NWGraph.
>
> If Andrew is able to attend, he should be able to review the changes he's
> made to P3126 and P3127.
>
>
> P3495 from Oliver/Mark
>
> >From Phil: There are updates to the P3126 Overview and P3127 Background
> and
> Terminology papers for the Graph Library. They haven’t been published yet,
> but it would be helpful to get input on them before they’re published.
>
>
>
> Since the changes are a response to Oliver’s concerns, I think Oliver and
> Andrew would need to attend to make it useful to have a session for the
> Graph Library. Unless they want to do that, I think we can send draft
> versions to the reflector, unless there’s a better idea.
>
>
> 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
>
> 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:
>
> 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 9, 2025 02:00 PM ET: Cancelled
> * Feb 13, 2025 02:00 PM ET: Hagenberg F2F; Cancelled
> * Mar 13, 2025 02:00 PM ET: Graph
> * Apr 10, 2025 02:00 PM ET: Stats
> * May 8, 2025 02:00 PM ET: Graph
> * June 12, 2025 02:00 PM ET: Stats
> * July 10, 2025 02:00 PM ET: Graphs
> * Aug 14, 2025 02:00 PM ET: Stats
> * Sep 11, 2025 02:00 PM ET: Graph, CPPCON
> * Oct 9, 2025 02:00 PM ET: Stats
> * Nov 13, 2025 02:00 PM ET: Graph
> * Dec 11, 2025 02:00 PM ET: Stats
>
Received on 2025-05-12 16:40:54