Age Owner TLA Line data Source code
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-2023, 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 :
31 : static bool hk_breadth_search(BipartiteMatchState *state);
32 : static 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 : */
38 : BipartiteMatchState *
2885 andres 39 CBC 340 : BipartiteMatch(int u_size, int v_size, short **adjacency)
40 : {
41 340 : BipartiteMatchState *state = palloc(sizeof(BipartiteMatchState));
42 :
2786 tgl 43 340 : if (u_size < 0 || u_size >= SHRT_MAX ||
44 340 : v_size < 0 || v_size >= SHRT_MAX)
2786 tgl 45 UBC 0 : elog(ERROR, "invalid set size for BipartiteMatch");
46 :
2885 andres 47 CBC 340 : state->u_size = u_size;
48 340 : state->v_size = v_size;
49 340 : state->adjacency = adjacency;
2786 tgl 50 340 : state->matching = 0;
51 340 : state->pair_uv = (short *) palloc0((u_size + 1) * sizeof(short));
52 340 : state->pair_vu = (short *) palloc0((v_size + 1) * sizeof(short));
53 340 : state->distance = (short *) palloc((u_size + 1) * sizeof(short));
54 340 : state->queue = (short *) palloc((u_size + 2) * sizeof(short));
55 :
2885 andres 56 849 : while (hk_breadth_search(state))
57 : {
58 : int u;
59 :
2786 tgl 60 706 : for (u = 1; u <= u_size; u++)
61 : {
2885 andres 62 537 : if (state->pair_uv[u] == 0)
2786 tgl 63 537 : if (hk_depth_search(state, u))
2885 andres 64 255 : state->matching++;
65 : }
66 :
2878 bruce 67 169 : CHECK_FOR_INTERRUPTS(); /* just in case */
68 : }
69 :
2885 andres 70 340 : 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 : */
77 : void
78 340 : BipartiteMatchFree(BipartiteMatchState *state)
79 : {
80 : /* adjacency matrix is treated as owned by the caller */
81 340 : pfree(state->pair_uv);
82 340 : pfree(state->pair_vu);
83 340 : pfree(state->distance);
84 340 : pfree(state->queue);
85 340 : pfree(state);
86 340 : }
87 :
88 : /*
89 : * Perform the breadth-first search step of H-K matching.
90 : * Returns true if successful.
91 : */
92 : static bool
93 509 : hk_breadth_search(BipartiteMatchState *state)
94 : {
95 509 : int usize = state->u_size;
96 509 : short *queue = state->queue;
2786 tgl 97 509 : short *distance = state->distance;
2885 andres 98 509 : int qhead = 0; /* we never enqueue any node more than once */
99 509 : int qtail = 0; /* so don't have to worry about wrapping */
100 : int u;
101 :
2786 tgl 102 509 : distance[0] = HK_INFINITY;
103 :
104 1885 : for (u = 1; u <= usize; u++)
105 : {
2885 andres 106 1376 : if (state->pair_uv[u] == 0)
107 : {
108 1121 : distance[u] = 0;
109 1121 : queue[qhead++] = u;
110 : }
111 : else
2786 tgl 112 255 : distance[u] = HK_INFINITY;
113 : }
114 :
2885 andres 115 1813 : while (qtail < qhead)
116 : {
117 1304 : u = queue[qtail++];
118 :
119 1304 : if (distance[u] < distance[0])
120 : {
2878 bruce 121 1135 : short *u_adj = state->adjacency[u];
122 1135 : int i = u_adj ? u_adj[0] : 0;
123 :
2786 tgl 124 1688 : for (; i > 0; i--)
125 : {
2878 bruce 126 553 : int u_next = state->pair_vu[u_adj[i]];
127 :
2786 tgl 128 553 : if (distance[u_next] == HK_INFINITY)
129 : {
2885 andres 130 183 : distance[u_next] = 1 + distance[u];
2786 tgl 131 183 : Assert(qhead < usize + 2);
2885 andres 132 183 : queue[qhead++] = u_next;
133 : }
134 : }
135 : }
136 : }
137 :
2786 tgl 138 509 : 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 : */
145 : static bool
146 792 : hk_depth_search(BipartiteMatchState *state, int u)
147 : {
148 792 : short *distance = state->distance;
2885 andres 149 792 : short *pair_uv = state->pair_uv;
150 792 : short *pair_vu = state->pair_vu;
151 792 : short *u_adj = state->adjacency[u];
152 792 : int i = u_adj ? u_adj[0] : 0;
153 : short nextdist;
154 :
155 792 : if (u == 0)
156 255 : return true;
2786 tgl 157 537 : if (distance[u] == HK_INFINITY)
2786 tgl 158 UBC 0 : return false;
2786 tgl 159 CBC 537 : nextdist = distance[u] + 1;
160 :
161 537 : check_stack_depth();
162 :
163 655 : for (; i > 0; i--)
164 : {
2878 bruce 165 373 : int v = u_adj[i];
166 :
2786 tgl 167 373 : if (distance[pair_vu[v]] == nextdist)
168 : {
169 255 : if (hk_depth_search(state, pair_vu[v]))
170 : {
2885 andres 171 255 : pair_vu[v] = u;
172 255 : pair_uv[u] = v;
173 255 : return true;
174 : }
175 : }
176 : }
177 :
2786 tgl 178 282 : distance[u] = HK_INFINITY;
2885 andres 179 282 : return false;
180 : }
|
