The meeting discussed the evolution of the forward index and its impact on simplifying code, including the addition of sparse vertex IDs and bi-directional graph support. The reference implementation now includes a full suite of tests, totaling 80,000 lines. Algorithm changes were highlighted, such as the introduction of vertex property maps and visitor patterns for shortest paths and depth-first search. The team debated the acceptability of algorithms that allocate memory internally and the need for parallel implementations. The discussion also covered the integration of the statistics library with existing libraries and the potential impact of the units library on future developments.

Action Items

• PR Email the LEWG reflector to ask whether graph algorithms allocating internal workspace is acceptable and introduce the requestor on their behalf
• PR Contact L E WG (or relevant reflector) about allocation/space-complexity policy for algorithms and present the trade-offs to de-risk the proposal
• @Michael Wong - Mention the statistics/graph library to the C++ Alliance / Beeman project maintainers and inquire about hosting or review options
• @Michael Wong - Provide the vote results and information on accessing the ISO CPP wiki (voting records) to the statistics paper author
• @Michael Wong - Connect the statistics proposal author with the units-library author (Matus) and evaluate how the units library impacts the statistics proposal; report back
• Phil take responsibility for the SG-19 meeting on May 14 (cover the meeting in the presenter's absence)
• Richard Cite the committee vote results in the next version of the statistics paper (include voting evidence in the paper)
• MW Contact the boost maintainers for the graph library to request review and discuss hosting or collaboration

Outline

Forward Iterators and Additional Features

• PR discusses the introduction of forward iterators and how it simplifies the code by reducing the number of functions needed.
• The addition of sparse vertex IDs allows for non-interval vertex IDs, which can be useful in certain use cases.
• View chaining using the pipe operator is introduced to support bi-directional graphs, with additional functions added to support this.
• The dynamic graph is extended to support bi-directional graphs, which is not part of the proposal but is included for testing purposes.

Reorganization of Namespaces and Testing

• PR explains the reorganization of namespaces to separate adjacency lists and edge lists, ensuring they are true peers.
• The testing suite has been expanded to include a full suite of tests, now totaling around 80,000 lines, providing more confidence in the implementation.
• The previous presentation and proposals are reviewed, with a focus on the algorithms and areas that have changed.
• Common algorithm definitions are discussed, including edge weight concepts and the introduction of the vertex descriptor and ordered vertex edges.

Vertex Property Map and Distance Function

• The vertex property map is introduced to store values like distance or predecessor, which can be stored in a vector or unordered map.
• The distance function and predecessor function are discussed, with changes to accommodate storing these values in either an external container or as properties on the vertex itself.
• The concept of vertex visitors is introduced, which can be called on different events during the algorithm's execution.
• The algorithms for breadth-first search and depth-first search are updated to support both random access and forward range types of vertex containers.

Discussion on Allocation and Space Complexity

• The discussion shifts to the allocation of internal data structures used by algorithms, such as stacks or queues, and the importance of considering space complexity.
• Scott raises a question about whether algorithms that allocate their own internal workspace will be accepted by the library evolution working group (LEWG).
• Michael Wong suggests framing allocation as an observable, bounded, and optional user-supplied buffer to address space efficiency concerns.
• The importance of documenting space complexity and offering overloads that take a caller-provided working buffer is emphasized.

Feedback on Graph Algorithms and Future Steps

• The discussion includes feedback on the Dijkstra shortest paths algorithm, with changes to the edge descriptor to improve performance.
• The use of visitors in algorithms like shortest paths, breadth-first search, and depth-first search is highlighted.
• The need for early engagement with LEWG to address questions about allocation and space complexity is emphasized.
• The meeting concludes with a discussion on the next steps for the graph library, including the need to reduce placeholder sections and complete the paper.