Re: [Boost-users] BGL transitive reduction algorithm?

I've looked for a decent algorithm and everyone seems to reference the Aho and Ullman paper from SIAM Computing 1972 which I cannot find online. The only algorithm I've come up with is for DAGs. Basic idea is to topo sort the DAG and then for each node in the DAG iterate over the children of it's highest topo order child and use this to prune direct edges to children that can be reached over a longer path. It seems kind of expensive so I'm wondering if there is a smarter way to do it. I have no real experience in graph computation past what I've picked up using BGL for a few months. On Jul 15, 2004, at 7:58 PM, Jeremy Graham Siek wrote:

Hi Thomas,

Nope, there is no transitive reduction algorithm. If you write one please consider adding it to the BGL!

Cheers, Jeremy

On Jul 15, 2004, at 3:51 PM, Thomas Costa wrote:

...

I've been looking at the BGL headers and documentation looking for a templated algorithm to compute the transitive reduction of a directed graph and I don't see anything. Am I missing something obvious, showing my total lack of experience in graph theory, or is this algorithm not in BGL yet?

---

Jeremy Siek http://www.osl.iu.edu/~jsiek Ph.D. Candidate, Indiana University Bloomington C++ Booster (http://www.boost.org) _______________________________________________

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users