BipartiteMatching

bpm.go

// refer https://www.geeksforgeeks.org/maximum-bipartite-matching/

package main

import "fmt"

func BPM(graph [][]bool, m, n int) []int {
	matchR := make([]int, n)
	matchR, _ = fill(matchR, -1, 0, len(matchR))
	for u := 0; u < m; u++ {
		seen := make([]bool, n)
		search(graph, u, seen, matchR, m, n)
	}
	return matchR
}

func search(graph [][]bool, u int, seen []bool, matchR []int, m, n int) bool {
	for v := 0; v < n; v++ {
		if graph[u][v] && !seen[v] {
			seen[v] = true
			if matchR[v] < 0 || search(graph, matchR[v], seen, matchR, m, n) {
				matchR[v] = u
				return true
			}
		}
	}
	return false
}

func fill(slice []int, val, start, end int) ([]int, error) {
	if len(slice) < start || len(slice) < end {
		return nil, fmt.Errorf("Error")
	}
	for i := start; i < end; i++ {
		slice[i] = val
	}
	return slice, nil
}

func main() {
	graph := [][]bool{
		{false, true, true},
		{false, false, true},
		{true, true, false},
	}
	m := 3
	n := 3
	matchR := BPM(graph, m, n)

	fmt.Println("Pairs (s, t)")
	for i, v := range matchR {
		fmt.Printf("(%d, %d)\n", v, i)
	}
}