Gale-Shapley Algorithm in Golang

Acceptor.go

package Village

type Acceptor struct {
  Name string
  preferences map[*Proposer]int
  Free bool
  partner *Proposer
  proposalPool []*Proposer
}

func NewAcceptor(name string) Acceptor {
  return Acceptor{Name: name, Free: true, proposalPool: []*Proposer {}}
}

// This adds a proposer to proposal pool
func (self *Acceptor) Propose(proposer *Proposer) {
  self.proposalPool = append(self.proposalPool, proposer)
}

// This function assigns a spouse from a group
func (self *Acceptor) Consider() {
  if (len(self.proposalPool) == 0) {
    return
  }

  highestIndex := 0
  changeProposer := false

  // If we don't have a partner
  if (self.partner == nil) {
    for i, proposer := range self.proposalPool {
      if (self.preferences[proposer] <= self.preferences[self.proposalPool[highestIndex]]) {
        highestIndex = i
        changeProposer = true
      }
    }
  } else {
    for i, proposer := range self.proposalPool {
      if (self.preferences[proposer] <= self.preferences[self.partner]) {
        highestIndex = i
        changeProposer = true
      }
    }
  }

  if (changeProposer) {
    self.Accept(self.proposalPool[highestIndex])
  } else {
    highestIndex = -1
  }

  for i, proposer := range self.proposalPool {
    if (i != highestIndex) {
      proposer.Reject()
    }
  }

  self.proposalPool = []*Proposer {}
}

// This will accept a proposal
func (self *Acceptor) Accept(proposer *Proposer) {
  self.Free = false
  self.partner = proposer
}

// Setters
func (self *Acceptor) AddPreferences(proposers []*Proposer) {
  prefProposers := make(map[*Proposer]int)

  for i, proposer := range proposers {
    prefProposers[proposer] = i
  }

  self.preferences = prefProposers
}

// Getters
func (self *Acceptor) Preferences() map[*Proposer]int {
  return self.preferences
}

func (self *Acceptor) Partner() *Proposer {
  return self.partner
}

example.go

package main

import(
  "fmt"
  "./Village"
)

func main() {
  // Acceptors: { "Mary", "Alex", "Nicki", "Cindy" }
  // Proposers: { "John", "Rob", "Mark", "Mac" }
  village, err := Village.NewVillage([]string { "Mary", "Alex", "Nicki", "Cindy" }, []string { "John", "Rob", "Mark", "Mac" })

  if (err != nil) {
    fmt.Println(err)
    panic(err)
  }

  /*
    Constructs a relationship between acceptors to proposers:

    Acceptor |  Rank 1 |  Rank 2 |  Rank 3 |  Rank 4
    Mary        John      Rob       Mark      Mac
    Alex        Rob       John      Mac       Mark
    Nicki       Mac       Rob       Mark      John
    Cindy       Rob       John      Mac       Mark
  */
  village.AddPreferencesAcceptors(
    map[string][]string {
      "Mary"  : []string {  "John",  "Rob",  "Mark", "Mac"   },
      "Alex"  : []string {  "Rob",   "John", "Mac",  "Mark"  },
      "Nicki" : []string {  "Mac",   "Rob",  "Mark", "John"  },
      "Cindy" : []string {  "Rob",   "John", "Mac",  "Mark"  },
    },
  )

  /*
    Constructs a relationship between proposers to acceptors:

    Acceptor |  Rank 1 |  Rank 2 |  Rank 3 |  Rank 4
    John        Mary      Alex      Nicki     Cindy
    Mark        Alex      Cindy     Nicki     Mary
    Rob         Cindy     Nicki     Mary      Alex
    Mac         Nicki     Mary      Alex      Cindy
  */
  village.AddPreferencesProposers(
    map[string][]string {
      "John"  : []string {  "Mary",   "Alex",   "Nicki",  "Cindy" },
      "Mark"  : []string {  "Alex",   "Cindy",  "Nicki",  "Mary"  },
      "Rob"   : []string {  "Cindy",  "Nicki",  "Mary",   "Alex"  },
      "Mac"   : []string {  "Nicki",  "Mary",   "Alex",   "Cindy" },
    },
  )

  finals := village.MarryCouples()

  for acceptor, proposer := range finals {
    fmt.Println(acceptor.Name, "married", proposer.Name)
  }
  /*
    Output:

    Mary married John
    Alex married Mark
    Nicki married Mac
    Cindy married Rob
  */
}

