Science of Computer North-Holland Programming 151 12 (1989) 151-155 AN ALGORITHM FOR TRANSITIVE AN ACYCLIC GRAPH David OF GRIES Computer Alain REDUCTION Science Department, Cornell University, Ithaca, NY 14853-7501, U.S.A. J. MARTIN California institute of Technology, Pasadena, Jan L. A. van de SNEPSCHEUT Department CA 91125, U.S.A. and Jan Tijmen of Computing Science, Groningen University, UDDING Groningen, Netherlands Communicated by M. Rem Received June 1987 Revised March 1988 1. Introduction We derive a new algorithm for computing the transitive reduction of a directed acyclic graph. The algorithm was developed by attempting to invert Warshall’s algorithm for computing the transitive closure of a graph [4]. Thus, the concept of program inversion (cf. [2, 31) led to the algorithm, although it could not be strictly used. The transitive closure of a finite, directed graph is obtained by adding a directed edge wherever the original graph contains a path from the source to the destination node of the new edge. The graph thus obtained is called closed. For any graph, its transitive closure is uniquely determined. Further, the transitive closure of an acyclic graph is itself acyclic. The transitive reduction of a finite, directed graph is obtained by removing edges whose absence do not affect the transitive closure. A graph thus obtained is called reduced. The intersection of acyclic graphs with the same transitive closure has that same transitive closure. Hence, the transitive reduction of an acyclic graph is uniquely determined-as the intersection of all acyclic graphs with the same transitive closure. On the other hand, the transitive reduction of a cyclic directed graph is not unique (see [l] for an analysis). Because of the properties just mentioned, we restrict our attention to directed acyclic graphs. In the sequel, we first describe Warshall’s algorithm. We then analyze the algorithm informally and suggest an invariant for an algorithm for reducing an initially closed 0167.6423/89/$3.50 @ 1989, Elsevier Science Publishers B.V. (North-Holland) D. 1.52 Grieser al. graph, which is in some sense the inverse of War-shall’s algorithm. an algorithm for the transitive We use the following denotes reduction notation. of x textually The graph contains N nodes numbered k, 0 s k G N, predicate i +sk j denotes we obtain P and e and identifier For expressions P with all free occurrences Finally, of an acyclic graph. replaced 0 onwards. x, P: by e. For nodes i and j and integer the presence in the initial graph of a path from i to j via one or more intermediate nodes, all of which have a number at least k; predicate i +ckj denotes the presence in the initial graph of a path from i to j via one or more intermediate nodes, all of which have a number less than k. In the sequel, we omit the ranges of i, j, and k. The graph that is being modified is recorded in variable b as an adjacency matrix: b, is equivalent to the presence of edge (i, j) in the graph. variable b is given by constant a. We list some properties of predicate (0) i jck j and its “dual” The initial value of i +j”k j. V(i,j::b,,=ativi+“j)=(b=a). (1) V(i,j::bij=a,Ali+“Nj)=(b=a). (2) V(i,j::bg=a,-vi+ (3) (4) V(i,j::b,j=a,j~li+“oj)=(b=reduction (5) i~rkj~i,~kt'j~((i~rk+'k~~ik)~(k-,~kfljv~kj)). cN j) = (b = closure of a). of a). i+<k+‘j=i+ckjv((i+ckkvaik)A(k-+‘kjvakj)). 2. Warshall’s algorithm for computing transitive closure Warshall’s TC: algorithm k:=O; is {C} do k # N+forall(i, j: bikA bkj: b,:= k:= k-t1 true); {C~,,} {C} od. Its invariant c: C is bij=avv i eckj. We have omitted the universal quantification over i and j, as well as the ranges of i., j, and k. Notice that the forall statement can also be written as We prefer the latter form in our proofs and the original form in the program text. C,” is vacuously true on account of (0) and the initial condition b = a. C A k = N implies, on account of (2), that b is the transitive closure of a. Transitive We must right-hand show the invariance side of C:,, C&jvt+ = . reduction of an acyclic graph of C over the loop We investigate the . <k+l J ((4)) ati v i +<k j v ((i +<k k v a;k) h (k jckj = body. 153 v &j)) {Cl 6, V (bik A 6,). It follows that simultaneous execution of the up-to-N* assignments to 6, maintain C. The assignments may, however, also be executed in any order since the values bik and 6, are not changed: for example, bik is assigned the value true if bik A bkk holds, which implies that bik is already true. 3. From reduced to closed graph and vice versa We now consider the operational aspects of Warshall’s algorithm. Iteration k of the loop of Warshall’s algorithm adds edges between nodes that are connected by a path all of whose intermediate nodes have a number less than k. A corresponding reduction algorithm will undo the actions of the closure algorithm: edges will be deleted only between nodes that are connected by a path whose intermediate nodes are at least k. If we succeed in finding the exact “undoing”, we have two algorithms with the same invariant. However, this is too strong to hope for, because i +ck j and i +sk J may hold simultaneously. In the closure algorithm, an edge (i, j) is added as soon as i +ck j is found to be true, even if i +ak j is also true. Similarly, in the proposed reduction algorithm, an edge (i, j) is deleted as soon as i +ak j is found to be true, even if i etk j is also true. Thus, we obtain two distinct invariants, C for the closure and R for the reduction algorithm. C: bG=avvi+‘kj. R: b, c a0 A ii +zk j, Inspired by the discussion leading transitive reduction of an initially TR: to R, we propose closed graph. the following algorithm for the k:= N; {R} do k#O-+k:= k-l; {R;,,} forall( i,j: bik A bk,-: 6, :=false) {R} od. We need to check the invariance of R in algorithm TR. The initialization establishes R since R”, holds on account of (I). R A k =0 implies, on account of (3), that b is the transitive reduction of a. We check the invariance of R over the loop body of 0. Gries et al. 154 TR. We do so by manipulating is closed. J ((5)) atih7(i = 2k+‘jv((i-+2k+’ + {since + kvaik)h(k+~k+‘j~akj))) is closed a aijAi(i = side of R while using the fact that a z/S aijh7i+ = the right-hand ==k+‘jv i +zk+’ (aik {rewrite aik A akj zk+l Al((&k A akj) Using x = (x A y) v (x A iy); of Rkk+, we aim at term of the form ai, Aii on account f$Ali-, a&} A abj)) {calculus} aoA7i-+ zk+‘j I\ ?(a;k = k implies + zk+‘jI J kAayAlk+3k+‘j) Ali+3k+' k v k +3k+’ j))) {since a is closed i +aktl j is implied by aik A akj A (i +zk+’ k v k +*‘+I j)} v (aik = aij h ii = A akj A (i -+sk+’ ~k+'j~~(uik~li+bk+l + kI\akj~~k+"k+'j) Wi+J b, A l( b, A bkj). It follows that simultaneous execution of the up-to-N2 assignments to b, maintains R. Again, the assignments may also be executed in any order: whether an assignment is executed depends only on the values bik and bki, and these are not changed since the acyclic nature of the graph enforces bkk= fahe. 4. Transitive reduction of any acyclic graph Warshall’s algorithm, TC, computes the transitive closure of an arbitrary graph; it has C as an invariant. The dual of algorithm TC is algorithm TR which reduces an initially closed, acyclic graph; it has invariant R. The optimist might hope that a weaker invariant of TR exists that can be used to prove that TR reduces an arbitrary acyclic graph. The example below shows that this is not the case, for executio-n of TR with this graph does not eliminate the redundant edge (0,3). Fortunately there is a way out: algorithm TC; TR computes the transitive close of an arbitrary acyclic graph and then reduces the closed graph-which has the same transitive reduction as the original graph. The time complexity of the in-situ Transitive reduction of an acyclic graph algorithm TC; TR is0( N3).In [l] it is shown that transitive reduction have equal time complexity. 155 closure and transitive References [l] A.V. Aho, M.R. Garey and J.D. Ullman, The transitive reduction of a directed graph, SIAM J. Comput. I(2) (1972) 131-137. [2] E.W. Dijkstra, Selected Writings on Computing: A Persond Perspective (Springer, New York, 1982) 3.51-354. [3] D. Gries, The Science ofProgramming (Springer, New York, 1981) 265-274. [4] S. Warshall, A theorem on Boolean matrices, J. ACM 9 (1962) 11-12.

© Copyright 2018 ExploreDoc