munkres

README

An implementation of the Hungarian algorithm for solving the assignment problem. An instance of the assignment problem consists of a number of workers along with a number of jobs and a cost matrix which gives the cost of assigning the i'th worker to the j'th job at position (i, j). The goal is to find an assignment of workers to jobs so that no job is assigned more than one worker and so that no worker is assigned to more than one job in such a manner so as to minimize the total cost of completing the jobs.

An assignment for a cost matrix that has more workers than jobs will necessarily include unassigned workers, indicated by an assignment value of -1; in no other circumstance will there be unassigned workers. Similarly, an assignment for a cost matrix that has more jobs than workers will necessarily include unassigned jobs; in no other circumstance will there be unassigned jobs. For completeness, an assignment for a square cost matrix will give exactly one unique worker to each job.

This version of the Hungarian algorithm runs in time O(n^3), where n is the maximum among the number of workers and the number of jobs.

This is a Go implementation of the Java version found at https://github.com/KevinStern/software-and-algorithms/

Documentation

Overview

Package "munkres" is an implementation of Munkres's Hungarian algorithm for solving the assignment problem. An instance of the assignment problem consists of a number of workers along with a number of jobs and a cost matrix which gives the cost of assigning the i'th worker to the j'th job at position (i, j). The goal is to find an assignment of workers to jobs so that no job is assigned more than one worker and so that no worker is assigned to more than one job in such a manner so as to minimize the total cost of completing the jobs.

An assignment for a cost matrix that has more workers than jobs will necessarily include unassigned workers, indicated by an assignment value of -1; in no other circumstance will there be unassigned workers. Similarly, an assignment for a cost matrix that has more jobs than workers will necessarily include unassigned jobs; in no other circumstance will there be unassigned jobs. For completeness, an assignment for a square cost matrix will give exactly one unique worker to each job.

This version of the Hungarian algorithm runs in time O(n^3), where n is the maximum among the number of workers and the number of jobs.

ported from the Java version by Kevin L. Stern https://github.com/KevinStern/software-and-algorithms/

Index

• Variables
• type HungarianAlgorithm
  • func NewHungarianAlgorithm(costMatrix [][]float64) (HungarianAlgorithm, error)
  • func (h *HungarianAlgorithm) Execute() []int

Variables

var ErrorIrregularCostMatrix,

	ErrorInfiniteCost,

	ErrorNaNCost error

Types

type HungarianAlgorithm

type HungarianAlgorithm struct {
	// contains filtered or unexported fields
}

func NewHungarianAlgorithm

func NewHungarianAlgorithm(costMatrix [][]float64) (HungarianAlgorithm, error)

Construct an instance of the algorithm.

costMatrix is the cost matrix, where matrix[i][j] holds the cost of assigning worker i to job j, for all i, j. The cost matrix must not be irregular in the sense that all rows must be the same length; in addition, all entries must be non-infinite numbers.

func (*HungarianAlgorithm) Execute

func (h *HungarianAlgorithm) Execute() []int

Execute the algorithm.

return the minimum cost matching of workers to jobs based upon the provided cost matrix. A matching value of -1 indicates that the corresponding worker is unassigned.