Proposer.go

package Village

type Proposer struct {
  Name string
  preferences map[int]*Acceptor
  prefIndex int
  free bool
  partner *Acceptor
}

func NewProposer(name string) Proposer {
  return Proposer{Name: name, prefIndex: 0, free: true}
}

// This will propose to a acceptor
func (self *Proposer) Propose(acceptor *Acceptor) {
  acceptor.Propose(self)
  self.partner = acceptor
  self.free = false
}

// This will handle a reject from a acceptor
func (self *Proposer) Reject() {
  self.partner = nil
  self.free = true
  self.prefIndex++
}

// This function returns the next acceptor of interest
func (self *Proposer) Next() *Acceptor {
  return self.preferences[self.prefIndex]
}

// Setters
func (self *Proposer) AddPreferences(acceptors []*Acceptor) {
  prefAcceptors := make(map[int]*Acceptor)

  for i, acceptor := range acceptors {
    prefAcceptors[i] = acceptor
  }

  self.preferences = prefAcceptors
}

// Getters
func (self *Proposer) Preferences() map[int]*Acceptor {
  return self.preferences
}

func (self *Proposer) Free() bool {
  return self.free
}

func (self *Proposer) Partner() *Acceptor {
  return self.partner
}

Village.go

package Village

import (
  "errors"
)

type village struct {
  acceptors map[string]*Acceptor
  proposers map[string]*Proposer
}

func NewVillage(ac []string, pr []string) (village, error) {
  if (len(ac) != len(pr)) {
    return village{}, errors.New("Unable to make stable marraiges with uneven count of acceptors/proposers.")
  }

  acceptors := make(map[string]*Acceptor)
  proposers := make(map[string]*Proposer)

  for _, acceptor := range ac {
    acceptorRef := NewAcceptor(acceptor)
    acceptors[acceptor] = &acceptorRef
  }

  for _, proposer := range pr {
    proposerRef := NewProposer(proposer)
    proposers[proposer] = &proposerRef
  }

  return village { acceptors, proposers }, nil
}

// Preferences for acceptors
func (self *village) AddPreferencesAcceptors(proposers map[string][]string) error {
  // First we loop through the acceptors
  for acceptorName, acceptor := range self.acceptors {
    acceptorPreferences := []*Proposer {}

    // Now for each acceptor, we check their preferences
    for _, proposerName := range proposers[acceptorName] {
      acceptorPreferences = append(acceptorPreferences, self.proposers[proposerName])
    }

    acceptor.AddPreferences(acceptorPreferences)
  }

  return nil
}

// Preferences for proposers
func (self *village) AddPreferencesProposers(acceptors map[string][]string) error {
  // First we loop through all the proposers
  for proposerName, proposer := range self.proposers {
    proposerPreferences := []*Acceptor {}

    // Now for each proposer, we check their preferences
    for _, acceptorName := range acceptors[proposerName] {
      proposerPreferences = append(proposerPreferences, self.acceptors[acceptorName])
    }

    proposer.AddPreferences(proposerPreferences)
  }

  return nil
}

func (self *village) MarryCouples() map[*Acceptor]*Proposer {
  wasFree := false

  for {
    wasFree = false

    for _, proposer := range self.proposers {
      if (proposer.Free()) {
        self.ProposeFreeMen()
        self.ConsiderProposingMen()
        wasFree = true
        break
      }
    }

    if (!wasFree) {
      break
    }
  }

  couples := make(map[*Acceptor]*Proposer)

  for _, acceptor := range self.acceptors {
    couples[acceptor] = acceptor.Partner()
  }

  return couples
}

func (self *village) ProposeFreeMen() {
  for _, proposer := range self.proposers {
    if (proposer.Free()) {
      proposer.Propose(proposer.Next())
    }
  }
}

func (self *village) ConsiderProposingMen() {
  for _, acceptor := range self.acceptors {
    acceptor.Consider()
  }
}