Re: [boost] [SoC] BGL project idea

Subject: Re: [boost] [SoC] BGL project idea
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-03-28 15:05:21

On Tue, 23 Mar 2010, Eric Wolf wrote:

> 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.

I guess you could do a BFS, but if the traditional algorithm uses an 
explicit closure you probably should too.  You might want to mention the 
quadratic memory usage though.  It would be better to have an explicit 
adjacency_matrix graph for the closure.  Is there a reason you're not 
using the current transitive_closure algorithm in BGL?

>> 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.

OK.  Is there a way to factor out the common code?

>> 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?

I guess not -- 
ftp://db.stanford.edu/pub/cstr/reports/cs/tr/75/508/CS-TR-75-508.pdf 
suggests that Tarjan's algorithm does prodice the components in order, but 
that's a variant that may not be the same as the BGL one.

-- Jeremiah Willcock