ReScript-Blossom 🌺

ReScript-Blossom is a ReScript implementation of the famous blossom algorithm. It finds a maximum matching of vertices on general, undirected, weighted graphs.

📖 Read the documentation

Installation

You can add ReScript-Blossom to your project by running:

npm install rescript-blossom

You will need to edit your project's bsconfig.json file and list ReScript-Blossom in the bs-dependencies.

{
  "bs-dependencies": [
    "rescript-blossom"
  ]
}

Development

Download the code:

git clone https://github.com/johnridesabike/rescript-blossom.git

If you want to make your own changes, then it's recommended to fork the repository on GitHub and clone your forked version.

Install the dependencies:

npm install

Compile a production build:

npm run build

Run the ReScript watcher.

npm run start

Run the tests:

npm run test

Run benchmarks that compare it to the similar JavaScript algorithm:

npm run bench

Run benchmarks in a browser:

npm run browser

Then open the URL provided and navigate to the __benchmarks__ directory.

This code uses many terms and ideas from "Efficient algorithms for finding maximum matching in graphs" by Zvi Galil, ACM Computing Surveys, 1986. Reading the paper will make this code much more understandable.