Java Program to Implement the Hungarian Algorithm for Bipartite Matching

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.

  1.  
  2. package com.hinguapps.graph;
  3.  
  4. import java.util.Arrays;
  5. import java.util.Scanner;
  6.  
  7. public class HungarianBipartiteMatching
  8. {
  9.     private final double[][] costMatrix;
  10.     private final int        rows, cols, dim;
  11.     private final double[]   labelByWorker, labelByJob;
  12.     private final int[]      minSlackWorkerByJob;
  13.     private final double[]   minSlackValueByJob;
  14.     private final int[]      matchJobByWorker, matchWorkerByJob;
  15.     private final int[]      parentWorkerByCommittedJob;
  16.     private final boolean[]  committedWorkers;
  17.  
  18.     public HungarianBipartiteMatching(double[][] costMatrix)
  19.     {
  20.         this.dim = Math.max(costMatrix.length, costMatrix[0].length);
  21.         this.rows = costMatrix.length;
  22.         this.cols = costMatrix[0].length;
  23.         this.costMatrix = new double[this.dim][this.dim];
  24.         for (int w = 0; w < this.dim; w++)
  25.         {
  26.             if (w < costMatrix.length)
  27.             {
  28.                 if (costMatrix[w].length != this.cols)
  29.                 {
  30.                     throw new IllegalArgumentException("Irregular cost matrix");
  31.                 }
  32.                 this.costMatrix[w] = Arrays.copyOf(costMatrix[w], this.dim);
  33.             }
  34.             else
  35.             {
  36.                 this.costMatrix[w] = new double[this.dim];
  37.             }
  38.         }
  39.         labelByWorker = new double[this.dim];
  40.         labelByJob = new double[this.dim];
  41.         minSlackWorkerByJob = new int[this.dim];
  42.         minSlackValueByJob = new double[this.dim];
  43.         committedWorkers = new boolean[this.dim];
  44.         parentWorkerByCommittedJob = new int[this.dim];
  45.         matchJobByWorker = new int[this.dim];
  46.         Arrays.fill(matchJobByWorker, -1);
  47.         matchWorkerByJob = new int[this.dim];
  48.         Arrays.fill(matchWorkerByJob, -1);
  49.     }
  50.  
  51.     protected void computeInitialFeasibleSolution()
  52.     {
  53.         for (int j = 0; j < dim; j++)
  54.         {
  55.             labelByJob[j] = Double.POSITIVE_INFINITY;
  56.         }
  57.         for (int w = 0; w < dim; w++)
  58.         {
  59.             for (int j = 0; j < dim; j++)
  60.             {
  61.                 if (costMatrix[w][j] < labelByJob[j])
  62.                 {
  63.                     labelByJob[j] = costMatrix[w][j];
  64.                 }
  65.             }
  66.         }
  67.     }
  68.  
  69.     public int[] execute()
  70.     {
  71.         /*
  72.          * Heuristics to improve performance: Reduce rows and columns by their
  73.          * smallest element, compute an initial non-zero dual feasible solution
  74.          * and
  75.          * create a greedy matching from workers to jobs of the cost matrix.
  76.          */
  77.         reduce();
  78.         computeInitialFeasibleSolution();
  79.         greedyMatch();
  80.         int w = fetchUnmatchedWorker();
  81.         while (w < dim)
  82.         {
  83.             initializePhase(w);
  84.             executePhase();
  85.             w = fetchUnmatchedWorker();
  86.         }
  87.         int[] result = Arrays.copyOf(matchJobByWorker, rows);
  88.         for (w = 0; w < result.length; w++)
  89.         {
  90.             if (result[w] >= cols)
  91.             {
  92.                 result[w] = -1;
  93.             }
  94.         }
  95.         return result;
  96.     }
  97.  
  98.     protected void executePhase()
  99.     {
  100.         while (true)
  101.         {
  102.             int minSlackWorker = -1, minSlackJob = -1;
  103.             double minSlackValue = Double.POSITIVE_INFINITY;
  104.             for (int j = 0; j < dim; j++)
  105.             {
  106.                 if (parentWorkerByCommittedJob[j] == -1)
  107.                 {
  108.                     if (minSlackValueByJob[j] < minSlackValue)
  109.                     {
  110.                         minSlackValue = minSlackValueByJob[j];
  111.                         minSlackWorker = minSlackWorkerByJob[j];
  112.                         minSlackJob = j;
  113.                     }
  114.                 }
  115.             }
  116.             if (minSlackValue > 0)
  117.             {
  118.                 updateLabeling(minSlackValue);
  119.             }
  120.             parentWorkerByCommittedJob[minSlackJob] = minSlackWorker;
  121.             if (matchWorkerByJob[minSlackJob] == -1)
  122.             {
  123.                 /*
  124.                  * An augmenting path has been found.
  125.                  */
  126.                 int committedJob = minSlackJob;
  127.                 int parentWorker = parentWorkerByCommittedJob[committedJob];
  128.                 while (true)
  129.                 {
  130.                     int temp = matchJobByWorker[parentWorker];
  131.                     match(parentWorker, committedJob);
  132.                     committedJob = temp;
  133.                     if (committedJob == -1)
  134.                     {
  135.                         break;
  136.                     }
  137.                     parentWorker = parentWorkerByCommittedJob[committedJob];
  138.                 }
  139.                 return;
  140.             }
  141.             else
  142.             {
  143.                 /*
  144.                  * Update slack values since we increased the size of the
  145.                  * committed
  146.                  * workers set.
  147.                  */
  148.                 int worker = matchWorkerByJob[minSlackJob];
  149.                 committedWorkers[worker] = true;
  150.                 for (int j = 0; j < dim; j++)
  151.                 {
  152.                     if (parentWorkerByCommittedJob[j] == -1)
  153.                     {
  154.                         double slack = costMatrix[worker][j]
  155.                                 - labelByWorker[worker] - labelByJob[j];
  156.                         if (minSlackValueByJob[j] > slack)
  157.                         {
  158.                             minSlackValueByJob[j] = slack;
  159.                             minSlackWorkerByJob[j] = worker;
  160.                         }
  161.                     }
  162.                 }
  163.             }
  164.         }
  165.     }
  166.  
  167.     protected int fetchUnmatchedWorker()
  168.     {
  169.         int w;
  170.         for (w = 0; w < dim; w++)
  171.         {
  172.             if (matchJobByWorker[w] == -1)
  173.             {
  174.                 break;
  175.             }
  176.         }
  177.         return w;
  178.     }
  179.  
  180.     protected void greedyMatch()
  181.     {
  182.         for (int w = 0; w < dim; w++)
  183.         {
  184.             for (int j = 0; j < dim; j++)
  185.             {
  186.                 if (matchJobByWorker[w] == -1
  187.                         && matchWorkerByJob[j] == -1
  188.                         && costMatrix[w][j] - labelByWorker[w] - labelByJob[j] == 0)
  189.                 {
  190.                     match(w, j);
  191.                 }
  192.             }
  193.         }
  194.     }
  195.  
  196.     protected void initializePhase(int w)
  197.     {
  198.         Arrays.fill(committedWorkers, false);
  199.         Arrays.fill(parentWorkerByCommittedJob, -1);
  200.         committedWorkers[w] = true;
  201.         for (int j = 0; j < dim; j++)
  202.         {
  203.             minSlackValueByJob[j] = costMatrix[w][j] - labelByWorker[w]
  204.                     - labelByJob[j];
  205.             minSlackWorkerByJob[j] = w;
  206.         }
  207.     }
  208.  
  209.     protected void match(int w, int j)
  210.     {
  211.         matchJobByWorker[w] = j;
  212.         matchWorkerByJob[j] = w;
  213.     }
  214.  
  215.     protected void reduce()
  216.     {
  217.         for (int w = 0; w < dim; w++)
  218.         {
  219.             double min = Double.POSITIVE_INFINITY;
  220.             for (int j = 0; j < dim; j++)
  221.             {
  222.                 if (costMatrix[w][j] < min)
  223.                 {
  224.                     min = costMatrix[w][j];
  225.                 }
  226.             }
  227.             for (int j = 0; j < dim; j++)
  228.             {
  229.                 costMatrix[w][j] -= min;
  230.             }
  231.         }
  232.         double[] min = new double[dim];
  233.         for (int j = 0; j < dim; j++)
  234.         {
  235.             min[j] = Double.POSITIVE_INFINITY;
  236.         }
  237.         for (int w = 0; w < dim; w++)
  238.         {
  239.             for (int j = 0; j < dim; j++)
  240.             {
  241.                 if (costMatrix[w][j] < min[j])
  242.                 {
  243.                     min[j] = costMatrix[w][j];
  244.                 }
  245.             }
  246.         }
  247.         for (int w = 0; w < dim; w++)
  248.         {
  249.             for (int j = 0; j < dim; j++)
  250.             {
  251.                 costMatrix[w][j] -= min[j];
  252.             }
  253.         }
  254.     }
  255.  
  256.     protected void updateLabeling(double slack)
  257.     {
  258.         for (int w = 0; w < dim; w++)
  259.         {
  260.             if (committedWorkers[w])
  261.             {
  262.                 labelByWorker[w] += slack;
  263.             }
  264.         }
  265.         for (int j = 0; j < dim; j++)
  266.         {
  267.             if (parentWorkerByCommittedJob[j] != -1)
  268.             {
  269.                 labelByJob[j] -= slack;
  270.             }
  271.             else
  272.             {
  273.                 minSlackValueByJob[j] -= slack;
  274.             }
  275.         }
  276.     }
  277.  
  278.     public static void main(String[] args)
  279.     {
  280.         Scanner sc = new Scanner(System.in);
  281.         System.out.println("Enter the dimentsions of the cost matrix: ");
  282.         System.out.println("r:");
  283.         int r = sc.nextInt();
  284.         System.out.println("c:");
  285.         int c = sc.nextInt();
  286.         System.out.println("Enter the cost matrix: <row wise>");
  287.         double[][] cost = new double[r][c];
  288.         for (int i = 0; i < r; i++)
  289.         {
  290.             for (int j = 0; j < c; j++)
  291.             {
  292.                 cost[i][j] = sc.nextDouble();
  293.             }
  294.         }
  295.         HungarianBipartiteMatching hbm = new HungarianBipartiteMatching(cost);
  296.         int[] result = hbm.execute();
  297.         System.out.println("Bipartite Matching: " + Arrays.toString(result));
  298.         sc.close();
  299.     }
  300. }

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...

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.