In the field of Graph Theory this challenge is modeled as the problem of finding a maximum bipartite matching. The fact that a worker

This document presents a new and very efficient algorithm to solve the maximum matching problem for an unweighted bipartite or non-bipartite graph, in O(E log V) time where E and V are respectively the number of edges and vertexes of the graph. It consists of two main parts: a simple vertex get-and-match traversal, followed by an improved backtracking-search for any residual unmatched vertexes.

- The common method
- The backtracking search
- The basic idea of the algorithm
- Steps for 1st part of algorithm
- Steps for 2nd part of algorithm
- Algorithm implementation
- Links
- See also

Difficulty arises when the next-taken vertex has no free adjacent vertex, in which case a

A vertex

When

The search starts with an unmatched

A minimum-heap data structure is used to get hold of this vertex of minimum count of free adjacent vertexes. A binary heap provides O(log V)-time push, pop, remove and update operations. There are O(E) of these, giving a total of O(E log V) execution time.

The 1st part of the algorithm is often enough to solve the problem optimally (actually the condition for which it fails remains unknown). But when it fails an improved backtracking-search is performed to match residual unmatched vertexes - this is the 2nd part of the algorithm.

The backtracking-search is improved in that it starts with

The 2nd part of the algorithm takes O(E) time. It is repeated until no free vertex is found. If it is executed a constant number of times then the overall time complexity of the algorithm is O(E log V) + O(E) = O(E log V). There is

**Initialise**the heap with all vertexes, based on their count of free adjacent vertexes. Those with no adjacent vertex can be skipped.- If heap is empty then quit. Otherwise
**pop**a vertex*u*, referred to as the*next-taken*vertex. It must have the minimum count of free adjacent vertexes. If this count is 0 then repeat this step 2. Otherwise go to next step. - Get
*v*, the one of the free adjacent vertexes of*u*that has the smallest count of free adjacent vertexes, and**remove**it from the heap. Match the two vertexes*u*and*v*to each other, then go to next step.

- For each of
*u*and*v*, go through its adjacent vertexes still inside the heap, and tell each of them that one adjacent vertex has been monopolised. That is, decrement their count of free adjacent vertexes, then**update**their position in the heap. Now go to step 2.

... to be updated ...

Consider donating at http://rhyscitlema.com/donate to encourage improvement!

```
/*
To compile with GCC, execute:
gcc -Wall -std=c99 -pedantic -o match maximum-bipartite-matching.c
To run, execute: ./match graph.txt
*/
#include <stdio.h>
#include <string.h>
#include <stddef.h>
#include <stdbool.h>
#include <assert.h>
#include <malloc.h>
typedef struct { char* data; long size; } Array;
Array file_to_array (const char* filename, Array old);
typedef long cost; // must match with load_edge_list()
typedef struct { int u, v; cost c; } Edge, *EdgeP;
typedef struct { int v; cost c; } Adge, *Adja, **AdjaP;
typedef const Edge* const_EdgeP;
typedef const Adja* const_AdjaP;
AdjaP load_adja_list (const char* str); // parses and returns adjacency list
char* print_edge_list (char* out, const_EdgeP edge); // returns end of string
EdgeP maximum_matching_unweighted (const_AdjaP adja, bool skipPart1);
int main (int argc, char** argv)
{
if(argc!=2)
printf("Usage: <program> graph.txt\n");
else
{
Array content = {0};
content = file_to_array(argv[1], content);
if(content.size<=0)
printf("Error: failed to open file '%s'.\n", argv[1]);
else
{
AdjaP adjaList = load_adja_list(content.data);
EdgeP edgeList = maximum_matching_unweighted(adjaList, true);
char str[10000];
print_edge_list(str, edgeList);
puts(str);
free(adjaList);
free(edgeList);
}
free(content.data);
}
return 0;
}
/* ... rest of source code ... */
```

Download the complete C source code

Below is the portion of the source code that implements the algorithm.

