 # Boost :

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-14 08:36:57

----- Original Message -----

> 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.