Last summer, I participated in a student program from Google. Every year, the organizers select several Open Source projects, including from well-known organizations such as and . To work on these projects, Google invites students from around the world.
As a participant in Google Summer of Code 2019, I worked on a project within the library with the organization , which is dedicated to the development of the Haskell language — one of the most recognized functional programming languages. Alga is a library that provides representations for graphs in Haskell. It is used, for example, in , a library from Github that builds semantic trees, call graphs, and dependency graphs from code and can compare them. My project involved adding a type-safe representation for bipartite graphs and algorithms for that representation.
In this post, I will discuss my implementation of the algorithm for checking whether a graph is bipartite in Haskell. Although the algorithm is one of the most basic, its elegant implementation in a functional style took me several iterations and required quite a bit of work. Ultimately, I settled on an implementation using monad transformers.
About Me
My name is Vasily Alfyorov, and I am a fourth-year student at the Higher School of Economics in Saint Petersburg. Earlier in this blog, I wrote and . Right now, I am interning at in Norway, where I am working on approaches to the problem of My interests include parameterized algorithms and functional programming.
On the implementation of the algorithm
Preface
Students participating in the program are strongly encouraged to maintain a blog. I was provided with a platform for my blog, This article is a translation , which I wrote there in July in English, with a brief preface.
The Pull Request with the code discussed can be found .
You can read about the results of my work (in English) .
This post assumes that the reader is familiar with the basic concepts of functional programming, although I will try to remind all the relevant terms when the time comes.
Checking graphs for bipartiteness
The algorithm for checking if a graph is bipartite is usually presented in algorithm courses as one of the simplest graph algorithms. Its idea is straightforward: first, we somehow place the vertices into a left or right set, and upon detecting a conflicting edge, we assert that the graph is not bipartite.
To elaborate: first, we place some vertex in the left set. Obviously, all neighbors of this vertex must lie in the right set. Next, all neighbors of the neighbors of this vertex must lie in the left set, and so forth. We continue assigning sets to vertices until there are still vertices in the connected component we started from that have not been assigned neighbors. Then we repeat this action for all connected components.
If there is an edge between vertices that have ended up in the same set, it is not difficult to find an odd cycle in the graph, which is widely known (and quite obvious) to be impossible in a bipartite graph. Otherwise, we have a valid partition into sets, meaning the graph is bipartite.
Typically, this algorithm is implemented using or . In imperative languages, depth-first search is commonly used as it is somewhat simpler and does not require additional data structures. I also chose depth-first search as the more traditional approach.
Thus, we arrived at the following scheme. We traverse the vertices of the graph using depth-first search and assign them sets, changing the set number when moving along an edge. If we attempt to assign a set to a vertex that has already been assigned a set, we can confidently assert that the graph is not bipartite. At the moment when all vertices have been assigned a set and we have examined all edges, we have a good partition.
Purity of computations
In Haskell, we assume that all computations are pure. However, if that were really the case, we would not have the ability to print anything on the screen. In general, pure computations are so lazy that there is not a single pure reason to compute anything. All computations that happen in the program are forced into the "impure" IO monad.
Monads are a way to represent computations with effects. in Haskell. An explanation of how they work goes beyond this post. A good and clear description can be found in English. .
Here I want to point out that while some monads, such as IO, are implemented through compiler magic, almost all others are implemented programmatically and all computations in them are pure.
There are many effects, and each has its own monad. This is a very powerful and beautiful theory: all monads implement the same interface. We will talk about the following three monads:
- Either e a — a computation that returns a value of type a or throws an exception of type e. The behavior of this monad is very similar to handling exceptions in imperative languages: errors can be caught or propagated. The main difference is that the monad is fully logically implemented in the standard library in Haskell, whereas in imperative languages, operating system mechanisms are usually used.
- State s a — a computation that returns a value of type a and has access to mutable state of type s.
- Maybe a. The Maybe monad represents a computation that can be interrupted at any moment by returning Nothing. However, we will discuss the implementation of the MonadPlus class for the Maybe type, which expresses the opposite effect: this is a computation that can be interrupted at any moment by returning a specific value.
Algorithm implementation
We have two data types, Graph a and Bigraph a b, the first representing graphs with vertices labeled with values of type a, and the second representing bipartite graphs with left part vertices labeled with values of type a and right part vertices labeled with values of type b.
These are not types from the Alga library. Alga does not have a representation for undirected bipartite graphs. I made the types this way for clarity.
We will also need helper functions with the following signatures:
-- List of neighbors of this vertex.
neighbours :: Ord a => a -> Graph a -> [a]
-- Build a bipartite graph from the graph and a function for each vertex
-- returning its part and marker in the new part, ignoring conflicting edges.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graph a
-> Bigraph b c
-- List of vertices in the graph
vertexList :: Ord a => Graph a -> [a]
The signature of the function we will write looks like this:
type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)It is not difficult to notice that if during a depth-first search we found a conflicting edge, the odd cycle lies on top of the recursion stack. Thus, to recover it, we need to cut everything from the recursion stack to the first occurrence of the last vertex.
We will implement depth-first search while maintaining an associative array of part numbers for each vertex. The recursion stack will be automatically maintained through the implementation of the Functor class of our chosen monad: we just need to place all vertices from the path into the result returned from the recursive function.
My first idea was to use the Either monad, which seems to implement just the effects we need. The first implementation I wrote was very close to this version. In fact, I had five different implementations at one point, and I eventually settled on another.
Firstly, we need to maintain an associative array of part identifiers — this is something about State. Secondly, we need to be able to stop in case of detecting a conflict. This can be either a Monad for Either or MonadPlus for Maybe. The main difference is that Either can return a value if the computation was not stopped, while Maybe only provides information about it. Since we do not need a separate value in case of success (it is already stored in State), we choose Maybe. And the moment we need to combine the effects of two monads, we get , which precisely combine these effects.
Why did I choose such a complex type? Two reasons. First, the implementation closely resembles imperative programming. Second, we need to manipulate the value returned in the event of a conflict during backtracking from recursion to restore an odd cycle, which is much easier to do in the Maybe monad.
Thus, we get this implementation.
{-# 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 a -> PartMonad a
onEdge p v = do m 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 [a]
oddCycle c = tail (dropWhile ((/=) last c) c)
The where block is the core of the algorithm. I will try to explain what happens inside it.
- inVertex is part of the depth-first search where we visit a vertex for the first time. Here we assign a part number to the vertex and trigger onEdge for all its neighbors. This is also where we restore the call stack: if msum returns a value, we attach the vertex v there.
- onEdge is the part where we visit the edge. It is called twice for each edge. Here we check if the vertex on the other side has been visited, and we visit it if not. If it has been visited, we check whether the edge is conflicting. If it is, we return the value — the top of the recursion stack, where all other vertices will be placed upon return.
- processVertex checks whether each vertex has been visited, and runs inVertex on it if not.
- dfs runs processVertex on all vertices.
That's all.
The History of the Word INLINE
The term INLINE was not present in the first implementation of the algorithm; it emerged later. When I was searching for a better implementation, I found that on some graphs, the version without INLINE performed significantly slower. Given that semantically the functions should work the same, this surprised me greatly. Even more strangely, on another machine with a different version of GHC, there was no noticeable difference.
After spending a week reading the GHC Core output, I managed to fix the issue with a single line using explicit INLINE. At some point between GHC 8.4.4 and GHC 8.6.5, the optimizer stopped doing this automatically.
I didn't expect to encounter such messiness in Haskell programming. However, optimizers still make mistakes even in our time, and giving them hints is our task. For instance, here we know that the function should be inlined, as it is inlined in the imperative version, and this is a reason to give the compiler a hint.
What happened next?
Next, I implemented the Hopcroft-Karp algorithm with different monads, and thus the program concluded.
Thanks to Google Summer of Code, I gained practical experience in functional programming, which not only helped me secure an internship at Jane Street the following summer (I'm not sure how well-known this place is even among the knowledgeable audience of Habr, but it is one of the few places where you can engage in functional programming over the summer), but also introduced me to the amazing world of applying this paradigm in practice, which is significantly different from my experience with traditional languages.
Source: habr.com
