#matching #graph #edge #weighted #compute #undirected #maximum-weighted

mwmatching

Maximum-Weight Matching: Compute a maximum-weighted matching in the general undirected weighted graph given by 'edges'

2 releases

Uses old Rust 2015

0.1.1 Jul 11, 2018
0.1.0 Jun 28, 2018

#523 in Science

Download history 44/week @ 2024-10-14 37/week @ 2024-10-21 73/week @ 2024-10-28 60/week @ 2024-11-04 89/week @ 2024-11-11 98/week @ 2024-11-18 92/week @ 2024-11-25 69/week @ 2024-12-02 49/week @ 2024-12-09 31/week @ 2024-12-16 10/week @ 2024-12-23 22/week @ 2024-12-30 64/week @ 2025-01-06 77/week @ 2025-01-13 81/week @ 2025-01-20 55/week @ 2025-01-27

278 downloads per month

MIT license

53KB
780 lines

mwmatching

Weighted maximum matching in general graphs.

This is a Rust re-implementation of a Python program by Joris van Rantwijk. Nearly all of the comments are taken directly from that version. For the original code, go to http://jorisvr.nl/article/maximum-matching.

Compute a maximum-weighted matching in the general undirected weighted graph given by "edges".
General usage:

  let mates = Matching::new(edges).solve();

or

  let mates = Matching::new(edges).max_cardinality().solve();

If "max_cardinality()" is used, then only maximum-cardinality matchings are considered as solutions.

Edges is a sequence of tuples (i, j, wt) describing an undirected edge between vertex i and vertex j with weight wt. Currently, wt must be an i32. There is at most one edge between any two vertices; no vertex has an edge to itself. Vertices are identified by consecutive, non-negative integers (usize).

Returns a list "mates", such that mates[i] == j if vertex i is matched to vertex j, and mates[i] == SENTINEL if vertex i is not matched, where SENTINEL is usize::max_value().

No runtime deps