```
typedef struct {
int i; // the free-memory needed by heap.h
int c; // count of free adjacent vertexes
// i must be declared first so to have:
// vertex = (mmug*)heap_node - mmug_array;
} mmug;
/* compare count of free adjacent vertexes */
static int mmug_heap_node_compare (const void* a, const void* b, const void* arg)
{ return ( ((const mmug*)a)->c - ((const mmug*)b)->c ); }
/* See http://rhyscitlema.com/algorithms/maximum-bipartite-matching */
EdgeP maximum_matching_unweighted (const_AdjaP adja, bool skipPart1)
{
if(!adja) return NULL;
int i, m, u, v;
int V = AdjaV(adja); // get V = number of vertexes
const_AdjaP graph, prev = AdjaPrev(adja);
// adja = adjacency list of source-to-sink vertexes
// prev = adjacency list of sink-from-source vertexes
// if adja==prev then graph is an undirected graph
// get m = total memory needed
m = (1+V)*(sizeof(int)+sizeof(mmug)+sizeof(void*));
int* match = (int*)malloc(m);
mmug* count = (mmug*)(match+1+V);
void** hdata = (void**)(count+1+V);
if(match==NULL) return NULL; // if failed to allocate memory
for(u=1; u<=V; u++) match[u]=0; // else initialise main array
//*****************************************************************
//*** Part 1 of algorithm : is often enough to solve optimally! ***
//*****************************************************************
if(!skipPart1) {
// initialise the heap data structure
Heap _heap = { hdata, 0, V, true, NULL, mmug_heap_node_compare };
Heap *heap = &_heap;
// initialise the heap with all vertexes
for(u=1; u<=V; u++)
{
// get m = total number of adjacent vertexes
m = AdjaU(adja,u)[0].v;
if(adja!=prev) // if a directed graph
m += AdjaU(prev,u)[0].v;
count[u].c = m;
if(m) // if at least one adjacent vertex
heap_push(heap, &count[u].i);
}
while(true)
{
void* hnode = heap_pop(heap);
if(hnode==NULL) break; // if heap is empty then quit
// get u = vertex with minimum count of free adjacent vertexes
u = (mmug*)hnode - count;
if(count[u].c==0) continue; // if no free adjacent vertex then skip,
count[u].c=0; // else mark u as removed from the heap.
int t=0;
graph = adja; // start with 'adja' (source-to-sink) list
while(true)
{
Adja U = AdjaU(graph,u);
m = U[0].v; // get number of adjacent vertexes
for(i=1; i<=m; i++) // for every adjacent vertex
{
v = U[i].v; // get adjacent vertex
if(count[v].c>0) // if is inside heap
{
count[v].c--; // decrement count of free adjacent vertexes
heap_update(heap, &count[v].i); // update position in heap
// get free vertex with minimum count of free adjacent vertexes
if(t==0 || count[t].c > count[v].c) t=v;
}
}
if(graph==prev) break;
else graph = prev; // switch to 'prev' (sink-from-source) list
}
v=t; // get v = new free vertex
match[u] = v; // match free vertex
match[v] = u;
count[v].c = 0; // remove v from heap
heap_remove(heap, &count[v].i);
// now tell all adjacent to v that v is monopolised.
u=v; // set u=v so to use exact same code as before!
graph = adja; // start with 'adja' (source-to-sink) list
while(true)
{
Adja U = AdjaU(graph,u);
m = U[0].v; // get number of adjacent vertexes
for(i=1; i<=m; i++) // for every adjacent vertex
{
v = U[i].v; // get adjacent vertex
if(count[v].c>0) // if is inside heap
{
count[v].c--; // decrement count of free adjacent vertexes
heap_update(heap, &count[v].i); // update position in heap
}
}
if(graph==prev) break;
else graph = prev; // switch to 'prev' (sink-from-source) list
}
}
} // end of if(!skipPart1)
//****************************************************************
//*** Part 2 of algorithm : may be faster when executed alone! ***
//****************************************************************
int E; // number of edges of the result graph
while(true)
{
int beg=0, end=0;
int* queue = match+(1+V)*1; // queue used by the breadth-first search.
int* claim = match+(1+V)*2; // claim[v] is the claimer of the claimed v.
int* vfree = match+(1+V)*3; // vfree[v] is the free vertex to start claiming
// initialisations, push all unmatched vertexes to queue
for(u=1; u<=V; u++)
{
if(match[u]) // if u is a matched vertex
{ claim[u] = vfree[u] = 0; }
else { claim[u] = vfree[u] = queue[end++] = u; }
}
// get E = count of matched vertex pairs
E = (V-end)/2;
//printf("-------------------------------------- E=%d\n", E);
for( ; beg!=end; beg++) // do the queue-based backtracking-search
{
u = queue[beg];
v = vfree[u]; // get v = free vertex which u is derived from
assert(v>0);
if(match[v]) continue; // check whether this v is still unmatched
graph = adja; // start with 'adja' (source-to-sink) list
while(true)
{
Adja U = AdjaU(graph,u);
m = U[0].v; // get number of adjacent vertexes
for(i=1; i<=m; i++) // for every adjacent vertex
{
v = U[i].v; // get adjacent vertex
int t = vfree[v]; // get t = free vertex which v is derived from
// check whether a new re-matching has been uncovered
if(t && !match[t] && t != vfree[u])
{
claim[v] = u; // ensure v is never claimed again
int tv = match[v]; // prepare for 2nd re-matching
while(true)
{
claim[u] = u; // ensure u is never claimed again
t = match[u]; // prepare for next iteration
match[u] = v;
match[v] = u; // uncover the augmenting path
if(t==0){
if(tv==0) break; // if no further re-matching
t=tv; tv=0; // prevent any further re-matching
}
v = t; // get v = the next claimed vertex
u = claim[t]; // get u = the claimer to this v
}
E=-1; // notify that a re-matching process was performed
break;
}
if(!claim[v]) // if not yet claimed
{
claim[v] = u; // Mark u as claiming v
t = match[v]; // Get who monopolises v
vfree[t] = vfree[u];
queue[end++] = t; // Push it to queue
}
}
if(i<=m) break; // if re-matching was performed then break
if(graph==prev) break;
else graph = prev; // switch to 'prev' (sink-from-source) list
}
}
if(E!=-1) break; // no re-matching performed means solution is optimal
}
// allocate memory for the result graph
EdgeP edge = (EdgeP) malloc ((1+E)*sizeof(Edge));
// build the edge-list of the result graph
for(E=0, u=1; u<=V; u++)
{
v = match[u];
if(v<u) continue; // avoid repetitions
++E;
edge[E].u = u;
edge[E].v = v;
edge[E].c = 1; // set weight to = 1
}
edge[0].u = V;
edge[0].v = E;
edge[0].c = 0; // mark as undirected
// free allocated memory
free(match);
return edge;
}
```

- https://en.wikipedia.org/wiki/Matching_(graph_theory)
- https://en.wikipedia.org/wiki/Bipartite_graph
- https://en.wikipedia.org/wiki/Time_complexity
- https://en.wikipedia.org/wiki/Hopcroftâ€“Karp_algorithm
- https://en.wikipedia.org/wiki/Binary_heap
- https://en.wikipedia.org/wiki/Breadth-first_search

- Math expression parsing algorithm
- Convert sorted list to complete BST
- Generate nth palindromic number