[graph] Tree data structure

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

[graph] Tree data structure

Boost - Dev mailing list
Dear Boost community,

long ago, back in 2002 and 2009, Kasper Peeters proposed adding his tree
data structure to Boost.

http://tree.phi-sci.com/

There was a lot of discussion but nothing eventuated (so far as I am
aware). There are links to the historical discussions on his website.

...2018....

Recently, a Boost.Graph user suggested adding a tree class to it, and I was
like, "No, no, a tree is just a graph that satisfies certain constraints: a
tree class won't yield better performance."

But I also happen to be re-reading for nth time, Element of Programming,
which touches ever so briefly but intensely on binary trees, and I realized
"Oh, hold on, there is a world of conceptual difference between an
arbitrary tree, and a k-ary tree."

That discussion is here: https://github.com/boostorg/graph/issues/123

It seems very awkward to even try to represent a k-ary tree in existing
Boost.Graph data structures, let alone a mutable k-ary tree.

So I made a proof-of-concept, a mutable k-ary tree data structure with
specialized implementations of depth-first search and isomorphism. Unless
I've made a terrible mistake (which is possible), the performance gains are
huge, and the ease of use in an existing library is also huge.

OK, so huge things aside, this is really early days, exploratory work. And
I'm no Boost.Graph expert. I'm interested in what people think,
particularly whether they think it is an idea worth pursuing. I do. But I
basically need help from people smarter and more experienced.

I have made a PR for the sake of discussion, not for actually merging:
https://github.com/boostorg/graph/pull/139

Cheers.

Jeremy

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [graph] Tree data structure

Boost - Dev mailing list
On 11/28/18 11:51 AM, Jeremy Murphy via Boost wrote:

> long ago, back in 2002 and 2009, Kasper Peeters proposed adding his tree
> data structure to Boost.

There is also Rene's proposal, which sounds like a useful Boost library:

   http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3700.html

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [graph] Tree data structure

Boost - Dev mailing list
On Sun, 2 Dec 2018 at 02:31, Bjorn Reese via Boost <[hidden email]>
wrote:

> On 11/28/18 11:51 AM, Jeremy Murphy via Boost wrote:
>
> > long ago, back in 2002 and 2009, Kasper Peeters proposed adding his tree
> > data structure to Boost.
>
> There is also Rene's proposal, which sounds like a useful Boost library:
>
>    http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3700.html
>
>
Thanks, Bjorn, I didn't know about that!

My tree idea for Boost.Graph is not meant to be mutually exclusive with any
independent Boost library idea.
I'm interested to have a read through and see how similar or different it
is.

Cheers.

Jeremy

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost