10.8. NEIGHBORHOOD PROPERTIES OF GRAPHS
415
Path Facts Versus Paths
We should be careful to distinguish between a path, which is a sequence of
arcs, and a path fact, which is a statement that there exists a path from
some node x to some node y. The path fact has been shown typically as
Path(x, y). Smart transitive closure discovers each path only once, but it
may discover a path fact more than once. The reason is that often a graph
will have many paths from x to y, and may even have many diﬀerent paths
from x to y that are of the same length.
Not all paths are discovered independently by smart transitive closure.
For instance, if there are arcs w →x →y →z and also arcs x →u →z,
then the path fact Path(w, z) will be discovered twice, once by combining
Path(w, y) with Path(y, z) and again when combining Path(w, u) with
Path(u, z). On the other hand, if the arcs were w →x →y →z and w →
v →y, then Path(w, z) would be discovered only once, when combining
Path(w, y) with Path(y, z).
10.8.9
Comparison of Methods
The methods discussed in Sections 10.8.4 through 10.8.8 have their advantages
and disadvantages. The principal issues are the number of rounds required and
the time it takes to execute each round. We shall consider these costs on a
directed graph with n nodes, e arcs, and diameter d.
For all the algorithms discussed, the cost of the joins dominates the cost
of the other operations at a round – grouping, aggregation, and union. Thus,
we shall think only about the cost of the joins. Further, we shall assume that
the join is implemented eﬃciently, as in the algorithm of Section 2.3.7. In that
algorithm, each tuple from each of the two relations is sent to one reducer, and
the work at each reducer is the product of the numbers of tuples from each of
the two relations at that reducer. Finally, we shall assume all the algorithms
are implemented by their seminaive versions, since that is more eﬃcient than
the “naive” version. Figure 10.25 summarizes the analysis.
Algorithm
Computation
Rounds
Reachability
O(e)
d
Linear TC
O(ne)
d
Recursive Doubling
O(n3)
log2 d
Smart TC
O(n3)
log2 d
Figure 10.25: Costs of transitive-closure algorithms
The numbers of rounds for these algorithms have already been discussed.
