Computing 15, 33--39 (1975) 9 by Springer-Verlag 1975

Computational Experiences with Some Transitive Closure Algorithms M. M. Sys|o and J. DzLkiewicz, Wroc~aw Eingegangen am 28. September 1974 Abstract - - Zusammenfassung Computational Experiences with Some Transitive Closure Algorithms. The paper contains results of computational experiences with the following algorithms for finding the transitive closure of a digraph: (i) Warshall's algorithm [17], (ii) Purdom's algorithm [13], (iii) the modification of Yen's algorithm [14], and (iv) the new algorithms for finding the transitive closure [3, 4]. The tested digraphs were generated at random. The enclosed references contain all papers known to the authors concerning transitive closure algorithms. Reehnererfahrungen mit einigen Algorithmen fdr die transitive HiiUe eines gerichteten Graphen. Folgende Algorithmen wurden untersucht: 1. Warshall's Algo~thm [17], 2. Purdom's Algoritlun [13], 3. der modifizierte Algorithmus yon Yen [14], 4. der Algorithmus yon Dzikiewicz [3, 4]. Die getesteten Digraphen wurden durch einen Zufallsgenerator erzeugt. Das Literaturverzeichnis enth[ilt alle Ver6ffentlichungen fiber Algorithmen zur Bildung der transitiven Hfille, welche den Verfassern bekannt sind.

1. PreliminaryDefinitions Let D = (X, U) denote a directed graph (or digraph), where X is a set of vertices and U is a set of arcs, i.e. a set of ordered pairs of vertices. The number n = ] X ] we shall call the order of D. Let A=(aij ) ( i , j = l , 2 .... ,n) denote the adjecency matrix of D with elements aij defined by a i j -=

1 (true) if [i,j] e U, 0 (false) otherwise.

The transitive closure s [~) of a digraph D is a digraph such that [i, j] e U iff there is a path in D going from vertex i to vertex j. Let Av = (aij) denote the adjecency matrix of/). The condensation D*= (X*, U*) of a digraph D is a digraph such that vertices of D* correspond to the strongly connected components of D and [-i*,j*] ~ U* iff there is an arc from a vertex in component i* to one in component j* of the original digraph D. All definitions not given here my be found in the book [9]. Computing 15/1

3

34

M.M. Systo and J. Dzikiewicz:

2. Algorithms 2.1. The Algorithm o f Warshall [17, 7] The first description of an algorithm for finding the transitive closure of a digraph is due to Warshall [17]. Let T~ (1 _
where bhk = ahg ~ ahi c~ %

(k, h = 1, 2 . . . . , n).

It is easy to see that for fixed transformation i and for fixed row h we have if ahi = 0 (false) then bhk = ahl~ if ahi = 1 (true) then bhk= ahk ~ %

(](, = 1, 2 , . . . , n),

(k = 1, 2 , . . . , n),

i.e. the h-th row of the matrix T, A is equal to the Boolean sum of the h-th and i-th rows of the matrix A. Thus the matrix T i A can be stored on the place of the matrix A. The theorem of Warshall [17] states t h a t / 1 = T, T,_ 1 ..- T1 A. From the above considerations it follows that transformations T~ can be per,. formed on whole rows of the matrix. A realization of Warshall's method based on this observation has been also tested (see Table 3). For many small computers it is the only transitive closure algorithm for very large digraphs. For example, for the ODRA 1204 computer which has 16 K memory and 24-bit word it is possible to compute transitive closure only for digraphs of orders less than 70 by the method which used stored one matrix element per word and for digraphs of orders less than 450 by Warshall's method if the matrix has been packed.

2.2. The A l g o r i t h m o f P u r d o m [13] Purdom's algorithm is a realization of a method for finding the ~ransitive closure of a digraph D in which we can distinguish the following steps: (i) Computation of the strongly connected components of D and creation of the condensation D* of D. (ii) Computation of linear ordering of vertices of D*. (It is possibte because the digraph D* is an acircuit one.) (iii) Computation of the transitive closure/3" of D*. (iv) Extension of Step (iii) from/)* to/5. Other algorithms which are realizations of steps (i)--(iv) or some of them have been presented in papers [5, 1I], see also Section 2.4. A digraph is given in the form of its adjecency matrix in the Purdom's algorithm.

Computational Experiences with Some Transitive Closure Algorithms

35

2.3. The Modification of Yen's Algorithm [14, !8] The algorithm is an adaptation of Yen's version of Dijkstra's algorithm for finding the shortest paths in a non-negative distance network. The details of this method can be found in paper [14]. 2.4. The Algorithms of Dzikiewicz [3, 4] Algorithms of Dzikiewicz are realizations of a method similar to the method which has been presented in Section 2.2. A digraph is stored in the list form and results are stored in five arrays from which it is easy to obtain value of every element of the matrix ~ (see comment (8) in the programme [4]). The algorithms are of the following forms: (a) Steps (i), (ii) and (iii) from Section 2.2. (b) Steps (i) and (iii) from Section 2.2. In the both cases Step (i) has been realized by using a depth-first search technique presented by Tarjan [15] (see comment (4) in [4]) and in Step (iii) the modification of Yen's algorithm (Section 2.3) has been used (in the algorithm (a) the modification of Yen's algorithm has been simplified for we know a linear ordering of vertices of the acircuit digraph D*). The algorithm (b) has been presented in [4]. 2.5. Other Transitive Closure Algorithms Among other algorithms for finding the transitive closure of a digraph we can distinguish some which depend on a multiplication of Boolean matrices [2, 6, 8, 11, 123. Some of these algorithms utilize Strassen's method for matrix multiplication which requires only seven instead of eight multiplications. These algorithms have not been tested because if all operations in Strassen's method were taken into consideration then the method would be faster than the direct one for very large n only (e. g., for the GIER computer, for n > 1000 !).

3. Results of Computations The algorithms from Sections 2.1--2.4 have been tested on the ODRA 1204 computer for digraphs of orders n = 10 (10) 70 and of densities d = .0 (.005). 1 (.50) 1.0. For a fixed order n and a fixed density d ~ [0, 1] the adjecency matrix A =(a 0 of a tested digraph was of the form i, O<~ej+(i_l)n<_d aij =

O, d
where el, ez, ..., e,2is a sequence of uniquely distributed random numbers from the interval [0, 1]. 3*

36

M . M . Systo and J. Dzikiewicz:

The ALGOL-60 realizations of the algorithms presented in [7], [i3], ~t4], E3, 41, resp., have been used. The table 1 shows the times required by each of the tested algorithms for digraphs of different orders and of some densities, and table 2 shows these times for a digraphs of the fixed order n = 50 and all tested densities9 The Table 3 contains the times required by Warshall's method if the adjecency matrix has been packed9 Table 1

10

d

[71

[13t

[141

[4]

.01 .03 .05 .08 .1 .3 .5

,I ,2 ,2 .3 ,4 1.0 1.7 2.2

1.3 1.3 t.4 i .5 1.1 .8 .7 .9

,3 .4 .4 .7 .9

l.l 1.2 1.3 t .5 1,0

1.0 1.0 1.0

.4 ,5 .6

4.2 5.2 3.8 3.t 1.8 1.2 1.7 2.6

.8

20

.01 903 .05 908 .1 .3 .5 .8

,6 1.1 1.5 3.2 4.3 14.5 169 18.1

4.6 4.9 4.0 3.4 3.1 2.7 2.8 2.8

1.3 2.5 3.6 5.4 5.5 4.4 4.2 4.0

30

.01 .03 .05 .08 91 .3 .5 .8

1,8 4,0 5.8 23.3 26.8 51.5 58.5 61.8

10.3 10.8 11.3 5.5 5.3 5.7 6.0 6.3

3.8 10.4 12.9 12.4 12.2 9.8 99 9.1

.01 ,03 .05 .08 .1 93 .5 .8

3.5 t 3.4 25.3 76.3 85.7 1309 141.3 147.1

18.0 14.6 10.5 9.5 9.6 9.7 10.3 10.7

7.5 31.1 38.2 26.4 23.9 18.0 16.9 16.3

.01 .03 .05 .08 .1 .3 .5

7.4 48.6 142.1 254.0 284.0 464,8 488.1 502.3

40.3 26.6 21.3 20.4 20.7 22,1 22.9 24.1

16.1 97,7 57.9 49.1 49.0 39.5 38.0 36.8

40

60

,8

[ I

ii

[ I I

i ~ J

[ I

122 t5,4 6.5 2.0 1.8 3.2 4.7 7,2 18.2 19.7 7.0 2.7 2.9 59 9.2 14.5 42.4 26,5 5.6 59 5.6 169 27,4 43,2

Computational Experiences with Some Transitive Closure Algorithms Table 1 (continued) n

d

[7]

70

.01 .03 .05 .08 .1 .3 .5 .8

10.7 111.1 312.8 518.1 552.3 736,5 772.4 806.8

[13]

[14]

[4]

23.0 130.8 92.2 68.0 63.1 53.4 52.1 50.3

58.3 22.1 7.7 7,1 9.4 25.8 41.4 65.7

Table 2 d

[7]

[13]

[14]

[4]

.0O .005 .01 .015 .02 .025 .03 .035 .04 .045 .05 .055 .06 .065 .07 .075 .08 .085 .09 .095 .1 .15 ,2 .25 .3 .35 .4 .45 .5 ~55 .6 .65 .7 .75 .8 .85 .9 .95 ! .00

3.2 3,7 4.9 7.9 10.3 16.1 31.9 42.5 53.2 62.4 92.7 119.0 139.2 147.2 150.8 157.5 167.5 172.6 172.9 175.9 182.1 202.0 238.9 250.0 263.4 269.2 277.3 278.5 280.8 281.3 283,3 284.9 286.1 287.2 289.2 289.9 290.8 291.1 291.5

25.8 27.1 28.4 30.2 31.2 29.2 23.5 20.6 18.9 18,0 15.0 14.3 14.4 14.5 14.7 14.6 14.4 14.5 14.4 14.4 14.7 14.7 15.1 15.2 15.4 15.6 15.8 15.8 15.9 15.8 15.8 16.2 16.7 16.7 16.9 16.9 17.1 17,1 17.3

7.4 8,4 11,0 18.2 23,7 31,7 49.6 58.8 60.6 62.4 65.9 52.3 45.6 41.6 41.9 33.7 33.0 33.0 32.5 32.4 31.7 30.2 29.2 28.5 27.9 27.5 27.0 26.8 26.5 26.3 26.2 25.9 25.7 25.5 25.4 25.2 25,0 24.8 24.7

22.7 24.6 28.8 37.3 43.7 44,1 31.5 23.4 18.5 16.9 8.8 4.8 3,7 3.5 3.3 2.7 3.3 3.4 3.3 3.8 3.5 4,9 6.6 8.6 10.1 12.2 13.6 15.4 16.5 18.0 19,8 21,5 23.1 24.9 26.4 28.4 29.5 31.6 32.8

38

M o M. Systo and J. Dzikiewicz: Table 3

n = 50

n = 100

n=150

Time of packing in sec. 12

t

47

d

Time of closuring in sec.

.01 .05 .10 .30 .50

7 15 21 21

17 46 53 58 58

n = 250

n = 300

18

n = 200

106

Time of packing m sec. 188

294

423

Time of closuring m sec. .01 .05 .10 .30 .50

36 105 115 121 124

91 196 217 225 226

181 327 349 367 372

n=350

n=400

n=450

Time of packing in see. 576

752

954

Time of closuring m sec. .01 .05 .10 .30 .50

304 527 548 562 568

478 753 788 817 824

697 1066 1t14 1139 1150

4. Conclusions (1) T h e a l g o r i t h m o f W a r s h a l l w i t h a fixed o r d e r o f o p e r a t i o n s T~ a n d w i t h o u t a d d i t i o n a l i n v e s t i g a t i o n of t h e s t r u c t u r e s o f a d i g r a p h a n d its t r a n s i t i v e c l o s u r e is s l o w e r t h a n o t h e r a l g o r i t h m s for d e n s i t i e s g r e a t e r t h a n , 0 3 - - . 0 4 a n d for s m a l l d e n s i t i e s it is t h e fastest m e t h o d a n d its effectiveness m a y be still i n c r e a s e d b y a c o n t r o l l a b l e p e r f o r m a n c e o f o p e r a t i o n s T i (see [3] a n d [13]). (2) T h e a l g o r i t h m s (a) a n d (b) o f D z i k i e w i c z r e q u i r e t h e s a m e a m o u n t o f t i m e

Computational Experiences with Some Transitive Closure Algorithms

39

and the version (b) has been published in [4] because it is much simpler than the version (a). (3) The algorithm of Dzikiewicz is the fastest method for matrices of densities between .04 and. 5. (4) The algorithm of Warshall for the adjecency matrix in the packed form (for n = 50) is faster than other methods (even after addition the time of packing to the time of computation) with one exception, the algorithm (b) of Dzikiewicz for densities .06_< d _ . l requires the same amount of time as this realization of Warshall's algorithm without addition the time of packing of the matrix. A very important adventage of Warshall's algorithm for the matrix in the packed form is the possibility of computation of the transitive closure for matrices of very large orders. References

[l] Aho, A. V., Garey, M. R., Ullman, J. D.: The transitive reduction of directed graph. SIAM J. Comput. 1, 131--137 (1972). [2] Arlazarow, V. L., Dinic, E. A. Kronrod, M. A., Faradzehev, I. A. : On economical construction of the transitive closure of an oriented graph. DAN SSSR 194, 4 8 7 ~ 8 8 (1970). [3] Dzikiewicz, J. : Transitive closure algorithms. M. S. Dissertation, Dept. of Numerical Methods~ University of Wroclaw, Wroclaw 1974. [4] Dzikiewicz, J.: An algorithm for finding the transitive closure of a digraph. Computing 15, 75--79 (1975). [5] Faradzehev, I. A. : Effective algorithms for solving some problems of directed graph theory. Z. Vy~isl. Mat. i Mat. Fiz. 10, 1049--1054 (1970). [6] Fischer, M. J., Meyer, A. R. : Boolean matrix multiplication and transitive closure. IEEE Conf. Record of the Twelfth Annual Symp. on Switching and Automata Theory 1971, 129--131. [7] Floyd, R. W.: Algorithm 96: Ancestor. Comm. ACM 5, 344 (1962). [8] Furman, M. E. : Application of a method of fast multiplication of matrices in the problem of finding the transitive closure of a graph. DAN SSSR 194, 524 (1970). [9] Harary, F., Norman, R. Z., Cartwright, D. : Structural models: An introduction to the theory of directed graphs~ New York: Wiley. 1965. [10] Ma~ynjuk, V. V.: On economical construction of the transitive closure of a binary relation. ;~. Vy6isl. Mat. i Mat. Fiz. 2, 723--725 (1962). [! 1] Munro, J. I. : Efficient determination of the transitive closure of a directed graph. Information Processing Letters 1, 56--58 (1971). [12] O'Neil, P. E., O'Neil, E. J. : A fast expected time algorithm for Boolean matrix multiplication and transitive closure. Information and Control 22, 132--138 (1973). [13] Purdom, P. : A transitive closure algorithm. BIT 10, 76--94 (1970). [14] Sys~ro, M. M. : Transitive closure of a graph. Zastosow. Matem. 14, 4 7 7 ~ 8 0 (1974). [15] Tarjan, R. E. : Depth, first search and linear graph algorithms. SIAM J. Comput. I, 146--160 (1972). [16] Thorelli, L. E.: An algorithm for computing all paths in a graph. BIT 6, 347--349 (1966). [17] Warshall, S.: A theorem on Boolean matrices. Journ. ACM 9, 11--12 (1962). [18] Yen, J. Y.: Algorithms for finding all conneetivities in directed and undirected networks. Preprint, 1973. Dr. M. M. Syslo Mathematical Institute of Wroctaw University pl. Grunwaldzki 2/4 50 384 Wroetaw Poland

Mgr. J. Dzikiewicz Institute of Material Science and Technical Mechanics Technical University of Wroctaw Smoluchowskiego 25 50372 Wroctaw Poland