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

Okay, I'm going to take a crack at writing a routine to identify transitive edges in a DAG which will hopefully be good enough to contribute to the Boost. I'm going to try to use chain decomposition to manage successor sets just like transitive_closure does. Seem reasonable? On Jul 16, 2004, at 9:12 AM, Jeremy Siek wrote:

Hi Thomas,

Here's a couple more references. However, I wasn't able to find the actual text online. A trip to the library may be in order.

A. Goralcikova, V. Konbek: ``A Reduct and Closure Algorithm for Graphs''. Mathematical Foundations of Computer Science, LNCS 74, 301-307, 1979

David Gries, Alain J. Martin, Jan L. A. van de Snepscheut, and Jan Tijmen Udding. An algorithm for transitive reduction of an acyclic graph. Science of Computer Programming, 12(2):151--155, July 1989.

-Jeremy

On Jul 16, 2004, at 10:10 AM, Thomas Costa wrote:

...

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.

---

Jeremy Siek http://www.osl.iu.edu/~jsiek Ph.D. Student, 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