Boost logo

Boost Users :

From: Thomas Costa (oohrah_at_[hidden])
Date: 2004-07-16 10:10:16


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 <jsiek_at_[hidden]>
> http://www.osl.iu.edu/~jsiek
> Ph.D. Candidate, Indiana University Bloomington
> C++ Booster (http://www.boost.org)
> _______________________________________________
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net