A goal I’ve had from the beginning is to provide a foundation that we can grow from in the future. For instance, I want to make sure we can support sparse vertex id’s by storing vertices in an unordered_map. I’d like to also like to demonstrate incoming edges in a vertex in the implementation so that we can add another paper later to add that the library.

This is an important time where there’s still some flexibility to make some incremental changes. If you can take the time to determine how difficult it would be to add cardinal trees then I’d be interested to hear what you find.



From: SG19 <sg19-bounces_at_[hidden]> On Behalf Of Jeremy Murphy via SG19
Sent: Wednesday, October 23, 2024 7:14 PM
To: sg19_at_lists.isocpp.org
Cc: Jeremy Murphy <jeremy.william.murphy_at_[hidden]>
Subject: Re: [isocpp-sg19] cardinal trees


EXTERNAL
Btw, I should apologize for throwing this completely new topic up fairly late in the process. I don't want to hold up progress with it; my main concern is that the initial graph proposal doesn't accidentally make it difficult (or impossible) to add cardinal trees later.

From my experience of trying to add them to Boost.Graph, it was not that hard, so my concern might be unwarranted. But I think it's an important special case of graphs to bear in mind from the beginning, also so that the wider audience knows whether it is within the larger remit of the project or not.

The design of trees in Elements of Programming is fundamentally different to the design of graphs in Boost.Graph, so I think it's worth considering whether there is something to be learned from it, or why not, etc.

Cheers.

Jeremy


On Thu, 24 Oct 2024 at 05:09, Michael Wong via SG19 <sg19_at_[hidden]<mailto:sg19_at_[hidden]>> wrote:
Thank you, Jeremy I like to gather the group's opinion first. But this seems a good paper to be seen.

On Wed, Oct 23, 2024 at 9:52 AM Phil Ratzloff via SG19 <sg19_at_[hidden]<mailto:sg19_at_[hidden]>> wrote:
I haven’t looked into it at all because I’ve been consumed with what’s there as it is.
If you have some suggestion of ways to extend what’s there, please feel I’m willing to listen.


From: SG19 <sg19-bounces_at_[hidden]<mailto:sg19-bounces_at_[hidden]>> On Behalf Of Jeremy Murphy via SG19
Sent: Wednesday, October 23, 2024 3:29 AM
To: sg19_at_[hidden]<mailto:sg19_at_[hidden]>
Cc: Jeremy Murphy <jeremy.william.murphy_at_[hidden]<mailto:jeremy.william.murphy_at_[hidden]>>
Subject: [isocpp-sg19] cardinal trees


EXTERNAL
Dear SG19,
I had a quick look through the current papers and firstly just wanted to quickly ask if you had given any thought to using this library for working with cardinal trees?
They don't exist in Boost.Graph; although one can obviously create a structure that looks superficially like one, the concepts defining efficient algorithms on them don't exist.
There are some other libraries for creating a binary search tree, but they're quite specific in purpose, not generic.
The best treatment of the topic is in Elements of Programming by Stepanov and McJones, which is freely available online.
There is also a C++Now talk about adding binary trees to Boost.Graph that explains the new concepts, etc.
Thanks, cheers.
Jeremy


--
SG19 mailing list
SG19_at_[hidden]ocpp.org<mailto:SG19_at_[hidden]>
https://lists.isocpp.org/mailman/listinfo.cgi/sg19<https://protect.checkpoint.com/v2/r01/___https://lists.isocpp.org/mailman/listinfo.cgi/sg19___.YzJ1OnNhc2luc3RpdHV0ZTpjOm86YjczM2U2MjRlNmZiZjkzYmVkZGZmNWMzOWQwMGEwMmM6NzowMDIxOjlhYjhlYjI1NWQ2NjBiZjE4YWJjZGJiNTJlMTA1M2ZjODVhZTIzOTk4MjFjMjZkNjRjODk0YTcxMGI0YmJjMjc6aDpUOk4>
--
SG19 mailing list
SG19_at_[hidden]socpp.org<mailto:SG19_at_[hidden]>
https://lists.isocpp.org/mailman/listinfo.cgi/sg19<https://protect.checkpoint.com/v2/r01/___https://lists.isocpp.org/mailman/listinfo.cgi/sg19___.YzJ1OnNhc2luc3RpdHV0ZTpjOm86YjczM2U2MjRlNmZiZjkzYmVkZGZmNWMzOWQwMGEwMmM6NzplMjkxOjdlOGM0MTQ0NzBlZTI0Yzc4MzkyNjQzNzY2NjExMGFhYzg4NmNjMmY5NTIyZDU0MGI5NGZiZmFlMTczMDMwMzQ6aDpUOk4>