munkres

README

munkres

an implementation of the Hungarian algorithm

This code is heavily based on Bob Pilgrim's work outlined here.

Example

m := NewMatrix(4)
m.A = []int64{94, 93, 20, 37,
        75, 18, 71, 43,
        20, 29, 32, 25,
        37, 72, 17, 73}
fmt.Println(ComputeMunkresMin(m)) // [{0 3} {1 1} {2 0} {3 2}]

The assignment set which minimizes the total utility is:

(0, 3) = 37
(1, 1) = 18
(2, 0) = 20
(3, 2) = 17
       = 92

License

see LICENSE file

Author(s)

Brian Fallik - bfallik at clypd.com

Dependencies

This packages uses stretchr/testify for help with unit test assertions.

Development

We are no longer actively maintaining this package. Please fork it if you wish to develop it further.

Other

Thanks to clypd for agreeing to release this code into the wild.

Documentation

Index

• Variables
• type Context
  • func (ctx *Context) String() string
• type Mark
• type Matrix
  • func NewMatrix(n int) *Matrix
  • func (m *Matrix) Print()
• type RowCol
  • func ComputeMunkresMax(m *Matrix) []RowCol
  • func ComputeMunkresMin(m *Matrix) []RowCol
• type Step
• type Step1
  • func (Step1) Compute(ctx *Context) (Step, bool)
• type Step2
  • func (Step2) Compute(ctx *Context) (Step, bool)
• type Step3
  • func (Step3) Compute(ctx *Context) (Step, bool)
• type Step4
  • func (Step4) Compute(ctx *Context) (Step, bool)
• type Step5
  • func (Step5) Compute(ctx *Context) (Step, bool)
• type Step6
  • func (Step6) Compute(ctx *Context) (Step, bool)

Variables

var (
	Debugger func(Step, *Context) = func(Step, *Context) {}
)

Types

type Context

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

func (*Context) String

func (ctx *Context) String() string

type Mark

type Mark int

const (
	Unset Mark = iota
	Starred
	Primed
)

type Matrix

type Matrix struct {
	A []int64
	// contains filtered or unexported fields
}

func NewMatrix

func NewMatrix(n int) *Matrix

func (*Matrix) Print

func (m *Matrix) Print()

type RowCol

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

func ComputeMunkresMax

func ComputeMunkresMax(m *Matrix) []RowCol

func ComputeMunkresMin

func ComputeMunkresMin(m *Matrix) []RowCol

type Step

type Step interface {
	Compute(*Context) (Step, bool)
}

type Step1

type Step1 struct{}

func (Step1) Compute

func (Step1) Compute(ctx *Context) (Step, bool)

type Step2

type Step2 struct{}

func (Step2) Compute

func (Step2) Compute(ctx *Context) (Step, bool)

type Step3

type Step3 struct{}

func (Step3) Compute

func (Step3) Compute(ctx *Context) (Step, bool)

type Step4

type Step4 struct{}

func (Step4) Compute

func (Step4) Compute(ctx *Context) (Step, bool)

type Step5

type Step5 struct{}

func (Step5) Compute

func (Step5) Compute(ctx *Context) (Step, bool)

type Step6

type Step6 struct{}

func (Step6) Compute

func (Step6) Compute(ctx *Context) (Step, bool)