From: Vladimir Prus (ghost_at_[hidden])
Date: 2002-01-14 04:41:54
> 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>
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))
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
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk