Implementing C++ n-ary tree with Boost Graph Library

Question

I would like to have a relatively small and simple tree in C++. Each node would contain an integer. The tree should be traversable both ways.

I know it can be done with tree.hh by Kasper Peeters, but I am going to use BGL for other purposes as well. I've been learning BGL for some time, but don't have a firm grasp on the concept yet.

The main requirement is the ease of programming (concise code is desirable), traversing and editability. Space and performance aren't likely to be a consideration.

I would appreciate the advice on the concept. My guess the graph should be bidirectional (as I need to be able to access children and parents).

How do I enforce the tree structure? Is the requirement of a single parent sufficient? Should I have an artificial root node in case of multiple orphaned nodes? What is the best way of quickly accessing the node if I know the value?

P.S. I originally posted this question on Stack Overflow and one of the comments suggested this site.

Answer 1

How do I enforce the tree structure?

Just like any other invariant you want to guarantee/enforce in your code - by writing code that doesn't break it. Wrap it in a class that guarantees the tree structure as pre- and post-conditions.

Is the requirement of a single parent sufficient?

Are you asking what a tree is? The constraints required for a graph to be called a tree are pretty well-established. You can look them up if you're unsure (for example, on wikipedia).

Hint: the requirement you missed is no cycles.

Should I have an artificial root node in case of multiple orphaned nodes?

If you have orphaned nodes, you have something other than a tree. If you know that a (single) tree can't have orphaned nodes, why did you either create these nodes or detach them from the tree in the first place?

It's fine as a transient condition (creating a node which is briefly orphaned, right before attaching it to the parent; detaching a node just before destroying it). It's not fine outside the tree's public interface, because it violates the tree-like postcondition.

What is the best way of quickly accessing the node if I know the value?

You haven't said anything about ordering or indexing, so I have no idea. Search for it. If there is some ordering, that will help you search faster. If not, you can always keep a separate index.

Answer 2

I've no specific advice on how to use a specific implementation, other then read the manual. BGL has a very good manual, and short of that it is used in many open source projects. Perhaps a little digging in other codebases for examples?

---

Aside from that it sounds like you do not have a firm grasp on the specific tree/graph structure you actually want to use in the first place.

I say this because done right a node will never be without a parent in a tree (unless its the root and something outside the tree owns that). It might help to do some research on the structures. Personally i found "Computational Geometry - Algorithms and Applications" (i've the 3rd edition) to be a good primer on graphs, how to use them, and how to construct them for your usage. Doubtlessly there are other resource you need only find them.