Re: [boost] BGL: like transitive_closure, but not exactly

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-14 10:01:46

----- Original Message -----
From: "Vladimir Prus" <ghost_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Monday, January 14, 2002 9:48 AM
Subject: Re: [boost] BGL: like transitive_closure, but not exactly

> David Abrahams wrote:
>
> > > In this case we don't know if (t-->d) is due to (t-->s) plus (s-->d)
or
> > > there's independent path. Observe that (t-->s) means t and s belong to
> > > the same SCC. Again, the interesting case is when d belongs to a
> > > different
> >
> > SCC.
> >
> > I'm not sure of that:
> >
> > +---+____   +---+____   +---+
> > | d |<-  `->| s |<-  `->| t |
> > +---+  `----+---+  `----+---+
>
> > +---+____   +---+____   +---+
> > | d |    `->| s |    `->| t |
> > +---+       +---+    ---+---+
> >   ^                       |
> >   `----------------------/
> >
> > Isn't that enough to make the case where they're all in the same SCC
> > interesting?
>
> Absolutely true! I'll think more about this. Can you tell me any details
> about the type of graph? Is it tree or DAG or general graph? Any
information
> can help.

It's a casting graph through an inheritance hierarchy. Non-polymorphic parts
of the graph have unidirectional (upcast) edges, but when a polymorphic
class is introduced we suddenly have only bidirectional edges.

In general, each component of the graph looks like a (possibly empty) DAG
with a (possibly empty) bidirectional graph attached at its roots. Or
vice-versa :^)

There are likely to be components which are all DAG, and others which are
all bidirectional.

-Dave