#graph #matching

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

#1265 in Data structures

Download history 135/week @ 2023-11-10 248/week @ 2023-11-17 78/week @ 2023-11-24 120/week @ 2023-12-01 65/week @ 2023-12-08 203/week @ 2023-12-15 52/week @ 2023-12-22 128/week @ 2023-12-29 122/week @ 2024-01-05 317/week @ 2024-01-12 242/week @ 2024-01-19 134/week @ 2024-01-26 116/week @ 2024-02-02 113/week @ 2024-02-09 95/week @ 2024-02-16 105/week @ 2024-02-23

436 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