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.

Список литературы
  1. 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
  2. ZhengX.,RuginaR. Demand-driven alias analysis for C //Proc. 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL’08). 2008.P. 197–208.https://doi.org/10.1145/1328438.1328464
  3. 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
  4. 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
  5. Medeiros C., Musicante M.A., Costa U.S. Efficient evaluation of context-free path queries for graph databases // Proc. 33rd Annual ACM Symposium on Applied Computing (SAC-2018). 2018. P. 1230–1237. https://doi.org/10.1145/3167132.3167265
  6. 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
  7. Grigorev S., Ragozina A. Context-free path querying with structural representation of result // Proc. 13th Central & Eastern European Software Engineering Conference in Russia (CEE-SECR’17). 2017. P. 3166104. https://doi.org/10.1145/3166094.3166104
  8. 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
  9. Verbitskaia E., Kirillov I., Nozkin I., Grigorev S. Parser combinators for context-free path querying // Proc. 9th ACM SIGPLAN International Symposium on Scala (Scala 2018). 2018. P. 13–23. https://doi.org/10.1145/3241653.3241655
  10. Kuijpers J., Fletcher G., Yakovets N., Lindaaker T. An experimental study of context-free path query evaluation methods // Proc. 31st International Conference on Scientific and Statistical Database Management (SSDBM-2019). 2019. P. 121–132. https://doi.org/10.1145/3335783.3335791
  11. Azimov R., Grigorev S. Context-free path querying by matrix multiplication // Proc. 1st 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
  12. Terekhov A., Khoroshev A., Azimov R., Grigorev S. Context-free path querying with single-path semantics by matrix multiplication // Proc. 3rd 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
  13. 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
  14. 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
  15. AbiteboulS., Hull R., Vianu V.Foundations ofDatabases: The Logical Level. 1st ed. Addison-Wesley, 1995.704 p.


Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Информация 2001-2021 ©
Научно-технический вестник информационных технологий, механики и оптики.
Все права защищены.

Яндекс.Метрика