Hopcroft-Karp Algorithm
The Hopcroft-Karp Algorithm addresses the problem of finding a maximum cardinality matching in a bipartite graph. A bipartite graph is a graph whose vertices can be divided into two disjoint sets, say and , such that every edge connects a vertex in to a vertex in . A matching in this context is a set of edges where no two edges share a common vertex. The goal is to maximize the number of edges in the matching, ensuring the largest possible number of vertices in and are paired.
You are encouraged to solve this task according to the task description, using any language you may know.
The problem can be formally stated as follows: Given a bipartite graph , where and are the two sets of vertices and is the set of edges, find a matching such that the size of (denoted ), the number of edges in the matching, is maximized. This is known as the maximum bipartite matching problem.
Mathematically, the objective is to maximize: subject to the constraint that for any two edges and in , and , ensuring no vertex is incident to more than one edge in the matching.
The pseudocode for the Hopcroft-Karp Algorithm looks like:
ALGORITHM Hopcroft-Karp(G, U, V)
// G is the bipartite graph with partitions U and V
// U is the left partition, V is the right partition
// NIL represents an unmatched vertex (0)
// INF represents infinity
// Initialize matching arrays
pair_u ← array of size |U| + 1 initialized with NIL
pair_v ← array of size |V| + 1 initialized with NIL
dist ← array of size |U| + 1 for distances
matching_size ← 0
WHILE BFS(G, pair_u, pair_v, dist) DO
FOR each u ∈ U DO
IF pair_u[u] = NIL THEN
IF DFS(G, u, pair_u, pair_v, dist) THEN
matching_size ← matching_size + 1
RETURN matching_size
FUNCTION BFS(G, pair_u, pair_v, dist)
queue ← empty queue
// Initialize distances
FOR u ← 1 to |U| DO
IF pair_u[u] = NIL THEN
dist[u] ← 0
enqueue(queue, u)
ELSE
dist[u] ← INF
dist[NIL] ← INF
WHILE queue not empty DO
u ← dequeue(queue)
IF dist[u] < dist[NIL] THEN
FOR each v in G.adj[u] DO
matched_u ← pair_v[v]
IF dist[matched_u] = INF THEN
dist[matched_u] ← dist[u] + 1
enqueue(queue, matched_u)
RETURN dist[NIL] ≠ INF
FUNCTION DFS(G, u, pair_u, pair_v, dist)
IF u ≠ NIL THEN
FOR each v in G.adj[u] DO
matched_u ← pair_v[v]
IF dist[matched_u] = dist[u] + 1 THEN
IF DFS(G, matched_u, pair_u, pair_v, dist) THEN
pair_v[v] ← u
pair_u[u] ← v
RETURN TRUE
dist[u] ← INF
RETURN FALSE
RETURN TRUE
// Graph Representation
// G.adj[u] contains the list of neighbors of vertex u in V
// pair_u[u] stores the vertex v matched with u (or NIL)
// pair_v[v] stores the vertex u matched with v (or NIL)
// dist[u] stores the distance of vertex u during BFS
using System;
using System.Collections.Generic;
using System.Linq;
public sealed class HopcroftKarpAlgorithm
{
// Define Edge class instead of record
private sealed class Edge
{
public int From { get; }
public int To { get; }
public Edge(int from, int to)
{
From = from;
To = to;
}
}
public static void Main(string[] args)
{
Console.WriteLine("Running tests:");
int successCount = 0;
// Test Case 1
successCount = TestValue(1, 3, 5, new List<Edge> { new Edge(1, 4) }, 1);
// Test Case 2
successCount += TestValue(2, 6, 6, new List<Edge> { new Edge(1, 4), new Edge(1, 5), new Edge(5, 1) }, 2);
// Test Case 3: Complete Bipartite Graph K(3, 3)
var edges = new List<Edge>();
for (int i = 1; i <= 3; i++)
{
for (int j = 1; j <= 3; j++)
{
edges.Add(new Edge(i, j));
}
}
successCount += TestValue(3, 3, 3, edges, 3);
// Test Case 4: No edges
successCount += TestValue(4, 2, 2, new List<Edge>(), 0);
// Test Case 5
edges = new List<Edge>
{
new Edge(1, 1), new Edge(1, 3), new Edge(2, 3), new Edge(3, 4), new Edge(4, 3), new Edge(4, 2)
};
successCount += TestValue(5, 4, 4, edges, 4);
if (successCount == 5)
{
Console.WriteLine("All tests passed.");
}
}
private static int TestValue(int testNumber, int m, int n, List<Edge> edges, int expectedResult)
{
BipartiteGraph graph = new BipartiteGraph(m, n);
foreach (var edge in edges)
{
graph.AddEdge(edge.From, edge.To);
}
int result = graph.HopcroftKarpAlgorithm();
Console.WriteLine($"Test {testNumber}: Result = {result}, Expected = {expectedResult}");
if (result == expectedResult)
{
return 1;
}
Console.WriteLine($"Test {testNumber} failed.");
return 0;
}
}
/// <summary>
/// Representation of a bipartite graph.
/// Vertices in the left partition, U, are numbered from 1 to m,
/// and vertices in the right partition, V, are numbered 1 to n.
/// </summary>
internal sealed class BipartiteGraph
{
public BipartiteGraph(int aM, int aN)
{
m = aM;
n = aN;
adjacencyLists = Enumerable.Range(0, m + 1)
.Select(i => new List<int>()).ToList();
pairU = Enumerable.Repeat(NIL, m + 1).ToList();
pairV = Enumerable.Repeat(NIL, n + 1).ToList();
levels = Enumerable.Repeat(INFINITY, m + 1).ToList();
}
public void AddEdge(int u, int v)
{
if (1 <= u && u <= m && 1 <= v && v <= n)
{
adjacencyLists[u].Add(v);
}
else
{
throw new InvalidOperationException($"Attempt to add an edge ({u}, {v}) which is out of bounds");
}
}
/// <summary>
/// Return the matching size of the bipartite graph.
/// </summary>
public int HopcroftKarpAlgorithm()
{
pairU = Enumerable.Repeat(NIL, m + 1).ToList();
pairV = Enumerable.Repeat(NIL, n + 1).ToList();
int matchingSize = 0;
while (BreadthFirstSearch())
{
for (int u = 1; u <= m; u++)
{
if (pairU[u] == NIL && DepthFirstSearch(u))
{ // vertex u is free and an augmenting path starting
matchingSize += 1; // from u has been found by the depth first search
}
}
}
return matchingSize;
}
/// <summary>
/// Determines whether there exists an augmenting path starting from a free vertex in U.
///
/// Return true if an augmenting path could exist, otherwise false.
/// </summary>
private bool BreadthFirstSearch()
{
Queue<int> queue = new Queue<int>();
for (int u = 1; u <= m; u++)
{ // Initialise 'levels' for the vertices in U
if (pairU[u] == NIL)
{ // If u is a free vertex, its level is 0 add it is added to the queue
levels[u] = 0;
queue.Enqueue(u);
}
else
{ // Otherwise, set 'levels' to infinity
levels[u] = INFINITY;
}
}
// The 'level' to the NIL node represents the length of the shortest augmenting path
levels[NIL] = INFINITY;
while (queue.Count > 0)
{
int u = queue.Dequeue();
if (levels[u] < levels[NIL])
{ // The path through u could lead to a shorter augmenting path
foreach (int v in adjacencyLists[u])
{ // Explore the neighbours v of u in V
int matchedU = pairV[v];
if (levels[matchedU] == INFINITY)
{ // The matched vertex has not been visited yet
levels[matchedU] = levels[u] + 1;
queue.Enqueue(matchedU); // Enqueue the matched vertex to explore it further
}
}
}
}
// An augmenting path from the initial free vertices was found if levels[NIL] is not INFINITY
return levels[NIL] != INFINITY;
}
/// <summary>
/// Determine whether the shortest path from vertex u in U found by BreadthFirstSearch() can be augmented.
///
/// Return true if an augmenting path was found starting from u, otherwise false.
/// </summary>
private bool DepthFirstSearch(int u)
{
if (u != NIL)
{
foreach (int v in adjacencyLists[u])
{ // Explore neighbours v of u in V
int matchedU = pairV[v];
// Check whether the edge (u, v) leads to a vertex matchedU
// such that the path u -> v -> matchedU is part of a shortest augmenting path
if (levels[matchedU] == levels[u] + 1)
{
if (DepthFirstSearch(matchedU))
{ // An augmenting path is found starting from 'matchedU'
pairV[v] = u; // Match v with u,
pairU[u] = v; // and u with v
return true;
}
}
}
// No augmenting path was found starting from vertex u through any of its neighbours v,
// so remove u from the depth first search phase of the algorithm
levels[u] = INFINITY;
return false;
}
return true;
}
private List<List<int>> adjacencyLists; // adjacencyLists(u) stores a list of neighbours of u in V
private List<int> pairU; // pairU(u) stores the vertex v in V matched with u in U, or NIL if unmatched
private List<int> pairV; // pairV(v) stores the vertex u in U matched with v in V, or NIL if unmatched
private List<int> levels; // levels(u) stores the level of vertex u in U during a breadth first search
private readonly int m; // Index of the vertices in the left partition
private readonly int n; // Index of the vertices in the right partition
private const int NIL = 0;
private const int INFINITY = int.MaxValue;
}
- Output:
Running tests: Test 1: Result = 1, Expected = 1 Test 2: Result = 2, Expected = 2 Test 3: Result = 3, Expected = 3 Test 4: Result = 0, Expected = 0 Test 5: Result = 4, Expected = 4 All tests passed.
#include <cstdint>
#include <limits>
#include <iostream>
#include <queue>
#include <stdexcept>
#include <string>
#include <vector>
/**
* Representation of a bipartite graph.
* Vertices in the left partition, U, are numbered from 1 to m,
* and vertices in the right partition, V, are numbered 1 to n.
*/
class BipartiteGraph {
public:
BipartiteGraph(const uint32_t& aM, const uint32_t& aN) {
m = aM;
n = aN;
adjacency_lists = { m + 1, std::vector<uint32_t>() };
pair_u.assign(m + 1, NIL);
pair_v.assign(n + 1, NIL);
levels.assign(m + 1, INFINITY);
}
void add_edge(const uint32_t& u, const uint32_t& v) {
if ( 1 <= u && u <= m && 1 <= v && v <= n ) {
adjacency_lists[u].emplace_back(v);
} else {
throw std::invalid_argument("Attempt to add an edge (" +
std::to_string(u) + ", " + std::to_string(v) + ") which is out of bounds");
}
}
/**
* Return the matching size of the bipartite graph.
*/
uint32_t hopcroftKarp_algorithm() {
pair_u.assign(m + 1, NIL);
pair_v.assign(n + 1, NIL);
uint32_t matching_size = 0;
while ( breadth_first_search() ) {
for ( uint32_t u = 1; u <= m; ++u ) {
if ( pair_u[u] == NIL && depth_first_search(u) ) { // vertex u is free and an augmenting path starting
matching_size++; // from u has been found by the depth first search
}
}
}
return matching_size;
}
private:
/**
* Determines whether there exists an augmenting path starting from a free vertex in U.
*
* Return true if an augmenting path could exist, otherwise false.
*/
bool breadth_first_search() {
std::queue<uint32_t> queue;
for ( uint32_t u = 1; u <= m; ++u ) { // Initialise 'levels' for the vertices in U
if ( pair_u[u] == NIL ) { // If u is a free vertex, its level is 0 add it is added to the queue
levels[u] = 0;
queue.push(u);
} else { // Otherwise, set 'levels' to infinity
levels[u] = INFINITY;
}
}
// The 'level' to the NIL node represents the length of the shortest augmenting path
levels[NIL] = INFINITY;
while ( ! queue.empty() ) {
const uint32_t u = queue.front();
queue.pop();
if ( levels[u] < levels[NIL] ) { // The path through u could lead to a shorter augmenting path
for ( const uint32_t& v : adjacency_lists[u] ) { // Explore the neighbours v of u in V
const uint32_t matched_u = pair_v[v];
if ( levels[matched_u] == INFINITY ) { // The matched vertex has not been visited yet
levels[matched_u] = levels[u] + 1;
queue.push(matched_u); // Enqueue the matched vertex to explore it further
}
}
}
}
// An augmenting path from the initial free vertices was found if levels[NIL] is not INFINITY
return levels[NIL] != INFINITY;
}
/**
* Determine whether the shortest path from vertex u in U found by breadth_first_search() can be augmented.
*
* Return true if an augmenting path was found starting from u, otherwise false.
*/
bool depth_first_search(const uint32_t& u) {
if ( u != NIL ) {
for ( const uint32_t& v : adjacency_lists[u] ) { // Explore neighbours v of u in V
const uint32_t matched_u = pair_v[v];
// Check whether the edge (u, v) leads to a vertex matched_u
// such that the path u -> v -> matched_u is part of a shortest augmenting path
if ( levels[matched_u] == levels[u] + 1 ) {
if ( depth_first_search(matched_u) ) { // An augmenting path is found starting from 'matched_u'
pair_v[v] = u; // Match v with u,
pair_u[u] = v; // and u with v
return true;
}
}
}
// No augmenting path was found starting from vertex u through any of its neighbours v,
// so remove u from the depth first search phase of the algorithm
levels[u] = INFINITY;
return false;
}
return true;
}
std::vector<std::vector<uint32_t>> adjacency_lists; // adjacency_lists(u) stores a list of neighbours of u in V
std::vector<uint32_t> pair_u; // pair_u(u) stores the vertex v in V matched with u in U, or NIL if unmatched
std::vector<uint32_t> pair_v; // pair_v(v) stores the vertex u in U matched with v in V, or NIL if unmatched
std::vector<uint32_t> levels; // levels(u) stores the level of vertex u in U during a breadth first search
uint32_t m; // Index of the vertices in the left partition
uint32_t n; // Index of the vertices in the right partition
const uint32_t NIL = 0;
const uint32_t INFINITY = INT_MAX;
};
struct Edge {
uint32_t from;
uint32_t to;
};
uint32_t test_value(const uint32_t& testNumber, const uint32_t& m, const uint32_t& n,
const std::vector<Edge>& edges, const uint32_t& expected_result) {
BipartiteGraph graph(m, n);
for ( const Edge& edge : edges ) {
graph.add_edge(edge.from, edge.to);
}
const uint32_t result = graph.hopcroftKarp_algorithm();
std::cout << "Test " << testNumber << ": Result = " << result << ", Expected = " << expected_result << std::endl;
if ( result == expected_result ) {
return 1;
}
std::cout << "Test " << testNumber << " failed." << std::endl;
return 0;
}
int main() {
std::cout << "Running tests:" << std::endl;
uint32_t success_count = 0;
// Test Case 1
success_count = test_value(1, 3, 5, { Edge(1, 4) }, 1);
// Test Case 2
success_count += test_value(2, 6, 6, { Edge(1, 4), Edge(1, 5), Edge(5, 1) }, 2);
// Test Case 3: Complete Bipartite Graph K(3, 3)
std::vector<Edge> edges;
for ( uint32_t i = 1; i <= 3; ++i ) {
for ( uint32_t j = 1; j <= 3; ++j ) {
edges.emplace_back( Edge(i, j) );
}
}
success_count += test_value(3, 3, 3, edges, 3);
// Test Case 4: No edges
success_count += test_value(4, 2, 2, { }, 0);
// Test Case 5
edges = { Edge(1, 1), Edge(1, 3), Edge(2, 3), Edge(3, 4), Edge(4, 3), Edge(4, 2) };
success_count += test_value(5, 4, 4, edges, 4);
if ( success_count == 5 ) {
std::cout << "All tests passed." << std::endl;
}
}
- Output:
Running tests: Test 1: Result = 1, Expected = 1 Test 2: Result = 2, Expected = 2 Test 3: Result = 3, Expected = 3 Test 4: Result = 0, Expected = 0 Test 5: Result = 4, Expected = 4 All tests passed.
IDENTIFICATION DIVISION.
PROGRAM-ID. HOPCROFT-KARP.
AUTHOR. TRANSLATED-FROM-JAVA.
*>================================================================
*> Hopcroft-Karp Maximum Bipartite Matching Algorithm
*>
*> Left partition U: vertices 1..M
*> Right partition V: vertices 1..N
*>
*> Limitations of this COBOL implementation:
*> MAX-M = max vertices in U (left)
*> MAX-N = max vertices in V (right)
*> MAX-ADJ = max total directed edges
*> QUEUE = BFS queue size
*>================================================================
ENVIRONMENT DIVISION.
CONFIGURATION SECTION.
SOURCE-COMPUTER. ANY-COMPUTER.
OBJECT-COMPUTER. ANY-COMPUTER.
DATA DIVISION.
WORKING-STORAGE SECTION.
*>--- Graph dimensions ---
01 WS-M PIC 9(4) VALUE 0.
01 WS-N PIC 9(4) VALUE 0.
01 WS-MATCH-SIZE PIC 9(4) VALUE 0.
*>--- Constants ---
01 WS-NIL PIC 9(4) VALUE 0.
01 WS-INFINITY PIC 9(9) VALUE 999999999.
01 WS-MAX-M PIC 9(4) VALUE 50.
01 WS-MAX-N PIC 9(4) VALUE 50.
01 WS-MAX-ADJ PIC 9(6) VALUE 2500.
*>--- Adjacency list (CSR-style): adj-dest(i) = destination vertex
*> adj-start(u) = first index in adj-dest for vertex u
*> adj-end(u) = one past last index ---
01 WS-ADJ-DEST OCCURS 2500 TIMES PIC 9(4) VALUE 0.
01 WS-ADJ-COUNT PIC 9(6) VALUE 0.
*>--- Per-vertex adjacency bounds (indexed 0..MAX-M) ---
01 WS-ADJ-START OCCURS 51 TIMES PIC 9(6) VALUE 0.
01 WS-ADJ-LEN OCCURS 51 TIMES PIC 9(4) VALUE 0.
*>--- Temporary edge list before building CSR ---
01 WS-EDGE-TABLE.
05 WS-EDGE OCCURS 2500 TIMES.
10 WS-EDGE-FROM PIC 9(4) VALUE 0.
10 WS-EDGE-TO PIC 9(4) VALUE 0.
01 WS-EDGE-COUNT PIC 9(6) VALUE 0.
*>--- Matching arrays ---
01 WS-PAIR-U OCCURS 51 TIMES PIC 9(4) VALUE 0.
01 WS-PAIR-V OCCURS 51 TIMES PIC 9(4) VALUE 0.
*>--- Level array (indexed 0..MAX-M, index 0 = NIL node) ---
01 WS-LEVEL OCCURS 51 TIMES PIC 9(9) VALUE 0.
*>--- BFS Queue ---
01 WS-QUEUE OCCURS 5100 TIMES PIC 9(4) VALUE 0.
01 WS-Q-HEAD PIC 9(6) VALUE 1.
01 WS-Q-TAIL PIC 9(6) VALUE 0.
*>--- Loop / work variables ---
01 WS-U PIC 9(4) VALUE 0.
01 WS-V PIC 9(4) VALUE 0.
01 WS-MATCHED-U PIC 9(4) VALUE 0.
01 WS-BFS-RESULT PIC 9(1) VALUE 0.
01 WS-DFS-RESULT PIC 9(1) VALUE 0.
01 WS-I PIC 9(6) VALUE 0.
01 WS-J PIC 9(4) VALUE 0.
01 WS-IDX PIC 9(6) VALUE 0.
*>--- DFS recursion stack (simulate recursion) ---
01 WS-STACK OCCURS 51 TIMES PIC 9(4) VALUE 0.
01 WS-STACK-POS OCCURS 51 TIMES PIC 9(6) VALUE 0.
01 WS-STACK-TOP PIC 9(4) VALUE 0.
01 WS-STACK-V PIC 9(4) VALUE 0.
01 WS-STACK-U2 PIC 9(4) VALUE 0.
*>--- Test harness ---
01 WS-TEST-NUM PIC 9(2) VALUE 0.
01 WS-EXPECTED PIC 9(4) VALUE 0.
01 WS-SUCCESS-CNT PIC 9(2) VALUE 0.
01 WS-PASS-FAIL PIC X(6) VALUE SPACES.
01 WS-ALL-PASS PIC 9(2) VALUE 5.
*>--- Display work ---
01 WS-DISP-NUM PIC Z(4).
PROCEDURE DIVISION.
MAIN-PARA.
DISPLAY "Running tests:"
MOVE 0 TO WS-SUCCESS-CNT
*>--- Test 1: M=3 N=5, edge (1,4), expected=1 ---
MOVE 1 TO WS-TEST-NUM
MOVE 3 TO WS-M
MOVE 5 TO WS-N
MOVE 0 TO WS-EDGE-COUNT
PERFORM INIT-EDGE-TABLE
MOVE 1 TO WS-EDGE-COUNT
MOVE 1 TO WS-EDGE-FROM(1)
MOVE 4 TO WS-EDGE-TO(1)
MOVE 1 TO WS-EXPECTED
PERFORM RUN-TEST
ADD WS-DFS-RESULT TO WS-SUCCESS-CNT
*>--- Test 2: M=6 N=6, edges (1,4)(1,5)(5,1), expected=2 ---
MOVE 2 TO WS-TEST-NUM
MOVE 6 TO WS-M
MOVE 6 TO WS-N
PERFORM INIT-EDGE-TABLE
MOVE 3 TO WS-EDGE-COUNT
MOVE 1 TO WS-EDGE-FROM(1)
MOVE 4 TO WS-EDGE-TO(1)
MOVE 1 TO WS-EDGE-FROM(2)
MOVE 5 TO WS-EDGE-TO(2)
MOVE 5 TO WS-EDGE-FROM(3)
MOVE 1 TO WS-EDGE-TO(3)
MOVE 2 TO WS-EXPECTED
PERFORM RUN-TEST
ADD WS-DFS-RESULT TO WS-SUCCESS-CNT
*>--- Test 3: K(3,3) complete bipartite, expected=3 ---
MOVE 3 TO WS-TEST-NUM
MOVE 3 TO WS-M
MOVE 3 TO WS-N
PERFORM INIT-EDGE-TABLE
MOVE 0 TO WS-EDGE-COUNT
PERFORM VARYING WS-I FROM 1 BY 1 UNTIL WS-I > 3
PERFORM VARYING WS-J FROM 1 BY 1 UNTIL WS-J > 3
ADD 1 TO WS-EDGE-COUNT
MOVE WS-I TO WS-EDGE-FROM(WS-EDGE-COUNT)
MOVE WS-J TO WS-EDGE-TO(WS-EDGE-COUNT)
END-PERFORM
END-PERFORM
MOVE 3 TO WS-EXPECTED
PERFORM RUN-TEST
ADD WS-DFS-RESULT TO WS-SUCCESS-CNT
*>--- Test 4: No edges, expected=0 ---
MOVE 4 TO WS-TEST-NUM
MOVE 2 TO WS-M
MOVE 2 TO WS-N
PERFORM INIT-EDGE-TABLE
MOVE 0 TO WS-EDGE-COUNT
MOVE 0 TO WS-EXPECTED
PERFORM RUN-TEST
ADD WS-DFS-RESULT TO WS-SUCCESS-CNT
*>--- Test 5: M=4 N=4, 6 edges, expected=4 ---
MOVE 5 TO WS-TEST-NUM
MOVE 4 TO WS-M
MOVE 4 TO WS-N
PERFORM INIT-EDGE-TABLE
MOVE 6 TO WS-EDGE-COUNT
MOVE 1 TO WS-EDGE-FROM(1) MOVE 1 TO WS-EDGE-TO(1)
MOVE 1 TO WS-EDGE-FROM(2) MOVE 3 TO WS-EDGE-TO(2)
MOVE 2 TO WS-EDGE-FROM(3) MOVE 3 TO WS-EDGE-TO(3)
MOVE 3 TO WS-EDGE-FROM(4) MOVE 4 TO WS-EDGE-TO(4)
MOVE 4 TO WS-EDGE-FROM(5) MOVE 3 TO WS-EDGE-TO(5)
MOVE 4 TO WS-EDGE-FROM(6) MOVE 2 TO WS-EDGE-TO(6)
MOVE 4 TO WS-EXPECTED
PERFORM RUN-TEST
ADD WS-DFS-RESULT TO WS-SUCCESS-CNT
IF WS-SUCCESS-CNT = WS-ALL-PASS
DISPLAY "All tests passed."
END-IF
STOP RUN.
*>================================================================
*> INIT-EDGE-TABLE: clear edge staging area
*>================================================================
INIT-EDGE-TABLE.
MOVE 0 TO WS-EDGE-COUNT
PERFORM VARYING WS-I FROM 1 BY 1 UNTIL WS-I > 2500
MOVE 0 TO WS-EDGE-FROM(WS-EDGE-COUNT + 1)
MOVE 0 TO WS-EDGE-TO(WS-EDGE-COUNT + 1)
ADD 1 TO WS-EDGE-COUNT
END-PERFORM
MOVE 0 TO WS-EDGE-COUNT.
*>================================================================
*> RUN-TEST: build graph from edge table, run algorithm, report
*> Input: WS-M, WS-N, WS-EDGE-COUNT/FROM/TO, WS-EXPECTED
*> Output: WS-DFS-RESULT = 1 if passed, 0 if failed
*>================================================================
RUN-TEST.
PERFORM BUILD-GRAPH
PERFORM HOPCROFT-KARP
MOVE WS-DISP-NUM TO WS-DISP-NUM
MOVE WS-MATCH-SIZE TO WS-DISP-NUM
IF WS-MATCH-SIZE = WS-EXPECTED
MOVE "PASSED" TO WS-PASS-FAIL
MOVE 1 TO WS-DFS-RESULT
ELSE
MOVE "FAILED" TO WS-PASS-FAIL
MOVE 0 TO WS-DFS-RESULT
END-IF
DISPLAY "Test " WS-TEST-NUM ": Result = " WS-MATCH-SIZE
" Expected = " WS-EXPECTED " " WS-PASS-FAIL.
*>================================================================
*> BUILD-GRAPH: convert edge list to CSR adjacency structure
*>================================================================
BUILD-GRAPH.
*> Clear adjacency lengths
PERFORM VARYING WS-I FROM 0 BY 1 UNTIL WS-I > 50
MOVE 0 TO WS-ADJ-LEN(WS-I + 1)
END-PERFORM
*> Count edges per source vertex
PERFORM VARYING WS-I FROM 1 BY 1 UNTIL WS-I > WS-EDGE-COUNT
MOVE WS-EDGE-FROM(WS-I) TO WS-U
ADD 1 TO WS-ADJ-LEN(WS-U + 1)
END-PERFORM
*> Compute start offsets (1-based in adj-dest)
MOVE 1 TO WS-ADJ-START(1) *> index 0 = NIL, unused
MOVE 1 TO WS-ADJ-START(2) *> vertex 1 starts at 1
PERFORM VARYING WS-U FROM 1 BY 1 UNTIL WS-U > 49
COMPUTE WS-ADJ-START(WS-U + 2) =
WS-ADJ-START(WS-U + 1) + WS-ADJ-LEN(WS-U + 1)
END-PERFORM
*> Place edges into adj-dest; use a temp cursor array
PERFORM VARYING WS-U FROM 0 BY 1 UNTIL WS-U > 50
MOVE WS-ADJ-START(WS-U + 1) TO WS-ADJ-LEN(WS-U + 1)
END-PERFORM
PERFORM VARYING WS-I FROM 1 BY 1 UNTIL WS-I > WS-EDGE-COUNT
MOVE WS-EDGE-FROM(WS-I) TO WS-U
MOVE WS-EDGE-TO(WS-I) TO WS-V
MOVE WS-ADJ-LEN(WS-U + 1) TO WS-IDX
MOVE WS-V TO WS-ADJ-DEST(WS-IDX)
ADD 1 TO WS-ADJ-LEN(WS-U + 1)
END-PERFORM.
*>================================================================
*> HOPCROFT-KARP: main algorithm
*>================================================================
HOPCROFT-KARP.
*> Initialise pairU and pairV to NIL
PERFORM VARYING WS-U FROM 0 BY 1 UNTIL WS-U > 50
MOVE 0 TO WS-PAIR-U(WS-U + 1)
MOVE 0 TO WS-PAIR-V(WS-U + 1)
END-PERFORM
MOVE 0 TO WS-MATCH-SIZE
PERFORM BFS-PHASE
PERFORM UNTIL WS-BFS-RESULT = 0
PERFORM VARYING WS-U FROM 1 BY 1 UNTIL WS-U > WS-M
IF WS-PAIR-U(WS-U + 1) = WS-NIL
PERFORM DFS-PHASE
IF WS-DFS-RESULT = 1
ADD 1 TO WS-MATCH-SIZE
END-IF
END-IF
END-PERFORM
PERFORM BFS-PHASE
END-PERFORM.
*>================================================================
*> BFS-PHASE: layered BFS over free vertices in U
*> Sets WS-BFS-RESULT = 1 if augmenting path found, else 0
*> Uses WS-U as loop variable (saved/restored via WS-STACK)
*>================================================================
BFS-PHASE.
MOVE 1 TO WS-Q-HEAD
MOVE 0 TO WS-Q-TAIL
*> Initialise levels
PERFORM VARYING WS-U FROM 0 BY 1 UNTIL WS-U > 50
MOVE WS-INFINITY TO WS-LEVEL(WS-U + 1)
END-PERFORM
*> Enqueue free vertices of U
PERFORM VARYING WS-U FROM 1 BY 1 UNTIL WS-U > WS-M
IF WS-PAIR-U(WS-U + 1) = WS-NIL
MOVE 0 TO WS-LEVEL(WS-U + 1)
ADD 1 TO WS-Q-TAIL
MOVE WS-U TO WS-QUEUE(WS-Q-TAIL)
END-IF
END-PERFORM
*> BFS loop
PERFORM UNTIL WS-Q-HEAD > WS-Q-TAIL
MOVE WS-QUEUE(WS-Q-HEAD) TO WS-U
ADD 1 TO WS-Q-HEAD
IF WS-LEVEL(WS-U + 1) < WS-LEVEL(1)
*> 1 = index for NIL (index 0+1)
PERFORM VARYING WS-IDX FROM WS-ADJ-START(WS-U + 1)
BY 1
UNTIL WS-IDX >=
WS-ADJ-START(WS-U + 2)
MOVE WS-ADJ-DEST(WS-IDX) TO WS-V
MOVE WS-PAIR-V(WS-V + 1) TO WS-MATCHED-U
IF WS-LEVEL(WS-MATCHED-U + 1) = WS-INFINITY
COMPUTE WS-LEVEL(WS-MATCHED-U + 1) =
WS-LEVEL(WS-U + 1) + 1
IF WS-MATCHED-U NOT = WS-NIL
ADD 1 TO WS-Q-TAIL
MOVE WS-MATCHED-U TO
WS-QUEUE(WS-Q-TAIL)
END-IF
END-IF
END-PERFORM
END-IF
END-PERFORM
IF WS-LEVEL(1) = WS-INFINITY
MOVE 0 TO WS-BFS-RESULT
ELSE
MOVE 1 TO WS-BFS-RESULT
END-IF.
*>================================================================
*> DFS-PHASE: augmenting path DFS from vertex WS-U
*> Input: WS-U (the starting free vertex)
*> Output: WS-DFS-RESULT = 1 if augmenting path found, 0 if not
*>
*> We simulate the recursive DFS with an explicit stack.
*> WS-STACK(k) = current U-node at depth k
*> WS-STACK-POS(k) = next adj-list index to try at depth k
*>================================================================
DFS-PHASE.
MOVE 1 TO WS-STACK-TOP
MOVE WS-U TO WS-STACK(1)
MOVE WS-ADJ-START(WS-U + 1) TO WS-STACK-POS(1)
MOVE 0 TO WS-DFS-RESULT
PERFORM UNTIL WS-STACK-TOP = 0
MOVE WS-STACK(WS-STACK-TOP) TO WS-STACK-U2
MOVE WS-STACK-POS(WS-STACK-TOP) TO WS-IDX
IF WS-STACK-U2 = WS-NIL
*> Reached NIL: augmenting path found; unwind
MOVE 1 TO WS-DFS-RESULT
SUBTRACT 1 FROM WS-STACK-TOP
PERFORM UNTIL WS-STACK-TOP = 0
*> Pair the edge we followed to reach NIL parent
MOVE WS-STACK-TOP TO WS-J
SUBTRACT 1 FROM WS-STACK-POS(WS-J)
MOVE WS-STACK-POS(WS-J) TO WS-IDX
MOVE WS-ADJ-DEST(WS-IDX) TO WS-STACK-V
MOVE WS-STACK(WS-J) TO WS-U
MOVE WS-U TO WS-PAIR-V(WS-STACK-V + 1)
MOVE WS-STACK-V TO WS-PAIR-U(WS-U + 1)
SUBTRACT 1 FROM WS-STACK-TOP
END-PERFORM
ELSE
*> Try next edge from WS-STACK-U2
IF WS-IDX < WS-ADJ-START(WS-STACK-U2 + 2)
MOVE WS-ADJ-DEST(WS-IDX) TO WS-V
ADD 1 TO WS-STACK-POS(WS-STACK-TOP)
MOVE WS-PAIR-V(WS-V + 1) TO WS-MATCHED-U
IF WS-LEVEL(WS-MATCHED-U + 1) =
WS-LEVEL(WS-STACK-U2 + 1) + 1
*> Follow this edge: push matched-U onto stack
ADD 1 TO WS-STACK-TOP
MOVE WS-MATCHED-U TO WS-STACK(WS-STACK-TOP)
IF WS-MATCHED-U = WS-NIL
MOVE 1 TO
WS-STACK-POS(WS-STACK-TOP)
ELSE
MOVE WS-ADJ-START(WS-MATCHED-U + 1) TO
WS-STACK-POS(WS-STACK-TOP)
END-IF
END-IF
ELSE
*> No more edges: dead end, set level to infinity
MOVE WS-INFINITY TO
WS-LEVEL(WS-STACK-U2 + 1)
SUBTRACT 1 FROM WS-STACK-TOP
END-IF
END-IF
END-PERFORM.
END PROGRAM HOPCROFT-KARP.
- Output:
Running tests: Test 01: Result = 0001 Expected = 0001 PASSED Test 02: Result = 0002 Expected = 0002 PASSED Test 03: Result = 0003 Expected = 0003 PASSED Test 04: Result = 0000 Expected = 0000 PASSED Test 05: Result = 0004 Expected = 0004 PASSED All tests passed.
import 'dart:collection';
import 'dart:math';
/// Representation of a bipartite graph.
/// Vertices in the left partition, U, are numbered from 1 to m,
/// and vertices in the right partition, V, are numbered 1 to n.
class BipartiteGraph {
late int m; // Index of the vertices in the left partition
late int n; // Index of the vertices in the right partition
final int NIL = 0;
final int INFINITY = 2147483647; // INT_MAX
late List<List<int>> adjacencyLists; // adjacencyLists[u] stores a list of neighbours of u in V
late List<int> pairU; // pairU[u] stores the vertex v in V matched with u in U, or NIL if unmatched
late List<int> pairV; // pairV[v] stores the vertex u in U matched with v in V, or NIL if unmatched
late List<int> levels; // levels[u] stores the level of vertex u in U during a breadth first search
BipartiteGraph(int aM, int aN) {
m = aM;
n = aN;
adjacencyLists = List.generate(m + 1, (index) => <int>[], growable: false);
pairU = List.filled(m + 1, NIL, growable: false);
pairV = List.filled(n + 1, NIL, growable: false);
levels = List.filled(m + 1, INFINITY, growable: false);
}
void addEdge(int u, int v) {
if (1 <= u && u <= m && 1 <= v && v <= n) {
adjacencyLists[u].add(v);
} else {
throw ArgumentError('Attempt to add an edge ($u, $v) which is out of bounds');
}
}
/// Return the matching size of the bipartite graph.
int hopcroftKarpAlgorithm() {
pairU = List.filled(m + 1, NIL, growable: false);
pairV = List.filled(n + 1, NIL, growable: false);
int matchingSize = 0;
while (breadthFirstSearch()) {
for (int u = 1; u <= m; u++) {
if (pairU[u] == NIL && depthFirstSearch(u)) { // vertex u is free and an augmenting path starting
matchingSize++; // from u has been found by the depth first search
}
}
}
return matchingSize;
}
/// Determines whether there exists an augmenting path starting from a free vertex in U.
///
/// Return true if an augmenting path could exist, otherwise false.
bool breadthFirstSearch() {
Queue<int> queue = Queue();
for (int u = 1; u <= m; u++) { // Initialise 'levels' for the vertices in U
if (pairU[u] == NIL) { // If u is a free vertex, its level is 0 and it is added to the queue
levels[u] = 0;
queue.add(u);
} else { // Otherwise, set 'levels' to infinity
levels[u] = INFINITY;
}
}
// The 'level' to the NIL node represents the length of the shortest augmenting path
levels[NIL] = INFINITY;
while (queue.isNotEmpty) {
final int u = queue.removeFirst();
if (levels[u] < levels[NIL]) { // The path through u could lead to a shorter augmenting path
for (final int v in adjacencyLists[u]) { // Explore the neighbours v of u in V
final int matchedU = pairV[v];
if (levels[matchedU] == INFINITY) { // The matched vertex has not been visited yet
levels[matchedU] = levels[u] + 1;
queue.add(matchedU); // Enqueue the matched vertex to explore it further
}
}
}
}
// An augmenting path from the initial free vertices was found if levels[NIL] is not INFINITY
return levels[NIL] != INFINITY;
}
/// Determine whether the shortest path from vertex u in U found by breadthFirstSearch() can be augmented.
///
/// Return true if an augmenting path was found starting from u, otherwise false.
bool depthFirstSearch(int u) {
if (u != NIL) {
for (final int v in adjacencyLists[u]) { // Explore neighbours v of u in V
final int matchedU = pairV[v];
// Check whether the edge (u, v) leads to a vertex matchedU
// such that the path u -> v -> matchedU is part of a shortest augmenting path
if (levels[matchedU] == levels[u] + 1) {
if (depthFirstSearch(matchedU)) { // An augmenting path is found starting from 'matchedU'
pairV[v] = u; // Match v with u,
pairU[u] = v; // and u with v
return true;
}
}
}
// No augmenting path was found starting from vertex u through any of its neighbours v,
// so remove u from the depth first search phase of the algorithm
levels[u] = INFINITY;
return false;
}
return true;
}
}
class Edge {
final int from;
final int to;
Edge(this.from, this.to);
}
int testValue(int testNumber, int m, int n, List<Edge> edges, int expectedResult) {
BipartiteGraph graph = BipartiteGraph(m, n);
for (final Edge edge in edges) {
graph.addEdge(edge.from, edge.to);
}
final int result = graph.hopcroftKarpAlgorithm();
print('Test $testNumber: Result = $result, Expected = $expectedResult');
if (result == expectedResult) {
return 1;
}
print('Test $testNumber failed.');
return 0;
}
void main() {
print('Running tests:');
int successCount = 0;
// Test Case 1
successCount = testValue(1, 3, 5, [Edge(1, 4)], 1);
// Test Case 2
successCount += testValue(2, 6, 6, [Edge(1, 4), Edge(1, 5), Edge(5, 1)], 2);
// Test Case 3: Complete Bipartite Graph K(3, 3)
List<Edge> edges = [];
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
edges.add(Edge(i, j));
}
}
successCount += testValue(3, 3, 3, edges, 3);
// Test Case 4: No edges
successCount += testValue(4, 2, 2, [], 0);
// Test Case 5
edges = [Edge(1, 1), Edge(1, 3), Edge(2, 3), Edge(3, 4), Edge(4, 3), Edge(4, 2)];
successCount += testValue(5, 4, 4, edges, 4);
if (successCount == 5) {
print('All tests passed.');
}
}
- Output:
Running tests: Test 1: Result = 1, Expected = 1 Test 2: Result = 2, Expected = 2 Test 3: Result = 3, Expected = 3 Test 4: Result = 0, Expected = 0 Test 5: Result = 4, Expected = 4 All tests passed.
' Constants
Const NULL As Any Ptr = 0
Const NIL As Integer = 0
Const INF As Double = 1e308 ' Equivalent to float('inf') in Python
Dim Shared success As Integer = 0
Type HKGraph
m As Integer ' Number of vertices in left partition (U)
n As Integer ' Number of vertices in right partition (V)
' Adjacency list: adj[u] contains list of neighbors of u in V
' We'll use dynamic arrays to simulate the Python lists
adj As Integer Ptr Ptr
adj_size As Integer Ptr ' Size of each adjacency list
adj_capacity As Integer Ptr ' Capacity of each adjacency list
' Matching pairs
pair_u As Integer Ptr ' pair_u[u] stores the vertex v in V matched with u in U
pair_v As Integer Ptr ' pair_v[v] stores the vertex u in U matched with v in V
' Distance array for BFS
dist As Double Ptr ' dist[u] stores the distance of vertex u in U during BFS
Declare Constructor(m As Integer, n As Integer)
Declare Destructor()
Declare Sub add_edge(u As Integer, v As Integer)
Declare Function bfs() As Boolean
Declare Function dfs(u As Integer) As Boolean
Declare Function hopcroft_karp_algorithm() As Integer
End Type
' Queue implementation for BFS
Type Queue
dato As Integer Ptr
front As Integer
rear As Integer
capacity As Integer
size As Integer
Declare Constructor()
Declare Destructor()
Declare Sub enqueue(item As Integer)
Declare Function dequeue() As Integer
Declare Function isEmpty() As Boolean
End Type
Constructor Queue()
capacity = 1000 ' Initial capacity
dato = Allocate(capacity * Sizeof(Integer))
front = 0
rear = -1
size = 0
End Constructor
Destructor Queue()
If dato <> NULL Then Deallocate(dato)
End Destructor
Sub Queue.enqueue(item As Integer)
If size = capacity Then
' Resize the queue if needed
capacity *= 2
dato = Reallocate(dato, capacity * Sizeof(Integer))
End If
rear = (rear + 1) Mod capacity
dato[rear] = item
size += 1
End Sub
Function Queue.dequeue() As Integer
If isEmpty() Then Return -1 ' Error: queue is empty
Dim item As Integer = dato[front]
front = (front + 1) Mod capacity
size -= 1
Return item
End Function
Function Queue.isEmpty() As Boolean
Return (size = 0)
End Function
' HKGraph implementation
Constructor HKGraph(m As Integer, n As Integer)
This.m = m
This.n = n
Dim As Integer i
' Initialize adjacency lists
adj = Allocate((m + 1) * Sizeof(Integer Ptr))
adj_size = Allocate((m + 1) * Sizeof(Integer))
adj_capacity = Allocate((m + 1) * Sizeof(Integer))
For i = 0 To m
adj_size[i] = 0
adj_capacity[i] = 10 ' Initial capacity
adj[i] = Allocate(adj_capacity[i] * Sizeof(Integer))
Next
' Initialize matching pairs
pair_u = Allocate((m + 1) * Sizeof(Integer))
pair_v = Allocate((n + 1) * Sizeof(Integer))
' Initialize distance array
dist = Allocate((m + 1) * Sizeof(Double))
' Set initial values
For i = 0 To m
pair_u[i] = NIL
Next
For i = 0 To n
pair_v[i] = NIL
Next
End Constructor
Destructor HKGraph()
' Free all allocated memory
For i As Integer = 0 To m
If adj[i] <> NULL Then Deallocate(adj[i])
Next
If adj <> NULL Then Deallocate(adj)
If adj_size <> NULL Then Deallocate(adj_size)
If adj_capacity <> NULL Then Deallocate(adj_capacity)
If pair_u <> NULL Then Deallocate(pair_u)
If pair_v <> NULL Then Deallocate(pair_v)
If dist <> NULL Then Deallocate(dist)
End Destructor
Sub HKGraph.add_edge(u As Integer, v As Integer)
' Ensure vertices are within the valid range
If u >= 1 Andalso u <= m Andalso v >= 1 Andalso v <= n Then
' Check if we need to resize the adjacency list
If adj_size[u] = adj_capacity[u] Then
adj_capacity[u] *= 2
adj[u] = Reallocate(adj[u], adj_capacity[u] * Sizeof(Integer))
End If
' Add v to u's adjacency list
adj[u][adj_size[u]] = v
adj_size[u] += 1
End If
End Sub
Function HKGraph.bfs() As Boolean
Dim queue As Queue
Dim As Integer u, i, v
' Initialize distances for vertices in U
For u = 1 To m
If pair_u[u] = NIL Then
' If u is a free vertex, its distance is 0, add to queue
dist[u] = 0
queue.enqueue(u)
Else
' Otherwise, set distance to infinity initially
dist[u] = INF
End If
Next
' Distance to the NIL node represents the length of the shortest augmenting path
dist[NIL] = INF
While Not queue.isEmpty()
u = queue.dequeue()
' If the path through u can potentially lead to a shorter augmenting path
If dist[u] < dist[NIL] Then
' Explore neighbors v of u in V
For i = 0 To adj_size[u] - 1
v = adj[u][i]
Dim matched_u As Integer = pair_v[v] ' Get the vertex u' matched with v
' If the matched vertex u' hasn't been visited yet (its distance is INF)
If dist[matched_u] = INF Then
' Set the distance of u' based on u
dist[matched_u] = dist[u] + 1
' Enqueue u' to explore further
queue.enqueue(matched_u)
End If
Next
End If
Wend
' If dist[NIL] is still INF, no augmenting path was found
Return dist[NIL] <> INF
End Function
Function HKGraph.dfs(u As Integer) As Boolean
If u <> NIL Then
' Explore neighbors v of u in V
For i As Integer = 0 To adj_size[u] - 1
Dim v As Integer = adj[u][i]
Dim matched_u As Integer = pair_v[v] ' Get the vertex u' matched with v
' Check if the edge (u, v) leads to a vertex u'
' such that the path u -> v -> u' is part of a shortest augmenting path
If dist[matched_u] = dist[u] + 1 Then
' Recursively call DFS on u'
If dfs(matched_u) Then
' If an augmenting path is found starting from u',
' update the matching: match v with u, and u with v
pair_v[v] = u
pair_u[u] = v
Return True ' Augmentation successful
End If
End If
Next
' If no augmenting path was found starting from u through any neighbor v,
' mark u as visited in this DFS phase by setting its distance to INF
dist[u] = INF
Return False ' Augmentation failed for this path
End If
' Base case: If u is NIL, it means we have reached the end of an alternating path
Return True
End Function
Function HKGraph.hopcroft_karp_algorithm() As Integer
Dim As Integer i
' Initialize matching pairs to NIL (unmatched)
For i = 0 To m
pair_u[i] = NIL
Next
For i = 0 To n
pair_v[i] = NIL
Next
Dim matching_size As Integer = 0 ' Initialize the size of the matching
' Keep finding augmenting paths using BFS and DFS until no more exist
While bfs()
' For every free vertex u in U
For i = 1 To m
' If i is free and an augmenting path starting from i is found via DFS
If pair_u[i] = NIL Andalso dfs(i) Then matching_size += 1 ' Increment the matching size
Next
Wend
Return matching_size
End Function
' --- Testing ---
Sub runTests()
' Runs test cases for the Hopcroft-Karp implementation.
Print "Running tests..."
Dim As Integer result, expected, i, j
' Test Case 1: Simple graph with one edge
' m=3, n=5, edges = [(1, 4)] - Expected matching size = 1
Print "Test 1: ";
Dim g1 As HKGraph = HKGraph(3, 5)
g1.add_edge(1, 4)
result = g1.hopcroft_karp_algorithm()
expected = 1
Print "Result=" & result; ", Expected=" & expected
'Print "Test 1"; Iif(result = expected, "Passed", "Failed")
If result = expected Then
'Print "Test 1 Passed"
success = success + 1
Else
Print "Test 1 Failed"
End If
' Test Case 2: Graph with multiple edges
' m=6, n=6, edges = [(1,4), (1,5), (5,1)]
' Expected matching size = 2 (e.g., (1,4), (5,1) or (1,5), (5,1))
Print "Test 2: ";
Dim g2 As HKGraph = HKGraph(6, 6)
g2.add_edge(1, 4)
g2.add_edge(1, 5)
g2.add_edge(5, 1)
result = g2.hopcroft_karp_algorithm()
expected = 2
Print "Result=" & result; ", Expected=" & expected
If result = expected Then
'Print "Test 2 Passed"
success = success + 1
Else
Print "Test 2 Failed"
End If
' Test Case 3: Complete Bipartite Graph K_{3,3}
' m=3, n=3, all possible edges. Expected matching size = 3
Print "Test 3: ";
Dim g3 As HKGraph = HKGraph(3, 3)
For i = 1 To 3
For j = 1 To 3
g3.add_edge(i, j)
Next
Next
result = g3.hopcroft_karp_algorithm()
expected = 3
Print "Result=" & result; ", Expected=" & expected
If result = expected Then
'Print "Test 3 Passed"
success = success + 1
Else
Print "Test 3 Failed"
End If
' Test Case 4: No edges
' m=2, n=2, no edges. Expected matching size = 0
Print "Test 4: ";
Dim g4 As HKGraph = HKGraph(2, 2)
result = g4.hopcroft_karp_algorithm()
expected = 0
Print "Result=" & result; ", Expected=" & expected
If result = expected Then
'Print "Test 4 Passed"
success = success + 1
Else
Print "Test 4 Failed"
End If
If success = 4 Then Print "All tests completed!"
End Sub
Sub main()
' Run self-tests first
runTests()
Print !"\n--- Running main execution with hard-coded input ---"
' --- Hard-coded input data ---
Dim v1 As Integer = 4 ' Number of vertices in left partition (m)
Dim v2 As Integer = 4 ' Number of vertices in right partition (n)
' Create the graph object
Dim g As HKGraph = HKGraph(v1, v2)
' Hard-coded edges
Dim edges(5, 1) As Integer = { {1, 1}, {1, 3}, {2, 3}, {3, 4}, {4, 3}, {4, 2} }
Dim e As Integer = 6 ' Number of edges
Print "Hard-coded graph dimensions: m=" & v1 & ", n=" & v2 & ", edges=" & e
Print "Adding hard-coded edges:"
' Add edges from the hard-coded list
For i As Integer = 0 To e - 1
Dim u As Integer = edges(i, 0)
Dim v As Integer = edges(i, 1)
Print " Adding edge: (" & u & ", " & v & ")"
' Add edge only if vertices are within valid 1-based range
If u >= 1 Andalso u <= v1 Andalso v >= 1 Andalso v <= v2 Then
g.add_edge(u, v)
Else
' This warning is important if hardcoded data might be invalid
Print "Warning: Skipping invalid hard-coded edge (" & u & ", " & v & ") - indices out of range [1.." & v1 & "] or [1.." & v2 & "]"
End If
Next
' Run the Hopcroft-Karp algorithm
Dim max_matching_size As Integer = g.hopcroft_karp_algorithm()
' Print the result
Print !"\nMaximum matching size is"; max_matching_size
End Sub
main()
Sleep
- Output:
Running tests... Test 1: Result=1, Expected=1 Test 2: Result=2, Expected=2 Test 3: Result=3, Expected=3 Test 4: Result=0, Expected=0 All tests completed! --- Running main execution with hard-coded input --- Hard-coded graph dimensions: m=4, n=4, edges=6 Adding hard-coded edges: Adding edge: (1, 1) Adding edge: (1, 3) Adding edge: (2, 3) Adding edge: (3, 4) Adding edge: (4, 3) Adding edge: (4, 2) Maximum matching size is 4
package main
import (
"container/list"
"fmt"
"math"
)
const (
NIL = 0
)
type HKGraph struct {
m, n int
adj [][]int
pairU []int
pairV []int
dist []float64
}
func NewHKGraph(m, n int) *HKGraph {
adj := make([][]int, m+1)
for i := range adj {
adj[i] = make([]int, 0)
}
return &HKGraph{
m: m,
n: n,
adj: adj,
pairU: make([]int, m+1),
pairV: make([]int, n+1),
dist: make([]float64, m+1),
}
}
func (g *HKGraph) AddEdge(u, v int) {
if 1 <= u && u <= g.m && 1 <= v && v <= g.n {
g.adj[u] = append(g.adj[u], v)
}
}
func (g *HKGraph) BFS() bool {
queue := list.New()
for u := 1; u <= g.m; u++ {
if g.pairU[u] == NIL {
g.dist[u] = 0
queue.PushBack(u)
} else {
g.dist[u] = math.Inf(1)
}
}
g.dist[NIL] = math.Inf(1)
for queue.Len() > 0 {
u := queue.Remove(queue.Front()).(int)
if g.dist[u] < g.dist[NIL] {
for _, v := range g.adj[u] {
matchedU := g.pairV[v]
if math.IsInf(g.dist[matchedU], 1) {
g.dist[matchedU] = g.dist[u] + 1
queue.PushBack(matchedU)
}
}
}
}
return !math.IsInf(g.dist[NIL], 1)
}
func (g *HKGraph) DFS(u int) bool {
if u != NIL {
for _, v := range g.adj[u] {
matchedU := g.pairV[v]
if g.dist[matchedU] == g.dist[u]+1 {
if g.DFS(matchedU) {
g.pairV[v] = u
g.pairU[u] = v
return true
}
}
}
g.dist[u] = math.Inf(1)
return false
}
return true
}
func (g *HKGraph) HopcroftKarpAlgorithm() int {
g.pairU = make([]int, g.m+1)
g.pairV = make([]int, g.n+1)
matchingSize := 0
for g.BFS() {
for u := 1; u <= g.m; u++ {
if g.pairU[u] == NIL && g.DFS(u) {
matchingSize++
}
}
}
return matchingSize
}
func runTests() {
fmt.Println("Running tests...")
g1 := NewHKGraph(3, 5)
g1.AddEdge(1, 4)
res1 := g1.HopcroftKarpAlgorithm()
expectedRes1 := 1
fmt.Printf("Test 1: Result=%d, Expected=%d\n", res1, expectedRes1)
if res1 != expectedRes1 {
panic(fmt.Sprintf("Test 1 Failed: Expected %d, got %d", expectedRes1, res1))
}
g2 := NewHKGraph(6, 6)
g2.AddEdge(1, 4)
g2.AddEdge(1, 5)
g2.AddEdge(5, 1)
res2 := g2.HopcroftKarpAlgorithm()
expectedRes2 := 2
fmt.Printf("Test 2: Result=%d, Expected=%d\n", res2, expectedRes2)
if res2 != expectedRes2 {
panic(fmt.Sprintf("Test 2 Failed: Expected %d, got %d", expectedRes2, res2))
}
g3 := NewHKGraph(3, 3)
for i := 1; i <= 3; i++ {
for j := 1; j <= 3; j++ {
g3.AddEdge(i, j)
}
}
res3 := g3.HopcroftKarpAlgorithm()
expectedRes3 := 3
fmt.Printf("Test 3: Result=%d, Expected=%d\n", res3, expectedRes3)
if res3 != expectedRes3 {
panic(fmt.Sprintf("Test 3 Failed: Expected %d, got %d", expectedRes3, res3))
}
g4 := NewHKGraph(2, 2)
res4 := g4.HopcroftKarpAlgorithm()
expectedRes4 := 0
fmt.Printf("Test 4: Result=%d, Expected=%d\n", res4, expectedRes4)
if res4 != expectedRes4 {
panic(fmt.Sprintf("Test 4 Failed: Expected %d, got %d", expectedRes4, res4))
}
fmt.Println("All tests passed!")
}
func main() {
runTests()
fmt.Println("\n--- Running main execution with hard-coded input ---")
hardcodedV1 := 4
hardcodedV2 := 4
hardcodedEdges := [][2]int{
{1, 1},
{1, 3},
{2, 3},
{3, 4},
{4, 3},
{4, 2},
}
v1 := hardcodedV1
v2 := hardcodedV2
edgesData := hardcodedEdges
e := len(edgesData)
g := NewHKGraph(v1, v2)
fmt.Printf("Hard-coded graph dimensions: m=%d, n=%d, edges=%d\n", v1, v2, e)
fmt.Println("Adding hard-coded edges:")
for _, edge := range edgesData {
u, v := edge[0], edge[1]
fmt.Printf(" Adding edge: (%d, %d)\n", u, v)
if 1 <= u && u <= v1 && 1 <= v && v <= v2 {
g.AddEdge(u, v)
} else {
fmt.Printf("Warning: Skipping invalid hard-coded edge (%d, %d) - indices out of range [1..%d] or [1..%d]\n",
u, v, v1, v2)
}
}
maxMatchingSize := g.HopcroftKarpAlgorithm()
fmt.Printf("\nMaximum matching size is %d\n", maxMatchingSize)
}
- Output:
Running tests... Test 1: Result=1, Expected=1 Test 2: Result=2, Expected=2 Test 3: Result=3, Expected=3 Test 4: Result=0, Expected=0 All tests passed! --- Running main execution with hard-coded input --- Hard-coded graph dimensions: m=4, n=4, edges=6 Adding hard-coded edges: Adding edge: (1, 1) Adding edge: (1, 3) Adding edge: (2, 3) Adding edge: (3, 4) Adding edge: (4, 3) Adding edge: (4, 2) Maximum matching size is 4
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;
public final class HopcroftKarpAlgorithm {
public static void main(String[] args) {
System.out.println("Running tests:");
int successCount = 0;
// Test Case 1
successCount = testValue(1, 3, 5, List.of( new Edge(1, 4) ), 1);
// Test Case 2
successCount += testValue(2, 6, 6, List.of( new Edge(1, 4), new Edge(1, 5), new Edge(5, 1) ), 2);
// Test Case 3: Complete Bipartite Graph K(3, 3)
List<Edge> edges = new ArrayList<Edge>();
for ( int i = 1; i <= 3; i++ ) {
for ( int j = 1; j <= 3; j++ ) {
edges.addLast( new Edge(i, j) );
}
}
successCount += testValue(3, 3, 3, edges, 3);
// Test Case 4: No edges
successCount += testValue(4, 2, 2, List.of(), 0);
// Test Case 5
edges = List.of(
new Edge(1, 1), new Edge(1, 3), new Edge(2, 3), new Edge(3, 4), new Edge(4, 3), new Edge(4, 2) );
successCount += testValue(5, 4, 4, edges, 4);
if ( successCount == 5 ) {
System.out.println("All tests passed.");
}
}
private static int testValue(int testNumber, int m, int n, List<Edge> edges, int expectedResult) {
BipartiteGraph graph = new BipartiteGraph(m, n);
edges.forEach( edge -> graph.addEdge(edge.from, edge.to) );
final int result = graph.hopcroftKarpAlgorithm();
System.out.println("Test " + testNumber + ": Result = " + result + ", Expected = " + expectedResult);
if ( result == expectedResult ) {
return 1;
}
System.out.println("Test " + testNumber + " failed.");
return 0;
}
private record Edge(int from, int to) {}
}
/**
* Representation of a bipartite graph.
* Vertices in the left partition, U, are numbered from 1 to m,
* and vertices in the right partition, V, are numbered 1 to n.
*/
final class BipartiteGraph {
public BipartiteGraph(int aM, int aN) {
m = aM;
n = aN;
adjacencyLists = IntStream.range(0, m + 1).boxed()
.map( i -> new ArrayList<Integer>() ).collect(Collectors.toList());
pairU = Stream.generate( () -> NIL ).limit(m + 1).collect(Collectors.toList());
pairV = Stream.generate( () -> NIL ).limit(n + 1).collect(Collectors.toList());
levels = Stream.generate( () -> INFINITY ).limit(m + 1).collect(Collectors.toList());
}
public void addEdge(int u, int v) {
if ( 1 <= u && u <= m && 1 <= v && v <= n ) {
adjacencyLists.get(u).addLast(v);
} else {
throw new AssertionError("Attempt to add an edge (" + u + ", " + v + ") which is out of bounds");
}
}
/**
* Return the matching size of the bipartite graph.
*/
public int hopcroftKarpAlgorithm() {
pairU = Stream.generate( () -> NIL ).limit(m + 1).collect(Collectors.toList());
pairV = Stream.generate( () -> NIL ).limit(n + 1).collect(Collectors.toList());
int matchingSize = 0;
while ( breadthFirstSearch() ) {
for ( int u = 1; u <= m; u++ ) {
if ( pairU.get(u) == NIL && depthFirstSearch(u) ) { // vertex u is free and an augmenting path starting
matchingSize += 1; // from u has been found by the depth first search
}
}
}
return matchingSize;
}
/**
* Determines whether there exists an augmenting path starting from a free vertex in U.
*
* Return true if an augmenting path could exist, otherwise false.
*/
private boolean breadthFirstSearch() {
Deque<Integer> queue = new ArrayDeque<Integer>();
for ( int u = 1; u <= m; u++ ) { // Initialise 'levels' for the vertices in U
if ( pairU.get(u) == NIL ) { // If u is a free vertex, its level is 0 add it is added to the queue
levels.set(u, 0);
queue.offerLast(u);
} else { // Otherwise, set 'levels' to infinity
levels.set(u, INFINITY);
}
}
// The 'level' to the NIL node represents the length of the shortest augmenting path
levels.set(NIL, INFINITY);
while ( ! queue.isEmpty() ) {
final int u = queue.pollFirst();
if ( levels.get(u) < levels.get(NIL) ) { // The path through u could lead to a shorter augmenting path
for ( int v : adjacencyLists.get(u) ) { // Explore the neighbours v of u in V
final int matchedU = pairV.get(v);
if ( levels.get(matchedU) == INFINITY ) { // The matched vertex has not been visited yet
levels.set(matchedU, levels.get(u) + 1);
queue.offerLast(matchedU); // Enqueue the matched vertex to explore it further
}
}
}
}
// An augmenting path from the initial free vertices was found if levels.get(NIL) is not INFINITY
return levels.get(NIL) != INFINITY;
}
/**
* Determine whether the shortest path from vertex u in U found by breadthFirstSearch() can be augmented.
*
* Return true if an augmenting path was found starting from u, otherwise false.
*/
private boolean depthFirstSearch(int u) {
if ( u != NIL ) {
for ( int v : adjacencyLists.get(u) ) { // Explore neighbours v of u in V
final int matchedU = pairV.get(v);
// Check whether the edge (u, v) leads to a vertex matchedU
// such that the path u -> v -> matchedU is part of a shortest augmenting path
if ( levels.get(matchedU) == levels.get(u) + 1 ) {
if ( depthFirstSearch(matchedU) ) { // An augmenting path is found starting from 'matchedU'
pairV.set(v, u); // Match v with u,
pairU.set(u, v); // and u with v
return true;
}
}
}
// No augmenting path was found starting from vertex u through any of its neighbours v,
// so remove u from the depth first search phase of the algorithm
levels.set(u, INFINITY);
return false;
}
return true;
}
private List<List<Integer>> adjacencyLists; // adjacencyLists(u) stores a list of neighbours of u in V
private List<Integer> pairU; // pairU(u) stores the vertex v in V matched with u in U, or NIL if unmatched
private List<Integer> pairV; // pairV(v) stores the vertex u in U matched with v in V, or NIL if unmatched
private List<Integer> levels; // levels(u) stores the level of vertex u in U during a breadth first search
private final int m; // Index of the vertices in the left partition
private final int n; // Index of the vertices in the right partition
private static final int NIL = 0;
private static final int INFINITY = Integer.MAX_VALUE;
}
- Output:
Running tests: Test 1: Result = 1, Expected = 1 Test 2: Result = 2, Expected = 2 Test 3: Result = 3, Expected = 3 Test 4: Result = 0, Expected = 0 Test 5: Result = 4, Expected = 4 All tests passed.
class HKGraph {
/**
* Implementation of the Hopcroft-Karp algorithm for finding maximum matching
* in a bipartite graph.
*
* Assumes vertices in the left partition (U) are numbered 1 to m,
* and vertices in the right partition (V) are numbered 1 to n.
* The NIL node is represented by 0.
*/
/**
* Constructor for the HKGraph class.
*
* @param {number} m Number of vertices in the left partition (U).
* @param {number} n Number of vertices in the right partition (V).
*/
constructor(m, n) {
this.m = m; // Number of vertices on the left side (U)
this.n = n; // Number of vertices on the right side (V)
// Adjacency list: adj[u] contains list of neighbors of u in V
// Initialize with empty lists for vertices 1 to m
this.adj = Array(m + 1).fill(null).map(() => []);
// Matching pairs:
// pair_u[u] stores the vertex v in V matched with u in U (or NIL if unmatched)
this.pair_u = Array(m + 1).fill(0);
// pair_v[v] stores the vertex u in U matched with v in V (or NIL if unmatched)
this.pair_v = Array(n + 1).fill(0);
// dist[u] stores the distance (level) of vertex u in U during BFS
// Initialized within the hopcroft_karp_algorithm or bfs method
this.dist = Array(m + 1).fill(Infinity);
}
/**
* Adds a directed edge from vertex u (left partition) to vertex v (right partition).
*
* @param {number} u Vertex index in the left partition (1 to m).
* @param {number} v Vertex index in the right partition (1 to n).
*/
addEdge(u, v) {
// Ensure vertices are within the valid range
if (1 <= u && u <= this.m && 1 <= v && v <= this.n) {
this.adj[u].push(v); // Add v to u's adjacency list
} else {
// Optionally print a warning for edges added outside the defined range
// This check is now also done in the main section when adding edges.
//console.warn(`Warning: Attempted to add edge (${u}, ${v}) outside graph bounds [1..${this.m}], [1..${this.n}]`);
//pass
}
}
/**
* Performs Breadth-First Search (BFS) to find layers in the graph.
* It checks if there exists an augmenting path starting from a free vertex in U.
*
* @returns {boolean} True if an augmenting path might exist (dist[NIL] is finite),
* False otherwise.
*/
bfs() {
const queue = []; // Use array as queue
// Initialize distances for vertices in U
for (let u = 1; u <= this.m; u++) {
if (this.pair_u[u] === 0) {
// If u is a free vertex, its distance is 0, add to queue
this.dist[u] = 0;
queue.push(u);
} else {
// Otherwise, set distance to infinity initially
this.dist[u] = Infinity;
}
}
// Distance to the NIL node represents the length of the shortest augmenting path
this.dist[0] = Infinity;
while (queue.length > 0) {
const u = queue.shift(); // Dequeue a vertex from U
// If the path through u can potentially lead to a shorter augmenting path
if (this.dist[u] < this.dist[0]) {
// Explore neighbors v of u in V
for (const v of this.adj[u]) {
const matched_u = this.pair_v[v]; // Get the vertex u' matched with v
// If the matched vertex u' hasn't been visited yet (its distance is INF)
if (this.dist[matched_u] === Infinity) {
// Set the distance of u' based on u
this.dist[matched_u] = this.dist[u] + 1;
// Enqueue u' to explore further
queue.push(matched_u);
}
}
}
}
// If dist[NIL] is still INF, no augmenting path was found originating
// from the initial free vertices. Otherwise, augmenting paths might exist.
return this.dist[0] !== Infinity;
}
/**
* Performs Depth-First Search (DFS) starting from vertex u in U
* to find and augment along a shortest path identified by BFS.
*
* @param {number} u The current vertex in U being visited (or NIL).
*
* @returns {boolean} True if an augmenting path was found and used starting from u,
* False otherwise.
*/
dfs(u) {
if (u !== 0) {
// Explore neighbors v of u in V
for (const v of this.adj[u]) {
const matched_u = this.pair_v[v]; // Get the vertex u' matched with v
// Check if the edge (u, v) leads to a vertex u'
// such that the path u -> v -> u' is part of a shortest augmenting path
if (this.dist[matched_u] === this.dist[u] + 1) {
// Recursively call DFS on u'
if (this.dfs(matched_u)) {
// If an augmenting path is found starting from u',
// update the matching: match v with u, and u with v
this.pair_v[v] = u;
this.pair_u[u] = v;
return true; // Augmentation successful
}
}
}
// If no augmenting path was found starting from u through any neighbor v,
// mark u as visited in this DFS phase by setting its distance to INF
this.dist[u] = Infinity;
return false; // Augmentation failed for this path
}
// Base case: If u is NIL, it means we have reached the end of an alternating path
// originating from a free vertex in U and ending at a free vertex in V (represented by NIL).
return true;
}
/**
* Executes the Hopcroft-Karp algorithm to find the maximum matching.
*
* @returns {number} The size of the maximum matching found.
*/
hopcroftKarpAlgorithm() {
// Initialize matching pairs to NIL (unmatched)
this.pair_u = Array(this.m + 1).fill(0);
this.pair_v = Array(this.n + 1).fill(0);
let matching_size = 0; // Initialize the size of the matching
// Keep finding augmenting paths using BFS and DFS until no more exist
while (this.bfs()) {
// For every free vertex u in U
for (let u = 1; u <= this.m; u++) {
// If u is free and an augmenting path starting from u is found via DFS
if (this.pair_u[u] === 0 && this.dfs(u)) {
// Increment the matching size
matching_size++;
}
}
}
return matching_size;
}
}
// --- Testing ---
function tests() {
/** Runs test cases for the Hopcroft-Karp implementation. */
console.log("Running tests...");
// Test Case 1 (Corrected from C++ version - using 1-based indexing)
// m=3, n=5, edges = [(1, 4)] - Expected matching size = 1
let g1 = new HKGraph(3, 5);
g1.addEdge(1, 4);
let res1 = g1.hopcroftKarpAlgorithm();
let expected_res1 = 1;
console.log(`Test 1: Result=${res1}, Expected=${expected_res1}`);
console.assert(res1 === expected_res1, `Test 1 Failed: Expected ${expected_res1}, got ${res1}`);
// Test Case 2 (Corrected from C++ version - using 1-based indexing, assuming (5,0) meant (5,1) or similar valid edge)
// m=6, n=6, edges = [(1,4), (1,5), (5,1)]
// Expected matching size = 2 (e.g., (1,4), (5,1) or (1,5), (5,1))
// Note: Original C++ test had (0,1) and (5,0) which are problematic with 1-based index logic.
let g2 = new HKGraph(6, 6);
// g3.addEdge(0,1); // Invalid vertex 0 in U
g2.addEdge(1, 4);
g2.addEdge(1, 5);
g2.addEdge(5, 1); // Assuming (5,0) meant a valid edge like (5,1)
// g2.addEdge(5, 0); // Invalid vertex 0 in V
let res2 = g2.hopcroftKarpAlgorithm();
let expected_res2 = 2;
console.log(`Test 2: Result=${res2}, Expected=${expected_res2}`);
console.assert(res2 === expected_res2, `Test 3 Failed: Expected ${expected_res2}, got ${res2}`);
// Test Case 3: Complete Bipartite Graph K_{3,3}
// m=3, n=3, all possible edges. Expected matching size = 3
let g3 = new HKGraph(3, 3);
for (let i = 1; i <= 3; i++) {
for (let j = 1; j <= 3; j++) {
g3.addEdge(i, j);
}
}
let res3 = g3.hopcroftKarpAlgorithm();
let expected_res3 = 3;
console.log(`Test 3: Result=${res3}, Expected=${expected_res3}`);
console.assert(res3 === expected_res3, `Test 4 Failed: Expected ${expected_res3}, got ${res3}`);
// Test Case 4: No edges
// m=2, n=2, no edges. Expected matching size = 0
let g4 = new HKGraph(2, 2);
let res4 = g4.hopcroftKarpAlgorithm();
let expected_res4 = 0;
console.log(`Test 4: Result=${res4}, Expected=${expected_res4}`);
console.assert(res4 === expected_res4, `Test 4 Failed: Expected ${expected_res4}, got ${res4}`);
console.log("All tests passed!");
}
// --- Main execution ---
// Check if running in a Node.js environment
if (typeof window === 'undefined') {
// Run self-tests first
tests();
console.log("\n--- Running main execution with hard-coded input ---");
// --- Hard-coded input data ---
// Example 1: Corresponds to Test Case 2
let hardcoded_v1 = 4; // Number of vertices in left partition (m)
let hardcoded_v2 = 4; // Number of vertices in right partition (n)
let hardcoded_edges = [
[1, 1],
[1, 3],
[2, 3],
[3, 4],
[4, 3],
[4, 2]
];
// Expected output for Example 1: 3
// Use the selected hardcoded data
let v1 = hardcoded_v1;
let v2 = hardcoded_v2;
let edges_data = hardcoded_edges;
let e = edges_data.length; // Number of edges is derived from the list
// Create the graph object
let g = new HKGraph(v1, v2);
console.log(`Hard-coded graph dimensions: m=${v1}, n=${v2}, edges=${e}`);
console.log("Adding hard-coded edges:");
// Add edges from the hard-coded list
for (const [u, v] of edges_data) {
console.log(` Adding edge: (${u}, ${v})`);
// Add edge only if vertices are within valid 1-based range
if (1 <= u && u <= v1 && 1 <= v && v <= v2) {
g.addEdge(u, v);
} else {
// This warning is important if hardcoded data might be invalid
console.warn(`Warning: Skipping invalid hard-coded edge (${u}, ${v}) - indices out of range [1..${v1}] or [1..${v2}]`);
}
}
// Run the Hopcroft-Karp algorithm
let max_matching_size = g.hopcroftKarpAlgorithm();
// Print the result
console.log(`\nMaximum matching size is ${max_matching_size}`);
}
- Output:
Running tests... Test 1: Result=1, Expected=1 Test 2: Result=2, Expected=2 Test 3: Result=3, Expected=3 Test 4: Result=0, Expected=0 All tests passed! --- Running main execution with hard-coded input --- Hard-coded graph dimensions: m=4, n=4, edges=6 Adding hard-coded edges: Adding edge: (1, 1) Adding edge: (1, 3) Adding edge: (2, 3) Adding edge: (3, 4) Adding edge: (4, 3) Adding edge: (4, 2) Maximum matching size is 4
"""
Note that because Julia's arrays are 1-based, the 1-based algorithm used
in the original posting works more naturally under Julia as a 2-based algorithm.
Hard coded edges in the tests have been adjusted accordingly.
"""
using DataStructures
const NIL = 1
const INF = typemax(Int)
"""
Implementation of the Hopcroft-Karp algorithm for finding maximum matching
in a bipartite graph.
Assumes vertices in the left partition (U) are numbered 2 to m+1,
and vertices in the right partition (V) are numbered 2 to n+1.
The NIL node is represented by 1.
"""
mutable struct HKGraph
m::Int
n::Int
adj::Vector{Vector{Int}}
pair_u::Vector{Int}
pair_v::Vector{Int}
dist::Vector{Int}
end
"""
Constructor for the HKGraph class.
Arguments:
m (int): Number of vertices in the left partition (U).
n (int): Number of vertices in the right partition (V).
"""
function HKGraph(m, n)
pair_u = fill(NIL, m + 1)
pair_v = fill(NIL, n + 1)
dist = fill(INF, m + 1)
return HKGraph(m, n, [Int[] for _ in 1:m+1], pair_u, pair_v, dist)
end
"""
Adds a directed edge from vertex u (left partition) to vertex v (right partition).
Arguments:
u (int): Vertex index in the left partition (2 to m+1).
v (int): Vertex index in the right partition (2 to n+1).
"""
function add_edge!(g::HKGraph, u, v)
# Ensure vertices are within the valid range
if 2 <= u <= g.m+1 && 2 <= v <= g.n+1
push!(g.adj[u], v) # Add v to u's adjacency list
else
@warn "Attempted to add edge ({u}, {v}) outside graph bounds [2..$(g.m+1)], [2..$(g.n+1)]"
end
end
"""
Performs Breadth-First Search (BFS) to find layers in the graph.
It checks if there exists an augmenting path starting from a free vertex in U.
Returns:
bool: True if an augmenting path might exist (dist[NIL] is finite),
False otherwise.
"""
function bfs(g::HKGraph)::Bool
queue = Deque{Int}()
# Initialize distances for vertices in U
for u in 2:g.m+1
if g.pair_u[u] == NIL
# If u is a free vertex, its distance is 0, add to queue
g.dist[u] = 0
push!(queue, u)
else
# Otherwise, set distance to infinity initially
g.dist[u] = INF
end
end
# Distance to the NIL node represents the length of the shortest augmenting path
g.dist[NIL] = INF
while !isempty(queue)
u = popfirst!(queue) # Dequeue a vertex from U
# If the path through u can potentially lead to a shorter augmenting path
if g.dist[u] < g.dist[NIL]
# Explore neighbors v of u in V
for v in g.adj[u]
matched_u = g.pair_v[v] # Get the vertex u' matched with v
# If the matched vertex u' hasn't been visited yet (its distance is INF)
if g.dist[matched_u] == INF
# Set the distance of u' based on u
g.dist[matched_u] = g.dist[u] + 1
# Enqueue u' to explore further
push!(queue, matched_u)
end
end
end
end
# INIL is still INF, no augmenting path was found originating
# from the initial free vertices. Otherwise, augmenting paths might exist.
return g.dist[NIL] != INF
end
"""
Performs Depth-First Search (DFS) starting from vertex u in U
to find and augment along a shortest path identified by BFS.
Arguments:
u (int): The current vertex in U being visited (oNIL).
Returns:
bool: True if an augmenting path was found and used starting from u,
False otherwise.
"""
function dfs(g::HKGraph, u)::Bool
if u != NIL
# Explore neighbors v of u in V
for v in g.adj[u]
matched_u = g.pair_v[v] # Get the vertex u' matched with v
# Check if the edge (u, v) leads to a vertex u'
# such that the path u -> v -> u' is part of a shortest augmenting path
if g.dist[matched_u] == g.dist[u] + 1
# Recursively call DFS on u'
if dfs(g, matched_u)
# If an augmenting path is found starting from u',
# update the matching: match v with u, and u with v
g.pair_v[v] = u
g.pair_u[u] = v
return true # Augmentation successful
end
end
end
# If no augmenting path was found starting from u through any neighbor v,
# mark u as visited in this DFS phase by setting its distance to INF
g.dist[u] = INF
return false # Augmentation failed for this path
end
# Base case: If u iNIL, it means we have reached the end of an alternating path
# originating from a free vertex in U and ending at a free vertex in V (represented bNIL).
return true
end
"""
Executes the Hopcroft-Karp algorithm to find the maximum matching.
Returns:
int: The size of the maximum matching found.
"""
function hopcroft_karp_algorithm(g)::Int
# Initialize matching pairs tNIL (unmatched)
g.pair_u = fill(NIL, g.m + 1)
g.pair_v = fill(NIL, g.n + 1)
matching_size = 0 # Initialize the size of the matching
# Keep finding augmenting paths using BFS and DFS until no more exist
while bfs(g)
# For every free vertex u in U
for u in 2:g.m+1
# If u is free and an augmenting path starting from u is found via DFS
if g.pair_u[u] == NIL && dfs(g, u)
# Increment the matching size
matching_size += 1
end
end
end
return matching_size
end
# --- Testing ---
""" Runs test cases for the Hopcroft-Karp implementation. """
function hk_g_tests()
println("Running tests...")
# Test Case 1
# m=3, n=5, edges = [(1+1, 4+1)] - 2 based indices, expected matching size = 1
g1 = HKGraph(3, 5)
add_edge!(g1, 1+1, 4+1)
res1 = hopcroft_karp_algorithm(g1)
expected_res1 = 1
println("Test 1: Result=$res1, Expected=$expected_res1")
@assert res1 == expected_res1 "Test 1 Failed: Expected $expected_res1, got $res1"
# Test Case 2 (changed values to 2 based indices)
# m=6, n=6, edges = [(1,4), (1,5), (5,1)]
# Expected matching size = 2 (e.g., (1,4), (5,1) or (1,5), (5,1))
# Note: Original C++ test had (0,1) and (5,0) which are problematic with 1-based index logic.
g2 = HKGraph(6, 6)
add_edge!(g2,1+1, 4+1)
add_edge!(g2, 1+1, 5+1)
add_edge!(g2, 5+1, 1+1) # Assuming (5,0) meant a valid edge like (5,1)
res2 = hopcroft_karp_algorithm(g2)
expected_res2 = 2
println("Test 2: Result=$res2, Expected=$expected_res2")
@assert res2 == expected_res2 "Test 3 Failed: Expected $expected_res2, got $res2"
# Test Case 3: Complete Bipartite Graph K_{3,3}
# m=3, n=3, all possible edges. Expected matching size = 3
g3 = HKGraph(3, 3)
for i in 2:4, j in 2:4
add_edge!(g3, i, j)
end
res3 = hopcroft_karp_algorithm(g3)
expected_res3 = 3
println("Test 3: Result=$res3, Expected=$expected_res3")
@assert res3 == expected_res3 "Test 4 Failed: Expected $expected_res3, got $res3"
# Test Case 4: No edges
# m=2, n=2, no edges. Expected matching size = 0
g4 = HKGraph(2, 2)
res4 = hopcroft_karp_algorithm(g4)
expected_res4 = 0
println("Test 4: Result=$res4, Expected=$expected_res4")
@assert res4 == expected_res4 "Test 4 Failed: Expected $expected_res4, got $res4"
print("All tests passed!")
end
function all_hk_tests()
# Run g-tests first
hk_g_tests()
println("\n--- Running main execution with hard-coded input ---")
# --- Hard-coded input data ---
# Example 1: Corresponds to Test Case 2
hardcoded_v1 = 4 # Number of vertices in left partition (m)
hardcoded_v2 = 4 # Number of vertices in right partition (n)
hardcoded_edges = [
(2, 2),
(2, 4),
(3, 4),
(4, 5),
(5, 4),
(5, 3)
]
# Expected output for Example 1: 3
# Use the selected hardcoded data
v1 = hardcoded_v1
v2 = hardcoded_v2
edges_data = hardcoded_edges
e_len = length(edges_data) # Number of edges is derived from the list
# Create the graph object
g = HKGraph(v1, v2)
println("Hard-coded graph dimensions: m=$v1, n=$v2, edges=$e_len")
println("Adding hard-coded edges:")
# Add edges from the hard-coded list
for (u, v) in edges_data
println(" Adding edge: 2-based ($u, $v), 1-based ($(u-1), $(v-1)) ")
# Add edge only if vertices are within valid 2-based range
if 2 <= u <= v1+1 && 2 <= v <= v2+1
add_edge!(g, u, v)
else
# This warning is important if hardcoded data might be invalid
println("Warning: Skipping invalid hard-coded edge ($u, $v) - indices out of range [1..$v1] or [1..$v2]")
end
end
# Run the Hopcroft-Karp algorithm
max_matching_size = hopcroft_karp_algorithm(g)
# Print the result
println("Maximum matching size is $max_matching_size")
end
all_hk_tests()
- Output:
Running tests... Test 1: Result=1, Expected=1 Test 2: Result=2, Expected=2 Test 3: Result=3, Expected=3 Test 4: Result=0, Expected=0 All tests passed! --- Running main execution with hard-coded input --- Hard-coded graph dimensions: m=4, n=4, edges=6 Adding hard-coded edges: Adding edge: 2-based (2, 2), 1-based (1, 1) Adding edge: 2-based (2, 4), 1-based (1, 3) Adding edge: 2-based (3, 4), 1-based (2, 3) Adding edge: 2-based (4, 5), 1-based (3, 4) Adding edge: 2-based (5, 4), 1-based (4, 3) Adding edge: 2-based (5, 3), 1-based (4, 2) Maximum matching size is 4
import java.util.*
data class Edge(val from: Int, val to: Int)
class BipartiteGraph(private val m: Int, private val n: Int) {
private var adjacencyLists: List<MutableList<Int>> = List(m + 1) { mutableListOf<Int>() }
private var pairU: MutableList<Int> = MutableList(m + 1) { NIL }
private var pairV: MutableList<Int> = MutableList(n + 1) { NIL }
private var levels: MutableList<Int> = MutableList(m + 1) { INFINITY }
fun addEdge(u: Int, v: Int) {
require(u in 1..m && v in 1..n) { "Attempt to add an edge ($u, $v) which is out of bounds" }
adjacencyLists[u].add(v)
}
fun hopcroftKarpAlgorithm(): Int {
pairU = MutableList(m + 1) { NIL }
pairV = MutableList(n + 1) { NIL }
var matchingSize = 0
while (breadthFirstSearch()) {
for (u in 1..m) {
if (pairU[u] == NIL && depthFirstSearch(u)) {
matchingSize++
}
}
}
return matchingSize
}
private fun breadthFirstSearch(): Boolean {
val queue: Queue<Int> = ArrayDeque()
for (u in 1..m) {
if (pairU[u] == NIL) {
levels[u] = 0
queue.offer(u)
} else {
levels[u] = INFINITY
}
}
levels[NIL] = INFINITY
while (queue.isNotEmpty()) {
val u = queue.poll()
if (levels[u] < levels[NIL]) {
for (v in adjacencyLists[u]) {
val matchedU = pairV[v]
if (levels[matchedU] == INFINITY) {
levels[matchedU] = levels[u] + 1
queue.offer(matchedU)
}
}
}
}
return levels[NIL] != INFINITY
}
private fun depthFirstSearch(u: Int): Boolean {
if (u != NIL) {
for (v in adjacencyLists[u]) {
val matchedU = pairV[v]
if (levels[matchedU] == levels[u] + 1) {
if (depthFirstSearch(matchedU)) {
pairV[v] = u
pairU[u] = v
return true
}
}
}
levels[u] = INFINITY
return false
}
return true
}
companion object {
private const val NIL = 0
private const val INFINITY = Int.MAX_VALUE
}
}
fun testValue(testNumber: Int, m: Int, n: Int, edges: List<Edge>, expectedResult: Int): Int {
val graph = BipartiteGraph(m, n)
edges.forEach { edge -> graph.addEdge(edge.from, edge.to) }
val result = graph.hopcroftKarpAlgorithm()
println("Test $testNumber: Result = $result, Expected = $expectedResult")
if (result == expectedResult) return 1
println("Test $testNumber failed.")
return 0
}
fun main() {
println("Running tests:")
var successCount = 0
// Test Case 1
successCount += testValue(1, 3, 5, listOf(Edge(1, 4)), 1)
// Test Case 2
successCount += testValue(2, 6, 6, listOf(Edge(1, 4), Edge(1, 5), Edge(5, 1)), 2)
// Test Case 3: Complete Bipartite Graph K(3,3)
val edges3 = mutableListOf<Edge>()
for (i in 1..3) {
for (j in 1..3) {
edges3.add(Edge(i, j))
}
}
successCount += testValue(3, 3, 3, edges3, 3)
// Test Case 4: No edges
successCount += testValue(4, 2, 2, emptyList(), 0)
// Test Case 5
val edges5 = listOf(
Edge(1, 1), Edge(1, 3), Edge(2, 3),
Edge(3, 4), Edge(4, 3), Edge(4, 2)
)
successCount += testValue(5, 4, 4, edges5, 4)
if (successCount == 5) {
println("All tests passed.")
}
}
- Output:
Running tests: Test 1: Result = 1, Expected = 1 Test 2: Result = 2, Expected = 2 Test 3: Result = 3, Expected = 3 Test 4: Result = 0, Expected = 0 Test 5: Result = 4, Expected = 4 All tests passed.
#!/usr/bin/env lua
-- Representation of a bipartite graph
-- Vertices in the left partition, U, are numbered from 1 to m,
-- and vertices in the right partition, V, are numbered 1 to n.
local BipartiteGraph = {}
BipartiteGraph.__index = BipartiteGraph
function BipartiteGraph:new(m, n)
local self = {
m = m,
n = n,
adjacency_lists = {},
pair_u = {},
pair_v = {},
levels = {},
NIL = 0,
INFINITY = 999999999
}
-- Initialize adjacency lists
for u = 1, m do
self.adjacency_lists[u] = {}
end
-- Initialize pairs
for u = 1, m do
self.pair_u[u] = self.NIL
end
for v = 1, n do
self.pair_v[v] = self.NIL
end
-- Initialize levels
for u = 1, m do
self.levels[u] = self.INFINITY
end
setmetatable(self, BipartiteGraph)
return self
end
function BipartiteGraph:add_edge(u, v)
if u >= 1 and u <= self.m and v >= 1 and v <= self.n then
table.insert(self.adjacency_lists[u], v)
else
error("Attempt to add an edge (" .. u .. ", " .. v .. ") which is out of bounds")
end
end
-- Return the matching size of the bipartite graph
function BipartiteGraph:hopcroft_karp_algorithm()
-- Reset pairs
for u = 1, self.m do
self.pair_u[u] = self.NIL
end
for v = 1, self.n do
self.pair_v[v] = self.NIL
end
local matching_size = 0
while self:breadth_first_search() do
for u = 1, self.m do
if self.pair_u[u] == self.NIL and self:depth_first_search(u) then
-- vertex u is free and an augmenting path starting
-- from u has been found by the depth first search
matching_size = matching_size + 1
end
end
end
return matching_size
end
-- Determines whether there exists an augmenting path starting from a free vertex in U.
-- Return true if an augmenting path could exist, otherwise false.
function BipartiteGraph:breadth_first_search()
local queue = {}
-- Initialize 'levels' for the vertices in U
for u = 1, self.m do
if self.pair_u[u] == self.NIL then
-- If u is a free vertex, its level is 0 and it is added to the queue
self.levels[u] = 0
table.insert(queue, u)
else
-- Otherwise, set 'levels' to infinity
self.levels[u] = self.INFINITY
end
end
-- The 'level' to the NIL node represents the length of the shortest augmenting path
self.levels[self.NIL] = self.INFINITY
local queue_front = 1
local queue_back = #queue
while queue_front <= queue_back do
local u = queue[queue_front]
queue_front = queue_front + 1
if self.levels[u] < self.levels[self.NIL] then
-- The path through u could lead to a shorter augmenting path
for _, v in ipairs(self.adjacency_lists[u]) do
-- Explore the neighbours v of u in V
local matched_u = self.pair_v[v]
if self.levels[matched_u] == self.INFINITY then
-- The matched vertex has not been visited yet
self.levels[matched_u] = self.levels[u] + 1
queue_back = queue_back + 1
queue[queue_back] = matched_u -- Enqueue the matched vertex to explore it further
end
end
end
end
-- An augmenting path from the initial free vertices was found if levels[NIL] is not INFINITY
return self.levels[self.NIL] ~= self.INFINITY
end
-- Determine whether the shortest path from vertex u in U found by breadth_first_search() can be augmented.
-- Return true if an augmenting path was found starting from u, otherwise false.
function BipartiteGraph:depth_first_search(u)
if u ~= self.NIL then
for _, v in ipairs(self.adjacency_lists[u]) do
-- Explore neighbours v of u in V
local matched_u = self.pair_v[v]
-- Check whether the edge (u, v) leads to a vertex matched_u
-- such that the path u -> v -> matched_u is part of a shortest augmenting path
if self.levels[matched_u] == self.levels[u] + 1 then
if self:depth_first_search(matched_u) then
-- An augmenting path is found starting from 'matched_u'
self.pair_v[v] = u -- Match v with u,
self.pair_u[u] = v -- and u with v
return true
end
end
end
-- No augmenting path was found starting from vertex u through any of its neighbours v,
-- so remove u from the depth first search phase of the algorithm
self.levels[u] = self.INFINITY
return false
end
return true
end
function test_value(test_number, m, n, edges, expected_result)
local graph = BipartiteGraph:new(m, n)
for _, edge in ipairs(edges) do
graph:add_edge(edge.from, edge.to)
end
local result = graph:hopcroft_karp_algorithm()
print("Test " .. test_number .. ": Result = " .. result .. ", Expected = " .. expected_result)
if result == expected_result then
return 1
end
print("Test " .. test_number .. " failed.")
return 0
end
-- Main execution
print("Running tests:")
local success_count = 0
-- Test Case 1
success_count = success_count + test_value(1, 3, 5, {{from = 1, to = 4}}, 1)
-- Test Case 2
success_count = success_count + test_value(2, 6, 6, {
{from = 1, to = 4},
{from = 1, to = 5},
{from = 5, to = 1}
}, 2)
-- Test Case 3: Complete Bipartite Graph K(3, 3)
local edges = {}
for i = 1, 3 do
for j = 1, 3 do
table.insert(edges, {from = i, to = j})
end
end
success_count = success_count + test_value(3, 3, 3, edges, 3)
-- Test Case 4: No edges
success_count = success_count + test_value(4, 2, 2, {}, 0)
-- Test Case 5
edges = {
{from = 1, to = 1},
{from = 1, to = 3},
{from = 2, to = 3},
{from = 3, to = 4},
{from = 4, to = 3},
{from = 4, to = 2}
}
success_count = success_count + test_value(5, 4, 4, edges, 4)
if success_count == 5 then
print("All tests passed.")
end
- Output:
Running tests: Test 1: Result = 1, Expected = 1 Test 2: Result = 2, Expected = 2 Test 3: Result = 3, Expected = 3 Test 4: Result = 0, Expected = 0 Test 5: Result = 4, Expected = 4 All tests passed.
(* ===================== Hopcroft-Karp in Mathematica ===================== *)
(* Uses indexed global symbols for mutable graph state, since Associations *)
(* are immutable value types in Mathematica and cannot be mutated in-place. *)
$NIL = 1;
$INF = Infinity;
(* ---------- Graph constructor ----------
Stores graph data in global indexed symbols:
hkM[id], hkN[id], hkAdj[id,u], hkPairU[id,u], hkPairV[id,v], hkDist[id,u]
Returns a graph id (integer). *)
$hkNextId = 1;
HKGraph[m_, n_] := Module[{id = $hkNextId},
$hkNextId++;
hkM[id] = m;
hkN[id] = n;
Do[hkAdj[id, u] = {}, {u, 1, m + 1}];
Do[hkPairU[id, u] = $NIL, {u, 1, m + 1}];
Do[hkPairV[id, v] = $NIL, {v, 1, n + 1}];
Do[hkDist[id, u] = $INF, {u, 1, m + 1}];
id
]
(* ---------- Add edge (2-based indices) ---------- *)
AddEdge[id_, u_, v_] :=
If[2 <= u <= hkM[id] + 1 && 2 <= v <= hkN[id] + 1,
hkAdj[id, u] = Append[hkAdj[id, u], v],
Print["Warning: Edge (", u, ",", v, ") out of bounds"]
]
(* ---------- BFS ---------- *)
BFS[id_] := Module[{queue = {}, u, v, mu},
Do[
If[hkPairU[id, u] == $NIL,
hkDist[id, u] = 0; AppendTo[queue, u],
hkDist[id, u] = $INF
],
{u, 2, hkM[id] + 1}
];
hkDist[id, $NIL] = $INF;
While[queue =!= {},
u = First[queue]; queue = Rest[queue];
If[hkDist[id, u] < hkDist[id, $NIL],
Do[
mu = hkPairV[id, v];
If[hkDist[id, mu] == $INF,
hkDist[id, mu] = hkDist[id, u] + 1;
AppendTo[queue, mu]
],
{v, hkAdj[id, u]}
]
]
];
hkDist[id, $NIL] =!= $INF
]
(* ---------- DFS ---------- *)
DFS[id_, u_] := Module[{mu, found = False},
If[u == $NIL, Return[True]];
Do[
mu = hkPairV[id, v];
If[hkDist[id, mu] == hkDist[id, u] + 1,
If[DFS[id, mu],
hkPairV[id, v] = u;
hkPairU[id, u] = v;
found = True;
Break[]
]
],
{v, hkAdj[id, u]}
];
If[!found, hkDist[id, u] = $INF];
found
]
(* ---------- Main algorithm ---------- *)
HopcroftKarp[id_] := Module[{matchingSize = 0},
Do[hkPairU[id, u] = $NIL, {u, 1, hkM[id] + 1}];
Do[hkPairV[id, v] = $NIL, {v, 1, hkN[id] + 1}];
While[BFS[id],
Do[
If[hkPairU[id, u] == $NIL && DFS[id, u],
matchingSize++
],
{u, 2, hkM[id] + 1}
]
];
matchingSize
]
(* ===================== Tests ===================== *)
Print["Running tests..."]
(* Test 1: single edge *)
g1 = HKGraph[3, 5];
AddEdge[g1, 2, 5];
res1 = HopcroftKarp[g1];
Print["Test 1: Result=", res1, ", Expected=1"];
Assert[res1 == 1, "Test 1 Failed"]
(* Test 2 *)
g2 = HKGraph[6, 6];
AddEdge[g2, 2, 5]; AddEdge[g2, 2, 6]; AddEdge[g2, 6, 2];
res2 = HopcroftKarp[g2];
Print["Test 2: Result=", res2, ", Expected=2"];
Assert[res2 == 2, "Test 2 Failed"]
(* Test 3: Complete bipartite K_{3,3} *)
g3 = HKGraph[3, 3];
Do[AddEdge[g3, i, j], {i, 2, 4}, {j, 2, 4}];
res3 = HopcroftKarp[g3];
Print["Test 3: Result=", res3, ", Expected=3"];
Assert[res3 == 3, "Test 3 Failed"]
(* Test 4: No edges *)
g4 = HKGraph[2, 2];
res4 = HopcroftKarp[g4];
Print["Test 4: Result=", res4, ", Expected=0"];
Assert[res4 == 0, "Test 4 Failed"]
Print["All tests passed!"]
(* ===================== Hard-coded main example ===================== *)
Print["\n--- Running main execution with hard-coded input ---"]
v1 = 4; v2 = 4;
hardcodedEdges = {{2,2},{2,4},{3,4},{4,5},{5,4},{5,3}};
elen = Length[hardcodedEdges];
g = HKGraph[v1, v2];
Print["Hard-coded graph dimensions: m=", v1, ", n=", v2, ", edges=", elen];
Print["Adding hard-coded edges:"];
Do[
{u, v} = e;
Print[" Adding edge: 2-based (", u, ", ", v, "), 1-based (", u-1, ", ", v-1, ") "];
If[2 <= u <= v1+1 && 2 <= v <= v2+1,
AddEdge[g, u, v],
Print["Warning: Skipping invalid hard-coded edge (", u, ",", v, ") - indices out of range"]
],
{e, hardcodedEdges}
]
maxMatchingSize = HopcroftKarp[g];
Print["Maximum matching size is ", maxMatchingSize]
- Output:
Running tests... Test 1: Result=1, Expected=1 Test 2: Result=2, Expected=2 Test 3: Result=3, Expected=3 Test 4: Result=0, Expected=0 All tests passed! --- Running main execution with hard-coded input --- Hard-coded graph dimensions: m=4, n=4, edges=6 Adding hard-coded edges: Adding edge: 2-based (2, 2), 1-based (1, 1) Adding edge: 2-based (2, 4), 1-based (1, 3) Adding edge: 2-based (3, 4), 1-based (2, 3) Adding edge: 2-based (4, 5), 1-based (3, 4) Adding edge: 2-based (5, 4), 1-based (4, 3) Adding edge: 2-based (5, 3), 1-based (4, 2) Maximum matching size is 4
program HopcroftKarp;
{$mode objfpc}{$H+}
uses
Classes, SysUtils, fgl;
const
NIL_VERTEX = 0;
INFINITE_LEVEL = MaxInt;
type
// Edge structure
TEdge = record
from, to_: Integer;
end;
// Dynamic array of integers
TIntArray = array of Integer;
// Dynamic array of integer arrays
TIntArray2D = array of TIntArray;
// Bipartite graph class
TBipartiteGraph = class
private
m, n: Integer; // Size of partitions
adjacency_lists: TIntArray2D; // Adjacency lists for U vertices
pair_u, pair_v: TIntArray; // Matching pairs
levels: TIntArray; // BFS levels
// Helper methods
function BreadthFirstSearch: Boolean;
function DepthFirstSearch(u: Integer): Boolean;
public
constructor Create(aM, aN: Integer);
procedure AddEdge(u, v: Integer);
function HopcroftKarpAlgorithm: Integer;
end;
constructor TBipartiteGraph.Create(aM, aN: Integer);
begin
m := aM;
n := aN;
// Initialize adjacency lists
SetLength(adjacency_lists, m + 1);
// Initialize matching arrays
SetLength(pair_u, m + 1);
SetLength(pair_v, n + 1);
// Initialize levels array
SetLength(levels, m + 1);
end;
procedure TBipartiteGraph.AddEdge(u, v: Integer);
begin
if (u >= 1) and (u <= m) and (v >= 1) and (v <= n) then
begin
SetLength(adjacency_lists[u], Length(adjacency_lists[u]) + 1);
adjacency_lists[u][High(adjacency_lists[u])] := v;
end
else
begin
raise Exception.Create('Attempt to add an edge (' +
IntToStr(u) + ', ' + IntToStr(v) +
') which is out of bounds');
end;
end;
function TBipartiteGraph.HopcroftKarpAlgorithm: Integer;
var
u: Integer;
matching_size: Integer;
begin
// Initialize matching
for u := 0 to m do
pair_u[u] := NIL_VERTEX;
for u := 0 to n do
pair_v[u] := NIL_VERTEX;
matching_size := 0;
while BreadthFirstSearch do
begin
for u := 1 to m do
begin
if (pair_u[u] = NIL_VERTEX) and DepthFirstSearch(u) then
begin
Inc(matching_size);
end;
end;
end;
Result := matching_size;
end;
function TBipartiteGraph.BreadthFirstSearch: Boolean;
var
queue: specialize TFPGList<Integer>;
u, v, matched_u, i: Integer;
begin
queue := specialize TFPGList<Integer>.Create;
try
// Initialize levels for vertices in U
for u := 1 to m do
begin
if pair_u[u] = NIL_VERTEX then
begin
levels[u] := 0;
queue.Add(u);
end
else
begin
levels[u] := INFINITE_LEVEL;
end;
end;
// Level of NIL represents shortest augmenting path length
levels[NIL_VERTEX] := INFINITE_LEVEL;
while queue.Count > 0 do
begin
u := queue[0];
queue.Delete(0);
if levels[u] < levels[NIL_VERTEX] then
begin
// Explore neighbors v of u in V
for i := 0 to High(adjacency_lists[u]) do
begin
v := adjacency_lists[u][i];
matched_u := pair_v[v];
if levels[matched_u] = INFINITE_LEVEL then
begin
levels[matched_u] := levels[u] + 1;
queue.Add(matched_u);
end;
end;
end;
end;
Result := (levels[NIL_VERTEX] <> INFINITE_LEVEL);
finally
queue.Free;
end;
end;
function TBipartiteGraph.DepthFirstSearch(u: Integer): Boolean;
var
v, matched_u, i: Integer;
begin
if u <> NIL_VERTEX then
begin
// Explore neighbors v of u in V
for i := 0 to High(adjacency_lists[u]) do
begin
v := adjacency_lists[u][i];
matched_u := pair_v[v];
// Check if edge leads to a vertex on shortest augmenting path
if levels[matched_u] = levels[u] + 1 then
begin
if DepthFirstSearch(matched_u) then
begin
pair_v[v] := u;
pair_u[u] := v;
Result := True;
Exit;
end;
end;
end;
// No augmenting path found, remove from DFS
levels[u] := INFINITE_LEVEL;
Result := False;
end
else
begin
// NIL vertex reached, augmenting path found
Result := True;
end;
end;
// Test function
function TestValue(testNumber, m, n: Integer; edges: array of TEdge; expected_result: Integer): Integer;
var
graph: TBipartiteGraph;
i: Integer;
result_value: Integer;
begin
graph := TBipartiteGraph.Create(m, n);
try
for i := 0 to High(edges) do
begin
graph.AddEdge(edges[i].from, edges[i].to_);
end;
result_value := graph.HopcroftKarpAlgorithm;
WriteLn('Test ', testNumber, ': Result = ', result_value, ', Expected = ', expected_result);
if result_value = expected_result then
begin
Result := 1;
end
else
begin
WriteLn('Test ', testNumber, ' failed.');
Result := 0;
end;
finally
graph.Free;
end;
end;
// Main procedure
var
success_count: Integer;
edges: array of TEdge;
i, j, idx: Integer;
begin
WriteLn('Running tests:');
success_count := 0;
// Test Case 1
SetLength(edges, 1);
edges[0].from := 1;
edges[0].to_ := 4;
success_count := success_count + TestValue(1, 3, 5, edges, 1);
// Test Case 2
SetLength(edges, 3);
edges[0].from := 1;
edges[0].to_ := 4;
edges[1].from := 1;
edges[1].to_ := 5;
edges[2].from := 5;
edges[2].to_ := 1;
success_count := success_count + TestValue(2, 6, 6, edges, 2);
// Test Case 3: Complete Bipartite Graph K(3, 3)
SetLength(edges, 9);
idx := 0;
for i := 1 to 3 do
begin
for j := 1 to 3 do
begin
edges[idx].from := i;
edges[idx].to_ := j;
Inc(idx);
end;
end;
success_count := success_count + TestValue(3, 3, 3, edges, 3);
// Test Case 4: No edges
SetLength(edges, 0);
success_count := success_count + TestValue(4, 2, 2, edges, 0);
// Test Case 5
SetLength(edges, 6);
edges[0].from := 1;
edges[0].to_ := 1;
edges[1].from := 1;
edges[1].to_ := 3;
edges[2].from := 2;
edges[2].to_ := 3;
edges[3].from := 3;
edges[3].to_ := 4;
edges[4].from := 4;
edges[4].to_ := 3;
edges[5].from := 4;
edges[5].to_ := 2;
success_count := success_count + TestValue(5, 4, 4, edges, 4);
if success_count = 5 then
begin
WriteLn('All tests passed.');
end;
end.
- Output:
Running tests: Test 1: Result = 1, Expected = 1 Test 2: Result = 2, Expected = 2 Test 3: Result = 3, Expected = 3 Test 4: Result = 0, Expected = 0 Test 5: Result = 4, Expected = 4 All tests passed.
#!/usr/bin/perl
use strict;
use warnings;
use List::Util qw(max);
# Representation of a bipartite graph
# Vertices in the left partition, U, are numbered from 1 to m,
# and vertices in the right partition, V, are numbered 1 to n.
package BipartiteGraph;
sub new {
my ($class, $m, $n) = @_;
my $self = {
m => $m,
n => $n,
adjacency_lists => {},
pair_u => {},
pair_v => {},
levels => {},
NIL => 0,
INFINITY => 999999999
};
# Initialize adjacency lists
for my $u (1..$m) {
$self->{adjacency_lists}{$u} = [];
}
# Initialize pairs
for my $u (1..$m) {
$self->{pair_u}{$u} = $self->{NIL};
}
for my $v (1..$n) {
$self->{pair_v}{$v} = $self->{NIL};
}
# Initialize levels
for my $u (1..$m) {
$self->{levels}{$u} = $self->{INFINITY};
}
bless $self, $class;
return $self;
}
sub add_edge {
my ($self, $u, $v) = @_;
if ($u >= 1 && $u <= $self->{m} && $v >= 1 && $v <= $self->{n}) {
push @{$self->{adjacency_lists}{$u}}, $v;
} else {
die "Attempt to add an edge ($u, $v) which is out of bounds\n";
}
}
# Return the matching size of the bipartite graph
sub hopcroft_karp_algorithm {
my ($self) = @_;
# Reset pairs
for my $u (1..$self->{m}) {
$self->{pair_u}{$u} = $self->{NIL};
}
for my $v (1..$self->{n}) {
$self->{pair_v}{$v} = $self->{NIL};
}
my $matching_size = 0;
while ($self->breadth_first_search()) {
for my $u (1..$self->{m}) {
if ($self->{pair_u}{$u} == $self->{NIL} && $self->depth_first_search($u)) {
# vertex u is free and an augmenting path starting
# from u has been found by the depth first search
$matching_size++;
}
}
}
return $matching_size;
}
# Determines whether there exists an augmenting path starting from a free vertex in U.
# Return true if an augmenting path could exist, otherwise false.
sub breadth_first_search {
my ($self) = @_;
my @queue = ();
# Initialize 'levels' for the vertices in U
for my $u (1..$self->{m}) {
if ($self->{pair_u}{$u} == $self->{NIL}) {
# If u is a free vertex, its level is 0 and it is added to the queue
$self->{levels}{$u} = 0;
push @queue, $u;
} else {
# Otherwise, set 'levels' to infinity
$self->{levels}{$u} = $self->{INFINITY};
}
}
# The 'level' to the NIL node represents the length of the shortest augmenting path
$self->{levels}{$self->{NIL}} = $self->{INFINITY};
while (@queue) {
my $u = shift @queue;
if ($self->{levels}{$u} < $self->{levels}{$self->{NIL}}) {
# The path through u could lead to a shorter augmenting path
for my $v (@{$self->{adjacency_lists}{$u}}) {
# Explore the neighbours v of u in V
my $matched_u = $self->{pair_v}{$v};
if ($self->{levels}{$matched_u} == $self->{INFINITY}) {
# The matched vertex has not been visited yet
$self->{levels}{$matched_u} = $self->{levels}{$u} + 1;
push @queue, $matched_u; # Enqueue the matched vertex to explore it further
}
}
}
}
# An augmenting path from the initial free vertices was found if levels[NIL] is not INFINITY
return $self->{levels}{$self->{NIL}} != $self->{INFINITY};
}
# Determine whether the shortest path from vertex u in U found by breadth_first_search() can be augmented.
# Return true if an augmenting path was found starting from u, otherwise false.
sub depth_first_search {
my ($self, $u) = @_;
if ($u != $self->{NIL}) {
for my $v (@{$self->{adjacency_lists}{$u}}) {
# Explore neighbours v of u in V
my $matched_u = $self->{pair_v}{$v};
# Check whether the edge (u, v) leads to a vertex matched_u
# such that the path u -> v -> matched_u is part of a shortest augmenting path
if ($self->{levels}{$matched_u} == $self->{levels}{$u} + 1) {
if ($self->depth_first_search($matched_u)) {
# An augmenting path is found starting from 'matched_u'
$self->{pair_v}{$v} = $u; # Match v with u,
$self->{pair_u}{$u} = $v; # and u with v
return 1;
}
}
}
# No augmenting path was found starting from vertex u through any of its neighbours v,
# so remove u from the depth first search phase of the algorithm
$self->{levels}{$u} = $self->{INFINITY};
return 0;
}
return 1;
}
package main;
sub test_value {
my ($test_number, $m, $n, $edges_ref, $expected_result) = @_;
my $graph = BipartiteGraph->new($m, $n);
for my $edge (@$edges_ref) {
$graph->add_edge($edge->{from}, $edge->{to});
}
my $result = $graph->hopcroft_karp_algorithm();
print "Test $test_number: Result = $result, Expected = $expected_result\n";
if ($result == $expected_result) {
return 1;
}
print "Test $test_number failed.\n";
return 0;
}
# Main execution
print "Running tests:\n";
my $success_count = 0;
# Test Case 1
$success_count += test_value(1, 3, 5, [{from => 1, to => 4}], 1);
# Test Case 2
$success_count += test_value(2, 6, 6, [
{from => 1, to => 4},
{from => 1, to => 5},
{from => 5, to => 1}
], 2);
# Test Case 3: Complete Bipartite Graph K(3, 3)
my @edges = ();
for my $i (1..3) {
for my $j (1..3) {
push @edges, {from => $i, to => $j};
}
}
$success_count += test_value(3, 3, 3, \@edges, 3);
# Test Case 4: No edges
$success_count += test_value(4, 2, 2, [], 0);
# Test Case 5
@edges = (
{from => 1, to => 1},
{from => 1, to => 3},
{from => 2, to => 3},
{from => 3, to => 4},
{from => 4, to => 3},
{from => 4, to => 2}
);
$success_count += test_value(5, 4, 4, \@edges, 4);
if ($success_count == 5) {
print "All tests passed.\n";
}
- Output:
Running tests: Test 1: Result = 1, Expected = 1 Test 2: Result = 2, Expected = 2 Test 3: Result = 3, Expected = 3 Test 4: Result = 0, Expected = 0 Test 5: Result = 4, Expected = 4 All tests passed.
integer m, n
sequence adj, pairU, pairV, dist
constant inf = 1e308*1e308,
NIL = 1
function BFS()
sequence queue := {}
for u=2 to m+1 do
if pairU[u] == NIL then
dist[u] = 0
queue &= u
else
dist[u] = inf
end if
end for
dist[NIL] = inf
while length(queue) do
integer u := queue[1]
queue = queue[2..$]
if dist[u] < dist[NIL] then
for v in adj[u] do
integer matchedU := pairV[v]
if is_inf(dist[matchedU]) then
dist[matchedU] = dist[u] + 1
queue &= matchedU
end if
end for
end if
end while
return not is_inf(dist[NIL])
end function
function DFS(integer u)
if u != NIL then
for v in adj[u] do
integer matchedU := pairV[v]
if dist[matchedU] == dist[u]+1 then
if DFS(matchedU) then
pairV[v] = u
pairU[u] = v
return true
end if
end if
end for
dist[u] = inf
return false
end if
return true
end function
function HopcroftKarpAlgorithm()
pairU := repeat(NIL, m+1)
pairV := repeat(NIL, n+1)
integer matchingSize := 0
while BFS() do
for u=2 to m+1 do
if pairU[u] == NIL and DFS(u) then
matchingSize += 1
end if
end for
end while
return matchingSize
end function
procedure test(integer id, _m, _n, expected, sequence edges, bool verbose=false)
m = _m
n = _n
adj := repeat({},m+1)
dist := repeat(0, m+1)
if verbose then
integer e := length(edges)
printf(1,"Hard-coded graph dimensions: m=%d, n=%d, edges=%d\n", {m, n, e})
printf(1,"Adding hard-coded edges:\n")
end if
for edge in edges do
integer {u,v} = edge
if verbose then
printf(1," Adding edge: (%d, %d)\n", {u, v})
end if
assert(1<=u and u<=m and 1<=v and v<=n)
adj[u+1] = append(adj[u+1], v+1)
end for
integer actual := HopcroftKarpAlgorithm()
if verbose then
printf(1,"\nMaximum matching size is %d\n", actual)
else
printf(1,"Test %d: Result=%d, Expected=%d\n", {id,actual,expected})
assert(actual==expected)
end if
end procedure
printf(1,"Running tests...\n")
test(1,3,5,1,{{1,4}})
test(2,6,6,2,{{1,4},{1,5},{5,1}})
test(3,3,3,3,{{1,1},{1,2},{1,3},
{2,1},{2,2},{2,3},
{3,1},{3,2},{3,3}})
test(4,2,2,0,{})
printf(1,"All tests passed!\n")
printf(1,"\n--- Running main execution with hard-coded input ---\n")
constant hardcodedEdges := {{1,1},{1,3},{2,3},{3,4},{4,3},{4,2}}
test(0,4,4,0,hardcodedEdges,true)
- Output:
Running tests... Test 1: Result=1, Expected=1 Test 2: Result=2, Expected=2 Test 3: Result=3, Expected=3 Test 4: Result=0, Expected=0 All tests passed! --- Running main execution with hard-coded input --- Hard-coded graph dimensions: m=4, n=4, edges=6 Adding hard-coded edges: Adding edge: (1, 1) Adding edge: (1, 3) Adding edge: (2, 3) Adding edge: (3, 4) Adding edge: (4, 3) Adding edge: (4, 2) Maximum matching size is 4
import collections
# Setting a large value for infinity, equivalent to C++ INT_MAX for distance calculations
INF = float('inf')
# Using 0 as the NIL node, consistent with the C++ code
NIL = 0
class HKGraph:
"""
Implementation of the Hopcroft-Karp algorithm for finding maximum matching
in a bipartite graph.
Assumes vertices in the left partition (U) are numbered 1 to m,
and vertices in the right partition (V) are numbered 1 to n.
The NIL node is represented by 0.
"""
def __init__(self, m, n):
"""
Constructor for the HKGraph class.
Args:
m (int): Number of vertices in the left partition (U).
n (int): Number of vertices in the right partition (V).
"""
self.m = m # Number of vertices on the left side (U)
self.n = n # Number of vertices on the right side (V)
# Adjacency list: adj[u] contains list of neighbors of u in V
# Initialize with empty lists for vertices 1 to m
self.adj = [[] for _ in range(m + 1)]
# Matching pairs:
# pair_u[u] stores the vertex v in V matched with u in U (or NIL if unmatched)
self.pair_u = [NIL] * (m + 1)
# pair_v[v] stores the vertex u in U matched with v in V (or NIL if unmatched)
self.pair_v = [NIL] * (n + 1)
# dist[u] stores the distance (level) of vertex u in U during BFS
# Initialized within the hopcroft_karp_algorithm or bfs method
self.dist = [INF] * (m + 1)
def add_edge(self, u, v):
"""
Adds a directed edge from vertex u (left partition) to vertex v (right partition).
Args:
u (int): Vertex index in the left partition (1 to m).
v (int): Vertex index in the right partition (1 to n).
"""
# Ensure vertices are within the valid range
if 1 <= u <= self.m and 1 <= v <= self.n:
self.adj[u].append(v) # Add v to u's adjacency list
else:
# Optionally print a warning for edges added outside the defined range
# This check is now also done in the main section when adding edges.
# print(f"Warning: Attempted to add edge ({u}, {v}) outside graph bounds [1..{self.m}], [1..{self.n}]")
pass
def bfs(self) -> bool:
"""
Performs Breadth-First Search (BFS) to find layers in the graph.
It checks if there exists an augmenting path starting from a free vertex in U.
Returns:
bool: True if an augmenting path might exist (dist[NIL] is finite),
False otherwise.
"""
queue = collections.deque() # Use deque for efficient queue operations
# Initialize distances for vertices in U
for u in range(1, self.m + 1):
if self.pair_u[u] == NIL:
# If u is a free vertex, its distance is 0, add to queue
self.dist[u] = 0
queue.append(u)
else:
# Otherwise, set distance to infinity initially
self.dist[u] = INF
# Distance to the NIL node represents the length of the shortest augmenting path
self.dist[NIL] = INF
while queue:
u = queue.popleft() # Dequeue a vertex from U
# If the path through u can potentially lead to a shorter augmenting path
if self.dist[u] < self.dist[NIL]:
# Explore neighbors v of u in V
for v in self.adj[u]:
matched_u = self.pair_v[v] # Get the vertex u' matched with v
# If the matched vertex u' hasn't been visited yet (its distance is INF)
if self.dist[matched_u] == INF:
# Set the distance of u' based on u
self.dist[matched_u] = self.dist[u] + 1
# Enqueue u' to explore further
queue.append(matched_u)
# If dist[NIL] is still INF, no augmenting path was found originating
# from the initial free vertices. Otherwise, augmenting paths might exist.
return self.dist[NIL] != INF
def dfs(self, u: int) -> bool:
"""
Performs Depth-First Search (DFS) starting from vertex u in U
to find and augment along a shortest path identified by BFS.
Args:
u (int): The current vertex in U being visited (or NIL).
Returns:
bool: True if an augmenting path was found and used starting from u,
False otherwise.
"""
if u != NIL:
# Explore neighbors v of u in V
for v in self.adj[u]:
matched_u = self.pair_v[v] # Get the vertex u' matched with v
# Check if the edge (u, v) leads to a vertex u'
# such that the path u -> v -> u' is part of a shortest augmenting path
if self.dist[matched_u] == self.dist[u] + 1:
# Recursively call DFS on u'
if self.dfs(matched_u):
# If an augmenting path is found starting from u',
# update the matching: match v with u, and u with v
self.pair_v[v] = u
self.pair_u[u] = v
return True # Augmentation successful
# If no augmenting path was found starting from u through any neighbor v,
# mark u as visited in this DFS phase by setting its distance to INF
self.dist[u] = INF
return False # Augmentation failed for this path
# Base case: If u is NIL, it means we have reached the end of an alternating path
# originating from a free vertex in U and ending at a free vertex in V (represented by NIL).
return True
def hopcroft_karp_algorithm(self) -> int:
"""
Executes the Hopcroft-Karp algorithm to find the maximum matching.
Returns:
int: The size of the maximum matching found.
"""
# Initialize matching pairs to NIL (unmatched)
self.pair_u = [NIL] * (self.m + 1)
self.pair_v = [NIL] * (self.n + 1)
matching_size = 0 # Initialize the size of the matching
# Keep finding augmenting paths using BFS and DFS until no more exist
while self.bfs():
# For every free vertex u in U
for u in range(1, self.m + 1):
# If u is free and an augmenting path starting from u is found via DFS
if self.pair_u[u] == NIL and self.dfs(u):
# Increment the matching size
matching_size += 1
return matching_size
# --- Testing ---
def tests():
""" Runs test cases for the Hopcroft-Karp implementation. """
print("Running tests...")
# Test Case 1 (Corrected from C++ version - using 1-based indexing)
# m=3, n=5, edges = [(1, 4)] - Expected matching size = 1
g1 = HKGraph(3, 5)
g1.add_edge(1, 4)
res1 = g1.hopcroft_karp_algorithm()
expected_res1 = 1
print(f"Test 1: Result={res1}, Expected={expected_res1}")
assert res1 == expected_res1, f"Test 1 Failed: Expected {expected_res1}, got {res1}"
# Test Case 2 (Corrected from C++ version - using 1-based indexing, assuming (5,0) meant (5,1) or similar valid edge)
# m=6, n=6, edges = [(1,4), (1,5), (5,1)]
# Expected matching size = 2 (e.g., (1,4), (5,1) or (1,5), (5,1))
# Note: Original C++ test had (0,1) and (5,0) which are problematic with 1-based index logic.
g2 = HKGraph(6, 6)
# g3.add_edge(0,1) # Invalid vertex 0 in U
g2.add_edge(1, 4)
g2.add_edge(1, 5)
g2.add_edge(5, 1) # Assuming (5,0) meant a valid edge like (5,1)
# g2.add_edge(5, 0) # Invalid vertex 0 in V
res2 = g2.hopcroft_karp_algorithm()
expected_res2 = 2
print(f"Test 2: Result={res2}, Expected={expected_res2}")
assert res2 == expected_res2, f"Test 3 Failed: Expected {expected_res2}, got {res2}"
# Test Case 3: Complete Bipartite Graph K_{3,3}
# m=3, n=3, all possible edges. Expected matching size = 3
g3 = HKGraph(3, 3)
for i in range(1, 4):
for j in range(1, 4):
g3.add_edge(i, j)
res3 = g3.hopcroft_karp_algorithm()
expected_res3 = 3
print(f"Test 3: Result={res3}, Expected={expected_res3}")
assert res3 == expected_res3, f"Test 4 Failed: Expected {expected_res3}, got {res3}"
# Test Case 4: No edges
# m=2, n=2, no edges. Expected matching size = 0
g4 = HKGraph(2, 2)
res4 = g4.hopcroft_karp_algorithm()
expected_res4 = 0
print(f"Test 4: Result={res4}, Expected={expected_res4}")
assert res4 == expected_res4, f"Test 4 Failed: Expected {expected_res4}, got {res4}"
print("All tests passed!")
# --- Main execution ---
if __name__ == "__main__":
# Run self-tests first
tests()
print("\n--- Running main execution with hard-coded input ---")
# --- Hard-coded input data ---
# Example 1: Corresponds to Test Case 2
hardcoded_v1 = 4 # Number of vertices in left partition (m)
hardcoded_v2 = 4 # Number of vertices in right partition (n)
hardcoded_edges = [
(1, 1),
(1, 3),
(2, 3),
(3, 4),
(4, 3),
(4, 2)
]
# Expected output for Example 1: 3
# Use the selected hardcoded data
v1 = hardcoded_v1
v2 = hardcoded_v2
edges_data = hardcoded_edges
e = len(edges_data) # Number of edges is derived from the list
# Create the graph object
g = HKGraph(v1, v2)
print(f"Hard-coded graph dimensions: m={v1}, n={v2}, edges={e}")
print("Adding hard-coded edges:")
# Add edges from the hard-coded list
for u, v in edges_data:
print(f" Adding edge: ({u}, {v})")
# Add edge only if vertices are within valid 1-based range
if 1 <= u <= v1 and 1 <= v <= v2:
g.add_edge(u, v)
else:
# This warning is important if hardcoded data might be invalid
print(f"Warning: Skipping invalid hard-coded edge ({u}, {v}) - indices out of range [1..{v1}] or [1..{v2}]")
# Run the Hopcroft-Karp algorithm
max_matching_size = g.hopcroft_karp_algorithm()
# Print the result
print(f"\nMaximum matching size is {max_matching_size}")
- Output:
Running tests... Test 1: Result=1, Expected=1 Test 2: Result=2, Expected=2 Test 3: Result=3, Expected=3 Test 4: Result=0, Expected=0 All tests passed! --- Running main execution with hard-coded input --- Hard-coded graph dimensions: m=4, n=4, edges=6 Adding hard-coded edges: Adding edge: (1, 1) Adding edge: (1, 3) Adding edge: (2, 3) Adding edge: (3, 4) Adding edge: (4, 3) Adding edge: (4, 2) Maximum matching size is 4
You may try the code at https://rdrr.io/snippets/
library(R6)
# Constants
NIL <- 1
INF <- .Machine$integer.max
# HKGraph class
HKGraph <- R6Class("HKGraph",
public = list(
m = NULL,
n = NULL,
adj = NULL,
pair_u = NULL,
pair_v = NULL,
dist = NULL,
initialize = function(m, n) {
self$m <- m
self$n <- n
self$adj <- vector("list", m + 1)
self$pair_u <- rep(NIL, m + 1)
self$pair_v <- rep(NIL, n + 1)
self$dist <- rep(INF, m + 1)
},
add_edge = function(u, v) {
if (u >= 2 & u <= self$m + 1 & v >= 2 & v <= self$n + 1) {
self$adj[[u]] <- c(self$adj[[u]], v)
} else {
warning(paste0("Attempted to add edge (", u, ", ", v, ") outside graph bounds [2..", self$m + 1, "], [2..", self$n + 1, "]"))
}
}
)
)
# BFS function
bfs <- function(g) {
queue <- c()
# Reset distances
for (u in 2:(g$m + 1)) {
if (g$pair_u[u] == NIL) {
g$dist[u] <- 0
queue <- c(queue, u)
} else {
g$dist[u] <- INF
}
}
g$dist[NIL] <- INF
while (length(queue) > 0) {
u <- queue[1]
queue <- queue[-1]
if (g$dist[u] < g$dist[NIL]) {
for (v in g$adj[[u]]) {
matched_u <- g$pair_v[v]
if (g$dist[matched_u] == INF) {
g$dist[matched_u] <- g$dist[u] + 1
queue <- c(queue, matched_u)
}
}
}
}
return(g$dist[NIL] != INF)
}
# DFS function
dfs <- function(g, u) {
if (u != NIL) {
for (v in g$adj[[u]]) {
matched_u <- g$pair_v[v]
if (g$dist[matched_u] == g$dist[u] + 1) {
if (dfs(g, matched_u)) {
g$pair_v[v] <- u
g$pair_u[u] <- v
return(TRUE)
}
}
}
g$dist[u] <- INF
return(FALSE)
}
return(TRUE)
}
# Main Hopcroft-Karp function
hopcroft_karp_algorithm <- function(g) {
# Reset matching
g$pair_u <- rep(NIL, g$m + 1)
g$pair_v <- rep(NIL, g$n + 1)
matching_size <- 0
while (bfs(g)) {
for (u in 2:(g$m + 1)) {
if (g$pair_u[u] == NIL & dfs(g, u)) {
matching_size <- matching_size + 1
}
}
}
return(matching_size)
}
# Test cases
hk_g_tests <- function() {
cat("Running tests...\n")
# Test 1
g1 <- HKGraph$new(3, 5)
g1$add_edge(2, 5)
res1 <- hopcroft_karp_algorithm(g1)
expected_res1 <- 1
cat("Test 1: Result =", res1, ", Expected =", expected_res1, "\n")
stopifnot(res1 == expected_res1)
# Test 2
g2 <- HKGraph$new(6, 6)
g2$add_edge(2, 5)
g2$add_edge(2, 6)
g2$add_edge(6, 2)
res2 <- hopcroft_karp_algorithm(g2)
expected_res2 <- 2
cat("Test 2: Result =", res2, ", Expected =", expected_res2, "\n")
stopifnot(res2 == expected_res2)
# Test 3: Complete Bipartite Graph K_{3,3}
g3 <- HKGraph$new(3, 3)
for (i in 2:4) {
for (j in 2:4) {
g3$add_edge(i, j)
}
}
res3 <- hopcroft_karp_algorithm(g3)
expected_res3 <- 3
cat("Test 3: Result =", res3, ", Expected =", expected_res3, "\n")
stopifnot(res3 == expected_res3)
# Test 4: No edges
g4 <- HKGraph$new(2, 2)
res4 <- hopcroft_karp_algorithm(g4)
expected_res4 <- 0
cat("Test 4: Result =", res4, ", Expected =", expected_res4, "\n")
stopifnot(res4 == expected_res4)
cat("All tests passed!\n")
}
# Hard-coded example run
all_hk_tests <- function() {
hk_g_tests()
cat("\n--- Running main execution with hard-coded input ---\n")
# Hardcoded data
hardcoded_v1 <- 4
hardcoded_v2 <- 4
hardcoded_edges <- list(
c(2, 2),
c(2, 4),
c(3, 4),
c(4, 5),
c(5, 4),
c(5, 3)
)
v1 <- hardcoded_v1
v2 <- hardcoded_v2
edges_data <- hardcoded_edges
e_len <- length(edges_data)
g <- HKGraph$new(v1, v2)
cat("Hard-coded graph dimensions: m=", v1, ", n=", v2, ", edges=", e_len, "\n")
cat("Adding hard-coded edges:\n")
for (edge in edges_data) {
u <- edge[1]
v <- edge[2]
cat(" Adding edge: 2-based (", u, ", ", v, ")\n")
if (u >= 2 & u <= v1 + 1 & v >= 2 & v <= v2 + 1) {
g$add_edge(u, v)
} else {
cat("Warning: Skipping invalid hard-coded edge (", u, ", ", v, ")\n")
}
}
max_matching_size <- hopcroft_karp_algorithm(g)
cat("Maximum matching size is", max_matching_size, "\n")
}
# Run all tests and main example
all_hk_tests()
- Output:
Running tests... Test 1: Result = 1 , Expected = 1 Test 2: Result = 2 , Expected = 2 Test 3: Result = 3 , Expected = 3 Test 4: Result = 0 , Expected = 0 All tests passed! --- Running main execution with hard-coded input --- Hard-coded graph dimensions: m= 4 , n= 4 , edges= 6 Adding hard-coded edges: Adding edge: 2-based ( 2 , 2 ) Adding edge: 2-based ( 2 , 4 ) Adding edge: 2-based ( 3 , 4 ) Adding edge: 2-based ( 4 , 5 ) Adding edge: 2-based ( 5 , 4 ) Adding edge: 2-based ( 5 , 3 ) Maximum matching size is 4
# 20250708 Raku programming solution
# Edge record to represent graph edges
class Edge { has Int ($.from, $.to);
method new(Int $from, Int $to) { self.bless(:$from, :$to) }
}
# BipartiteGraph class implementing the Hopcroft-Karp algorithm
class BipartiteGraph {
has Int $.m; # Number of vertices in left partition U
has Int $.n; # Number of vertices in right partition V
has @.adj; # Adjacency lists for vertices in U
has @.pair-u; # Matching for vertices in U
has @.pair-v; # Matching for vertices in V
has @.levels; # Distance levels for BFS
# Constants
constant NIL = 0;
constant INFINITY = Inf;
method new(Int $m, Int $n where * > 0) {
my @adj = [] xx ($m + 1);
my @pair-u = (NIL) xx ($m + 1);
my @pair-v = (NIL) xx ($n + 1);
my @levels = Inf xx ($m + 1);
return self.bless(:$m, :$n, :@adj, :@pair-u, :@pair-v, :@levels);
}
method add-edge( Int $u where 1 <= * <= $.m, Int $v where 1 <= * <= $.n ) {
return @!adj[$u].push: $v;
}
method hopcroft-karp-algorithm() returns Int {
@!pair-u = (NIL) xx ($!m + 1); # Reset
@!pair-v = (NIL) xx ($!n + 1); # Reset
my Int $matching-size = 0;
while self.breadth-first-search() {
for 1..$!m -> $u {
# Check if vertex u is free and can be part of an augmenting path
$matching-size++ if @!pair-u[$u] == NIL and $.depth-first-search($u)
}
} # Continue until no more augmenting paths can be found
return $matching-size
}
# BFS to find if augmenting paths exist and compute shortest path lengths
method breadth-first-search() returns Bool {
my @queue = gather for 1..$!m -> $u { # Initialize levels for vertices
@!pair-u[$u] == NIL ?? ( @!levels[take $u] = 0 )
!! ( @!levels[$u] = INFINITY )
}
# NIL vertex level represents shortest augmenting path length
@!levels[NIL] = INFINITY;
# BFS traversal
while my $u = @queue.shift {
# Only process if this path could lead to a shorter augmenting path
if @!levels[$u] < @!levels[NIL] {
for @!adj[$u].list -> $v {
my $matched-u = @!pair-v[$v];
# If the matched vertex hasn't been visited yet
if @!levels[$matched-u] == INFINITY {
@!levels[$matched-u] = @!levels[$u] + 1;
@queue.push($matched-u);
}
}
}
}
return @!levels[NIL] != INFINITY; # true if an augmenting path was found
}
# DFS to find and construct augmenting paths
method depth-first-search(Int $u) returns Bool {
if $u != NIL {
for @!adj[$u].list -> $v {
my $matched-u = @!pair-v[$v];
# Check if this edge is part of a shortest augmenting path
if @!levels[$matched-u] == @!levels[$u] + 1 {
# Recursively try to find augmenting path from matched vertex
if self.depth-first-search($matched-u) {
(@!pair-v[$v], @!pair-u[$u]) = $u, $v; # Update matching
return True;
}
}
}
@!levels[$u] = INFINITY; # No augmenting path found through this vertex
return False;
}
return True;
}
}
# Test runner function
sub test-case(Int $test-num, Int $m, Int $n, @edges, Int $expected) returns Bool {
my $graph = BipartiteGraph.new($m, $n);
for @edges -> $edge { $graph.add-edge($edge.from, $edge.to) }
my $result = $graph.hopcroft-karp-algorithm();
say "Test $test-num: Result = $result, Expected = $expected";
return True if $result == $expected;
say "Test $test-num failed!";
return False;
}
say "Running Hopcroft-Karp Algorithm Tests:";
my $success-count = 0;
# Test Case 1: Simple case
$success-count += test-case(1, 3, 5, [Edge.new(1, 4)], 1) ?? 1 !! 0;
# Test Case 2: Multiple edges
$success-count += test-case(
2, 6, 6, [ Edge.new(1, 4), Edge.new(1, 5), Edge.new(5, 1) ], 2
) ?? 1 !! 0;
# Test Case 3: Complete bipartite graph K(3,3)
my @edges = gather for 1..3 X 1..3 -> ($i,$j) { take Edge.new($i,$j) };
$success-count += test-case(3, 3, 3, @edges, 3) ?? 1 !! 0;
# Test Case 4: No edges
$success-count += test-case(4, 2, 2, [], 0) ?? 1 !! 0;
# Test Case 5: Complex case
$success-count += test-case(
5, 4, 4, [ Edge.new(1, 1), Edge.new(1, 3), Edge.new(2, 3),
Edge.new(3, 4), Edge.new(4, 3), Edge.new(4, 2) ], 4
) ?? 1 !! 0;
say $success-count == 5 ?? "All tests passed!\n"
!! "$success-count/5 tests passed.\n";
say "Running main execution with hard-coded input:";
my ($hardcoded-m, $hardcoded-n) = 4, 4;
my @hardcoded-edges = [ [1, 1], [1, 3], [2, 3], [3, 4], [4, 3], [4, 2] ];
my $graph = BipartiteGraph.new($hardcoded-m, $hardcoded-n);
say "Hard-coded graph dimensions: m=$hardcoded-m, n=$hardcoded-n, edges={@hardcoded-edges.elems}";
say "Adding hard-coded edges:";
for @hardcoded-edges -> [$u, $v] {
say " Adding edge: ($u, $v)";
if 1 <= $u <= $hardcoded-m and 1 <= $v <= $hardcoded-n {
$graph.add-edge($u, $v);
} else {
say "Warning: Skipping invalid edge ($u, $v) - indices out of range";
}
}
say "\nMaximum matching size is $graph.hopcroft-karp-algorithm()";
You may Attempt This Online!
use std::collections::VecDeque;
use std::u32;
/// Representation of a bipartite graph.
/// Vertices in the left partition, U, are numbered from 1 to m,
/// and vertices in the right partition, V, are numbered 1 to n.
struct BipartiteGraph {
adjacency_lists: Vec<Vec<u32>>, // adjacency_lists(u) stores a list of neighbours of u in V
pair_u: Vec<u32>, // pair_u(u) stores the vertex v in V matched with u in U, or NIL if unmatched
pair_v: Vec<u32>, // pair_v(v) stores the vertex u in U matched with v in V, or NIL if unmatched
levels: Vec<u32>, // levels(u) stores the level of vertex u in U during a breadth first search
m: u32, // Index of the vertices in the left partition
n: u32, // Index of the vertices in the right partition
nil: u32,
infinity: u32,
}
impl BipartiteGraph {
fn new(m: u32, n: u32) -> Self {
let nil = 0;
let infinity = u32::MAX;
let mut adjacency_lists = Vec::with_capacity((m + 1) as usize);
for _ in 0..=m {
adjacency_lists.push(Vec::new());
}
let pair_u = vec![nil; (m + 1) as usize];
let pair_v = vec![nil; (n + 1) as usize];
let levels = vec![infinity; (m + 1) as usize];
BipartiteGraph {
adjacency_lists,
pair_u,
pair_v,
levels,
m,
n,
nil,
infinity,
}
}
fn add_edge(&mut self, u: u32, v: u32) -> Result<(), String> {
if 1 <= u && u <= self.m && 1 <= v && v <= self.n {
self.adjacency_lists[u as usize].push(v);
Ok(())
} else {
Err(format!("Attempt to add an edge ({}, {}) which is out of bounds", u, v))
}
}
/// Return the matching size of the bipartite graph.
fn hopcroft_karp_algorithm(&mut self) -> u32 {
self.pair_u = vec![self.nil; (self.m + 1) as usize];
self.pair_v = vec![self.nil; (self.n + 1) as usize];
let mut matching_size = 0;
while self.breadth_first_search() {
for u in 1..=self.m {
// vertex u is free and an augmenting path starting
// from u has been found by the depth first search
if self.pair_u[u as usize] == self.nil && self.depth_first_search(u) {
matching_size += 1;
}
}
}
matching_size
}
/// Determines whether there exists an augmenting path starting from a free vertex in U.
///
/// Return true if an augmenting path could exist, otherwise false.
fn breadth_first_search(&mut self) -> bool {
let mut queue = VecDeque::new();
// Initialize 'levels' for the vertices in U
for u in 1..=self.m {
if self.pair_u[u as usize] == self.nil {
// If u is a free vertex, its level is 0 and it is added to the queue
self.levels[u as usize] = 0;
queue.push_back(u);
} else {
// Otherwise, set 'levels' to infinity
self.levels[u as usize] = self.infinity;
}
}
// The 'level' to the NIL node represents the length of the shortest augmenting path
self.levels[self.nil as usize] = self.infinity;
while !queue.is_empty() {
let u = queue.pop_front().unwrap();
// The path through u could lead to a shorter augmenting path
if self.levels[u as usize] < self.levels[self.nil as usize] {
// Explore the neighbours v of u in V
for &v in &self.adjacency_lists[u as usize] {
let matched_u = self.pair_v[v as usize];
// The matched vertex has not been visited yet
if self.levels[matched_u as usize] == self.infinity {
self.levels[matched_u as usize] = self.levels[u as usize] + 1;
// Enqueue the matched vertex to explore it further
queue.push_back(matched_u);
}
}
}
}
// An augmenting path from the initial free vertices was found if levels[NIL] is not INFINITY
self.levels[self.nil as usize] != self.infinity
}
/// Determine whether the shortest path from vertex u in U found by breadth_first_search() can be augmented.
///
/// Return true if an augmenting path was found starting from u, otherwise false.
fn depth_first_search(&mut self, u: u32) -> bool {
if u != self.nil {
// Explore neighbours v of u in V
for &v in &self.adjacency_lists[u as usize].clone() {
let matched_u = self.pair_v[v as usize];
// Check whether the edge (u, v) leads to a vertex matched_u
// such that the path u -> v -> matched_u is part of a shortest augmenting path
if self.levels[matched_u as usize] == self.levels[u as usize] + 1 {
// An augmenting path is found starting from 'matched_u'
if self.depth_first_search(matched_u) {
// Match v with u and u with v
self.pair_v[v as usize] = u;
self.pair_u[u as usize] = v;
return true;
}
}
}
// No augmenting path was found starting from vertex u through any of its neighbours v,
// so remove u from the depth first search phase of the algorithm
self.levels[u as usize] = self.infinity;
false
} else {
true
}
}
}
struct Edge {
from: u32,
to: u32,
}
fn test_value(test_number: u32, m: u32, n: u32, edges: &[Edge], expected_result: u32) -> u32 {
let mut graph = BipartiteGraph::new(m, n);
for edge in edges {
if let Err(e) = graph.add_edge(edge.from, edge.to) {
println!("{}", e);
return 0;
}
}
let result = graph.hopcroft_karp_algorithm();
println!("Test {}: Result = {}, Expected = {}", test_number, result, expected_result);
if result == expected_result {
1
} else {
println!("Test {} failed.", test_number);
0
}
}
fn main() {
println!("Running tests:");
let mut success_count = 0;
// Test Case 1
success_count += test_value(1, 3, 5, &[Edge { from: 1, to: 4 }], 1);
// Test Case 2
success_count += test_value(2, 6, 6, &[
Edge { from: 1, to: 4 },
Edge { from: 1, to: 5 },
Edge { from: 5, to: 1 }
], 2);
// Test Case 3: Complete Bipartite Graph K(3, 3)
let mut edges = Vec::new();
for i in 1..=3 {
for j in 1..=3 {
edges.push(Edge { from: i, to: j });
}
}
success_count += test_value(3, 3, 3, &edges, 3);
// Test Case 4: No edges
success_count += test_value(4, 2, 2, &[], 0);
// Test Case 5
let edges = vec![
Edge { from: 1, to: 1 },
Edge { from: 1, to: 3 },
Edge { from: 2, to: 3 },
Edge { from: 3, to: 4 },
Edge { from: 4, to: 3 },
Edge { from: 4, to: 2 }
];
success_count += test_value(5, 4, 4, &edges, 4);
if success_count == 5 {
println!("All tests passed.");
}
}
- Output:
Running tests: Test 1: Result = 1, Expected = 1 Test 2: Result = 2, Expected = 2 Test 3: Result = 3, Expected = 3 Test 4: Result = 0, Expected = 0 Test 5: Result = 4, Expected = 4 All tests passed.
import Foundation
// Setting a large value for infinity
let INF = Int.max
// Using 0 as the NIL node
let NIL = 0
class HKGraph {
/**
Implementation of the Hopcroft-Karp algorithm for finding maximum matching
in a bipartite graph.
Assumes vertices in the left partition (U) are numbered 1 to m,
and vertices in the right partition (V) are numbered 1 to n.
The NIL node is represented by 0.
*/
private var m: Int // Number of vertices on the left side (U)
private var n: Int // Number of vertices on the right side (V)
// Adjacency list: adj[u] contains list of neighbors of u in V
private var adj: [[Int]]
// Matching pairs:
// pair_u[u] stores the vertex v in V matched with u in U (or NIL if unmatched)
private var pair_u: [Int]
// pair_v[v] stores the vertex u in U matched with v in V (or NIL if unmatched)
private var pair_v: [Int]
// dist[u] stores the distance (level) of vertex u in U during BFS
private var dist: [Int]
/**
Constructor for the HKGraph class.
- Parameters:
- m: Number of vertices in the left partition (U).
- n: Number of vertices in the right partition (V).
*/
init(_ m: Int, _ n: Int) {
self.m = m
self.n = n
// Initialize with empty lists for vertices 1 to m
self.adj = Array(repeating: [Int](), count: m + 1)
// Initialize matching arrays
self.pair_u = Array(repeating: NIL, count: m + 1)
self.pair_v = Array(repeating: NIL, count: n + 1)
// Initialize distance array
self.dist = Array(repeating: INF, count: m + 1)
}
/**
Adds a directed edge from vertex u (left partition) to vertex v (right partition).
- Parameters:
- u: Vertex index in the left partition (1 to m).
- v: Vertex index in the right partition (1 to n).
*/
func addEdge(_ u: Int, _ v: Int) {
// Ensure vertices are within the valid range
if 1 <= u && u <= self.m && 1 <= v && v <= self.n {
self.adj[u].append(v) // Add v to u's adjacency list
} else {
// Optionally print a warning for edges added outside the defined range
// print("Warning: Attempted to add edge (\(u), \(v)) outside graph bounds [1..\(self.m)], [1..\(self.n)]")
}
}
/**
Performs Breadth-First Search (BFS) to find layers in the graph.
It checks if there exists an augmenting path starting from a free vertex in U.
- Returns: True if an augmenting path might exist (dist[NIL] is finite),
False otherwise.
*/
func bfs() -> Bool {
var queue: [Int] = []
// Initialize distances for vertices in U
for u in 1...(self.m) {
if self.pair_u[u] == NIL {
// If u is a free vertex, its distance is 0, add to queue
self.dist[u] = 0
queue.append(u)
} else {
// Otherwise, set distance to infinity initially
self.dist[u] = INF
}
}
// Distance to the NIL node represents the length of the shortest augmenting path
self.dist[NIL] = INF
while !queue.isEmpty {
let u = queue.removeFirst() // Dequeue a vertex from U
// If the path through u can potentially lead to a shorter augmenting path
if self.dist[u] < self.dist[NIL] {
// Explore neighbors v of u in V
for v in self.adj[u] {
let matched_u = self.pair_v[v] // Get the vertex u' matched with v
// If the matched vertex u' hasn't been visited yet (its distance is INF)
if self.dist[matched_u] == INF {
// Set the distance of u' based on u
self.dist[matched_u] = self.dist[u] + 1
// Enqueue u' to explore further
queue.append(matched_u)
}
}
}
}
// If dist[NIL] is still INF, no augmenting path was found originating
// from the initial free vertices. Otherwise, augmenting paths might exist.
return self.dist[NIL] != INF
}
/**
Performs Depth-First Search (DFS) starting from vertex u in U
to find and augment along a shortest path identified by BFS.
- Parameter u: The current vertex in U being visited (or NIL).
- Returns: True if an augmenting path was found and used starting from u,
False otherwise.
*/
func dfs(_ u: Int) -> Bool {
if u != NIL {
// Explore neighbors v of u in V
for v in self.adj[u] {
let matched_u = self.pair_v[v] // Get the vertex u' matched with v
// Check if the edge (u, v) leads to a vertex u'
// such that the path u -> v -> u' is part of a shortest augmenting path
if self.dist[matched_u] == self.dist[u] + 1 {
// Recursively call DFS on u'
if self.dfs(matched_u) {
// If an augmenting path is found starting from u',
// update the matching: match v with u, and u with v
self.pair_v[v] = u
self.pair_u[u] = v
return true // Augmentation successful
}
}
}
// If no augmenting path was found starting from u through any neighbor v,
// mark u as visited in this DFS phase by setting its distance to INF
self.dist[u] = INF
return false // Augmentation failed for this path
}
// Base case: If u is NIL, it means we have reached the end of an alternating path
// originating from a free vertex in U and ending at a free vertex in V (represented by NIL).
return true
}
/**
Executes the Hopcroft-Karp algorithm to find the maximum matching.
- Returns: The size of the maximum matching found.
*/
func hopcroftKarpAlgorithm() -> Int {
// Initialize matching pairs to NIL (unmatched)
self.pair_u = Array(repeating: NIL, count: self.m + 1)
self.pair_v = Array(repeating: NIL, count: self.n + 1)
var matchingSize = 0 // Initialize the size of the matching
// Keep finding augmenting paths using BFS and DFS until no more exist
while self.bfs() {
// For every free vertex u in U
for u in 1...(self.m) {
// If u is free and an augmenting path starting from u is found via DFS
if self.pair_u[u] == NIL && self.dfs(u) {
// Increment the matching size
matchingSize += 1
}
}
}
return matchingSize
}
}
// --- Testing ---
func tests() {
print("Running tests...")
// Test Case 1 (Corrected from C++ version - using 1-based indexing)
// m=3, n=5, edges = [(1, 4)] - Expected matching size = 1
let g1 = HKGraph(3, 5)
g1.addEdge(1, 4)
let res1 = g1.hopcroftKarpAlgorithm()
let expected_res1 = 1
print("Test 1: Result=\(res1), Expected=\(expected_res1)")
assert(res1 == expected_res1, "Test 1 Failed: Expected \(expected_res1), got \(res1)")
// Test Case 2 (Corrected from C++ version - using 1-based indexing, assuming (5,0) meant (5,1) or similar valid edge)
// m=6, n=6, edges = [(1,4), (1,5), (5,1)]
// Expected matching size = 2 (e.g., (1,4), (5,1) or (1,5), (5,1))
// Note: Original C++ test had (0,1) and (5,0) which are problematic with 1-based index logic.
let g2 = HKGraph(6, 6)
// g3.addEdge(0,1) // Invalid vertex 0 in U
g2.addEdge(1, 4)
g2.addEdge(1, 5)
g2.addEdge(5, 1) // Assuming (5,0) meant a valid edge like (5,1)
// g2.addEdge(5, 0) // Invalid vertex 0 in V
let res2 = g2.hopcroftKarpAlgorithm()
let expected_res2 = 2
print("Test 2: Result=\(res2), Expected=\(expected_res2)")
assert(res2 == expected_res2, "Test 2 Failed: Expected \(expected_res2), got \(res2)")
// Test Case 3: Complete Bipartite Graph K_{3,3}
// m=3, n=3, all possible edges. Expected matching size = 3
let g3 = HKGraph(3, 3)
for i in 1...3 {
for j in 1...3 {
g3.addEdge(i, j)
}
}
let res3 = g3.hopcroftKarpAlgorithm()
let expected_res3 = 3
print("Test 3: Result=\(res3), Expected=\(expected_res3)")
assert(res3 == expected_res3, "Test 3 Failed: Expected \(expected_res3), got \(res3)")
// Test Case 4: No edges
// m=2, n=2, no edges. Expected matching size = 0
let g4 = HKGraph(2, 2)
let res4 = g4.hopcroftKarpAlgorithm()
let expected_res4 = 0
print("Test 4: Result=\(res4), Expected=\(expected_res4)")
assert(res4 == expected_res4, "Test 4 Failed: Expected \(expected_res4), got \(res4)")
print("All tests passed!")
}
// --- Main execution ---
func main() {
// Run self-tests first
tests()
print("\n--- Running main execution with hard-coded input ---")
// --- Hard-coded input data ---
// Example 1: Corresponds to Test Case 2
let hardcoded_v1 = 4 // Number of vertices in left partition (m)
let hardcoded_v2 = 4 // Number of vertices in right partition (n)
let hardcoded_edges = [
(1, 1),
(1, 3),
(2, 3),
(3, 4),
(4, 3),
(4, 2)
]
// Expected output for Example 1: 3
// Use the selected hardcoded data
let v1 = hardcoded_v1
let v2 = hardcoded_v2
let edges_data = hardcoded_edges
let e = edges_data.count // Number of edges is derived from the list
// Create the graph object
let g = HKGraph(v1, v2)
print("Hard-coded graph dimensions: m=\(v1), n=\(v2), edges=\(e)")
print("Adding hard-coded edges:")
// Add edges from the hard-coded list
for (u, v) in edges_data {
print(" Adding edge: (\(u), \(v))")
// Add edge only if vertices are within valid 1-based range
if 1 <= u && u <= v1 && 1 <= v && v <= v2 {
g.addEdge(u, v)
} else {
// This warning is important if hardcoded data might be invalid
print("Warning: Skipping invalid hard-coded edge (\(u), \(v)) - indices out of range [1..\(v1)] or [1..\(v2)]")
}
}
// Run the Hopcroft-Karp algorithm
let max_matching_size = g.hopcroftKarpAlgorithm()
// Print the result
print("\nMaximum matching size is \(max_matching_size)")
}
// Run the main function
main()
- Output:
Running tests... Test 1: Result=1, Expected=1 Test 2: Result=2, Expected=2 Test 3: Result=3, Expected=3 Test 4: Result=0, Expected=0 All tests passed! --- Running main execution with hard-coded input --- Hard-coded graph dimensions: m=4, n=4, edges=6 Adding hard-coded edges: Adding edge: (1, 1) Adding edge: (1, 3) Adding edge: (2, 3) Adding edge: (3, 4) Adding edge: (4, 3) Adding edge: (4, 2) Maximum matching size is 4
#!/usr/bin/env tclsh
# Representation of a bipartite graph
# Vertices in the left partition, U, are numbered from 1 to m,
# and vertices in the right partition, V, are numbered 1 to n.
namespace eval BipartiteGraph {
namespace export new add_edge hopcroft_karp_algorithm
}
proc BipartiteGraph::new {m n} {
set self [dict create]
dict set self m $m
dict set self n $n
dict set self adjacency_lists [dict create]
dict set self pair_u [dict create]
dict set self pair_v [dict create]
dict set self levels [dict create]
dict set self NIL 0
dict set self INFINITY 999999999
# Initialize adjacency lists
for {set u 1} {$u <= $m} {incr u} {
dict set self adjacency_lists $u [list]
}
# Initialize pairs
for {set u 1} {$u <= $m} {incr u} {
dict set self pair_u $u [dict get $self NIL]
}
for {set v 1} {$v <= $n} {incr v} {
dict set self pair_v $v [dict get $self NIL]
}
# Initialize levels
for {set u 1} {$u <= $m} {incr u} {
dict set self levels $u [dict get $self INFINITY]
}
return $self
}
proc BipartiteGraph::add_edge {self_ref u v} {
upvar $self_ref self
set m [dict get $self m]
set n [dict get $self n]
if {$u >= 1 && $u <= $m && $v >= 1 && $v <= $n} {
set adj_lists [dict get $self adjacency_lists]
set u_list [dict get $adj_lists $u]
lappend u_list $v
dict set adj_lists $u $u_list
dict set self adjacency_lists $adj_lists
} else {
error "Attempt to add an edge ($u, $v) which is out of bounds"
}
}
# Return the matching size of the bipartite graph
proc BipartiteGraph::hopcroft_karp_algorithm {self_ref} {
upvar $self_ref self
set m [dict get $self m]
set n [dict get $self n]
set NIL [dict get $self NIL]
set INFINITY [dict get $self INFINITY]
# Reset pairs
for {set u 1} {$u <= $m} {incr u} {
dict set self pair_u $u $NIL
}
for {set v 1} {$v <= $n} {incr v} {
dict set self pair_v $v $NIL
}
set matching_size 0
while {[breadth_first_search self]} {
for {set u 1} {$u <= $m} {incr u} {
set pair_u_dict [dict get $self pair_u]
if {[dict get $pair_u_dict $u] == $NIL && [depth_first_search self $u]} {
# vertex u is free and an augmenting path starting
# from u has been found by the depth first search
incr matching_size
}
}
}
return $matching_size
}
# Determines whether there exists an augmenting path starting from a free vertex in U.
# Return true if an augmenting path could exist, otherwise false.
proc BipartiteGraph::breadth_first_search {self_ref} {
upvar $self_ref self
set m [dict get $self m]
set n [dict get $self n]
set NIL [dict get $self NIL]
set INFINITY [dict get $self INFINITY]
set queue [list]
# Initialize 'levels' for the vertices in U
for {set u 1} {$u <= $m} {incr u} {
set pair_u_dict [dict get $self pair_u]
if {[dict get $pair_u_dict $u] == $NIL} {
# If u is a free vertex, its level is 0 and it is added to the queue
dict set self levels $u 0
lappend queue $u
} else {
# Otherwise, set 'levels' to infinity
dict set self levels $u $INFINITY
}
}
# The 'level' to the NIL node represents the length of the shortest augmenting path
dict set self levels $NIL $INFINITY
while {[llength $queue] > 0} {
set u [lindex $queue 0]
set queue [lrange $queue 1 end]
set levels_dict [dict get $self levels]
if {[dict get $levels_dict $u] < [dict get $levels_dict $NIL]} {
# The path through u could lead to a shorter augmenting path
set adj_lists [dict get $self adjacency_lists]
set u_list [dict get $adj_lists $u]
set pair_v_dict [dict get $self pair_v]
foreach v $u_list {
# Explore the neighbours v of u in V
set matched_u [dict get $pair_v_dict $v]
set levels_dict [dict get $self levels]
if {[dict get $levels_dict $matched_u] == $INFINITY} {
# The matched vertex has not been visited yet
dict set self levels $matched_u [expr {[dict get $levels_dict $u] + 1}]
lappend queue $matched_u ;# Enqueue the matched vertex to explore it further
}
}
}
}
# An augmenting path from the initial free vertices was found if levels[NIL] is not INFINITY
set levels_dict [dict get $self levels]
return [expr {[dict get $levels_dict $NIL] != $INFINITY}]
}
# Determine whether the shortest path from vertex u in U found by breadth_first_search() can be augmented.
# Return true if an augmenting path was found starting from u, otherwise false.
proc BipartiteGraph::depth_first_search {self_ref u} {
upvar $self_ref self
set NIL [dict get $self NIL]
set INFINITY [dict get $self INFINITY]
if {$u != $NIL} {
set adj_lists [dict get $self adjacency_lists]
set u_list [dict get $adj_lists $u]
set pair_v_dict [dict get $self pair_v]
set levels_dict [dict get $self levels]
foreach v $u_list {
# Explore neighbours v of u in V
set matched_u [dict get $pair_v_dict $v]
# Check whether the edge (u, v) leads to a vertex matched_u
# such that the path u -> v -> matched_u is part of a shortest augmenting path
if {[dict get $levels_dict $matched_u] == [expr {[dict get $levels_dict $u] + 1}]} {
if {[depth_first_search self $matched_u]} {
# An augmenting path is found starting from 'matched_u'
dict set self pair_v $v $u ;# Match v with u,
dict set self pair_u $u $v ;# and u with v
return 1
}
}
}
# No augmenting path was found starting from vertex u through any of its neighbours v,
# so remove u from the depth first search phase of the algorithm
dict set self levels $u $INFINITY
return 0
}
return 1
}
proc test_value {test_number m n edges expected_result} {
set graph [BipartiteGraph::new $m $n]
foreach edge $edges {
set from_val [dict get $edge from]
set to_val [dict get $edge to]
BipartiteGraph::add_edge graph $from_val $to_val
}
set result [BipartiteGraph::hopcroft_karp_algorithm graph]
puts "Test $test_number: Result = $result, Expected = $expected_result"
if {$result == $expected_result} {
return 1
}
puts "Test $test_number failed."
return 0
}
# Main execution
puts "Running tests:"
set success_count 0
# Test Case 1
set edges1 [list [dict create from 1 to 4]]
incr success_count [test_value 1 3 5 $edges1 1]
# Test Case 2
set edges2 [list \
[dict create from 1 to 4] \
[dict create from 1 to 5] \
[dict create from 5 to 1] \
]
incr success_count [test_value 2 6 6 $edges2 2]
# Test Case 3: Complete Bipartite Graph K(3, 3)
set edges3 [list]
for {set i 1} {$i <= 3} {incr i} {
for {set j 1} {$j <= 3} {incr j} {
lappend edges3 [dict create from $i to $j]
}
}
incr success_count [test_value 3 3 3 $edges3 3]
# Test Case 4: No edges
incr success_count [test_value 4 2 2 [list] 0]
# Test Case 5
set edges5 [list \
[dict create from 1 to 1] \
[dict create from 1 to 3] \
[dict create from 2 to 3] \
[dict create from 3 to 4] \
[dict create from 4 to 3] \
[dict create from 4 to 2] \
]
incr success_count [test_value 5 4 4 $edges5 4]
if {$success_count == 5} {
puts "All tests passed."
}
- Output:
Running tests: Test 1: Result = 1, Expected = 1 Test 2: Result = 2, Expected = 2 Test 3: Result = 3, Expected = 3 Test 4: Result = 0, Expected = 0 Test 5: Result = 4, Expected = 4 All tests passed.
import "./queue" for Deque
// Setting a large value for infinity.
var INF = Num.maxSafeInteger
// Using 0 as the NIL code
var NIL = 0
/* Implementation of the Hopcroft-Karp algorithm for finding maximum matching
in a bipartite graph.
Assumes vertices in the left partition (U) are numbered 1 to m,
and vertices in the right partition (V) are numbered 1 to n.
The NIL node is represented by 0. */
class HKGraph {
// Constructs a new HKGraph object with m vertices in the left partition (U)
// and n vertices in the right partition (V).
construct new(m, n) {
_m = m
_n = n
// Adjacency list: _adj[u] contains list of neighbors of u in V
// Initialize with empty lists for vertices 1 to m.
_adj = List.filled(m+1, null)
for (i in 1..m) _adj[i] = []
// Matching pairs:
// pairU[u] stores the vertex v in V matched with u in U (or NIL if unmatched).
_pairU = List.filled(m+1, NIL)
// pairV[v] stores the vertex u in U matched with v in V (or NIL if unmatched).
_pairV = List.filled(n+1, NIL)
// _dist[u] stores the distance (level) of vertex u in U during BFS.
// Initialized within the hopcroftKarp or bfs methods.
_dist = List.filled(m+1, INF)
}
// Adds a directed edge from vertex u (left partition) to vertex v (right partition).
addEdge(u, v) {
// Ensure vertices are within the valid range.
if (1 <= u && u <= _m && 1 <= v && v <= _n) {
_adj[u].add(v) // add v to u's adjacency list
} else {
System.print("Warning: Attempted to add edge (%(u), %(v))" +
" outside graph bounds [1..%(m)], [1..%(n)]")
}
}
// Performs Breadth-First Search (BFS) to find layers in the graph.
// It checks if there exists an augmenting path starting from a free vertex in U.
// Returns true if an augmenting path might exist (_dist[NIL] is finite),
// false otherwise.
bfs() {
var queue = Deque.new() // use deque for efficient queue operations
// Initialize distances for vertices in U.
for (u in 1.._m) {
if (_pairU[u] == NIL) {
// If u is a free vertex, its distance is 0, add to queue.
_dist[u] = 0
queue.pushBack(u)
} else {
// Otherwise, set distance to infinity initially.
_dist[u] = INF
}
}
// Distance to the NIL node represents the length of the shortest augmenting path.
_dist[NIL] = INF
while (!queue.isEmpty) {
var u = queue.popFront() // dequeue a vertex from U
// If the path through u can potentially lead to a shorter augmenting path:
if (_dist[u] < _dist[NIL]) {
// Explore neighbors v of u in V.
for (v in _adj[u]) {
var matchedU = _pairV[v] // get the vertex u' matched with v
// If the matched vertex u' hasn't been visited yet (its distance is INF):
if (_dist[matchedU] == INF) {
// Set the distance of u' based on u.
_dist[matchedU] = _dist[u] + 1
// Enqueue u' to explore further.
queue.pushBack(matchedU)
}
}
}
}
// If _dist[NIL] is still INF, no augmenting path was found originating
// from the initial free vertices. Otherwise, augmenting paths might exist.
return _dist[NIL] != INF
}
// Performs Depth-First Search (DFS) starting from vertex u in U
// to find and augment along a shortest path identified by BFS.
// Returns true if an augmenting path was found and used starting from u,
// false otherwise.
dfs(u) {
if (u != NIL) {
// Explore neighbors v of u in V.
for (v in _adj[u]) {
var matchedU = _pairV[v] // get the vertex u' matched with v
// Check if the edge (u, v) leads to a vertex u'
// such that the path u -> v -> u' is part of a shortest augmenting path.
if (_dist[matchedU] == _dist[u] + 1) {
// Recursively call DFS on u'.
if (dfs(matchedU)) {
// If an augmenting path is found starting from u',
// update the matching: match v with u, and u with v.
_pairV[v] = u
_pairU[u] = v
return true // augmentation successful
}
}
}
// If no augmenting path was found starting from u through any neighbor v,
// mark u as visited in this DFS phase by setting its distance to INF.
_dist[u] = INF
return false // augmentation failed for this path
}
// Base case: If u is NIL, it means we have reached the end of an alternating path
// originating from a free vertex in U and ending at a free vertex in V (represented by NIL).
return true
}
// Executes the Hopcroft-Karp algorithm to find the maximum matching and returns its size.
hopcroftKarp() {
// Initialize matching pairs to NIL (unmatched).
_pairU = List.filled(_m+1, NIL)
_pairV = List.filled(_n+1, NIL)
var matchingSize = 0 // initialize the size of the matching
// Keep finding augmenting paths using BFS and DFS until no more exist.
while (bfs()) {
// For every free vertex u in U:
for (u in 1.._m) {
// If u is free and an augmenting path starting from u is found via DFS:
if (_pairU[u] == NIL && dfs(u)) {
// Increment the matching size.
matchingSize = matchingSize + 1
}
}
}
return matchingSize
}
}
// --- Testing ---
// Runs test cases for the Hopcroft-Karp implementation.
var tests = Fn.new {
System.print("Running tests...")
var success = 0
// Test Case 1
// m=3, n=5, edges = [(1, 4)] - Expected matching size = 1.
var g1 = HKGraph.new(3, 5)
g1.addEdge(1, 4)
var res1 = g1.hopcroftKarp()
var expectedRes1 = 1
System.print("Test 1: Result = %(res1), Expected = %(expectedRes1)")
if (res1 != expectedRes1) System.print("So test 1 Failed.") else success = success + 1
// Test Case 2
// m=6, n=6, edges = [(1,4), (1,5), (5,1)]
// Expected matching size = 2 (e.g., (1,4), (5,1) or (1,5), (5,1)).
var g2 = HKGraph.new(6, 6)
g2.addEdge(1, 4)
g2.addEdge(1, 5)
g2.addEdge(5, 1)
var res2 = g2.hopcroftKarp()
var expectedRes2 = 2
System.print("Test 2: Result = %(res2), Expected = %(expectedRes2)")
if (res2 != expectedRes2) System.print("So test 2 failed") else success = success + 1
// Test Case 3: Complete Bipartite Graph K_{3,3}
// m=3, n=3, all possible edges. Expected matching size = 3.
var g3 = HKGraph.new(3, 3)
for (i in 1..3) {
for (j in 1..3) g3.addEdge(i, j)
}
var res3 = g3.hopcroftKarp()
var expectedRes3 = 3
System.print("Test 3: Result = %(res3), Expected = %(expectedRes3)")
if (res3 != expectedRes3) System.print("So test 3 failed") else success = success + 1
// Test Case 4: No edges
// m=2, n=2, no edges. Expected matching size = 0.
var g4 = HKGraph.new(2, 2)
var res4 = g4.hopcroftKarp()
var expectedRes4 = 0
System.print("Test 4: Result = %(res4), Expected = %(expectedRes4)")
if (res4 != expectedRes4) System.print("So test 4 Failed") else success = success + 1
if (success == 4) System.print("All tests passed!")
}
// --- Main execution ---
// Run self-tests first.
tests.call()
System.print("\n--- Running main execution with hard-coded input ---")
// --- Hard-coded input data ---
// Example 1: Corresponds to Test Case 2.
var hardcodedV1 = 4 // mumber of vertices in left partition (m)
var hardcodedV2 = 4 // number of vertices in right partition (n)
var hardcodedEdges = [ [1, 1], [1, 3], [2, 3], [3, 4], [4, 3], [4, 2] ]
// Expected output for Example 1: 3.
// Use the selected hardcoded data.
var v1 = hardcodedV1
var v2 = hardcodedV2
var edgesData = hardcodedEdges
var e = edgesData.count // number of edges is derived from the list
// Create the graph object.
var g = HKGraph.new(v1, v2)
System.print("Hard-coded graph dimensions: m=%(v1), n=%(v2), edges=%(e)")
System.print("Adding hard-coded edges:")
// Add edges from the hard-coded list.
for (edge in edgesData) {
var u = edge[0]
var v = edge[1]
System.print(" Adding edge: (%(u), %(v))")
// Add edge only if vertices are within valid 1-based range.
if (1 <= u && u <= v1 && 1 <= v && v <= v2) {
g.addEdge(u, v)
} else {
// This warning is important if hardcoded data might be invalid.
System.print("Warning: Skipping invalid hard-coded edge (%(u), %(v)) - " +
"indices out of range [1..%(v1)] or [1..%(v2)]")
}
}
// Run the Hopcroft-Karp algorithm.
var maxMatchingSize = g.hopcroftKarp()
// Print the result.
System.print("\nMaximum matching size is %(maxMatchingSize)")
- Output:
Running tests... Test 1: Result = 1, Expected = 1 Test 2: Result = 2, Expected = 2 Test 3: Result = 3, Expected = 3 Test 4: Result = 0, Expected = 0 All tests passed! --- Running main execution with hard-coded input --- Hard-coded graph dimensions: m=4, n=4, edges=6 Adding hard-coded edges: Adding edge: (1, 1) Adding edge: (1, 3) Adding edge: (2, 3) Adding edge: (3, 4) Adding edge: (4, 3) Adding edge: (4, 2) Maximum matching size is 4
const std = @import("std");
/// Representation of a bipartite graph.
/// Vertices in the left partition, U, are numbered from 1 to m,
/// and vertices in the right partition, V, are numbered 1 to n.
const BipartiteGraph = struct {
adjacency_lists: std.ArrayList(std.ArrayList(u32)),
pair_u: std.ArrayList(u32),
pair_v: std.ArrayList(u32),
levels: std.ArrayList(u32),
m: u32,
n: u32,
allocator: std.mem.Allocator,
const NIL: u32 = 0;
const INFINITY: u32 = std.math.maxInt(u32);
pub fn init(allocator: std.mem.Allocator, m: u32, n: u32) !BipartiteGraph {
var adjacency_lists = std.ArrayList(std.ArrayList(u32)).init(allocator);
try adjacency_lists.resize(m + 1);
for (0..m + 1) |i| {
adjacency_lists.items[i] = std.ArrayList(u32).init(allocator);
}
var pair_u = try std.ArrayList(u32).initCapacity(allocator, m + 1);
try pair_u.appendNTimes(NIL, m + 1);
var pair_v = try std.ArrayList(u32).initCapacity(allocator, n + 1);
try pair_v.appendNTimes(NIL, n + 1);
var levels = try std.ArrayList(u32).initCapacity(allocator, m + 1);
try levels.appendNTimes(INFINITY, m + 1);
return BipartiteGraph{
.adjacency_lists = adjacency_lists,
.pair_u = pair_u,
.pair_v = pair_v,
.levels = levels,
.m = m,
.n = n,
.allocator = allocator,
};
}
pub fn deinit(self: *BipartiteGraph) void {
for (0..self.adjacency_lists.items.len) |i| {
self.adjacency_lists.items[i].deinit();
}
self.adjacency_lists.deinit();
self.pair_u.deinit();
self.pair_v.deinit();
self.levels.deinit();
}
pub fn add_edge(self: *BipartiteGraph, u: u32, v: u32) !void {
if (1 <= u and u <= self.m and 1 <= v and v <= self.n) {
try self.adjacency_lists.items[u].append(v);
} else {
return error.InvalidEdge;
}
}
/// Return the matching size of the bipartite graph.
pub fn hopcroftKarp_algorithm(self: *BipartiteGraph) !u32 {
var matching_size: u32 = 0;
// Reset the matching
for (0..self.pair_u.items.len) |i| {
self.pair_u.items[i] = NIL;
}
for (0..self.pair_v.items.len) |i| {
self.pair_v.items[i] = NIL;
}
while (try self.breadth_first_search()) {
var u: u32 = 1;
while (u <= self.m) : (u += 1) {
if (self.pair_u.items[u] == NIL and try self.depth_first_search(u)) {
matching_size += 1;
}
}
}
return matching_size;
}
/// Determines whether there exists an augmenting path starting from a free vertex in U.
///
/// Return true if an augmenting path could exist, otherwise false.
fn breadth_first_search(self: *BipartiteGraph) !bool {
var queue = std.fifo.LinearFifo(u32, .Dynamic).init(self.allocator);
defer queue.deinit();
// Initialize 'levels' for the vertices in U
var u: u32 = 1;
while (u <= self.m) : (u += 1) {
if (self.pair_u.items[u] == NIL) {
// If u is a free vertex, its level is 0 and it is added to the queue
self.levels.items[u] = 0;
try queue.writeItem(u);
} else {
// Otherwise, set 'levels' to infinity
self.levels.items[u] = INFINITY;
}
}
// The 'level' to the NIL node represents the length of the shortest augmenting path
self.levels.items[NIL] = INFINITY;
while (queue.readItem()) |my_u| {
if (self.levels.items[my_u] < self.levels.items[NIL]) {
// The path through u could lead to a shorter augmenting path
for (self.adjacency_lists.items[my_u].items) |v| {
const matched_u = self.pair_v.items[v];
if (self.levels.items[matched_u] == INFINITY) {
// The matched vertex has not been visited yet
self.levels.items[matched_u] = self.levels.items[my_u] + 1;
try queue.writeItem(matched_u);
}
}
}
}
// An augmenting path from the initial free vertices was found if levels[NIL] is not INFINITY
return self.levels.items[NIL] != INFINITY;
}
/// Determine whether the shortest path from vertex u in U found by breadth_first_search() can be augmented.
///
/// Return true if an augmenting path was found starting from u, otherwise false.
fn depth_first_search(self: *BipartiteGraph, u: u32) !bool {
if (u != NIL) {
// Explore neighbours v of u in V
for (self.adjacency_lists.items[u].items) |v| {
const matched_u = self.pair_v.items[v];
// Check whether the edge (u, v) leads to a vertex matched_u
// such that the path u -> v -> matched_u is part of a shortest augmenting path
if (self.levels.items[matched_u] == self.levels.items[u] + 1) {
if (try self.depth_first_search(matched_u)) {
// An augmenting path is found starting from 'matched_u'
self.pair_v.items[v] = u; // Match v with u
self.pair_u.items[u] = v; // and u with v
return true;
}
}
}
// No augmenting path was found starting from vertex u through any of its neighbours v,
// so remove u from the depth first search phase of the algorithm
self.levels.items[u] = INFINITY;
return false;
}
return true;
}
};
const Edge = struct {
from: u32,
to: u32,
};
fn test_value(allocator: std.mem.Allocator, test_number: u32, m: u32, n: u32, edges: []const Edge, expected_result: u32) !u32 {
var graph = try BipartiteGraph.init(allocator, m, n);
defer graph.deinit();
for (edges) |edge| {
try graph.add_edge(edge.from, edge.to);
}
const result = try graph.hopcroftKarp_algorithm();
const stdout = std.io.getStdOut().writer();
try stdout.print("Test {d}: Result = {d}, Expected = {d}\n", .{ test_number, result, expected_result });
if (result == expected_result) {
return 1;
}
try stdout.print("Test {d} failed.\n", .{test_number});
return 0;
}
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
const stdout = std.io.getStdOut().writer();
try stdout.print("Running tests:\n", .{});
var success_count: u32 = 0;
// Test Case 1
{
const edges = [_]Edge{.{ .from = 1, .to = 4 }};
success_count += try test_value(allocator, 1, 3, 5, &edges, 1);
}
// Test Case 2
{
const edges = [_]Edge{
.{ .from = 1, .to = 4 },
.{ .from = 1, .to = 5 },
.{ .from = 5, .to = 1 },
};
success_count += try test_value(allocator, 2, 6, 6, &edges, 2);
}
// Test Case 3: Complete Bipartite Graph K(3, 3)
{
var edges = std.ArrayList(Edge).init(allocator);
defer edges.deinit();
var i: u32 = 1;
while (i <= 3) : (i += 1) {
var j: u32 = 1;
while (j <= 3) : (j += 1) {
try edges.append(.{ .from = i, .to = j });
}
}
success_count += try test_value(allocator, 3, 3, 3, edges.items, 3);
}
// Test Case 4: No edges
{
const edges = [_]Edge{};
success_count += try test_value(allocator, 4, 2, 2, &edges, 0);
}
// Test Case 5
{
const edges = [_]Edge{
.{ .from = 1, .to = 1 },
.{ .from = 1, .to = 3 },
.{ .from = 2, .to = 3 },
.{ .from = 3, .to = 4 },
.{ .from = 4, .to = 3 },
.{ .from = 4, .to = 2 },
};
success_count += try test_value(allocator, 5, 4, 4, &edges, 4);
}
if (success_count == 5) {
try stdout.print("All tests passed.\n", .{});
}
}
- Output:
Running tests: Test 1: Result = 1, Expected = 1 Test 2: Result = 2, Expected = 2 Test 3: Result = 3, Expected = 3 Test 4: Result = 0, Expected = 0 Test 5: Result = 4, Expected = 4 All tests passed.