FastHungarian 1.0.0

FastHungarian

Fast assignment problem solver based on modified Kwok's algorithm for maximum weight matching on bipartite graphs. Supports anything from .NET Standard 2.0 to modern .NET 10+ with no dependencies. Solves both minimum cost assignment (Hungarian algorithm) and maximum weight matching problems. ~12-20× faster than classical Hungarian algorithm implementations while maintaining optimal solutions. Extensively tested with comprehensive fuzz testing across thousands of matrix configurations.

Getting Started

Install the package via NuGet:

dotnet add package FastHungarian

Solve assignment problems:

using FastHungarian;

// Cost matrix: assign workers to tasks minimizing total cost
int[,] costs = new int[,]
{
    { 10, 25, 15, 20 },  // Worker 0 costs for tasks 0-3
    { 15, 30, 5,  15 },  // Worker 1 costs for tasks 0-3
    { 20, 5,  10, 25 },  // Worker 2 costs for tasks 0-3
    { 25, 20, 15, 10 }   // Worker 3 costs for tasks 0-3
};

int[] assignments = FastHungarian.FindAssignments(costs);
// assignments[i] = task assigned to worker i
// Result: [2, 2, 1, 3] means Worker 0→Task 2, Worker 1→Task 2, etc.

⭐ That's it! The algorithm automatically handles:

• Non-square matrices (different number of workers and tasks)
• Transposition for optimal performance
• Edge retention optimization for large graphs

Advanced Usage

Get Total Cost

Matching result = FastHungarian.FindAssignmentsWithWeight(costs);
Console.WriteLine($"Optimal cost: {result.WeightSum}");
Console.WriteLine($"Assignments: {string.Join(", ", result.LeftPairs)}");

Maximum Weight Matching (Adjacency List API)

For sparse graphs or when you want to maximize weights instead of minimize costs:

// Bipartite graph: L = {0, 1, 2}, R = {0, 1, 2, 3}
// Each list contains (vertex, weight) pairs
var adjacencyList = new List<List<(int vertex, int weight)>>
{
    [(0, 10), (1, 5), (2, 3)],     // Vertex 0 edges
    [(1, 8), (2, 7), (3, 9)],      // Vertex 1 edges
    [(0, 4), (2, 12), (3, 6)]      // Vertex 2 edges
};

Matching result = FastHungarian.MaximumWeightMatching(
    leftCount: 3, 
    rightCount: 4, 
    adjacencyList
);

Console.WriteLine($"Maximum weight: {result.WeightSum}");
// result.LeftPairs[i] = matched right vertex for left vertex i
// result.RightPairs[j] = matched left vertex for right vertex j

Handling Non-Square Matrices

// More workers than tasks: some workers won't be assigned
int[,] costs = new int[5, 3];  // 5 workers, 3 tasks
int[] assignments = FastHungarian.FindAssignments(costs);
// assignments.Length == 5
// assignments[i] == -1 if worker i is not assigned

// More tasks than workers: all workers assigned, some tasks unassigned
int[,] costs2 = new int[3, 5];  // 3 workers, 5 tasks
int[] assignments2 = FastHungarian.FindAssignments(costs2);
// assignments2.Length == 3
// All assignments2[i] >= 0

Algorithm Details

FastHungarian implements modified Kwok's 2025 algorithm for maximum weight matching with several optimizations:

1. Flat adjacency list - Better cache locality vs nested lists
2. Edge retention (Theorem 4.2.1) - Reduces edges to O(|L|) per vertex using QuickSelect
3. Pre-computed labels - Eliminates redundant scans
4. Incremental slack tracking - Avoids repeated minimum calculations
5. Ring buffer BFS - Reduces queue overhead
6. Span<T> bounds check elimination (.NET 8+) - Zero-overhead array access
7. Branchless operations - Better CPU pipelining

Complexity

• Time: O(|L| × |R| × min(|L|, |R|)) worst case, typically much faster in practice
• Space: O(|L| × min(|L|, |R|)) due to edge retention
• Classical Hungarian: O(|L|³) or O(|L|² × |R|)

Performance

Benchmark results on Intel Core i7-8700 (Coffee Lake), baseline is available here:

Memory usage: ~5% less allocation than Baseline Hungarian algorithm.

Sparse matrices (90% high cost, 10% low cost): 60× faster than vanilla for 100×100.

Full benchmark results and reproduction available in the benchmark project.

Testing

FastHungarian is thoroughly tested with 11 comprehensive fuzz test suites covering:

• ✅ Square matrices (2×2 to 200×200)
• ✅ Non-square matrices (all aspect ratios)
• ✅ Extreme shapes (1×N, N×1, 10:1 ratios)
• ✅ Edge case patterns (diagonal, sparse, bimodal, outliers)
• ✅ Degenerate cases (1×1, single row/column, near-overflow)
• ✅ Total: 350+ test iterations, thousands of matrix configurations

All tests verify correctness against the proven Hungarian algorithm implementation from the HungarianAlgorithm NuGet package.

Limitations

• Integer weights: Currently supports int weights. For floating-point weights, scale to integers.

The algorithm handles:

• ✅ Non-square matrices (automatic transposition)
• ✅ Unbalanced assignments (more workers than tasks or vice versa)
• ✅ Zero costs and identical values
• ✅ Large cost ranges (tested up to int.MaxValue / 2)

Contributing

If you are looking to add new functionality, please open an issue first to verify your intent is aligned with the scope of the project. The library is covered by comprehensive fuzz tests with over 350 test iterations. Please run them against your work before proposing changes:

dotnet test

When reporting issues, providing a minimal reproduction with the specific cost matrix that fails greatly reduces turnaround time.

References

• Kwok, J. T. (2025). An Improved Algorithm for Maximum Weight Matching in Bipartite Graphs
• Based on the classical Hungarian algorithm (Kuhn-Munkres algorithm)

License

This library is licensed under the MIT license. 💜