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

From: Vladimir Prus (ghost_at_[hidden])
Date: 2002-01-14 04:41:54

Hi David,

> I'd like to do something very much like transitive_closure. What I want to
> do is build an index which tells me, for every (edge,vertex) pair, whether
> the vertex is reachable through the edge without looping. Put another way,
> can I reach the destination from the edge's target vertex without visiting
> the edge's source vertex? Or another way, does a spanning tree exist which
> includes the edge and the destination vertex?
>
> It seems like the transitive_closure algorithm does all the right work, but
> I can't see how to make it give me the answer I want.

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)
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. 
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. 
- or, the first edge in SCC(t)->SCC(d) path corresponds to several vertices 
in the original graph.

[The following two paragraphs may be ignored: there's a better way]
The first case mean there are two vertices adjacent to SCC(t) which have 
SCC(d) in their successor set. Computing this naively seems easy
vector<int> count(num_vertices(g)) ;
for <all adjacent vertices>
        for <all chains>
                foo <all vertices in chain>
                        <update 'count'>

Complexity is O(VE) (for the entire graph), which is the same as for 
transitive_closure. However, the average complexity may suffer.

The second case means that we need to take SCC m, such that m --> SCC(d) and 
then compute (count( x,y: (x,y) \in G, x \in SCC(t), t \in m).
It can work like
int count = 0;
for <all vertices in SCC(t)>
        for v in <all adjacent_vertices>
                if (SCC(v) != SCC(t) && v --> SCC(d))
                        ++count;
In plain english: we consider all edges that go from SCC(t) to a different 
SCC, and if SCC(d) is reachable from it, then there's another unqiue first 
edge crossing SCC boundary from t to d. If there are two such pathes, then 
the answer to the original question is "yes". I also realized that the 
previous case in handled by this one and is not needed. The complexity of 
this code will be O(VE) (Almost always.... although slight optimization is 
possible).
                        
So, the conclusion is:
1. It is possible to solve the problem.
2. The solution will probably run slower on the average than the transitive 
closure, but both will have O(VE) complexity.
3. This is better implemented on top of transitive_closure, but we'd need 
acccess to scc map that transitive_closure internally computed. I.e. we'd 
need to add more named parameters to transitive_closure. 
But I still don't know how they work!
4. We can compute SCC externally as well, since it's only O(V+E). In this 
case, very little coding is required.

David, if the ideas above are too obscurely expressed, I can try to write an 
implementation of them. In this case, any tests that you might have available 
will help.

- Volodya