RuVector adds an optional native graph engine without replacing the one it trusts

What this is about

A minimum cut is the cheapest way to split a graph in two. It turns up wherever you need to know where a network is weakest: clustering, routing, partitioning a workload. RuVector has had an implementation of it in its graph algorithms for a long time.

The usual story at this point is that somebody replaces the slow version with a fast compiled one. That is not what happened here, and the commit message goes out of its way to say so.

What changed

Commit b6921e79, landed on September 16 as pull request #991, adds a compiled minimum-cut package as an optional dependency of the published package. The existing implementation is not replaced and is not described as buggy. It is a genuine Stoer-Wagner algorithm, and differential fuzzing against brute-force enumeration over every bipartition of 3,844 random graphs found zero mismatches. It remains both the default and the fallback.

What the optional package adds is capability the pure implementation does not have:

• An availability check that never throws, so calling code can branch on whether the native package is present.
• A fast path that returns the same result as the existing function, at native speed when the package is installed and transparently falling back when it is not.
• An incremental structure that maintains the cut across edge inserts, deletes and updates instead of recomputing it from scratch. There is no equivalent in the existing implementation.
• Exact directed routing with turn restrictions, closures and landmark search. Also no equivalent.

The integration follows the convention already used for another optional native module: a lazy require and a single cached, actionable install error rather than a stack trace. Two details about the native boundary are recorded as found by testing rather than assumed, including that vertex identifiers are wide integers on input but come back as plain numbers in the partition result. A follow-up commit the same day fixed version pins that were blocking publication and built the distributed artefacts.

Get started

Prerequisites: Node.js 22 or later and a project that already depends on the published package. Nothing extra is needed to use the default path, because the optional package is optional.

npm install ruvector

Expected result: the package installs, and the existing minimum-cut function works whether or not the native package resolved. If it did not, the availability check returns false and the fast path quietly uses the same code you were using before.

Command read from the published package documentation. It was not executed here, and no package was installed while writing this article.

Use it today

Practical case: a graph that changes constantly, where you need the current weakest split after every edit. Input is a stream of edge changes. The workflow with the existing function is to recompute from scratch each time. The workflow with the incremental structure is to apply the edit and read the maintained cut. Output is the same answer, without paying full price per change.

Reader acceptance test: run the fast path and the original function on the same graph and compare the results. They should be identical. If they differ, do not trust the native path on your data, and report it.

Push it further

Experimental commentary. The honest framing here is the interesting part. Most optional native modules arrive advertised as a correctness fix, which quietly tells every user that what they were running was wrong. This one carries the fuzzing result that justifies leaving the original in place, which is a far stronger claim than being fast.

Limitation: the incremental structure and the routing engine exist only in the native package, so any code that depends on them stops working where the package cannot install, rather than falling back. Falsifiable test: install without the optional package, confirm the availability check returns false, and confirm the fast path still returns the correct cut while the incremental structure is genuinely unavailable rather than silently degraded.