The Goal
There are many algorithms in other Julia packages capable of finding maximum cardinality matches in bipartite graphs. However, those algorithms are very general, and mostly use linear programming or generic flow algorithms. For most small instances of bipartite matching those algorithms will work fine, but they do not scale nearly as well on large problems as algorithms optimized for bipartite graphs. BipartiteMatching.jl provides a method of finding max cardinality matches that performs extremely well on both very small and very large bipartite graphs.
The Algorithm
The algorithm used for this package is a breadth-first search for augmenting paths, which is shown to be fast in practice in the paper Sequential and Parallel Experimental Results with Bipartite Matching Algorithms by Joao C. Setubal. The algorithm is implemented nearly as described in the aforementioned paper, but it has one added procedure. While, Hopcroft-Karp is known to be slower in practice than a breadth first search, the obervations used to construct the Hopcroft-Karp algorithm can be used to speed up a breadth-first search by running different sub-routines depending on which part of the augmenting path the breadth-first search is on. I have not found any mention of this in existing literature, but I would be surprised if it was an original observation.
Performance
The following data was collected on my laptop which has a 2.6 GHz Quad-Core Intel Core i7 processor. For each listed time, 100 graphs were created randomly (10 for the 218 node graphs), and the average solve time was reported. The values in the number of nodes column are the number of total nodes in the graph being solved. The density is the percent of maximum possible edges that were incuded in the graph. Solve times are reported in seconds for each category.
| Number of Nodes | Density = 10% | Density = 50% | Density = 90% |
|---|---|---|---|
| 210 | .00049 | .00025 | .00021 |
| 212 | .0031 | .0028 | .0027 |
| 214 | .049 | .051 | .055 |
| 216 | 0.71 | 0.71 | 0.64 |
| 218 | 9.69 | 9.58 | 9.59 |
Next Steps
- At the moment the package only performs maximum cardinality matches, I intend to add the ability to handle maximum weight matches.
- It accepts only BitArray{2} as an input right now, but if there is interest in using this with other data structures, let me know and I will probably be happy to add it.
Very Long Term Plan
- For the last couple years I have been writing highly optimized algorithms in Julia. As part of my thesis I hope to tie many of them together in a package that offers near state-of-the-art performance for solving many common graph theoretical problems. BipartiteMatching.jl may be small in scope, but it is my first foray into contributing to the Julia ecosystem, and I hope to make a more significant contribution in the future.
