maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2022-1-30-43mais-1606Research ArticleSoftwareРекурсивно-параллельный алгоритм решения задачи об изоморфизме граф-подграфRecursive-Parallel Algorithm for Solving the Graph-Subgraph Isomorphism Problemhttps://orcid.org/0000-0001-7882-8906ВасильчиковВладимир ВасильевичVasilchikovVladimir V.vvv193@mail.ruЯрославский государственный университет им. П. Г. ДемидоваРоссияP. G. Demidov Yaroslavl State UniversityRussian Federation2022170320222913043Copyright © Васильчиков В.В., 20222022Васильчиков В.В.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/1606

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

The paper proposes a parallel algorithm for solving the Graph-Subgraph Isomorphism Problem and makes an experimental study of its efficiency. The problem is one of the most famous NP-complete problems. Its solution may be required when solving many practical problems associated with the study of complex structures. We solve the problem in a formulation that requires finding all existing isomorphic substitutions or proving their absence. In view of the high complexity of the problem, it is natural to want to speed up 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 under the control of the runtime environment .NET Framework. Thanks to this library, 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 of the .NET Framework can be used as a programming language in conjunction with this library. For the numerical experiment, an open database from the Internet was used, which was specially developed to study algorithms for searching for isomorphic substitutions. Also, the author has developed a special application in C# for generating additional sets of initial data with specified characteristics. The aim of the experiment was to study the speedup achieved due to the recursively parallel organization of computations. The paper provides a detailed description of the proposed algorithm, as well as the results obtained during the experiment.

изоморфизм граф-подграфпараллельный алгоритмрекурсия.NETgraph-subgraph isomorphism problemparallel algorithmrecursion.NETReferencesM. 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.J. R. Ullmann, “An Algorithm for Subgraph Isomorphism”, Journal of the Association for Computing Machinery, vol. 23, no. 1, pp. 31-42, 1976.J. R. Ullmann, “An Algorithm for Subgraph Isomorphism”, Journal of the Association for Computing Machinery, vol. 23, no. 1, pp. 31-42, 1976.L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, “Performance evaluation of the VF Graph Matching Algorithm”, in Proc. of the 10th ICIAP. IEEE Computer SocietyPress, 1999, pp. 1172-1177.L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, “Performance evaluation of the VF Graph Matching Algorithm”, in Proc. of the 10th ICIAP. IEEE Computer SocietyPress, 1999, pp. 1172-1177.L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, “An Improved Algorithm for Matching Large Graphs”, in Proc. of the 3rd IAPR-TC-15 International Workshop on Graph-based Representations - Italy, 2001, pp. 149-159.L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, “An Improved Algorithm for Matching Large Graphs”, in Proc. of the 3rd IAPR-TC-15 International Workshop on Graph-based Representations - Italy, 2001, pp. 149-159.V. Carletti, P. Foggia, A. Saggese, and M. Vento, “Challenging the Time Complexity of Exact Subgraph Isomorphism for Huge and Dense Graphs with VF3”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 40, no. 4, pp. 804-818, 2018.V. Carletti, P. Foggia, A. Saggese, and M. Vento, “Challenging the Time Complexity of Exact Subgraph Isomorphism for Huge and Dense Graphs with VF3”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 40, no. 4, pp. 804-818, 2018.M. B. Il’yashenko, “Unificirovannyj podhod k resheniyu zadach morfizma na grafah”, Elektronnoe modelirovanie, vol. 30, no. 1, pp. 19-41, 2008.M. B. Il’yashenko, “Unificirovannyj podhod k resheniyu zadach morfizma na grafah”, Elektronnoe modelirovanie, vol. 30, no. 1, pp. 19-41, 2008.M. B. Il’yashenko, “Reshenie zadachi poiska graf-podgraf izomorfizma dlya semanticheskogo analiza specializirovannyh cifrovyh sistem”, Nauchnye trudy DonTU. Seriya ”Informatika, kibernetika i vychislitel’naya tekhnika”, vol. 16, pp. 46-57, 2012.M. B. Il’yashenko, “Reshenie zadachi poiska graf-podgraf izomorfizma dlya semanticheskogo analiza specializirovannyh cifrovyh sistem”, Nauchnye trudy DonTU. Seriya ”Informatika, kibernetika i vychislitel’naya tekhnika”, vol. 16, pp. 46-57, 2012.J. R. Ullmann, “Bit-Vector Algorithms for Binary Constraint Satisfaction and Subgraph Isomorphism”, Journal of Experimental Algorithmics, vol. 15, no. 1, pp. 1-64, 2011.J. R. Ullmann, “Bit-Vector Algorithms for Binary Constraint Satisfaction and Subgraph Isomorphism”, Journal of Experimental Algorithmics, vol. 15, no. 1, pp. 1-64, 2011.M. B. Il’yashenko, “Razrabotka i issledovanie parallel’nogo algoritma proverki graf-podgraf izomorfizma”, Radioelektronika. Informatika. Upravlenie, vol. 1, pp. 63-69, 2006.M. B. Il’yashenko, “Razrabotka i issledovanie parallel’nogo algoritma proverki graf-podgraf izomorfizma”, Radioelektronika. Informatika. Upravlenie, vol. 1, pp. 63-69, 2006.V. Carletti, P. Foggia, P. Ritrovato, M. Vento, and V. Vigilante, “A parallel Algorithm for Subgraph Isomorphism”, in International Workshop on Graph-Based Representations in Pattern Recognition, ser. LNCS, vol. 11510, Springer, Cham, 2019, pp. 141-151.V. Carletti, P. Foggia, P. Ritrovato, M. Vento, and V. Vigilante, “A parallel Algorithm for Subgraph Isomorphism”, in International Workshop on Graph-Based Representations in Pattern Recognition, ser. LNCS, vol. 11510, Springer, Cham, 2019, pp. 141-151.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, 2013.V. V. Vasilchikov, Kommunikatsionnyy modul dlya organizatsii polnosvyaznogo soedineniya kompyuterov v lokalnoy seti s ispolzovaniem.NET Framework, 2013.V. V. Vasilchikov, Biblioteka podderzhki rekursivno-parallelnogo programmirovaniya dlya.NET Framework, 2013.V. V. Vasilchikov, Biblioteka podderzhki rekursivno-parallelnogo programmirovaniya dlya.NET Framework, 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.V. V. Vasilchikov, “Parallel algorithm for solving the graph isomorphism problem”, Modeling and analysis of information systems, vol. 27, no. 1, pp. 86-94, 2020.V. V. Vasilchikov, “Parallel algorithm for solving the graph isomorphism problem”, Modeling and analysis of information systems, vol. 27, no. 1, pp. 86-94, 2020.P. Foggia, C. Sansone, and M. Vento, A Database of Graphs for Isomorphism and Sub-Graph Isomorphism Benchmarkin, 2001. [Online]. Available: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.6803&rep=rep1&type=pdf.P. Foggia, C. Sansone, and M. Vento, A Database of Graphs for Isomorphism and Sub-Graph Isomorphism Benchmarkin, 2001. [Online]. Available: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.6803&rep=rep1&type=pdf.

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