Liking cljdoc? Tell your friends :D

# 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

``````[ageneau/blossom "0.1.1"]
[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
``````

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

Can you improve this documentation?Edit on GitHub

cljdoc is a website building & hosting documentation for Clojure/Script libraries

× close