[boost] [graph] Tree data structure

Subject: [boost] [graph] Tree data structure
From: Jeremy Murphy (jeremy.william.murphy_at_[hidden])
Date: 2018-11-28 10:51:40

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