
Boost : 
From: David Abrahams (david.abrahams_at_[hidden])
Date: 20020114 08:36:57
Hi Vladimir,
Thanks for your reply...
 Original Message 
From: "Vladimir Prus" <ghost_at_[hidden]>
> Here the first thoughts that I have:
>
> Say edge is (s, t), and destination vertex is d. ">" means reachable.
> The only interesting case is when
> (t > d) and (t>s) and (s>d)
(t>d) implies (s>d). So the only interesting case, asked that way, is
when (t>s), i.e. SCC(t) == SCC(s).
> 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 
++ `++ `++
In the above case the answer is "no", while in this one, it's "yes":
++____ ++____ ++
 d  `> s  `> t 
++ ++ ++
^ 
`/
Isn't that enough to make the case where they're all in the same SCC
interesting?
> When we consider the condensation graph (see the docs), the "yes" answer
is
> given when either
>  there are two different paths from SCC(t) to SCC(d)" where SCC(x)
denoted
> SCC to which x belongs.
Really? Unless I'm mistaken:
++____ ++____ ++
 x < `> s < `> t 
++ `++ `++
 
V V
++ ++
 y > d 
++ ++
SCC(s) == SCC(t) == {x,s,t}
SCC(y) == {y}
SCC(x) == {x}
++
 {x,s,t} \
++ 
 
V V
++ ++
 y > d 
++ ++
Am I confused?
>  or, the first edge in SCC(t)>SCC(d) path corresponds to several
vertices
> in the original graph.
Not sure what you mean by the above.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk