README: mentioning other make targets seem unnecessary
[rangi.git] / mat.c
blob4e775ab11e628aea323416c3559b86491d08a24f
1 /*
2 * Finding the maximum matching in the given bipartite graph using
3 * Hopcroft-Karp algorithm.
4 */
6 #include "rangi.h"
8 #define VNIL (MNODES - 1) /* the special null vertex */
9 #define INF 1000000
11 static int bfs(int **adj, int *pair, int *pair2, int *dist, int n1)
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;
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];
35 return dist[VNIL] != INF;
38 static int dfs(int **adj, int *pair, int *pair2, int *dist, int v)
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;
53 dist[v] = INF;
54 return 0;
58 * Find the maximum matching in the given bipartite graph. adj
59 * is the adjacency list of the first partition.
61 int matching(int **adj, int n1, int n2)
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;