Hi there, Gautam Sewani <gautamcool88@gmail.com> writes:
Hi, I am a Computer Science student hoping to contribute to Boost for this year's summer of code. I had a few questions regarding the BGL project idea (https://svn.boost.org/trac/boost/wiki/SoC2010#Boost.Graph) for SOC 2010.
I read throught the posted url and I'm a little astonished about "Closures and Reductions - Implement a suite qof generic graph algorithms that computer closures and reductions on graphs. The BGL already contains a transitive_closure algorithm, but not (yet) a transitive_reduction. Other kinds of computable closures and reductions include reflexive, symmetric, and congruence. This project can also include predicates to test whether or not a graph exhibits these properties (e.g., is_symmetric)." After all there is a transitive_reduction.hpp in boost BGL. Ok it is not documented at the moment. And there is https://svn.boost.org/trac/boost/ticket/3821 The algorithm in this ticket is not as efficient as the algorithm, which is already there in the transitive_closure.hpp. As I wrote transitive_reduction.hpp in the form in this ticket, I noticed, that besides adding the input and output parameters and reconstructing the transitive reduction of the graph from the transitive reduction of the structure graph, it is not much afford to add transitive reduction if one has transitive closure. (Why is the algorithm included in transitive_reduction.hpp not as efficient as the algorithm included in transitive_closure.hpp? The algorithm in transitive_closure.hpp uses successor sets there transitive_reduction.hpp uses a adjacency matrix for the core algorithm.) I see that there is much more to the proposed project, than to add a transitive reduction, but it is not true that there is none. Yours sincerely, Eric