I’ve attached our latest version of D1709 for review in the next SG19 meeting on 14-Dec-2023.

Our goal in this next meeting is to get feedback so we can complete the proposal. Following that, we’d like to get it voted out of SG19 by February, so it can be reviewed by LEWG in Tokyo in March.

The current version is close, but it still needs work, as you’ll see comments strewn around the paper about the things we’re aware of. We need your help to help us know what we’re missing or things we’re not doing well.

If you have limited time, focus on Dijkstra Single Source Shortest Paths (p 16) in the Algorithms section; we still need to review the remaining algorithms as a team. Beyond that, read the sections on Views, the Graph Container Interface, and Graph Container Implementation in that order. If you have time, read the whole paper.

Major changes from previous reviews

1. New Motivation section (p. 7)
2. Added defaults to GCI to reduce GCI overload requirements to just target_id(g,uv) in simple cases. See an example on pp. 4-5 and 7-8.
3. Realized that ranges::views::transform(rng,fnc) for edgelists from ranges. No need to create another view.
4. All algorithms now have a prototype definition.
5. Added index_adjacency_list concept to address the common use case where vertices are in a random_access_range and the vertex_id is integral.
6. Added “basic” views to return descriptors without a vertex or edge reference, because not all algorithms require the reference. (pp. 29-31).
7. Added section for Copyable Descriptor types and concepts (pp. 27-28)
8. Added support for bipartite and multipartite graphs (p. 34). The compressed_graph (renamed from csr_graph) that’s included in the paper supports this.
9. Added CPOs for load_graph, load_vertices, load_partition, and load_edges (pp. 34-36).
10. Added a section on using existing graph data structures (pp. 36-37).

Missing Pieces, to be completed before the following SG19 meeting:

1. Operators (p 23): Degree, Join, Relabel, Sort, Transpose
2. Adaptor to convert an edgelist to an adjacency list.

Something that hasn’t been brought out  that may be of help is that vertex_descriptor, edge_descriptor and neighbor_descriptor describe the data model exposed by views and used by algorithms. See chapter 5 for more.

The paper is currently 41 pages. I’m guessing we’ll be around 45 pages when it’s done.