Меню
Публикации
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
Главный редактор
![](/pic/nikiforov.jpg)
НИКИФОРОВ
Владимир Олегович
д.т.н., профессор
Партнеры
doi: 10.17586/2226-1494-2021-21-4-499-505
УДК 004.421.2:519.17 004.657
Алгоритм поиска всех путей в графе с заданными контекстно-свободными ограничениями с использованием матриц с множествами промежуточных вершин
Читать статью полностью
![](/images/pdf.png)
Язык статьи - русский
Ссылка для цитирования:
Аннотация
Ссылка для цитирования:
Азимов Р.Ш., Григорьев С.В. Алгоритм поиска всех путей в графе с заданными контекстно-свободными ограничениями с использованием матриц с множествами промежуточных вершин // Научно-технический вестник информационных технологий, механики и оптики. 2021. Т. 21, № 4. С. 499–505. doi: 10.17586/2226-1494-2021-21-4-499-505
Аннотация
Предмет исследования. Рассмотрена задача поиска путей в графе, которые удовлетворяют заданным контекстно-свободным ограничениям. Задача заключается в поиске всех путей в помеченном ориентированном графе, метки на ребрах которых образуют слова из языка, порожденного входной контекстно-свободной грамматикой. Существует два эффективных подхода к решению поставленной задачи с использованием операций линейной алгебры: с помощью обычного матричного умножения для поиска только одного пути и произведения Кронекера для поиска всех путей в графе. В настоящее время не существует алгоритма, который применяет обычное матричное умножение и способен найти все пути в соответствии с заданным контекстно-свободным ограничением. В работе предложен алгоритм поиска всех путей в графе с заданным контекстно-свободным ограничением, который основан на обычном матричном умножении. Метод. В матрицу смежности входного графа для каждой пары вершин добавляется дополнительная информация о найденных путях между этими вершинами в виде множества возможных промежуточных вершин. На первом этапе осуществлено построение множества матриц, хранящих в себе информацию обо всех путях, удовлетворяющих заданным ограничениям. На втором этапе выполнено построение искомых путей. Основные результаты. Предложенный алгоритм реализован в программе на языке С++. Проведено сравнение с эффективными алгоритмами поиска путей в графе с заданными контекстно-свободными ограничениями. Результаты экспериментального исследования показали, что предложенный алгоритм эффективнее (до 1000 раз быстрее) строит искомые пути, однако в некоторых случаях потребляет до 150 раз больший объем памяти, чем алгоритм, основанный на произведении Кронекера. Практическая значимость. Предложенный алгоритм может быть применен в задачах статического анализа кода, биоинформатике, сетевом анализе, а также в графовых базах данных, когда требуется найти все возможные зависимости в данных, представленных в виде помеченного графа.
Ключевые слова: поиск путей в графе, линейная алгебра, контекстно-свободные грамматики, матричное умножение, графовые базы данных, стандарт GraphBLAS
Благодарности. Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 19-37-90101.
Список литературы
Благодарности. Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 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. 35th 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. 33rd 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. 13th 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. 9th 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. 31st 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. 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
-
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
-
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. 1st ed. Addison-Wesley, 1995.704 p.