Summer of Haskell

Student Blog: Results for Bipartite Graphs Project

Posted on August 26, 2019 by Vasily Alferov (permalink)

I am a student at Summer of Haskell this year, and that’s my final post. This post is written to sum up the work I’ve done. Although this post is a formal requirement of GSoC, I wanted to publish it here to reach a wider audience.

My proposal

When you apply to Summer of Code, you write a proposal. The proposal is a document in which you describe your ideas on the chosen project. It should be a clear, detailed text with suggestions on every subtask. The proposal should also include a timeline, in which you estimate the time you intend to spend on each of those subtasks.

I chose this project for my summer. In my proposal, I drafted all the algorithms mentioned in the list and suggested a few more. I published this part of my proposal as a Github gist there.

I don’t suggest this gist as a complete example of a good proposal: it’s only a part of the document I submitted. You should also include some information about you, together with the timeline. Communication with your future mentors is also a significant part of the application.

However, as I mentioned in one of my previous posts, another student ended up doing the part suggested in the ideas list. So my task is to introduce bipartite graphs.

This task was my idea. I mentioned it in my proposal. I meant that finding maximum matchings in bipartite graphs should be easily implemented when we have algorithms for finding maximum flows in networks. Kuhn’s algorithm is an application of the Ford-Fulkerson algorithm, and the Hopcroft-Karp algorithm is an application of Dinic’s algorithm.

However, this option is not the best. Both algorithms have specialized implementations that work times faster. So my task for this summer was to introduce bipartite graphs and special functions for working with them.

What I’ve done

I made four pull requests to Alga this summer. Each pull request represents a separate task and summarizes the work of several weeks.

Each PR contains the actual implementation, tests, and documentation. The whole project is release-ready after merging each one of them. I put the tests in the test/ directory. The documentation for each function and datatype precedes the declaration. After release, it will compile to beautiful Haddock file like this.

Part I. Definition and properties.

Link to PR: https://github.com/snowleopard/alga/pull/207

In this part, I defined the Bipartite.AdjacencyMap datatype and added many functions to work with adjacency maps.

The datatype represents a map of vertices into their neighbours. I defined it as two maps:

data AdjacencyMap a b = BAM {
    leftAdjacencyMap :: Map.Map a (Set.Set b),
    rightAdjacencyMap :: Map.Map b (Set.Set a)
}

The properties are based on the existing properties of graphs in Alga.

Part II: Testing bipartiteness

Link to PR: https://github.com/snowleopard/alga/pull/218

There is a folklore algorithm that checks if a given graph is bipartite. The task to implement this algorithm in Haskell was a little challenging for me.

I finished up with the following definition of the function:

detectParts :: Ord a => AM.AdjacencyMap a -> Either (OddCycle a) (AdjacencyMap a a)

It is known that a graph is bipartite if and only if it contains no cycles of odd length. This function either finds an odd cycle or returns a partition.

The implementation is so exciting that I wrote a whole post about it. I explained the reason I needed monad transformers there and made some interesting benchmarks that pointed me to use the explicit INLINE directive.

[WIP] Part III. Graph families.

Link to the unfinished PR: https://github.com/snowleopard/alga/pull/226

Some families of graphs are bipartite: simple paths, even cycles, trees, bicliques, etc. The task is to provide a simple method to construct all those graphs.

The most exciting part of this task was to provide type-safe implementations. For example, only cycles of even length are bipartite. And speaking of paths, we should provide a method for constructing paths of vertices of two different types.

The circuit definition for constructing graphs containing one even cycle is simple:

circuit :: (Ord a, Ord b) => [(a, b)] -> AdjacencyMap a b

For the paths, I added a special type for alternating lists:

data List a b = Nil | Cons a (List b a)

So the path definition is:

path :: (Ord a, Ord b) => List a b -> AdjacencyMap a b

As for now, the PR is almost merge-ready, only several small comments need fixes.

[WIP] Part IV. Hopcroft-Karp algorithm for maximum matchings

Link to the unfinished PR: https://github.com/snowleopard/alga/pull/229

This algorithm is the fastest one for maximum matchings in bipartite graphs. The implementation is rather straightforward.

However, there is an aspect of this PR I’d like to share there.

I implemented the following function:

augmentingPath :: (Ord a, Ord b) => Matching a b
                                 -> AdjacencyMap a b
                                 -> Either (VertexCover a b) (List a b)

Given a matching in a graph, it returns either an augmenting path for the matching or a vertex cover of the same size, thus proving that the given matching is maximum. As both outcomes can be easily verified, this helps to write perfect tests that ensure that the matching returned by my function is maximum indeed.

This PR still needs some work. The reason is that two different implementations behave weirdly on the benchmarks.

Results

I wrote a lot of Haskell this summer. This gave me a lot of experience in this language. Although there’s still work to be done, I’m satisfied with the results I got.

I adore the way functional programs are developed. I was surprised to know how popular testing (QuickCheck) and benchmarking (Criterion) frameworks are organized. And preciseness of the documentation makes the work a lot easier.

Older posts

An RSS feed is also available.