Allow non-copyable IDs

[akrzemi1]

The current Graph Container Interface requires the IDs to be copy_constructible.

Suppose that I have my own graph representation that needs to use non-copyable IDs. How am I supposed to customize vertex_id?

ID const& vertex_id(Graph const& g, Graph::const_iterator it) { 
  return it->first;
}

Shall I return by value or by reference to const? If by value, then I need to copy. If by reference, then the CPO vertex_id will do the copying, because its return type is non-reference, and I am returning a reference to const, so even move will not work.

[akrzemi1]

In the envisioned support for graphs where IDs are not std::integral, are the same Graph Container Interface CPOs supposed to work?

[pratzl]

In theory, yes, though they may require refinement. It needs testing; I haven't had a chance to pursue that. One are in particular that needs some attention is whether vertex_id() returns a value or a reference and to carry that through the whole API. Sent from Outlook<http://aka.ms/weboutlook>

…

________________________________ From: Andrzej Krzemieński ***@***.***> Sent: Friday, July 4, 2025 5:27 PM To: stdgraph/graph-v2 ***@***.***> Cc: Subscribed ***@***.***> Subject: Re: [stdgraph/graph-v2] Allow non-copyable IDs (Issue #174) [https://avatars.githubusercontent.com/u/2912717?s=20&v=4]akrzemi1 left a comment (stdgraph/graph-v2#174)<#174 (comment)> In the envisioned support for graphs where IDs are not std::integral, are the same Graph Container Interface CPOs supposed to work? — Reply to this email directly, view it on GitHub<#174 (comment)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/AB7NKERIGQBFYE7WELHJNO33G3WTJAVCNFSM6AAAAACAVXP5JCVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZTAMZXGI3TEMRTHE>. You are receiving this because you are subscribed to this thread.

[akrzemi1]

On the other hand an "ID" sounds like something that should be easily passed around (by value), not requiring significant resources. Maybe this should be part of the contract that whatever type you choose for ID, copying it should be acceptable.

[pratzl]

That's true, until you accept a string as an ID. In the last product I worked on, which is a distributed graph for entity resolution, the Id is roughly a composite of {type, rank, Id} that are stored in a 64-bit integer. In that case, it may not be appropriate to treat it as an integer and use the existing bits, where we need to override operator<=>(). The containers we use are bidirectional. What are the concept requirements for an Id? I haven't delved into that yet. Sent from Outlook<http://aka.ms/weboutlook>

…

________________________________ From: Andrzej Krzemieński ***@***.***> Sent: Tuesday, July 8, 2025 2:35 AM To: stdgraph/graph-v2 ***@***.***> Cc: Phil Ratzloff ***@***.***>; Comment ***@***.***> Subject: Re: [stdgraph/graph-v2] Allow non-copyable IDs (Issue #174) [https://avatars.githubusercontent.com/u/2912717?s=20&v=4]akrzemi1 left a comment (stdgraph/graph-v2#174)<#174 (comment)> On the other hand an "ID" sounds like something that should be easily passed around (by value), not requiring significant resources. Maybe this should be part of the contract that whatever type you choose for ID, copying it should be acceptable. — Reply to this email directly, view it on GitHub<#174 (comment)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/AB7NKEUITATWAV4E6KLSCL33HNRDRAVCNFSM6AAAAACAVXP5JCVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZTANBXGU2TGMBSGA>. You are receiving this because you commented.Message ID: ***@***.***>

[pratzl]

The general design is intended to work, but I'm almost certain there are details that aren't correct. That's an area that needs to be flushed out and refined. Sent from Outlook<http://aka.ms/weboutlook>

…

________________________________ From: Andrzej Krzemieński ***@***.***> Sent: Friday, July 4, 2025 5:27 PM To: stdgraph/graph-v2 ***@***.***> Cc: Subscribed ***@***.***> Subject: Re: [stdgraph/graph-v2] Allow non-copyable IDs (Issue #174) [https://avatars.githubusercontent.com/u/2912717?s=20&v=4]akrzemi1 left a comment (stdgraph/graph-v2#174)<#174 (comment)> In the envisioned support for graphs where IDs are not std::integral, are the same Graph Container Interface CPOs supposed to work? — Reply to this email directly, view it on GitHub<#174 (comment)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/AB7NKERIGQBFYE7WELHJNO33G3WTJAVCNFSM6AAAAACAVXP5JCVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZTAMZXGI3TEMRTHE>. You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[akrzemi1]

In the last product I worked on, which is a distributed graph for entity resolution, the Id is roughly a composite of {type, rank, Id} that are stored in a 64-bit integer. In that case, it may not be appropriate to treat it as an integer and use the existing bits, where we need to override operator<=>(). The containers we use are bidirectional.

That's true. In the alternate design that I sketched here, one needs to specialize one CPO (registry) to account for this.

[akrzemi1]

What are the concept requirements for an Id? I haven't delved into that yet.

I would say the following.

At high-level: an "id" in a graph is like an index in a vector: an index is never invalidated (unless you shrink a vector): it remains valid when you clone a vector: you can use it to index the clone.

At the technical level:

• std::copyable as you need to be able to make and store copies of it, use it as a key in a map, store as members: write it to a file, and then load back.
• It need not be default-constructible: you already need to know which vertex you are identifying. Algorithms shouldn't have a need to create IDs that do not name vertices.
• It should be storable in containers as a key, so std::equally_comparable and hashable; although, I do not think there is a thing like "hashable": you can always provide a custom hash for a bizzare type.

[akrzemi1]

In the last product I worked on, which is a distributed graph for entity resolution, the Id is roughly a composite of {type, rank, Id} that are stored in a 64-bit integer. In that case, it may not be appropriate to treat it as an integer and use the existing bits, where we need to override operator<=>(). The containers we use are bidirectional.

That's true. In the alternate design that I sketched here, one needs to specialize one CPO (registry) to account for this.

Correction. Supporting this indexing would actually not even require specializing anything. For non-contiguous integral IDs, you would probably use a non-contiguous container for storing vertices. CPO registry would detect that and switch to using a non-contiguous container for marking the visited vertices. I added an example of such graph representation to https://raw.githubusercontent.com/akrzemi1/sandbox/refs/heads/master/gaph/new_concept.cpp.