Boost logo

Boost Users :

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

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]>
> Ph.D. Student, Indiana University Bloomington
> C++ Booster (
> _______________________________________________
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at