Re: [boost] [SoC] BGL project idea

Subject: Re: [boost] [SoC] BGL project idea
From: Eric Wolf (eric_at_[hidden])
Date: 2010-03-13 06:19:04

Hi there,

Gautam Sewani <gautamcool88_at_[hidden]> 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