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.3"]
[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 edges [[1 2 2][1 3 -2][2 3 1][2 4 -1][3 4 -6]])
(def g (-> (lg/weighted-graph) (lg/add-edges* edges)))

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

;; Compute the maximum-cardinality matching with maximum weight among all
;; maximum-cardinality matchings.
(def maxc-matching (mwm/max-weight-matching edges {: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.