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

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 -pedantic -o output maximum-bipartite-matching.c
*/
#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; // not used but needed for generic code
typedef struct { int u, v; cost c; } Edge;
typedef struct { int v; cost c; } *Adja;
Adja* load_adja_list (const char* str); // returns adjacency list
char* print_edge_list (char* out, const Edge* edge); // returns 'out'
Edge* maximum_matching_unweighted (const Adja* adja, bool skipPart1);
int main (int argc, char** argv)
{
if(argc!=2) printf("Usage: <program> <graph_data_file>\n");
else
{
Array file={0};
file = file_to_array(argv[1], file);
if(file.size<=0)
printf("Error: failed to open file '%s'\n", argv[1]);
else
{
Adja* adjaList = load_adja_list(file.data);
Edge* result = maximum_matching_unweighted(adjaList, true);
char str[10000];
puts(print_edge_list(str, result));
free(adjaList);
free(result);
}
}
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 ); }
/* return the result graph as an unweighted undirected edge_list */
Edge* maximum_matching_unweighted (const Adja* adja, bool skipPart1)
{
if(!adja) return NULL;
int V = AdjaV(adja); // get V = number of vertexes
int i, m, u, v;
const Adja* graph;
const Adja* prev = AdjaPrev(adja);
// adja = adjacency list of source-to-sink vertexes
// prev = adjacency list of sink-from-source vertexes
m = (1+V)*(sizeof(int)+sizeof(mmug)+sizeof(void*));
int* match = (int*)malloc(m); // m = total memory needed
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 with all vertexes
Heap _heap = { hdata, 0, V, true, NULL, mmug_heap_node_compare };
Heap *heap = &_heap;
for(u=1; u<=V; u++)
{
// get m = total number of adjacent vertexes
m = adja[u][0].v;
if(adja!=prev) // if a directed graph
m += prev[u][0].v;
count[u].c = m;
if(m) heap_push(heap, &count[u].i);
}
void* heapNode;
while(heap_pop(heap, &heapNode)) // while heap is not empty
{
// get u = vertex with minimum free adjacent vertexes
u = (mmug*)heapNode - count;
if(count[u].c==0) continue; // if no free adjacent vertex then skip
count[u].c=0; // else mark u as removed from heap
int t=0;
graph = adja; // start with 'adja' list
while(true)
{
m = graph[u][0].v; // get number of adjacent vertexes
for(i=1; i<=m; i++) // for every adjacent vertex
{
v = graph[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 of 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 from 'adja' to 'prev' 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' list
while(true)
{
m = graph[u][0].v; // get number of adjacent vertexes
for(i=1; i<=m; i++) // for every adjacent vertex
{
v = graph[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 from 'adja' to 'prev' list
}
}
}
//****************************************************************
//*** 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
for(u=1; u<=V; u++) // initialisations, push all unmatched vertexes to queue
{
if(match[u]) // if u is a matched vertex
{ claim[u] = vfree[u] = 0; }
else { claim[u] = vfree[u] = queue[end++] = u; }
}
E = (V-end)/2; // count of matched vertex pairs
//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' list
while(true)
{
m = graph[u][0].v; // get number of adjacent vertexes
for(i=1; i<=m; i++) // for every adjacent vertex
{
v = graph[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 from 'adja' to 'prev' list
}
}
if(E!=-1) break; // no re-matching performed means solution is optimal
}
// allocate memory for the result graph
Edge *edge = (Edge*) 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