Re: [boost] [SoC] BGL project idea

Subject: Re: [boost] [SoC] BGL project idea
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-03-22 15:54:14

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

There are a lot of tabs in the source file; they are not allowed in Boost 
code.  The copyright and license info at the top of the file are also 
incorrect; the old code in boost/graph/transitive_reduction.hpp has the 
correct text.

The coding style is different from the rest of the BGL code; we normally 
use K&R style.

You might want to remove the debugging code from the library itself.

Should edge_in_closure be a boost::multi_array or a 
boost::adjacency_matrix to be clearer on what it's being used for?

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?

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.

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.

Why are you using a vector of vectors as that adjacency list structure for 
CG and the other temporary graphs?  Why not boost::adjacency_list?

Line 243 is missing an "e" on the end of "transitive".

The documentation style is too informal compared to the rest of the BGL 
reference documentation.  The function signatures also need to be 
signatures at the top of the documentation file -- that is likely to be 
one of the first things a user will be looking for when they pull up the 
documentation page.  I do appreciate that you have figures in there; it 
might be better if they were a bit smaller, though, and you put each
grouping (graph, trans. closure, trans. reduction) in a single horizontal 
line.

In the examples and tests, "exspectation" should be "expectation" in 
several variable names; there are some spelling errors in the comments 
too.  For brevity, you might also want to use the graph constructors that 
take a sequence of pairs that becomes the edge list of the graph.

-- Jeremiah Willcock