motley / hopcroft-karp
Hopcroft-Karp algorithm
Fund package maintenance!
TamasSzigeti
Installs: 6 453
Dependents: 0
Suggesters: 0
Security: 0
Stars: 2
Watchers: 1
Forks: 0
Open Issues: 0
Requires
- php: ^8.1
Requires (Dev)
- motley/ecs-config: ^1.12
- phpstan/extension-installer: ^1.2
- phpstan/phpstan: ^1.10.3
- phpunit/phpunit: ^10.0
- symfony/var-dumper: ^6.2
README
PHP implementation of the Hopcroft-Karp algorithm
The Algorithm
The Hopcroft–Karp 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
- 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
composer require motley/hopcroft-karp
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
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
Issues and pull requests are welcome.