Re: [boost] [SoC] BGL project idea

Subject: Re: [boost] [SoC] BGL project idea
From: Eric Wolf (eric_at_[hidden])
Date: 2010-03-23 05:24:43

Hi Jeremiah,

first of all: thanks for the feedback! I'll work on your comments
in the next weeks (perhaps months). Some I answer here.

Jeremiah Willcock <jewillco_at_[hidden]> writes:

>> I don't know which rules apply to code in order to decide, wether it
>> should be contained in trunk.
>
> I looked through your tarball.  Here are some comments:
>
> Why are you computing the transitive closure explicitly when it is not
> part of the algorithm's documented output?  It there a reason that you
> can't use the SCC structure (and the connections between them)
> directly to compute the reduction without storing the full closure?

You mean the edge_in_closure adjacency matrix in
transitive_reduction_for_dag? It's part of the algorithm to have the
reflexive transitive closure stored. I have no idea how I could generate
the same behavior in the decision logic ( the "if( not
edge_in_closure[i][*it] )" line ) without it.

> Why are there functions that do the transitive closure as well as the
> reduction?  Is having both of them a common use case?  It appears that
> there is a lot of redundant code between the reduction-with-closure
> and reduction-only functions.

It's the same algorithm. The algorithm for computing the closure and the 
reduction is essentially the same. So you could have the other one for
free if you generate one of them. I doubt that it is a common use case,
I admit, but I thought one should have the possibility to get both in 
one run, if its for free. So the reduction-with-closure and
reduction-only functions are essentially duplicates of each other.

> I believe strong_components actually returns a topologically sorted
> list of the components (I do not remember which order the sort is in),
> so you may not need to do that separately on the DAG of components.

I'll have to investigate that ... but if it's not part of the documented 
behavior it would be not "right" to rely on it, wouldn't it?

> In the examples and tests, "exspectation" should be "expectation" in
> several variable names; there are some spelling errors in the comments
> too.  

I'm not a native speaker, so I have to search for spell checking
software. (aspell or ispell, wether one of them can do unicode) 

Yours sincerely,

Eric