libmatch

README

libmatch

libmatch is a library for solving matching problems.

---

libmatch can be used as a Go package (docs) or as a standalone executable (CLI).

It supports solving the following problems:

Matching Problem	Shorthand	Description	Example
Stable Marriage Problem	SMP	Matching between two groups of members	example→
Stable Roommates Problem	SRP	Matching within a group of members	example→

---

• What Does This Do?
• Go Package
  • Installation
  • Example
• CLI
  • Installation
  • Example
• Miscellaneous

What Does This Do?

Matching algorithms find an optimal matching between members, given one or more sets of member preferences.

libmatch provides solutions to solve this and variations of this classic matching problem, which have a wide range of real-world applications.

Go Package

View Go Package Documentation.

Installation

go get github.com/abhchand/libmatch

Example

Below is an example of the Stable Roommates Problem

Import it:

import (
  "github.com/abhchand/libmatch"
)

Use it:

prefTable := []libmatch.MatchPreference{
  {Name: "A", Preferences: []string{"B", "D", "C"}},
  {Name: "B", Preferences: []string{"D", "A", "C"}},
  {Name: "C", Preferences: []string{"D", "A", "B"}},
  {Name: "D", Preferences: []string{"C", "A", "B"}},
}

// Call the solver for the type of matching algorithm you'd like to solve.
// In this case `SolveSRP` solves the "Stable Roommate Problem".
result, err := libmatch.SolveSRP(&prefTable)
if err != nil {
  fmt.Println(err)
  os.Exit(1)
}

// => MatchResult{
//   Mapping: map[string]string{
//     "A": "F",
//     "B": "E",
//     "C": "D",
//     "D": "C",
//     "E": "B",
//     "F": "A",
//   }
// }

CLI

Installation

Download the the latest release for your platform.

Or alternatively, build it from source:

git clone git@github.com:abhchand/libmatch.git
cd libmatch/

make all

Example

Below is an example of the Stable Roommates Problem

Define member preferences as JSON data:

$ cat <<EOF > input.json
[
  { "name":"A", "preferences": ["B", "D", "F", "C", "E"] },
  { "name":"B", "preferences": ["D", "E", "F", "A", "C"] },
  { "name":"C", "preferences": ["D", "E", "F", "A", "B"] },
  { "name":"D", "preferences": ["F", "C", "A", "E", "B"] },
  { "name":"E", "preferences": ["F", "C", "D", "B", "A"] },
  { "name":"F", "preferences": ["A", "B", "D", "C", "E"] }
]
EOF

Run libmatch:

$ libmatch solve --algorithm SRP --file input.json
A,F
B,E
C,D
D,C
E,B
F,A

See libmatch --help for more options and examples.

Miscellaneous

• Create an issue to report a bug or request a feature
• Contributions are welcome! Please open an Issue to discuss your changes first
• The Changelog can be found in the releases

Documentation

Overview

Package libmatch provides an API for solving matching problems.

Each matching algorithm has a shorthand acronym that can be used to invoke the solver. For example "Stable Marriage Problem" has a shorthand of "SMP" and to invoke the solver, you can call:

libmatch.SolveSMP(...)

For a full list of available matching algorithms and their shorthands, see https://github.com/abhchand/libmatch#readme.

If you have the libmatch command line utility installed, you can also run

libmatch ls

to see this list.

Index

• func Load(r io.Reader) (*[]MatchPreference, error)
• type MatchPreference
• type MatchResult
  • func SolveSMP(prefsA, prefsB *[]MatchPreference) (MatchResult, error)
  • func SolveSRP(prefs *[]MatchPreference) (MatchResult, error)

Examples

• Load
• SolveSMP
• SolveSRP

Functions

func Load

func Load(r io.Reader) (*[]MatchPreference, error)

Load reads match preference data from an `io.Reader`.

The expected data is a JSON formatted preference table of the format:

