Maximum Bipartite Matching

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

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);

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

See Also

• Hopcroft Karp Algorithm

---

Copyright 2014 psjava team. View on GitHub