maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2020-1-86-94mais-1290Research ArticleSoftwareПараллельный алгоритм решения задачи об изоморфизме графовParallel Algorithm for Solving the Graph Isomorphism Problemhttps://orcid.org/0000-0001-7882-8906ВасильчиковВладимир ВасильевичVasilchikovVladimir Vasilyevich

канд. техн. наук, зав. кафедрой вычислительных и программных систем

PhD

vvv193@mail.ruЯрославский государственный университет им. П. Г. ДемидоваРоссияP. G. Demidov Yaroslavl State UniversityRussian Federation2020190320202718694Copyright © Васильчиков В.В., 20202020Васильчиков В.В.Vasilchikov V.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1290

В данной работе предлагается параллельный алгоритм решения задачи об изоморфизме графов. Целевым результатом для нас выступает построение подходящей подстановки вершин, либо доказательство отсутствия таковой. Задача решается для неориентированных графов без петель и кратных ребер, допускается, что графы могут быть несвязными. Вопрос о существовании либо отсутствии алгоритма с полиномиальной трудоемкостью в настоящее время является открытым. Следовательно, как и для любой трудоемкой задачи, возникает вопрос об ускорении ее решения за счет распараллеливания алгоритма. Для организации параллельных вычислений автором использовалась библиотека RPM_ParLib, которая позволяет создавать параллельные приложения, работающие в локальной вычислительной сети под управлением среды исполнения .NET Framework. Библиотека поддерживает рекурсивно-параллельный стиль программирования и обеспечивает эффективное распределение работы и динамическую балансировку загрузки вычислительных модулей в процессе исполнения программы. Она может быть использована для приложений, написанных на любом языке программирования, поддерживаемом .NET Framework. Для решения нашей задачи и проведения численного эксперимента было разработано несколько приложений на языке C#. Целью эксперимента было исследование ускорения, достигаемого за счет рекурсивно-параллельной организации вычислений. В качестве исходных данных использовались специально сгенерированные случайные регулярные графы с различной степенью вершин. Подробное описание алгоритма и эксперимента, а также полученные результаты также приводятся в работе.

In this paper, we offer an efficient parallel algorithm for solving the Graph Isomorphism Problem. Our goal is to construct a suitable vertex substitution or to prove the absence of such. The problem is solved for undirected graphs without loops and multiple edges, it is assumed that the graphs can be disconnected. ‘e question of the existence or absence of an algorithm for solving this problem with polynomial complexity is currently open. Therefore, as for any time-consuming task, the question arises of accelerating its solution by parallelizing the algorithm. We used the RPM ParLib library developed by the author as the main tool to program the algorithm. This library allows us to develop effective applications for parallel computing on a local network in the .NET Framework. Such applications have the ability to generate parallel branches of computation directly during program execution and dynamically redistribute work between computing modules. Any language with support for the .NET Framework can be used as a programming language in conjunction with this library. For our experiments, we developed some C# applications using this library. The main purpose of these experiments was to study the acceleration achieved by recursive-parallel computing. Specially generated random regular graphs with varying degrees of vertices were used as initial data. A detailed description of the algorithm and its testing, as well as the results obtained, are also given in the paper.

