.TH "Stable_matching" 3 2026-06-22 OCamldoc "OCaml library"
.SH NAME
Stable_matching \- no description
.SH Module
Module   Stable_matching
.SH Documentation
.sp
Module
.BI "Stable_matching"
 : 
.B sig end

.sp

.sp

.sp
.sp
.I module Item : 
.B sig end

.sp

.sp
.I type left_index 
= 
.B int

.sp

.sp
.I type right_index 
= 
.B int

.sp

.sp
.I type rank 
= 
.B int

.sp

.sp
.I type 
.B ('a, 'v)
.I matches 
= {
 left : 
.B 'a list
;
 pairs : 
.B ('v * 'v) list
;
 right : 
.B 'a list
;
 }

.sp

.sp
.I type 
.B ('v, 'k)
.I item_matches 
= 
.B (('v, 'k) Item.t, 'v) matches

.sp

.sp
.I type unstable_matching 
= {
 first : 
.B left_index * right_index
;
 second : 
.B left_index * right_index
;
 current_rank : 
.B rank * rank
;
 optimal : 
.B rank * rank
;
 }

.sp

.sp

.I val stable_matches 
: 
.B distance:(int -> int -> int) ->
.B   ('a, int) matches ->
.B   (unit, unstable_matching) Result.t
.sp

.sp

.I val strong_stable_matches 
: 
.B distance:(int -> int -> int) ->
.B   ('a, int) matches ->
.B   (unit, unstable_matching) Result.t
.sp

.sp

.I val matches 
: 
.B compatible:(left_index -> right_index -> bool) ->
.B   preferences:(right_index ->
.B                (left_index * rank) array) ->
.B   size:int * int -> (int, int) matches
.sp

.ft B
matches ~compatible ~preferences ~size:(ls,rs)
.ft R
computes a matching between
a set of 
.ft B
ls
.ft R
left items and 
.ft B
rs
.ft R
right items favoring the right side\&. The
matches are compatible and weakly stable according to the 
.ft B
preferences
.ft R
matrix\&. The size of the matching is at least 2/3 of the optimal matching
size (computing optimal matching with partial preferences and ties is in
NP)\&.

.sp

.I val fuzzy_match_names 
: 
.B compatibility:('k -> 'k -> bool) ->
.B   max_right_items:int ->
.B   cutoff:(string -> int) ->
.B   ('v, 'k) Item.t list ->
.B   ('v, 'k) Item.t list -> ('v, 'k) item_matches
.sp

.ft B
fuzzy_match_names ~compatibility ~max_right_item ~cutoff left right
.ft R
calls
the 
.ft B
Stable_matching\&.matches
.ft R
function using the OSA edit distance to compute preferences
with a cutoff function\&. To avoid quadratic complexity on large module size
we limit the right side to the first 
.ft B
max_right_item
.ft R
items

.sp