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
Stable Marriage Problem	SMP	Matching between two groups of members
Stable Roommates Problem	SRP	Matching within a group of members

---

• What Does This Do?
• Go Package
  • Installation
  • Examples
    • Stable Marriage Example
    • Stable Roommates Example
• CLI
  • Installation
  • Examples
    • Stable Marriage Example
    • Stable Roommates Example
• Miscellaneous

What Does This Do?

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

Algorithmic solutions to these problems have a wide range of real-world applications, from economics to computational mathematics.

libmatch provides solutions to solve this and variations of this classic matching problem at scale.

Go Package

View Go Package Documentation →.

Installation

go get github.com/abhchand/libmatch

Examples

Stable Marriage Example

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

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

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

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

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

Stable Roommates Example

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

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

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

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

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

Examples

Stable Marriage Example

$ cat <<EOF > prefs-a.json
[
  { "name": "A", "preferences": ["E", "F", "G", "H"] },
  { "name": "B", "preferences": ["F", "G", "H", "E"] },
  { "name": "C", "preferences": ["G", "F", "H", "E"] },
  { "name": "D", "preferences": ["H", "E", "G", "F"] }
]
EOF

$ cat <<EOF > prefs-b.json
[
  { "name": "E", "preferences": ["A", "B", "C", "D"] },
  { "name": "F", "preferences": ["C", "B", "D", "A"] },
  { "name": "G", "preferences": ["D", "A", "C", "B"] },
  { "name": "H", "preferences": ["B", "C", "D", "A"] }
]
EOF

$ libmatch solve --algorithm SMP --file prefs-a.json --file prefs-b.json
H,D
B,F
C,G
D,H
A,E
E,A
F,B
G,C

Stable Roommates Example

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

$ libmatch solve --algorithm SRP --file prefs.json
D,C
A,B
B,A
C,D

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