<div>
	Алгоритм поиска всех путей в графе с заданными контекстно-свободными ограничениями с использованием матриц с множествами промежуточных вершин</div>

Азимов Рустам Шухратуллович , Григорьев Семён Вячеславович

doi:10.17586/2226-1494-2021-21-4-499-505

2021 , ТОМ 21, НОМЕР 4 ( июль-август )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Меню

Публикации

Главный редактор

НИКИФОРОВ
Владимир Олегович
д.т.н., профессор

Партнеры

doi: 10.17586/2226-1494-2021-21-4-499-505

УДК 004.421.2:519.17 004.657

Алгоритм поиска всех путей в графе с заданными контекстно-свободными ограничениями с использованием матриц с множествами промежуточных вершин

Азимов Р.Ш., Григорьев С.В.

Читать статью полностью

Язык статьи - русский

Ссылка для цитирования:

Азимов Р.Ш., Григорьев С.В. Алгоритм поиска всех путей в графе с заданными контекстно-свободными ограничениями с использованием матриц с множествами промежуточных вершин // Научно-технический вестник информационных технологий, механики и оптики. 2021. Т. 21, № 4. С. 499–505. doi: 10.17586/2226-1494-2021-21-4-499-505

Аннотация

Предмет исследования. Рассмотрена задача поиска путей в графе, которые удовлетворяют заданным контекстно-свободным ограничениям. Задача заключается в поиске всех путей в помеченном ориентированном графе, метки на ребрах которых образуют слова из языка, порожденного входной контекстно-свободной грамматикой. Существует два эффективных подхода к решению поставленной задачи с использованием операций линейной алгебры: с помощью обычного матричного умножения для поиска только одного пути и произведения Кронекера для поиска всех путей в графе. В настоящее время не существует алгоритма, который применяет обычное матричное умножение и способен найти все пути в соответствии с заданным контекстно-свободным ограничением. В работе предложен алгоритм поиска всех путей в графе с заданным контекстно-свободным ограничением, который основан на обычном матричном умножении. Метод. В матрицу смежности входного графа для каждой пары вершин добавляется дополнительная информация о найденных путях между этими вершинами в виде множества возможных промежуточных вершин. На первом этапе осуществлено построение множества матриц, хранящих в себе информацию обо всех путях, удовлетворяющих заданным ограничениям. На втором этапе выполнено построение искомых путей. Основные результаты. Предложенный алгоритм реализован в программе на языке С++. Проведено сравнение с эффективными алгоритмами поиска путей в графе с заданными контекстно-свободными ограничениями. Результаты экспериментального исследования показали, что предложенный алгоритм эффективнее (до 1000 раз быстрее) строит искомые пути, однако в некоторых случаях потребляет до 150 раз больший объем памяти, чем алгоритм, основанный на произведении Кронекера. Практическая значимость. Предложенный алгоритм может быть применен в задачах статического анализа кода, биоинформатике, сетевом анализе, а также в графовых базах данных, когда требуется найти все возможные зависимости в данных, представленных в виде помеченного графа.

Ключевые слова: поиск путей в графе, линейная алгебра, контекстно-свободные грамматики, матричное умножение, графовые базы данных, стандарт GraphBLAS

Благодарности. Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 19-37-90101.

Список литературы

Rehof J., Fähndrich M. Type-base flow analysis: from polymorphic subtyping to CFL-reachability // SIGPLAN Notices. 2001. V. 36. N 3. P. 54–66. https://doi.org/10.1145/373243.360208
ZhengX.,RuginaR. Demand-driven alias analysis for C //Proc. 35^th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL’08). 2008.P. 197–208.https://doi.org/10.1145/1328438.1328464
SevonP.,EronenL. Subgraph queries by context-freegrammars // Journal of Integrative Bioinformatics. 2008.V. 5. N 2. P. 157–172. https://doi.org/10.1515/jib-2008-100
Zhang X., Feng Z., Wang X., Rao G.Z., Wu W.R. Context-free path queries on RDF graphs // Lecture Notes in Computer Science. 2016. V. 9981. P. 632–648. https://doi.org/10.1007/978-3-319-46523-4_38
Medeiros C., Musicante M.A., Costa U.S. Efficient evaluation of context-free path queries for graph databases // Proc. 33^rd Annual ACM Symposium on Applied Computing (SAC-2018). 2018. P. 1230–1237. https://doi.org/10.1145/3167132.3167265
Santos F., Costa U.S., Musicante M.A. A bottom-up algorithm for answering context-free path queries in graph databases // Lecture Notes in Computer Science. 2018. V. 10845. P. 225–233. https://doi.org/10.1007/978-3-319-91662-0_17
Grigorev S., Ragozina A. Context-free path querying with structural representation of result // Proc. 13^th Central & Eastern European Software Engineering Conference in Russia (CEE-SECR’17). 2017. P. 3166104. https://doi.org/10.1145/3166094.3166104
Verbitskaia E., Grigorev S., Avdyukhin D. Relaxed parsing of regular approximations of string-embedded languages // Lecture Notes in Computer Science. 2016. V. 9609. P. 291–302. https://doi.org/10.1007/978-3-319-41579-6_22
Verbitskaia E., Kirillov I., Nozkin I., Grigorev S. Parser combinators for context-free path querying // Proc. 9^th ACM SIGPLAN International Symposium on Scala (Scala 2018). 2018. P. 13–23. https://doi.org/10.1145/3241653.3241655
Kuijpers J., Fletcher G., Yakovets N., Lindaaker T. An experimental study of context-free path query evaluation methods // Proc. 31^st International Conference on Scientific and Statistical Database Management (SSDBM-2019). 2019. P. 121–132. https://doi.org/10.1145/3335783.3335791
Azimov R., Grigorev S. Context-free path querying by matrix multiplication // Proc. 1^st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems and Network Data Analytics (GRADES-NDA 2018). 2018. P. a5. https://doi.org/10.1145/3210259.3210264
Terekhov A., Khoroshev A., Azimov R., Grigorev S. Context-free path querying with single-path semantics by matrix multiplication // Proc. 3^rd ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems and Network Data Analytics (GRADES-NDA 2020). 2020. P. 5. https://doi.org/10.1145/3398682.3399163
Orachev E., Epelbaum I., Azimov R., Grigorev S. Context-free path querying by kronecker product // Lecture Notes in Computer Science. 2020. V. 12245. P. 49–59. https://doi.org/10.1007/978-3-030-54832-2_6
Chomsky N. On certain formal properties of grammars // Information and Control. 1959. V. 2. N 2. P. 137–167. https://doi.org/10.1016/S0019-9958(59)90362-6
AbiteboulS., Hull R., Vianu V.Foundations ofDatabases: The Logical Level. 1^st ed. Addison-Wesley, 1995.704 p.

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License