graph

package

v0.11.0 Latest Latest Go to latest Published: Jan 19, 2025 License: MIT, BSD-3-Clause Imports: 2 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 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

Constants ¶

This section is empty.

Variables ¶

This section is empty.

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

Source Files ¶

View all Source files

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