greedy-bipartite-matching

Greedy Bipartite Matching

Overview

Greedy matching finds pairs between two sets of points by iteratively selecting the closest unmatched pair until no more matches are possible below a distance threshold.

Algorithm

1. Compute pairwise distances between cluster centroids and expert points
2. Repeatedly find the closest pair (centroid, expert point) below max_distance
3. Mark both as matched and remove from consideration
4. Continue until no more valid pairs can be found

Implementation

import numpy as np

def greedy_match(centroids, expert_points, max_distance=100):
    """
    Match centroids to expert points using greedy algorithm.

    Args:
        centroids: (n, 2) array of cluster centroids
        expert_points: (m, 2) array of expert annotations
        max_distance: Maximum distance for a valid match

    Returns:
        matched_pairs: List of (centroid_idx, expert_idx, distance) tuples
    """
    centroids = np.asarray(centroids)
    expert_points = np.asarray(expert_points)

    if len(centroids) == 0 or len(expert_points) == 0:
        return []

    # Compute Euclidean distances (always standard Euclidean for matching)
    distances = np.linalg.norm(
        centroids[:, np.newaxis, :] - expert_points[np.newaxis, :, :],
        axis=2
    )

    matched_pairs = []
    unmatched_centroids = set(range(len(centroids)))
    unmatched_experts = set(range(len(expert_points)))

    while unmatched_centroids and unmatched_experts:
        # Find closest unmatched pair
        min_dist = np.inf
        best_c_idx = None
        best_e_idx = None

        for c_idx in unmatched_centroids:
            for e_idx in unmatched_experts:
                dist = distances[c_idx, e_idx]
                if dist < min_dist:
                    min_dist = dist
                    best_c_idx = c_idx
                    best_e_idx = e_idx

        # If distance exceeds threshold, stop
        if min_dist > max_distance:
            break

        # Record match and remove from unmatched sets
        matched_pairs.append((best_c_idx, best_e_idx, min_dist))
        unmatched_centroids.remove(best_c_idx)
        unmatched_experts.remove(best_e_idx)

    return matched_pairs