Re: [boost] [SoC] BGL project idea

Subject: Re: [boost] [SoC] BGL project idea
From: Eric Wolf (eric_at_[hidden])
Date: 2010-07-26 14:29:25

Dear Jeremiah,

Jeremiah Willcock <jewillco_at_[hidden]> writes:

> On Mon, 19 Jul 2010, Eric Wolf wrote:
>
>> I meant to say that I can't compute the reduction of a graph from an
>> existing transitive closure. One could say, I think, the algorithm
>> computes the transitive closure and from time to time writes an edge to
>> the transitive reduction. But the decision, whether to write an edge to
>> the transitive reduction isn't based on properties of the transitive
>> closure, but on properties of the state of the construction process of
>> the transitive closure.
>
> OK.  My understanding now is that you create the transitive closure
> and need to have explicit access to previously created parts of it,
> but the reduction is a possible side product of that computation that
> you do not need to look at during its creation.  Is that correct?

Yes. But the point is that not only “need to have explicit access to
previously created parts of it”, but also that access is needed to a
transitive closure, thats not yet finished. (Each state of the
construction process determines, wether to write an edge to the
transitive reduction.)

Yours

Eric