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

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

doi:10.17586/2226-1494-2023-23-2-271-278

2023 , ТОМ 23, НОМЕР 2 ( март-апрель )

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

Меню

Публикации

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

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

Партнеры

doi: 10.17586/2226-1494-2023-23-2-271-278

УДК 004.421.2:519.17004.657

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

Эпельбаум И.В., Азимов Р.Ш., Григорьев С.В.

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

Язык статьи - английский

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

Эпельбаум И.В., Азимов Р.Ш., Григорьев С.В. Решение задачи достижимости в графе с заданными ограничениями в виде многокомпонентной контекстно-свободной грамматики с использованием умножения матриц // Научно-технический вестник информационных технологий, механики и оптики. 2023. Т. 23, № 2. С. 271–278 (на англ. яз.). doi: 10.17586/2226-1494-2023-23-2-271-278

Аннотация

Предмет исследования. Многие задачи анализа графов могут быть сформулированы как задачи поиска путей с ограничениями в виде формальных языков. В последнее время задача достижимости в графе с заданными ограничениями в виде контекстно-свободных языков стала очень популярной и используется во многих областях, например, для запросов к графовым базам данных, для анализа RDF (Resource Description Framework) данных. Однако некоторые сложные ограничения на пути в графе не могут быть описаны с помощью контекстно-свободных языков, поэтому были предложены различные расширения. Многокомпонентные контекстно-свободные языки — одно из таких расширений. В данной работе представлены результаты разработки первого алгоритма поиска путей в графе с заданными ограничениями в виде многокомпонентных контекстно-свободных языков. Метод. Сущность предложенного алгоритма состоит в использовании набора булевых матриц и операций над ними для поиска путей в графе, удовлетворяющих заданным ограничениям. Основной операцией является умножение булевых матриц. В качестве результата алгоритм возвращает набор матриц, содержащий всю информацию, необходимую для решения задачи достижимости в графе с заданными ограничениями в виде многокомпонентного контекстно-свободного языка. Основные результаты. Представленный алгоритм реализован на языке Python с использованием стандарта GraphBLAS. Выполнен анализ реальных RDF данных и синтетических графов для некоторых классических многокомпонентных контекстно-свободных языков. Исследование показало, что при использовании разреженного формата для хранения матриц и параллельных вычислений для графов с десятками тысяч ребер время анализа может составлять 10–20 минут. Результат проведенного анализа представляет десятки миллионов пар достижимых вершин. Практическая значимость. Разработанный алгоритм может быть применен в задачах статического анализа программ, в биоинформатике, в сетевом анализе, а также в графовых базах данных, когда ограничения на пути в графе не могут быть выражены с помощью контекстно-свободных грамматик. Алгоритм основан на операциях линейной алгебры, что позволяет использовать высокопроизводительные библиотеки и задействовать современные параллельные вычислительные системы.

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

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

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

Barrett C., Jacob R., Marathe M. Formal-language-constrained path problems//SIAM Journal on Computing. 2000. V. 30. N 3.P. 809–837. https://doi.org/10.1137/S0097539798337716
Terekhov A., Khoroshev A., Azimov R., Grigorev S. Context-free pathquerying with single-path semantics by matrix multiplication//Proc. of the 3^rd Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA). 2020. P. 1–12. https://doi.org/10.1145/3398682.3399163
Zhang X., Feng Z., Wang X., Rao G., Wu W. 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
Zheng X., Rugina R. Demand-driven alias analysis for C//Proc. of the 35th Annual ACM SIGPLAN-SIGACT Symposium onPrinciples of Programming Languages.2008.P. 197–208. https://doi.org/10.1145/1328438.1328464
Sevon P., Eronen L. Subgraph queries by context-free grammars//Journal of Integrative Bioinformatics. 2008. V. 5. N 2.P. 157–172.https://doi.org/10.1515/jib-2008-100
Zhang Q., Lyu M.R., Yuan H., Su Z. Fast algorithms for dyck-cfl-reachability with applications to alias analysis // Proc. of the 34^th ACM SIGPLAN Conference on Programming Language Design and Implementation. 2013. P. 435–446. https://doi.org/10.1145/2491956.2462159
Reps T. Undecidability of context-sensitive data-dependence analysis // ACM Transactions on Programming Languages and Systems. 2000. V. 22. N 1. P. 162–186. https://doi.org/10.1145/345099.345137
Hopcroft J.E., Motwani R., Ullman J.D. Introduction to automata theory, languages, and computation // ACM Sigact News. 2001. V. 32. N 1. P. 60–65. https://doi.org/10.1145/568438.568455
Zhang Q., Su Z. Context-sensitive data-dependence analysis via linear conjunctive language reachability // Proc. of the 44^th ACM SIGPLAN Symposium on Principles of Programming Languages. 2017. P. 344–358. https://doi.org/10.1145/3009837.3009848
Kepner J., Aaltonen P., Bader D., Buluç A., Franchetti F., Gilbert J., Hutchison D., Kumar M., Lumsdaine A., Meyerhenke H., McMillan S., Yang C., Owens J.D., Zalewski M., Mattson T., Moreira J. Mathematical foundations of the graphblas // Proc. of the 2016 IEEE High Performance Extreme Computing Conference (HPEC). 2016. P. 1–9. https://doi.org/10.1109/hpec.2016.7761646
Azimov R., Epelbaum I., Grigorev S. Context-free path querying with all-path semantics by matrix multiplication // Proc. of the 4^th ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA). 2021. P. 1–7. https://doi.org/10.1145/3461837.3464513
Azimov R., Grigorev S. Context-free path querying by matrix multiplication // Proc. of the 1^stACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA). 2018. P. 1–10. https://doi.org/10.1145/3210259.3210264
Nakanish, R., Takada K., Seki H. An efficient recognition algorithm for multiple context-free languages // Proc. of the 5^th Meeting on the Mathematics of Language (MOL5). 1997. P. 119–123.
Cohen S.B., Gildea D. Parsing linear context-free rewriting systems with fast matrix multiplication // Computational Linguistics. 2016. V. 42. N 3. P. 421–455. https://doi.org/10.1162/coli_a_00254
Seki H., Matsumura T., Fujii M., Kasami T. On multiple context-free grammars // Theoretical Computer Science. 1991. V. 88. N 2. P. 191–229. https://doi.org/10.1016/0304-3975(91)90374-B
Hagberg A., Schult D., Swart P. Exploring network structure, dynamics, and function using network // Proc. of the 7^th Python in Science Conference (SciPy 2008). 2008. P. 11–15.

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