Fast Algorithm for Calculating Transitive Closures of Binary Relations in the Structure of a Network Object
DOI:
https://doi.org/10.47839/ijc.20.4.2444Keywords:
adjacency matrix, algorithm, computational complexity of the algorithm, disjunctive addition of matrix elements, network object, transitive closureAbstract
The article proposes a fast algorithm for constructing the transitive closures between all pairs of nodes in the structure of a network object, which can have both directional and non-directional links. The algorithm is based on the disjunctive addition of the elements of certain rows of the adjacency matrix, which models (describe) the structure of the original network object. The article formulates and proves a theorem that using such a procedure, the matrix of transitive closures of a network object can be obtained from the adjacency matrix in two iterations (traversal) on such an array. An estimate of the asymptotic computational complexity of the proposed algorithm is substantiated. The article presents the results of an experimental study of the execution time of such an algorithm on network structures of different dimensions and with different connection densities. For this indicator, the developed algorithm is compared with the well-known approaches of Bellman, Warshall-Floyd, Shimbel, which can also be used to determine the transitive closures of binary relations of network objects. The corresponding graphs of the obtained dependences are given. The proposed algorithm (the logic embedded in it) can become the basis for solving problems of monitoring the connectivity of various subscribers in data transmission networks in real time when managing the load in such networks, where the time spent on routing information flows directly depends on the execution time of control algorithms, as well as when solving other problems on the network structures.
References
R. Bellman, “On a Routing Problem,” Quarterly of Applied Mathematics, vol. 16, issue 1, pp. 87-90, 1958. https://doi.org/10.1090/qam/102435.
R. Floyd, “Algorithm 97: Shortest path,” Communications of the ACM, vol. 5, issue 6, 345 p., 1961, https://doi.org/10.1145/367766.368168.
S. Hougardy, “The Floyd-Warshall algorithm on graphs with negative cycles,” Information Processing Letters, vol. 110, no. 8-9, pp. 279-281, 2010. https://doi.org/10.1016/j.ipe.2010.02.001.
S. Warshall, “Algorithm on Boolean matrices,” Journal of the ACM, vol. 9, issue 1, pp. 11-12, 1962. https://doi.org/10.1145/321105.321107.
H. Warren, “A modification of Warshall’s algorithm for the transitive closure of binary relations,” Commun. ACM, vol. 18, issue 4, pp. 218-220, 1975. https://doi.org/10.1145/360715.360746.
Z. Ding, W. Shu and M. Wu, “FPGA based parallel transitive closure algorithm,” Proceedings of the 2011 ACM Symposium on Applied Computing SAC’11, March 2011, pp. 393-394. https://doi.org/10.1145/1982185.1982270.
A. Shimbel, “Structural parameters of communication networks,” Bulletin of Mathematical Biophysics, vol. 15, issue 4, pp. 501-507, 1953. https://doi.org/10.1007/BF02476438.
P. Purdom, “A transitive closure algorithm,” Bit 10, vol. 1, 1970, pp. 76-94. https://doi.org/10.1007/BF01940892.
T. Cormen, C. Leiserson, R. Rivest and C. Stein, Introduction to Algorithms, Second Edition. Section 22.3: Depth-first search, MIT Press and McGraw-Hill, 2001, pp. 540-549.
R. Tarjan, “Depth-first search and linear graph algorithms,” SIAM J. Computing, vol. 1, issue 2, pp. 146-160, 1972. https://doi.org/10.1137/0201010.
R. Agrawal, S. Dar and H. Jagadish, “Direct transitive closure algorithms: Design and performance evaluation,” ACM Trans. Database Syst., vol. 15, issue 3, pp. 427-458, 1990. https://doi.org/10.1145/88636.88888.
Y. Chen, “On the graph traversal and linear binary-chain programs,” IEEE Transactions on Knowledge and Data Engineering, vol. 15, pp. 573-596, 2003. https://doi.org/10.1109/TKDE.2003.1198392.
S. Dar, R. Ramarkrishnan, “A performance study of transitive closure algorithm,” Proceedings of the SIGMOD International Conference, Minneapolis, Minnesota, USA, 1994, pp. 454-465. https://doi.org/10.1145/191843.191928.
A. Velasquez, S. Jha, “Brief announcement: Parallel transitive closure within 3D crosspoint memory,” Proceedings of the 30th Symposium on Parallelism in Algorithms and Architectures SPAA '18, July 2018, pp. 95-98. https://doi.org/10.1145/3210377.3210657.
H. Jagadish, “A compression technique to materialize transitive closure,” ACM Trans. Database Systems, vol. 15, issue 4, pp. 558-598, 1990. https://doi.org/10.1145/99935.99944.
L. Cohen, R. N. S. Rowe, “non-well-founded proof theory of transitive closure logic,” ACM Transactions on Computational Logic, vol. 21, issue 4, Article no. 31, pp. 1-31, 2020. https://doi.org/10.1145/3404889.
W. Charatonik, E. Kieroński and F. Mazowiecki, “Decidability of weak logics with deterministic transitive closure,” Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL’14) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’14), July 2014, Article no. 29, pp. 1-10. https://doi.org/10.1145/2603088.2603134.
A. Eriksson, P. Jansson, “An agda formalisation of the transitive closure of block matrices (extended abstract),” Proceedings of the 1st International Workshop on Type-Driven Development TyDe’2016, September 2016, pp. 60-61. https://doi.org/10.1145/2976022.2976025.
H. Yin, A. Benson and J. Leskovec, “the local closure coefficient: a new perspective on network clustering,” Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining WSDM’19, January 2019, pp. 303–311. https://doi.org/10.1145/3289600.3290991.
J. Dzikiewicz, “An algorithm for finding the transitive closure of a digraph,” Computing, vol. 15, pp. 75-79, 1975. https://doi.org/10.1007/BF02252839.
M. Sysło, J. Dzikiewicz, “Computational experiences with some transitive closure algorithms,” Computing, vol. 15, pp. 33-39, 1975. https://doi.org/10.1007/BF02252834.
J. Eve, R. Kurki-Suonio, “On computing the transitive closure of a relation,” Acta Informatica, vol. 8, pp. 303-314, 1977. https://doi.org/10.1007/BF00271339.
L. Schmitz, “An improved transitive closure algorithm,” Computing, vol. 30, pp. 359-371, 1983. https://doi.org/10.1007/BF02242140.
Y. Ioannidis, R. Ramakrishnan and L. Winger, “Transitive closure algorithms based on graph traversal,” ACM Trans. Database Syst., vol. 18, vol. 3, pp. 512-576, 1993. https://doi.org/10.1145/155271.155273.
A. Kuznetsov, Mathematical Modeling of Design Objects in ADS, Kharkov Military University Press, Kharkov, Ukraine, 1994, 92 p.
C. Lee, “An algorithm for path connections and its applications,” IEEE Transactions on Electronic Computers, vol. 10, no. 3, pp. 346-365, 1961. https://doi.org/10.1109/TEC.1961.5219222.
K. Hanauer, M. Henzinger and C. Schulz, “Faster fully dynamic transitive closure in practice”, Proceedings of the 18th International Symposium on Experimental Algorithms (SEA’2020), 2020, Article no. 14; pp. 1-14. https://doi.org/10.4230/LIPIcs.SEA.2020.14.
V. Pieterse, L. Cleophas, “Benchmarking optimized algorithms for transitive closure,” Proceedings of the South African Institute of Computer Scientists and Information Technologists SAICSIT’17, September 2017, vol. 27, pp. 1-10. https://doi.org/10.1145/3129416.3129425.
V. Lipskyy, Combinatory for Programmers, Moscow, Mir Press., 1988, 213 p. (in Russian)
R. Al-Dujaily, T. Mak, F. Xia, A. Yakovlev and M. Palesi, “Embedded Transitive Closure Network for Runtime Deadlock Detection in Networks-on-Chip”, IEEE Transactions on Parallel and Distributed Systems, vol. 23, issue 7, pp. 1205-1215, 2012. https://doi.org/10.1109/TPDS.2011.275.
Downloads
Published
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
