graph

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 modified minimally in order to cut down the dependencies to zero.

Run import.sh to update the package from time to time.

Documentation

Index

• func Alloc(m, n int) (mat [][]float64)
• func Imax(a, b int) int
• func IntAlloc(m, n int) (mat [][]int)
• func IntAssertLessThan(a, b int)
• func Min(a, b float64) float64
• func Panic(a string)
• func Sf(msg string, prm ...interface{}) string
• type MaskType
• type Munkres
  • func (o *Munkres) Init(nrow, ncol int)
  • func (o *Munkres) Run()
  • func (o *Munkres) SetCostMatrix(C [][]float64)
  • func (o *Munkres) StrCostMatrix() (l string)

Functions

func Alloc

func Alloc(m, n int) (mat [][]float64)

Alloc allocates a slice of slices of float64.

func Imax

func Imax(a, b int) int

Imax returns the maximum between two integers

func IntAlloc

func IntAlloc(m, n int) (mat [][]int)

IntAlloc allocates a matrix of integers.

func IntAssertLessThan

func IntAssertLessThan(a, b int)

IntAssertLessThan panics if a >= b.

func Min

func Min(a, b float64) float64

Min returns the minimum between two float point numbers.

func Panic

func Panic(a string)

Panic just panics.

func Sf

func Sf(msg string, prm ...interface{}) string

Sf wraps Sprintf

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