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 на следующее лето (не уверен, насколько это место известно даже среди знающей аудитории Хабра, но оно — одно из немногих, где можно летом заниматься функциональным программированием), но и познакомил с удивительным миром применения этой парадигмы на практике, значительно отличающимся от моего опыта в традиционных языках.
    Питерская Вышка
    Не для школы, а для жизни

    Комментарии 2

      0
      Можете рассказать про стажировку в Jane Street в отдельном посте?
        +1
        Доброе утро от автора статьи!
        Стажировка у меня будет этим летом. Если там найдётся интересный материал, который можно будет рассказывать — обязательно расскажу!

      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

      Самое читаемое