mat.c

   1 /*
   2  * Finding the maximum matching in the given bipartite graph using
   3  * Hopcroft-Karp algorithm.
   4  */
   5
   6 #include "rangi.h"
   7
   8 #define VNIL            (MNODES - 1)    /* the special null vertex */
   9 #define INF             1000000
  10
  11 static int bfs(int **adj, int *pair, int *pair2, int *dist, int n1)
  12 {
  13         int q[MNODES];
  14         int n = 0;
  15         int i;
  16         for (i = 0; i < n1; i++) {
  17                 if (adj[i][0] >= 0 && pair[i] == VNIL) {
  18                         dist[i] = 0;
  19                         q[n++] = i;
  20                 } else {
  21                         dist[i] = INF;
  22                 }
  23         }
  24         dist[VNIL] = INF;
  25         while (n) {
  26                 int v = q[--n];
  27                 for (i = 0; adj[v][i] >= 0; i++) {
  28                         int u = adj[v][i];
  29                         if (dist[pair2[u]] == INF) {
  30                                 dist[pair2[u]] = dist[v] + 1;
  31                                 q[n++] = pair2[u];
  32                         }
  33                 }
  34         }
  35         return dist[VNIL] != INF;
  36 }
  37
  38 static int dfs(int **adj, int *pair, int *pair2, int *dist, int v)
  39 {
  40         int i;
  41         if (v == VNIL)
  42                 return 1;
  43         for (i = 0; adj[v][i] >= 0; i++) {
  44                 int u = adj[v][i];
  45                 if (dist[pair2[u]] == dist[v] + 1) {
  46                         if (dfs(adj, pair, pair2, dist, pair2[u])) {
  47                                 pair2[u] = v;
  48                                 pair[v] = u;
  49                                 return 1;
  50                         }
  51                 }
  52         }
  53         dist[v] = INF;
  54         return 0;
  55 }
  56
  57 /*
  58  * Find the maximum matching in the given bipartite graph.  adj
  59  * is the adjacency list of the first partition.
  60  */
  61 int matching(int **adj, int n1, int n2)
  62 {
  63         int i;
  64         int mat = 0;
  65         int dist[MNODES];
  66         int pair[MPARTS];       /* vertices matched to the first partition */
  67         int pair2[MPARTS];      /* vertices matched to the second partition */
  68         int noadj[] = {-1};
  69         for (i = 0; i < n1; i++)
  70                 pair[i] = VNIL;
  71         for (i = 0; i < n2; i++)
  72                 pair2[i] = VNIL;
  73         adj[VNIL] = noadj;
  74         while (bfs(adj, pair, pair2, dist, n1))
  75                 for (i = 0; i < n1; i++)
  76                         if (pair[i] == VNIL && dfs(adj, pair, pair2, dist, i))
  77                                 mat++;
  78         return mat;
  79 }