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

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-14 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.