This is a java program to implement Hungarian Algorithm for Bipartite Matching. The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal-dual methods.
Here is the source code of the Java Program to Implement the Hungarian Algorithm for Bipartite Matching. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
package com.maixuanviet.graph; import java.util.Arrays; import java.util.Scanner; public class HungarianBipartiteMatching { private final double[][] costMatrix; private final int rows, cols, dim; private final double[] labelByWorker, labelByJob; private final int[] minSlackWorkerByJob; private final double[] minSlackValueByJob; private final int[] matchJobByWorker, matchWorkerByJob; private final int[] parentWorkerByCommittedJob; private final boolean[] committedWorkers; public HungarianBipartiteMatching(double[][] costMatrix) { this.dim = Math.max(costMatrix.length, costMatrix[0].length); this.rows = costMatrix.length; this.cols = costMatrix[0].length; this.costMatrix = new double[this.dim][this.dim]; for (int w = 0; w < this.dim; w++) { if (w < costMatrix.length) { if (costMatrix[w].length != this.cols) { throw new IllegalArgumentException("Irregular cost matrix"); } this.costMatrix[w] = Arrays.copyOf(costMatrix[w], this.dim); } else { this.costMatrix[w] = new double[this.dim]; } } labelByWorker = new double[this.dim]; labelByJob = new double[this.dim]; minSlackWorkerByJob = new int[this.dim]; minSlackValueByJob = new double[this.dim]; committedWorkers = new boolean[this.dim]; parentWorkerByCommittedJob = new int[this.dim]; matchJobByWorker = new int[this.dim]; Arrays.fill(matchJobByWorker, -1); matchWorkerByJob = new int[this.dim]; Arrays.fill(matchWorkerByJob, -1); } protected void computeInitialFeasibleSolution() { for (int j = 0; j < dim; j++) { labelByJob[j] = Double.POSITIVE_INFINITY; } for (int w = 0; w < dim; w++) { for (int j = 0; j < dim; j++) { if (costMatrix[w][j] < labelByJob[j]) { labelByJob[j] = costMatrix[w][j]; } } } } public int[] execute() { /* * Heuristics to improve performance: Reduce rows and columns by their * smallest element, compute an initial non-zero dual feasible solution * and * create a greedy matching from workers to jobs of the cost matrix. */ reduce(); computeInitialFeasibleSolution(); greedyMatch(); int w = fetchUnmatchedWorker(); while (w < dim) { initializePhase(w); executePhase(); w = fetchUnmatchedWorker(); } int[] result = Arrays.copyOf(matchJobByWorker, rows); for (w = 0; w < result.length; w++) { if (result[w] >= cols) { result[w] = -1; } } return result; } protected void executePhase() { while (true) { int minSlackWorker = -1, minSlackJob = -1; double minSlackValue = Double.POSITIVE_INFINITY; for (int j = 0; j < dim; j++) { if (parentWorkerByCommittedJob[j] == -1) { if (minSlackValueByJob[j] < minSlackValue) { minSlackValue = minSlackValueByJob[j]; minSlackWorker = minSlackWorkerByJob[j]; minSlackJob = j; } } } if (minSlackValue > 0) { updateLabeling(minSlackValue); } parentWorkerByCommittedJob[minSlackJob] = minSlackWorker; if (matchWorkerByJob[minSlackJob] == -1) { /* * An augmenting path has been found. */ int committedJob = minSlackJob; int parentWorker = parentWorkerByCommittedJob[committedJob]; while (true) { int temp = matchJobByWorker[parentWorker]; match(parentWorker, committedJob); committedJob = temp; if (committedJob == -1) { break; } parentWorker = parentWorkerByCommittedJob[committedJob]; } return; } else { /* * Update slack values since we increased the size of the * committed * workers set. */ int worker = matchWorkerByJob[minSlackJob]; committedWorkers[worker] = true; for (int j = 0; j < dim; j++) { if (parentWorkerByCommittedJob[j] == -1) { double slack = costMatrix[worker][j] - labelByWorker[worker] - labelByJob[j]; if (minSlackValueByJob[j] > slack) { minSlackValueByJob[j] = slack; minSlackWorkerByJob[j] = worker; } } } } } } protected int fetchUnmatchedWorker() { int w; for (w = 0; w < dim; w++) { if (matchJobByWorker[w] == -1) { break; } } return w; } protected void greedyMatch() { for (int w = 0; w < dim; w++) { for (int j = 0; j < dim; j++) { if (matchJobByWorker[w] == -1 && matchWorkerByJob[j] == -1 && costMatrix[w][j] - labelByWorker[w] - labelByJob[j] == 0) { match(w, j); } } } } protected void initializePhase(int w) { Arrays.fill(committedWorkers, false); Arrays.fill(parentWorkerByCommittedJob, -1); committedWorkers[w] = true; for (int j = 0; j < dim; j++) { minSlackValueByJob[j] = costMatrix[w][j] - labelByWorker[w] - labelByJob[j]; minSlackWorkerByJob[j] = w; } } protected void match(int w, int j) { matchJobByWorker[w] = j; matchWorkerByJob[j] = w; } protected void reduce() { for (int w = 0; w < dim; w++) { double min = Double.POSITIVE_INFINITY; for (int j = 0; j < dim; j++) { if (costMatrix[w][j] < min) { min = costMatrix[w][j]; } } for (int j = 0; j < dim; j++) { costMatrix[w][j] -= min; } } double[] min = new double[dim]; for (int j = 0; j < dim; j++) { min[j] = Double.POSITIVE_INFINITY; } for (int w = 0; w < dim; w++) { for (int j = 0; j < dim; j++) { if (costMatrix[w][j] < min[j]) { min[j] = costMatrix[w][j]; } } } for (int w = 0; w < dim; w++) { for (int j = 0; j < dim; j++) { costMatrix[w][j] -= min[j]; } } } protected void updateLabeling(double slack) { for (int w = 0; w < dim; w++) { if (committedWorkers[w]) { labelByWorker[w] += slack; } } for (int j = 0; j < dim; j++) { if (parentWorkerByCommittedJob[j] != -1) { labelByJob[j] -= slack; } else { minSlackValueByJob[j] -= slack; } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("Enter the dimentsions of the cost matrix: "); System.out.println("r:"); int r = sc.nextInt(); System.out.println("c:"); int c = sc.nextInt(); System.out.println("Enter the cost matrix: <row wise>"); double[][] cost = new double[r]; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { cost[i][j] = sc.nextDouble(); } } HungarianBipartiteMatching hbm = new HungarianBipartiteMatching(cost); int[] result = hbm.execute(); System.out.println("Bipartite Matching: " + Arrays.toString(result)); sc.close(); } }
Output:
$ javac HungarianBipartiteMatching.java $ java HungarianBipartiteMatching Enter the dimentsions of the cost matrix: r: 4 c: 4 Enter the cost matrix: <row wise> 82 83 69 92 77 37 49 92 11 69 5 86 8 9 98 23 Bipartite Matching: [2, 1, 0, 3] //worker 1 should perform job 3, worker 2 should perform job 2 and so on...
Related posts:
Java Program to Perform Finite State Automaton based Search
Java Program to Implement PriorityQueue API
Tips for dealing with HTTP-related problems
Generic Constructors in Java
Comparing Arrays in Java
Java Program to implement Bit Matrix
Java Program to Implement Rope
Từ khóa throw và throws trong Java
Java Program to Implement Regular Falsi Algorithm
Giới thiệu HATEOAS
Spring 5 Functional Bean Registration
Java Program to Describe the Representation of Graph using Incidence Matrix
Hashing a Password in Java
Tìm hiểu về xác thực và phân quyền trong ứng dụng
Java Program to Implement Graph Coloring Algorithm
LinkedList trong java
Spring Boot - Servlet Filter
Spring Boot - Batch Service
Hướng dẫn Java Design Pattern – Proxy
Guide to DelayQueue
Một số tính năng mới về xử lý ngoại lệ trong Java 7
Transaction Propagation and Isolation in Spring @Transactional
Spring Cloud AWS – EC2
Java InputStream to String
Java Map With Case-Insensitive Keys
Guide to java.util.concurrent.BlockingQueue
Java Program to Check Whether a Directed Graph Contains a Eulerian Path
Java Program to Implement SynchronosQueue API
Java Program to implement Array Deque
Overview of Spring Boot Dev Tools
Java Program to Check if a Directed Graph is a Tree or Not Using DFS
Command-Line Arguments in Java