10.8. NEIGHBORHOOD PROPERTIES OF GRAPHS
417
smart-TC approach than if we use brute-force recursive doubling, even if the
theoretical worst cases are the same.
10.8.10
Transitive Closure by Graph Reduction
A strongly connected component (SCC) of a graph is a set of nodes S such that:
1. Every node in S reaches every other node in S.
2. S is maximal, in the sense that there is no node outside S that both
reaches every node in S and is reached by every node in S.
A typical directed graph such as the Web contains many strongly connected
components (SCC’s). We can collapse an SCC to a single node as far as com-
puting the transitive closure is concerned, since all the nodes in an SCC reach
exactly the same nodes. There is an elegant algorithm for ﬁnding the SCC’s of
a graph in time linear in the size of the graph, due to J.E. Hopcroft and R.E.
Tarjan. However, this algorithm is inherently sequential, based on depth-ﬁrst
search, and so not well suited to parallel impelementation on large graphs.
We can ﬁnd most of the SCC’s in a graph by some random node selections,
with two reachability calculations for each selected node. Moreover, the larger
an SCC is, the more likely it is to be collapsed early, thus reducing the size
of the graph quickly. The algorithm for reducing SCC’s to single nodes is as
follows. Let G be the graph to be reduced, and let G′ be G with all the arcs
reversed.
1. Pick a node v from G at random.
2. Find NG(v, ∞), the set of nodes reachable from v in G.
3. Find NG′(v, ∞), the set of nodes that v reaches in the graph G′ that has
the arcs of G reversed. Equivalently, this set is those nodes that reach v
in G.
4. Construct the SCC S containing v, which is NG(v, ∞) ∩NG′(v, ∞). That
is, v and u are in the same SCC of G if and only if v can reach u and u
can reach v.
5. Replace SCC S by a single node s in G. To do so, delete all nodes in S
from G and add s to the node set of G. Delete from G all arcs one or
both ends of which are in S. Then, add to the arc set of G an arc s →x
whenever there was an arc in G from any member of S to x. Finally, add
an arc x →s if there was an arc from x to any member of S.
We can iterate the above steps a ﬁxed number of times. Alternatively, we
can iterate until the graph becomes suﬃciently small. We even could examine
