GSoC 2019: Проверка графов на двудольность и трансформеры монад
Прошлым летом я участвовал в Google Summer of Code — программе для студентов от компании Google. Ежегодно организаторы отбирают несколько Open Source-проектов, в том числе от таких известных организаций, как Boost.org и The Linux Foundation. Для работы над этими проектами Google приглашает студентов со всего мира.
Как участник Google Summer of Code 2019 я делал проект в рамках библиотеки Alga с организацией Haskell.org, занимающейся развитием языка Хаскелль — одного из самых известных функциональных языков программирования. Alga — библиотека, представляющая типобезопасное представление для графов в Хаскелле. Она используется, например, в semantic — библиотеке компании Github, строящей по коду семантические деревья, графы вызовов и зависимостей и умеющей их сравнивать. Мой проект состоял в добавлении туда типобезопасного представления для двудольных графов и алгоритмов для этого представления.
В посте я расскажу про свою реализацию алгоритма проверки графа на двудольность на Хаскелле. Несмотря на то, что алгоритм является одним из самых базовых, его красивая реализация в функциональном стиле заняла у меня несколько итераций и потребовала довольно много работы. В результате я остановился на реализации с трансформерами монад.
Меня зовут Василий Алфёров, я студент четвёртого курса Питерской Вышки. Ранее в блоге я писал про мой проект про параметризованные алгоритмы и про поездку на ZuriHac. Прямо сейчас я нахожусь на стажировке в Бергенском университете в Норвегии, где занимаюсь подходами к задаче List Coloring. В сферу моих интересов входят параметризованные алгоритмы и функциональное программирование.
Предисловие
Студентам, участвующим в программе, настоятельно рекомендуется вести блог. Мне для блога предоставили площадку Summer of Haskell. Эта статья — перевод статьи, написанной мной туда в июле на английском языке, с небольшим предисловием.
Pull Request с кодом, про который идёт речь, можно найти тут.
Про результаты моей работы можно почитать (на английском) здесь.
Пост предполагает знакомство читателя с базовыми понятиями в функциональном программировании, хотя я постараюсь напомнить все используемые термины, когда до них дойдёт время.
Проверка графов на двудольность
Алгоритм проверки графа на двудольность обычно даётся в курсе алгоритмов как один из простейших графовых алгоритмов. Его идея прямолинейна: сначала мы каким-то образом кладём вершины в левую или правую долю, а при обнаружении конфликтного ребра утверждаем, что граф не является двудольным.
Чуть подробнее: сначала мы кладём какую-то вершину в левую долю. Очевидно, все соседи этой вершины должны лежать в правой доле. Далее, все соседи соседей этой вершины должны лежать в левой доле, и так далее. Мы продолжаем назначать вершинам доли до тех пор, пока в компоненте связности вершины, с которой мы начали, ещё есть вершины, которым мы не назначили соседей. Затем мы повторяем это действие для всех компонент связности.
Если есть ребро между вершинами, попавшими в одну и ту же долю, несложно найти в графе нечётный цикл, как широко известно (и достаточно очевидно) невозможный в двудольном графе. Иначе у нас есть корректное разбиение на доли, а значит, граф является двудольным.
Как правило, этот алгоритм реализуют с помощью поиска в ширину или поиска в глубину. В императивных языках обычно используют поиск в глубину, как чуть-чуть более простой и не требующий дополнительных структур данных. Я также выбрал поиск в глубину как более традиционный.
Таким образом, мы пришли к следующей схеме. Мы обходим вершины графа с помощью поиска в глубину и назначаем им доли, меняя номер доли при переходе по ребру. Если мы пытаемся назначить долю вершине, у которой доля уже назначена, можно смело утверждать, что граф не является двудольным. В тот момент, когда всем вершинам назначена доля и мы посмотрели на все рёбра, у нас есть хорошее разбиение.
Чистота вычислений
В Хаскелле мы предполагаем, что все вычисления являются чистыми. Однако, если бы это действительно было так, у нас не было бы возможности напечатать что-либо на экран. Вообще, чистые вычисления настолько ленивы, что не существует ни одной чистой причины что-либо вычислять. Все вычисления, происходящие в программе, так или иначе форсируются в «нечистой» монаде IO.
Монады — способ представления вычислений с эффектами в Хаскелле. Объяснение того, как они работают, выходит за рамки этого поста. Хорошее и понятное описание можно почитать на английском тут.
Здесь я хочу заметить, что в то время как некоторые монады, такие, как IO, реализованы через магию компилятора, почти все остальные реализованы программно и все вычисления в них являются чистыми.
Эффектов бывает очень много и под каждый заведена своя монада. Это очень сильная и красивая теория: все монады реализуют один и тот же интерфейс. Мы будем говорить о следующих трёх монадах:
- Either e a — вычисление, возвращающее значение типа a или кидающее исключение типа e. Поведение этой монады очень похоже на работу с исключениями в императивных языках: ошибки могут быть пойманы или переданы дальше. Основная разница в том, что монада полностью логически реализована в стандартной библиотеке на том же Хаскелле, в то время как в императивных языках обычно используются механизмы операционной системы.
- State s a — вычисление, возвращающее значение типа a и имеющее доступ к изменяемому состоянию типа s.
- Maybe a. Монада Maybe выражает вычисление, которое может быть в любой момент прервано возвращением Nothing. Однако мы будем говорить про реализацию класса MonadPlus для типа Maybe, выражающую противоположный эффект: это вычисление, которое может быть в любой момент прервано возвращением конкретного значения.
Реализация алгоритма
У нас есть два типа данных, Graph a и Bigraph a b, первый из которых представляет графы с вершинами, помеченными значениями типа a, а второй представляет двудольные графы с вершинами левой части, помеченными значениями типа a и вершинами правой части, помеченными значениями типа b.
Это не типы из библиотеки Alga. В Alga нет представления для ненаправленных двудольных графов. Типы я сделал такими для наглядности.
Также нам понадобятся вспомогательные функции со следующими сигнатурами:
-- Список соседей данной вершины.
neighbours :: Ord a => a -> Graph a -> [a]
-- Построить двудольный граф по графу и функции, для каждой вершины
-- выдающей её долю и пометку в новой доле, игнорируя конфликтные рёбра.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graph a
-> Bigraph b c
-- Список вершин в графе
vertexList :: Ord a => Graph a -> [a]
Сигнатура функции, которую мы будем писать, выглядит так:
type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)
Несложно заметить, что если в процессе поиска в глубину мы нашли конфликтное ребро, нечётный цикл лежит сверху стека рекурсии. Таким образом, чтобы восстановить его, нам нужно отрезать у стека рекурсии всё до первого вхождения последней вершины.
Мы реализуем поиск в глубину, поддерживая ассоциативный массив номеров доли для каждой вершины. Стек рекурсии будет автоматически поддерживаться через реализацию класса Functor выбранной нами монады: надо будет лишь класть все вершины с пути в результат, возвращаемый из рекурсивной функции.
Первой моей идеей было использовать монаду Either, которая вроде как реализует как раз те эффекты, которые нам нужны. Первая написанная мной реализация была очень близкой к этому варианту. На самом деле, у меня было пять разных реализаций в какой-то момент, и я в итоге остановился на другой.
Во-первых, нам нужно поддерживать ассоциативный массив идентификаторов долей — это что-то про State. Во-вторых, нам нужно уметь останавливаться в случае обнаружения конфликта. Это может быть или Monad для Either, или MonadPlus для Maybe. Основная разница в том, что Either может возвращать значение в случае, если вычисление не было остановлено, а Maybe возвращает в таком случае лишь информацию об этом. Поскольку нам не нужно отдельное значение в случае успеха (оно уже хранится в State), мы выбираем Maybe. А в тот момент, когда нам нужно комбинировать эффекты двух монад, вылезают трансформеры монад, которые как раз и комбинируют эти эффекты.
Почему я выбрал такой сложный тип? Две причины. Во-первых, реализация получается очень похожей на императивную. Во-вторых, нам нужно манипулировать значением, возвращаемым в случае конфликта, при возврате назад из рекурсии для восстановления нечётного цикла, а это гораздо проще делать в монаде Maybe.
Таким образом, мы получаем такую реализацию.
{-# LANGUAGE ExplicitForAll #-}
{-# LANGUAGE ScopedTypeVariables #-}
data Part = LeftPart | RightPart
otherPart :: Part -> Part
otherPart LeftPart = RightPart
otherPart RightPart = LeftPart
type PartMap a = Map.Map a Part
type OddCycle a = [a]
toEither :: Ord a => PartMap a -> a -> Either a a
toEither m v = case fromJust (v `Map.lookup` m) of
LeftPart -> Left v
RightPart -> Right v
type PartMonad a = MaybeT (State (PartMap a)) [a]
detectParts :: forall a. Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)
detectParts g = case runState (runMaybeT dfs) Map.empty of
(Just c, _) -> Left $ oddCycle c
(Nothing, m) -> Right $ toBipartiteWith (toEither m) g
where
inVertex :: Part -> a -> PartMonad a
inVertex p v = ((:) v) <$> do modify $ Map.insert v p
let q = otherPart p
msum [ onEdge q u | u <- neigbours v g ]
{-# INLINE onEdge #-}
onEdge :: Part -> a -> PartMonad a
onEdge p v = do m <- get
case v `Map.lookup` m of
Nothing -> inVertex p v
Just q -> do guard (q /= p)
return [v]
processVertex :: a -> PartMonad a
processVertex v = do m <- get
guard (v `Map.notMember` m)
inVertex LeftPart v
dfs :: PartMonad a
dfs = msum [ processVertex v | v <- vertexList g ]
oddCycle :: [a] -> [a]
oddCycle c = tail (dropWhile ((/=) last c) c)
Блок where — это ядро алгоритма. Я постараюсь объяснить, что происходит внутри него.
- inVertex — это часть поиска в глубину, в которой мы посещаем вершину впервые. Здесь мы присваиваем вершине номер доли и запускаем onEdge для всех соседей. Также это место, где мы восстанавливаем стек вызовов: если msum вернул значение, мы навешиваем туда вершину v.
- onEdge — это часть, в которой мы посещаем ребро. Она вызывается дважды для каждого ребра. Здесь мы проверяем, посещена ли вершина с другой стороны, и посещаем её, если нет. Если посещена, проверяем, не является ли ребро конфликтным. Если является, возвращаем значение — самую верхушку стека рекурсии, куда потом при возврате навесятся все остальные вершины.
- processVertex проверяет для каждой вершины, посещена ли она, и запускает на ней inVertex, если нет.
- dfs запускает processVertex на всех вершинах.
На этом всё.
История слова INLINE
Слова INLINE не было в первой реализации алгоритма, оно появилось позже. Когда я пытался найти лучшую реализацию, я обнаружил, что на некоторых графах версия без INLINE работает заметно медленее. С учётом того, что семантически функции должны работать одинаково, это меня сильно удивило. Ещё более странно, что на другой машине с другой версией GHC никакой разницы заметно не было.
После того, как я потратил неделю на чтение вывода GHC Core, я смог исправить проблему одной строчкой с явным INLINE. В какой-то момент между GHC 8.4.4 и GHC 8.6.5 оптимизатор перестал это делать самостоятельно.
Я не ожидал встретить такую грязь в программировании на Хаскелле. Однако оптимизаторы всё же даже в наше время иногда совершают ошибки и давать им подсказки — наша задача. Например, здесь мы знаем, что функция должна быть заинлайнена, так как она заинлайнена в императивной версии, и это повод дать компилятору подсказку.
Что было дальше?
Дальше я реализовал алгоритм Хопкрофта-Карпа уже с другими монадами, и на этом программа закончилась.
Благодаря Google Summer of Code я приобрёл практический опыт в функциональном программировании, который не только помог мне пройти на стажировку в Jane Street на следующее лето (не уверен, насколько это место известно даже среди знающей аудитории Хабра, но оно — одно из немногих, где можно летом заниматься функциональным программированием), но и познакомил с удивительным миром применения этой парадигмы на практике, значительно отличающимся от моего опыта в традиционных языках.
