Re: [Boost-users] Tree library?

Subject: Re: [Boost-users] Tree library?
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2009-01-24 04:51:40

joel falcou wrote:
> why not using boost::graph ?
> A tree is no more than a special graph anyway ?

Are you sure? The original poster seems to have a "rooted tree" in mind, which is a special "directed acyclic graph" (DAG). I just looked at the TOC of the boost::graph documentation, and the only DAG algorithm I could find was "topological_sort". There is also the transitive_closure algorithm, which could be used to compute the "partial order" relation of the DAG, but I'm not sure whether this is really the appropriate way to compute the "partial order" relation of a DAG (because the number of edges could increase to O(V^2) and DAG's are not mentioned in the corresponding documentation).

So I have the impression that DAG's and (rooted) trees are not really the main target applications of boost::graph.

Regards,
Thomas