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

From: Thomas Costa (oohrah_at_[hidden])
Date: 2004-07-16 18:01:05

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 <jsiek_at_[hidden]>
> http://www.osl.iu.edu/~jsiek
> Ph.D. Student, 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