me.lomin.sinho.bipartite — me.lomin/sinho 4.0.1

Bipartite-matching primitives for structural subset reasoning.

Implements Kuhn's augmenting-paths algorithm — a graph traversal that finds the maximum number of schema clauses that can be paired without reuse. Used by me.lomin.sinho.matcher to check structural exhaustiveness in set and map matching.

This is purely graph-algorithmic and is not coinductive in the type-theory sense.

build-cost-matrix clj/s

(build-cost-matrix cost-fn m n)

Build adjacency data for bipartite matching. Returns {:zero-adj (fn [i] -> seq of j with cost 0)}.

greedy-assignment clj/s

(greedy-assignment sorted-pairs)

Greedy bipartite assignment from sorted pairs.

max-bipartite-matching clj/s

(max-bipartite-matching adj-fn m)

Find maximum bipartite matching, return the assignment map. adj-fn: (fn [left-idx]) -> seq of right indices with cost 0. m: number of left nodes. Returns: map of left-idx -> right-idx for matched pairs.

max-bipartite-matching-count clj/s

(max-bipartite-matching-count adj-fn m)

Find maximum bipartite matching size using augmenting paths. adj-fn: (fn [left-idx]) -> seq of right indices with cost 0. m: number of left nodes.