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.4"]
[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 [email protected] Dan Schult [email protected] Pieter Swart [email protected]
Copyright © 2008 by Joris van Rantwijk.
Copyright © 2011 by Nicholas Mancuso [email protected]
Copyright © 2018 Sylvain Ageneau
All rights reserved.
This project is licensed under the BSD 3-Clause "New" or "Revised" License.