bipartite.go

package bipartite

//! # Maximum bipartite matching implementation

// Various resources for my own benefit
// - https://www.youtube.com/watch?v=HZLKDC9OSaQ
// - https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6_042JF10_chap05.pdf
// - https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm
// - https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm
// - https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm
// - http://olympiad.cs.uct.ac.za/presentations/camp2_2017/bipartitematching-robin.pdf

// Returns the size of the maximum matching set of the
// bipartite graph represented by the adjacency matrix
// `edges` with `mCount` rows and `nCount` columns.
// `seen` and `matches` are implementation-specific data structures
// that are expected to be correctly sized by the caller to reduce
// runtime allocations.
// Implementation based on the "Alternate Approach" from
// http://olympiad.cs.uct.ac.za/presentations/camp2_2017/bipartitematching-robin.pdf
func MaximumBipartiteMatching(e *[]uint8, mCount int, nCount int, s *[]*bool, m *[]*int) int {
	matchCount := 0

	if e == nil || s == nil || m == nil {
		return matchCount
	}

	edges := *e
	seen := *s
	matches := *m

	// reset matches
	for _, match := range matches {
		if match == nil {
			continue
		}

		*match = -1
	}

	// for each mana pip
	for m := 0; m < mCount; m++ {
		// reset lands seen
		for _, s := range seen {
			*s = false
		}

		// attempt to find a matching land
		foundMatch := recursiveFindMatch(&edges, nCount, m, &seen, &matches)
		if foundMatch {
			matchCount += 1
		}
	}

	return matchCount
}

func recursiveFindMatch(e *[]uint8, nCount int, m int, s *[]*bool, matchesPtr *[]*int) bool {
	if e == nil || s == nil || matchesPtr == nil {
		return false
	}

	edges := *e
	seen := *s
	matches := *matchesPtr
	// for each land
	for n := 0; n < nCount; n++ {
		i := nCount*m + n
		// Is this the first time we're seeing this land and does this land pay for pip m?
		if edges[i] != 0 && seen[n] != nil && !*seen[n] {
			*seen[n] = true
			// Is this land available to tap OR can we find a different land for pip (matches[n]) that
			// previously matched with this land
			thisLandOrOtherLandAvailable := (matches[n] != nil && *matches[n] < 0) || recursiveFindMatch(&edges, nCount, *matches[n], &seen, &matches)
			if thisLandOrOtherLandAvailable {
				*matches[n] = m
				return true
			}
		}
	}
	return false
}