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