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

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