Edmonds's blossom algorithm for maximum weight matching in undirected graphs

This library implements the Blossom algorithm that computes a maximum weighted matching of an undirected graph in O(number of nodes ** 3).

It was ported from the python code authored by Joris van Rantwijk included in the NetworkX graph library and modified.

Getting started

Add the necessary dependencies to your project:

[ageneau/blossom "0.1.0"]
[aysylu/loom "1.0.2"]

Usage

(ns test.blossom
  (:require [blossom.max-weight-matching :as mwm]
            [blossom.matching :as m]
            [loom.graph :as lg]))

(def g (-> (lg/weighted-graph)
                (lg/add-edges [1 2 2][1 3 -2][2 3 1]
                              [2 4 -1][3 4 -6])))

;; Compute a maximum weigted matching
(def maxw-matching (mwm/max-weight-matching g))
;; => #{#{1 2}}

;; Compute the maximum-cardinality matching with maximum weight among all
;; maximum-cardinality matchings.
(def maxc-matching (mwm/max-weight-matching g {:max-cardinality true}))
;; => #{#{4 2} #{1 3}}

;; Compute a maximal matching (not necessarily max weight)
(def max-matching (m/maximal-matching g))
;; => #{#{4 3} #{1 2}}

(m/is-matching? g maxw-matching)
;; => true

(m/is-maximal-matching? g maxw-matching)
;; => false

(m/is-maximal-matching? g maxc-matching)
;; => true

(m/is-maximal-matching? g max-matching)
;; => true

Unit tests

Some unit tests are auto-generated by instrumenting the python code which this project is based on running the python unit tests and outputting internal data to JSON which is then compared to the equivalent Clojure data structures.

The JSON data for these unit tests can be generated doing:

make -C python

To run the Clojure unit tests:

lein do clean, test

To run the Clojurescript unit tests:

lein do clean, doo node node-test once

License

Copyright © NetworkX developers. Copyright (C) 2004-2018 by Aric Hagberg hagberg@lanl.gov Dan Schult dschult@colgate.edu Pieter Swart swart@lanl.gov

Copyright © 2008 by Joris van Rantwijk.

Copyright © 2011 by Nicholas Mancuso nick.mancuso@gmail.com

Copyright © 2018 Sylvain Ageneau

All rights reserved.

This project is licensed under the BSD 3-Clause "New" or "Revised" License.