[Boost-users] The Graph Library Applied to Trees

From: Charles Brockman (cmbrockman_at_[hidden])
Date: 2008-02-27 22:24:07

I'm considering using the Boost Graph Library to represent binary trees in 
my application. This will be a planar acyclic directed graph with an 
adjacency-list representation. The vertices will have properties bundled in 
an exterior class.

A. While building the tree I need to track the depth of each branch and the 
greatest depth of any branch, that is, the distance from the source vertex 
to the farthest target vertex. For that I plan to use the distance_recorder. 
Is that reasonable? Are there pitfalls? Is there a better way?

B. I'll need to calculate the total length of the tree by which I mean the 
sum of all edges. I plan to do a depth-first search and increment a counter 
with a visitor event point such as discover_vertex. Is that the preferred 
method?

C. On occasion I'll have to swap vertices between two independent trees. My 
plan is to just swap the bundled properties of each vertex. At first I 
considered the remove_vertex function but the edges connected to a vertex 
must be removed first with clear_vertex so before I remove the vertex I'll 
have to record the source and the target vertices. Then I'll have to add the 
replacement vertex into the correct position. I can imagine that blowing up 
in my face. I would appreciate any guidance on this problem.

-- 
Charles Brockman