[
  { "name":"A", "preferences": ["B", "D", "F", "C", "E"] },
  { "name":"B", "preferences": ["D", "E", "F", "A", "C"] },
  { "name":"C", "preferences": ["D", "E", "F", "A", "B"] },
  { "name":"D", "preferences": ["F", "C", "A", "E", "B"] },
  { "name":"E", "preferences": ["F", "C", "D", "B", "A"] },
  { "name":"F", "preferences": ["A", "B", "D", "C", "E"] },
]

The return value is an array of `MatchPreference` structs containing the loaded JSON data

		*[]libmatch.MatchPreference{
		  {Name: "A", Preferences: []string{"B", "D", "F", "C", "E"}},
		  {Name: "B", Preferences: []string{"D", "E", "F", "A", "C"}},
		  {Name: "C", Preferences: []string{"D", "E", "F", "A", "B"}},
		  {Name: "D", Preferences: []string{"F", "C", "A", "E", "B"}},
		  {Name: "E", Preferences: []string{"F", "C", "D", "B", "A"}},
		  {Name: "F", Preferences: []string{"A", "B", "D", "C", "E"}},
   }

Example

// Load JSON contents as an `io.Reader`
// This could be data read from a file or another source
body := `
	[
	  { "name":"A", "preferences": ["B", "D", "F", "C", "E"] },
	  { "name":"B", "preferences": ["D", "E", "F", "A", "C"] },
	  { "name":"C", "preferences": ["D", "E", "F", "A", "B"] },
	  { "name":"D", "preferences": ["F", "C", "A", "E", "B"] },
	  { "name":"E", "preferences": ["F", "C", "D", "B", "A"] },
	  { "name":"F", "preferences": ["A", "B", "D", "C", "E"] }
	]
	`
reader := strings.NewReader(body)

// Load input preferences
prefTable, err := Load(reader)
if err != nil {
	fmt.Println(err)
	os.Exit(1)
}

// Call `libmatch`
result, err := SolveSRP(prefTable)
if err != nil {
	fmt.Println(err)
	os.Exit(1)
}

// Iterate through the results
for x, y := range result.Mapping {
	fmt.Printf("%v => %v\n", x, y)
}

Output:

A => F
B => E
C => D
D => C
E => B
F => A

Types

type MatchPreference

type MatchPreference = core.MatchPreference

type MatchResult

type MatchResult = core.MatchResult

func SolveSMP

func SolveSMP(prefsA, prefsB *[]MatchPreference) (MatchResult, error)

SolveSMP solves the Stable Marriage Problem for a set of preferences.

See: https://en.wikipedia.org/wiki/Stable_marriage_problem

The algorithm finds a stable matching between two same-sized sets. Implements the Gale-Shapley (1962) algorithm. A stable solution is always guranteed, but it is non-deterministic and potentially one of many.

Example:

SolveSMP takes a pair of preference tables as inputs. Each preference table is an array of match preferences.

prefTableA := []libmatch.MatchPreference{
	{Name: "A", Preferences: []string{"F", "J", "H", "G", "I"}},
	{Name: "B", Preferences: []string{"F", "J", "H", "G", "I"}},
	{Name: "C", Preferences: []string{"F", "G", "H", "J", "I"}},
	{Name: "D", Preferences: []string{"H", "J", "F", "I", "G"}},
	{Name: "E", Preferences: []string{"H", "F", "G", "I", "J"}},
}

prefTableB := []libmatch.MatchPreference{
	{Name: "F", Preferences: []string{"A", "E", "C", "B", "D"}},
	{Name: "G", Preferences: []string{"D", "E", "C", "B", "A"}},
	{Name: "H", Preferences: []string{"A", "B", "C", "D", "E"}},
	{Name: "I", Preferences: []string{"B", "E", "C", "D", "A"}},
	{Name: "J", Preferences: []string{"E", "A", "D", "B", "C"}},
}

On success, the return value will be a MatchResult containing the stable the mapping between pairs of members.