изоморфизм графовпараллельный алгоритмрекурсия.NETgraph isomorphism problemparallel algorithmrecursion.NETРабота выполнена в рамках инициативной НИР ВИП-004 (номер госрегистрации АААА-А16-116070610022-6).This work was supported by initiative program VIP-004 (state registration number AAAA-A16-116070610022-6).ReferencesM. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co, San Francisco, 1979.M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co, San Francisco, 1979.D. C. Schmidt and L. E. Druffel, “A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices”, Journal of the ACM (JACM), vol. 23, no. 3, pp. 433–445, 1976.D. C. Schmidt and L. E. Druffel, “A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices”, Journal of the ACM (JACM), vol. 23, no. 3, pp. 433–445, 1976.L. Babai, “Graph isomorphism in quasipolynomial time”, in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, 2016, pp. 684–697.L. Babai, “Graph isomorphism in quasipolynomial time”, in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, 2016, pp. 684–697.F. Harary, Graph theory. Addison-Wesley, 1969.F. Harary, Graph theory. Addison-Wesley, 1969.Y. German, O. German, and A. Dunaev, “An algorithm for establishing graph’s isomorfism”, Proceedings of BSTU. Issue 3, Physics and mathematics. Informatics, no. 2 (200), pp. 114–117, 2017.Y. German, O. German, and A. Dunaev, “An algorithm for establishing graph’s isomorfism”, Proceedings of BSTU. Issue 3, Physics and mathematics. Informatics, no. 2 (200), pp. 114–117, 2017.V. K. Pogrebnoy and A. Pogrebnoy, “Polynomial algorithm of computing complete graph invariant on the basis of integral structure descriptor”, Bulletin of the Tomsk Polytechnic University, vol. 323, no. 5, pp. 152–159, 2013.V. K. Pogrebnoy and A. Pogrebnoy, “Polynomial algorithm of computing complete graph invariant on the basis of integral structure descriptor”, Bulletin of the Tomsk Polytechnic University, vol. 323, no. 5, pp. 152–159, 2013.V. K. Pogrebnoy and A. Pogrebnoy, “Polynomiality of method for computing graph structure integral descriptor”, Bulletin of the Tomsk Polytechnic University, vol. 323, no. 5, pp. 146–151, 2013.V. K. Pogrebnoy and A. Pogrebnoy, “Polynomiality of method for computing graph structure integral descriptor”, Bulletin of the Tomsk Polytechnic University, vol. 323, no. 5, pp. 146–151, 2013.A. Pogrebnoy, “Complete graph invariant and algorithm of its computation”, Bulletin of the Tomsk Polytechnic University, vol. 325, no. 5, pp. 110–122, 2014.A. Pogrebnoy, “Complete graph invariant and algorithm of its computation”, Bulletin of the Tomsk Polytechnic University, vol. 325, no. 5, pp. 110–122, 2014.A. Pogrebnoy and V. K. Pogrebnoy, “Method of graph vertices differentiation and solution of the isomorphism problem”, Bulletin of the Tomsk Polytechnic University, vol. 326, no. 6, pp. 34–45, 2015.A. Pogrebnoy and V. K. Pogrebnoy, “Method of graph vertices differentiation and solution of the isomorphism problem”, Bulletin of the Tomsk Polytechnic University, vol. 326, no. 6, pp. 34–45, 2015.A. Pogrebnoy and V. K. Pogrebnoy, “Method of graph vertices differentiation and solution of the isomorphism problem in geoinformatics”, Bulletin of the Tomsk Polytechnic University, vol. 326, no. 11, pp. 56–66, 2015.A. Pogrebnoy and V. K. Pogrebnoy, “Method of graph vertices differentiation and solution of the isomorphism problem in geoinformatics”, Bulletin of the Tomsk Polytechnic University, vol. 326, no. 11, pp. 56–66, 2015.B. F. Melnikov and N. P. Churikova, “Algorithms of Comparative Analysis of Two Invariants of a Graph”, Sovremennye informacionnye tehnologii i IT-obrazovanie (Modern Information Technologies and IT-Education), vol. 15, no. 1, pp. 45–51, 2019.B. F. Melnikov and N. P. Churikova, “Algorithms of Comparative Analysis of Two Invariants of a Graph”, Sovremennye informacionnye tehnologii i IT-obrazovanie (Modern Information Technologies and IT-Education), vol. 15, no. 1, pp. 45–51, 2019.G. S. Ivanova and V. A. Ovchinnikov, “Completely described undirected graph structure”, Science and Education of the Bauman MSTU, no. 4, pp. 106–123, 2016.G. S. Ivanova and V. A. Ovchinnikov, “Completely described undirected graph structure”, Science and Education of the Bauman MSTU, no. 4, pp. 106–123, 2016.V. V. Vasilchikov, Sredstva parallelnogo programmirovaniya dlya vychislitelnykh sistem s dinamicheskoy balansirovkoy zagruzki. YarGU, Yaroslavl, 2001.V. V. Vasilchikov, Sredstva parallelnogo programmirovaniya dlya vychislitelnykh sistem s dinamicheskoy balansirovkoy zagruzki. YarGU, Yaroslavl, 2001.V. V. Vasilchikov, “Kommunikatsionnyy modul dlya organizatsii polnosvyaznogo soedineniya kompyuterov v lokalnoy seti s ispolzovaniem .NET Framework”, Svidetelstvo o gosudarstvennoy registratsii programmy dlya EVM № 2013619925, 2013.V. V. Vasilchikov, “Kommunikatsionnyy modul dlya organizatsii polnosvyaznogo soedineniya kompyuterov v lokalnoy seti s ispolzovaniem .NET Framework”, Svidetelstvo o gosudarstvennoy registratsii programmy dlya EVM № 2013619925, 2013.V. V. Vasilchikov, “Biblioteka podderzhki rekursivno-parallelnogo programmirovaniya dlya .NET Framework”, Svidetelstvo o gosudarstvennoy registratsii programmy dlya EVM № 2013619926, 2013.V. V. Vasilchikov, “Biblioteka podderzhki rekursivno-parallelnogo programmirovaniya dlya .NET Framework”, Svidetelstvo o gosudarstvennoy registratsii programmy dlya EVM № 2013619926, 2013.V. V. Vasilchikov, “On the recursive-parallel programming for the. NET framework”, Automatic Control and Computer Sciences, vol. 48, no. 7, pp. 575–580, 2014.V. V. Vasilchikov, “On the recursive-parallel programming for the. NET framework”, Automatic Control and Computer Sciences, vol. 48, no. 7, pp. 575–580, 2014.V. V. Vasilchikov, “On optimization and parallelization of the little algorithm for solving the travelling salesman problem”, Automatic Control and Computer Sciences, vol. 51, no. 7, pp. 551–557, 2017.V. V. Vasilchikov, “On optimization and parallelization of the little algorithm for solving the travelling salesman problem”, Automatic Control and Computer Sciences, vol. 51, no. 7, pp. 551–557, 2017.V. V. Vasilchikov, “On a recursive-parallel algorithm for solving the knapsack problem”, Automatic Control and Computer Sciences, vol. 52, no. 7, pp. 810–816, 2018.V. V. Vasilchikov, “On a recursive-parallel algorithm for solving the knapsack problem”, Automatic Control and Computer Sciences, vol. 52, no. 7, pp. 810–816, 2018.A. Steger and N. Wormald, “Generating random regular graphs quickly”, Combinatorics, Probability and Computing, vol. 8, no. 4, pp. 377–396, 1999.A. Steger and N. Wormald, “Generating random regular graphs quickly”, Combinatorics, Probability and Computing, vol. 8, no. 4, pp. 377–396, 1999.

The authors declare that there are no conflicts of interest present.