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

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

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

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

Оптимизации, предложенные Ильёй, показали свою состоятельность при решении задачи достижимости для всех пар вершин. Помогут ли они ускорить алгоритм для нескольких стартовых вершин, который был ранее предложен Арсением Тереховым: * Multiple-Source Context-Free Path Querying in Terms of Linear Algebra

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