Hopcroft Karp Algorithm in Java

Hopcroft Karp Algorithm

Download

Download jar file or use maven. psjava requires Java 1.6 (or above)

<dependency>
    <groupId>org.psjava</groupId>
    <artifactId>psjava</artifactId>
    <version>0.1.19</version>
</dependency>

Example Code

// Let's make a simple bipartite graph.

MutableBipartiteGraph<String> g = MutableBipartiteGraph.create();

g.insertLeftVertex("L1");
g.insertLeftVertex("L2");
g.insertLeftVertex("L3");
g.insertRightVertex("R1");
g.insertRightVertex("R2");

g.addEdge("L1", "R1");
g.addEdge("L1", "R2");
g.addEdge("L2", "R1");
g.addEdge("L3", "R1");

MaximumBipartiteMatchingResult<String> result = HopcroftKarpAlgorithm.getInstance().calc(g);

// In this example, (L1-R2, L2-R1) is one of the solutions.

int matchCount = result.getMaxMatchCount(); // must be 2
String matchOfL1 = result.getMatchedVertex("L1"); // must be "R2".

Implementation

HopcroftKarpAlgorithm.java in GitHub