Эффективная разреженная булева алгебра — то, что нужно алгоритмам анализа графов

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

Читать далее