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