1/*-------------------------------------------------------------------------
2 *
3 * bipartite_match.c
4 * Hopcroft-Karp maximum cardinality algorithm for bipartite graphs
5 *
6 * This implementation is based on pseudocode found at:
7 *
8 * https://en.wikipedia.org/w/index.php?title=Hopcroft%E2%80%93Karp_algorithm&oldid=593898016
9 *
10 * Copyright (c) 2015-2019, PostgreSQL Global Development Group
11 *
12 * IDENTIFICATION
13 * src/backend/lib/bipartite_match.c
14 *
15 *-------------------------------------------------------------------------
16 */
17#include "postgres.h"
18
19#include <limits.h>
20
21#include "lib/bipartite_match.h"
22#include "miscadmin.h"
23
24/*
25 * The distances computed in hk_breadth_search can easily be seen to never
26 * exceed u_size. Since we restrict u_size to be less than SHRT_MAX, we
27 * can therefore use SHRT_MAX as the "infinity" distance needed as a marker.
28 */
29#define HK_INFINITY SHRT_MAX
30
31static bool hk_breadth_search(BipartiteMatchState *state);
32static bool hk_depth_search(BipartiteMatchState *state, int u);
33
34/*
35 * Given the size of U and V, where each is indexed 1..size, and an adjacency
36 * list, perform the matching and return the resulting state.
37 */
38BipartiteMatchState *
39BipartiteMatch(int u_size, int v_size, short **adjacency)
40{
41 BipartiteMatchState *state = palloc(sizeof(BipartiteMatchState));
42
43 if (u_size < 0 || u_size >= SHRT_MAX ||
44 v_size < 0 || v_size >= SHRT_MAX)
45 elog(ERROR, "invalid set size for BipartiteMatch");
46
47 state->u_size = u_size;
48 state->v_size = v_size;
49 state->adjacency = adjacency;
50 state->matching = 0;
51 state->pair_uv = (short *) palloc0((u_size + 1) * sizeof(short));
52 state->pair_vu = (short *) palloc0((v_size + 1) * sizeof(short));
53 state->distance = (short *) palloc((u_size + 1) * sizeof(short));
54 state->queue = (short *) palloc((u_size + 2) * sizeof(short));
55
56 while (hk_breadth_search(state))
57 {
58 int u;
59
60 for (u = 1; u <= u_size; u++)
61 {
62 if (state->pair_uv[u] == 0)
63 if (hk_depth_search(state, u))
64 state->matching++;
65 }
66
67 CHECK_FOR_INTERRUPTS(); /* just in case */
68 }
69
70 return state;
71}
72
73/*
74 * Free a state returned by BipartiteMatch, except for the original adjacency
75 * list, which is owned by the caller. This only frees memory, so it's optional.
76 */
77void
78BipartiteMatchFree(BipartiteMatchState *state)
79{
80 /* adjacency matrix is treated as owned by the caller */
81 pfree(state->pair_uv);
82 pfree(state->pair_vu);
83 pfree(state->distance);
84 pfree(state->queue);
85 pfree(state);
86}
87
88/*
89 * Perform the breadth-first search step of H-K matching.
90 * Returns true if successful.
91 */
92static bool
93hk_breadth_search(BipartiteMatchState *state)
94{
95 int usize = state->u_size;
96 short *queue = state->queue;
97 short *distance = state->distance;
98 int qhead = 0; /* we never enqueue any node more than once */
99 int qtail = 0; /* so don't have to worry about wrapping */
100 int u;
101
102 distance[0] = HK_INFINITY;
103
104 for (u = 1; u <= usize; u++)
105 {
106 if (state->pair_uv[u] == 0)
107 {
108 distance[u] = 0;
109 queue[qhead++] = u;
110 }
111 else
112 distance[u] = HK_INFINITY;
113 }
114
115 while (qtail < qhead)
116 {
117 u = queue[qtail++];
118
119 if (distance[u] < distance[0])
120 {
121 short *u_adj = state->adjacency[u];
122 int i = u_adj ? u_adj[0] : 0;
123
124 for (; i > 0; i--)
125 {
126 int u_next = state->pair_vu[u_adj[i]];
127
128 if (distance[u_next] == HK_INFINITY)
129 {
130 distance[u_next] = 1 + distance[u];
131 Assert(qhead < usize + 2);
132 queue[qhead++] = u_next;
133 }
134 }
135 }
136 }
137
138 return (distance[0] != HK_INFINITY);
139}
140
141/*
142 * Perform the depth-first search step of H-K matching.
143 * Returns true if successful.
144 */
145static bool
146hk_depth_search(BipartiteMatchState *state, int u)
147{
148 short *distance = state->distance;
149 short *pair_uv = state->pair_uv;
150 short *pair_vu = state->pair_vu;
151 short *u_adj = state->adjacency[u];
152 int i = u_adj ? u_adj[0] : 0;
153 short nextdist;
154
155 if (u == 0)
156 return true;
157 if (distance[u] == HK_INFINITY)
158 return false;
159 nextdist = distance[u] + 1;
160
161 check_stack_depth();
162
163 for (; i > 0; i--)
164 {
165 int v = u_adj[i];
166
167 if (distance[pair_vu[v]] == nextdist)
168 {
169 if (hk_depth_search(state, pair_vu[v]))
170 {
171 pair_vu[v] = u;
172 pair_uv[u] = v;
173 return true;
174 }
175 }
176 }
177
178 distance[u] = HK_INFINITY;
179 return false;
180}
181