PHPackages                             motley/hopcroft-karp - PHPackages - PHPackages  [Skip to content](#main-content)[PHPackages](/)[Directory](/)[Categories](/categories)[Trending](/trending)[Leaderboard](/leaderboard)[Changelog](/changelog)[Analyze](/analyze)[Collections](/collections)[Log in](/login)[Sign up](/register)

1. [Directory](/)
2. /
3. [Utility & Helpers](/categories/utility)
4. /
5. motley/hopcroft-karp

ActiveLibrary[Utility & Helpers](/categories/utility)

motley/hopcroft-karp
====================

Hopcroft-Karp algorithm

0.7.0(3y ago)28.6k[2 PRs](https://github.com/motleyhand/HopcroftKarp/pulls)GPL-3.0-or-laterPHPPHP ^8.1CI passing

Since Jan 9Pushed 3w ago1 watchersCompare

[ Source](https://github.com/motleyhand/HopcroftKarp)[ Packagist](https://packagist.org/packages/motley/hopcroft-karp)[ GitHub Sponsors](https://github.com/TamasSzigeti)[ RSS](/packages/motley-hopcroft-karp/feed)WikiDiscussions main Synced 3w ago

READMEChangelog (6)Dependencies (5)Versions (10)Used By (0)

HopcroftKarp
============

[](#hopcroftkarp)

PHP implementation of the Hopcroft-Karp algorithm

The Algorithm
-------------

[](#the-algorithm)

The [Hopcroft–Karp algorithm](https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm) is the most efficient way to find a maximum cardinality matching in a bipartite graph.

Think of applicants for jobs, each applicant has skills for a certain sub-set of the jobs, and we need to employ the maximum number of applicants to jobs. Or scheduling appointments for a set of time slots when each person is only available at specific time slots.

The Implementation
------------------

[](#the-implementation)

- This is a quick and lazy implementation for now which works well for my use case.
- I am more than happy to improve it further as and when there is a need for that. Issues and pull requests are welcome.
- As per semver, there is no BC guarantee until 1.0

Installation
------------

[](#installation)

```
composer require motley/hopcroft-karp
```

Usage
-----

[](#usage)

You have to provide a set of edges describing your biparite graph. The vertex values can be object, string or int. The edge shall be one to many. Example:

```
    $matching = HopcroftKarp::matching([
        ['left1', ['right2', 'right3']],
        ['left2', ['right1']],
        ['left3', ['right2']],
        ['left4', ['right2']],
        ['left4', ['right4']],
    ]);
```

The resulting matching object has a few helper methods to inspect it.

```
$matching->toArray(); // [['left1', 'right3'], ['left2', 'right1'], ['left3', 'right2'], ['left4', 'right4']]
$matching->getRightByLeft('left2'); // 'right1'
$matching->getRightByLeft('unmatched'); // null
$matching->getLeftByRight('right2'); // 'left3'
$matching->getAllLeft(); // ['left1', 'left2', 'left3', 'left4']
$matching->getAllRight(); // ['right3', 'right1', 'right2', 'right4']
```

Freezing edges
--------------

[](#freezing-edges)

You can pass in a previous matching as an optional argument and the algorithm will try to keep as many edges from it as possible. Example:

```
$previousMatching = new Matching([
    new Edge('left1', 'right1'),
    new Edge('left2', 'right2'),
    new Edge('left3', 'right4'),
    new Edge('left4', 'right3'),
]);

$matching = HopcroftKarp::matching([
    ['left1', ['right1', 'left2', 'right3']],
    ['left2', ['right1', 'left2', 'right3', 'right4']],
    ['left3', ['left2', 'right3', 'right4']],
    ['left4', ['right1', 'right2', 'right3', 'right4']],
], $previousMatching);
```

Contributions
-------------

[](#contributions)

Issues and pull requests are welcome.

###  Health Score

41

—

FairBetter than 87% of packages

Maintenance62

Regular maintenance activity

Popularity24

Limited adoption so far

Community11

Small or concentrated contributor base

Maturity54

Maturing project, gaining track record

 Bus Factor1

Top contributor holds 59.3% of commits — single point of failure

How is this calculated?**Maintenance (25%)** — Last commit recency, latest release date, and issue-to-star ratio. Uses a 2-year decay window.

**Popularity (30%)** — Total and monthly downloads, GitHub stars, and forks. Logarithmic scaling prevents top-heavy scores.

**Community (15%)** — Contributors, dependents, forks, watchers, and maintainers. Measures real ecosystem engagement.

**Maturity (30%)** — Project age, version count, PHP version support, and release stability.

###  Release Activity

Cadence

Every ~78 days

Recently: every ~118 days

Total

7

Last Release

1156d ago

PHP version history (2 changes)0.1PHP >=7.4

0.6PHP ^8.1

### Community

Maintainers

![](https://www.gravatar.com/avatar/1a1d27670a95f08f55f62cbc0be0ac9ec00273e1dfa61a29d9224603e8d71ec2?d=identicon)[tamas](/maintainers/tamas)

---

Top Contributors

[![dependabot[bot]](https://avatars.githubusercontent.com/in/29110?v=4)](https://github.com/dependabot[bot] "dependabot[bot] (48 commits)")[![TamasSzigeti](https://avatars.githubusercontent.com/u/148897?v=4)](https://github.com/TamasSzigeti "TamasSzigeti (20 commits)")[![renovate[bot]](https://avatars.githubusercontent.com/in/2740?v=4)](https://github.com/renovate[bot] "renovate[bot] (10 commits)")[![benedekdul](https://avatars.githubusercontent.com/u/42741967?v=4)](https://github.com/benedekdul "benedekdul (3 commits)")

---

Tags

algorithmphp

###  Code Quality

TestsPHPUnit

Static AnalysisPHPStan

Type Coverage Yes

### Embed Badge

![Health badge](/badges/motley-hopcroft-karp/health.svg)

```
[![Health](https://phpackages.com/badges/motley-hopcroft-karp/health.svg)](https://phpackages.com/packages/motley-hopcroft-karp)
```

PHPackages © 2026

[Directory](/)[Categories](/categories)[Trending](/trending)[Changelog](/changelog)[Analyze](/analyze)