Graph: transitive closure interface

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-09-14 11:19:44

For those of you interesting in using the BGL transitive_closure
function...

Vladimir and I have been discussing two options for the interface
of transitive_closure:

(1) The 2-graph parameter version
transitive_closure(G,                      // IN
                   Gclose,                 // OUT
                   G_to_Gclose_vertex_map) // UTIL/OUT

or, using a default map:
transitive_closure(G, Gclose)

(2) The 1-graph parameter version
transitive_closure(G) // IN-OUT

Version (1) fills in the initially empty Gclose with the transitive
closure of G.

Version (2) deletes all the edges in G and then fills it back up again
with the transitive closure.

I like version (1) because it is a close match to the mathematical
abstraction, it uses to graphs, G and Gclose to model the two
mathematical objects G and G*.

Vladimir likes version (2) because he feels it is easier to use.

In terms of space/time efficiency, both versions are similar, though
version (2) may have a small advantage in terms of space.

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                          http://php.indiana.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------