MatchResult{
	Mapping: map[string]string{
		"A": "F",
		"B": "H",
		"C": "I",
		"D": "J",
		"E": "G",
		"F": "A",
		"G": "E",
		"H": "B",
		"I": "C",
		"J": "D",
	},
}

Example

prefTableA := []MatchPreference{
	{Name: "A", Preferences: []string{"F", "J", "H", "G", "I"}},
	{Name: "B", Preferences: []string{"F", "J", "H", "G", "I"}},
	{Name: "C", Preferences: []string{"F", "G", "H", "J", "I"}},
	{Name: "D", Preferences: []string{"H", "J", "F", "I", "G"}},
	{Name: "E", Preferences: []string{"H", "F", "G", "I", "J"}},
}

prefTableB := []MatchPreference{
	{Name: "F", Preferences: []string{"A", "E", "C", "B", "D"}},
	{Name: "G", Preferences: []string{"D", "E", "C", "B", "A"}},
	{Name: "H", Preferences: []string{"A", "B", "C", "D", "E"}},
	{Name: "I", Preferences: []string{"B", "E", "C", "D", "A"}},
	{Name: "J", Preferences: []string{"E", "A", "D", "B", "C"}},
}

// Call `libmatch`
result, err := SolveSMP(&prefTableA, &prefTableB)
if err != nil {
	fmt.Println(err)
	os.Exit(1)
}

// Iterate through the result mapping
for x, y := range result.Mapping {
	fmt.Printf("%v => %v\n", x, y)
}

Output:

A => F
B => H
C => I
D => J
E => G
F => A
G => E
H => B
I => C
J => D

func SolveSRP

func SolveSRP(prefs *[]MatchPreference) (MatchResult, error)

SolveSRP solves the Stable Roommates Problem for a set of preferences.

See: https://en.wikipedia.org/wiki/Stable_roommates_problem

The algorithm finds a stable matching within an even-sized set. A stable solution is not guranteed, but is always deterministic if exists. Implements Irving's (1985) algorithm.

Example:

SolveSRP takes a single preference table as an input. The preference table is an array of match preferences.

		prefs := *[]libmatch.MatchPreference{
		  {Name: "A", Preferences: []string{"B", "D", "F", "C", "E"}},
		  {Name: "B", Preferences: []string{"D", "E", "F", "A", "C"}},
		  {Name: "C", Preferences: []string{"D", "E", "F", "A", "B"}},
		  {Name: "D", Preferences: []string{"F", "C", "A", "E", "B"}},
		  {Name: "E", Preferences: []string{"F", "C", "D", "B", "A"}},
		  {Name: "F", Preferences: []string{"A", "B", "D", "C", "E"}}
   }

On success, the return value will be a MatchResult containing the stable the mapping between pairs of members.

MatchResult{
	Mapping: map[string]string{
		"A": "F",
		"B": "E",
		"C": "D",
		"D": "C",
		"E": "B",
		"F": "A",
	},
}

Example

ExampleSolveSRP solves the "Stable Roommates Problem" for some sample input

prefTable := []MatchPreference{
	{Name: "A", Preferences: []string{"B", "D", "F", "C", "E"}},
	{Name: "B", Preferences: []string{"D", "E", "F", "A", "C"}},
	{Name: "C", Preferences: []string{"D", "E", "F", "A", "B"}},
	{Name: "D", Preferences: []string{"F", "C", "A", "E", "B"}},
	{Name: "E", Preferences: []string{"F", "C", "D", "B", "A"}},
	{Name: "F", Preferences: []string{"A", "B", "D", "C", "E"}},
}

// Call `libmatch`
result, err := SolveSRP(&prefTable)
if err != nil {
	fmt.Println(err)
	os.Exit(1)
}

// Iterate through the result mapping
for x, y := range result.Mapping {
	fmt.Printf("%v => %v\n", x, y)
}

Output:

A => F
B => E
C => D
D => C
E => B
F => A