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@osl.iu.edu> 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