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

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

Илья Муравьёв предложил оптимизации алгоритма достижимости с ограничениями в виде КС языков, которые позволили обойти по производительности существующие аналоги:

• Optimization of the Context-Free Language Reachability Matrix-Based Algorithm
• Оптимизация алгоритма контекстно-свободной достижимости, основанного на операциях линейной алгебры

Оптимизации, предложенные Ильёй, показали свою состоятельность при решении задачи достижимости для всех пар вершин. Помогут ли они ускорить алгоритмы, которые позволяют находить пути (один или даже все)? Исходные версии алгоритмов используют ту же идею, что и алгоритм достижимости, и были предложены Рустамом Азимовым.

• Context-free path querying with all-path semantics by matrix multiplication
• Context-Free Path Querying with Single-Path Semantics by Matrix Multiplication
• Решение задач поиска путей в графе с заданными контекстно-свободными ограничениями с использованием методов линейной алгебры

В рамках работы предлагается интегрировать алгоритмы, предложенные Рустамом, в LAGraph --- библиотеку алгоритмов анализа графов, выраженных в терминах линейной алгебры, которая написана на C и использует SuiteSparse:GraphBLAS для операций над матрицами. За основу предлагается взять реализацию алгоритма достижимости, предложенную Ильхомом Комбаевым. Кроме этого, необходимо оценить применимость оптимизаций, предложенный Ильёй, для данного алгоритма и, возможно, предложить специфичные именно для поиска путей.

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

• Mutual Refinements of Context-Free Language Reachability
• A Better Approximation for Interleaved Dyck Reachability

Уровень работы зависит от объёма выполненных задач примерно следующим образом.

• Реализация базовых версий --- семестровая второго курса.
• Базовые версии и оптимизации --- 3 курс.
• Базовые версии, оптимизации, зашафленный язык скобочных последовательностей --- ВКР бакалавра.