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 rescript.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.

ReScript-Blossom Changelog

4.0

• Migrate to Rescript 11 uncurried mode
• Add dependency on @rescript/core

3.0

• Replaced bs-platform package with rescript package.
• Removed rescript-logger.
• Changed license to the Mozilla Public License.

2.0

• Changed name to rescript-blossom
• Converted Reason to ReScript syntax.

1.1.1

• Improved documentation.

1.1

• Replaced Belt.Id.comparable with a custom comparable type.
• Added Match.MakeComparable and Match.MakeComparableU functors.
• Added Match.comparable and Match.comparableU functions.
• Added Match.unsafeComparableFromBelt and Match.unsafeComparableFromBeltU functions.
• Match.make no longer requires the cmp function separate from the id.
• Improved performance.
• Removed dependency on Belt.List.
• Added types Match.String.t and Match.Int.t.
• Updated documentation.

1.0.8

• Fixed a bug in the function that scans for potential blossoms.
• Cleaned up documentation.
• Updated dependencies.

1.0.7

• Updated the function that scans for potential blossoms. It is now more robust and can handle more complex paths.
• Fixed a crash on some graphs.

1.0.6

• Fixed a crash on graphs with large blossoms.

1.0.5

• Fixed a crash on some graphs.

1.0.4

• Fixed a bug that allowed some duplicate edges.

1.0.3

• Fixed a crash on certain graphs.

1.0.2

• Added package description.

1.0.1

• Initial release.