graph

package

v0.6.0 Latest Latest Go to latest Published: Feb 18, 2020 License: MIT, BSD-3-Clause Imports: 4 Imported by: 0

Details

Valid go.mod file
Redistributable license
Tagged version
Stable version
Learn more about best practices

Repository

github.com/mbrt/gmailctl

Links

Open Source Insights

README ¶

Note

This is a minimal fork of cpmech/gosl. I have copied only one file of the graph subpackage to get rid of the annoying cgo dependencies that it's carrying with it. The contents are completely unmodified.

Documentation ¶

Constants ¶

This section is empty.

Variables ¶

This section is empty.

Functions ¶

This section is empty.

Types ¶

type MaskType ¶

type MaskType int

MaskType defines the type of mask

const (

	// NoneType defines the NONE mask type
	NoneType MaskType = iota

	// StarType defines the STAR mask type
	StarType

	// PrimeType defines the PRIME mask type
	PrimeType
)

type Munkres ¶

type Munkres struct {

	// main
	C     [][]float64 // [nrow][ncol] cost matrix
	Cori  [][]float64 // [nrow][ncol] original cost matrix
	Links []int       // [nrow] will contain links/assignments after Run(), where j := o.Links[i] means that i is assigned to j. -1 means no assignment/link
	Cost  float64     // total cost after Run() and links are established

	// auxiliary
	M [][]MaskType // [nrow][ncol] mask matrix. If Mij==1, then Cij is a starred zero. If Mij==2, then Cij is a primed zero
	// contains filtered or unexported fields
}

Munkres (Hungarian algorithm) method to solve the assignment problem

based on code by Bob Pilgrim from http://csclab.murraystate.edu/bob.pilgrim/445/munkres.html
Note: this method runs in O(n²), in the worst case; therefore is not efficient for large matrix
 Example:
         $ | Clean  Sweep   Wash
    -------|--------------------
    Fry    |   [2]      3      3
    Leela  |     3    [2]      3
    Bender |     3      3    [2]
    minimum cost = 6

Note: cost will be minimised

func (*Munkres) Init ¶

func (o *Munkres) Init(nrow, ncol int)

Init initialises Munkres' structure

func (*Munkres) Run ¶

func (o *Munkres) Run()

Run runs the iterative algorithm

Output:
 o.Links -- will contain assignments, where len(assignments) == nrow and
            j := o.Links[i] means that i is assigned to j
            -1 means no assignment/link
 o.Cost -- will have the total cost by following links

func (*Munkres) SetCostMatrix ¶

func (o *Munkres) SetCostMatrix(C [][]float64)

SetCostMatrix sets cost matrix by copying from C to internal o.C

Note: costs must be positive

func (*Munkres) StrCostMatrix ¶

func (o *Munkres) StrCostMatrix() (l string)

StrCostMatrix returns a representation of cost matrix with masks and covers

Source Files ¶

View all Source files

munkres.go

?	: This menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL