Age Owner Branch data 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-2025, 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 *
3766 andres@anarazel.de 39 :CBC 412 : BipartiteMatch(int u_size, int v_size, short **adjacency)
40 : : {
41 : 412 : BipartiteMatchState *state = palloc(sizeof(BipartiteMatchState));
42 : :
3667 tgl@sss.pgh.pa.us 43 [ + - + - : 412 : if (u_size < 0 || u_size >= SHRT_MAX ||
+ - ]
44 [ - + ]: 412 : v_size < 0 || v_size >= SHRT_MAX)
3667 tgl@sss.pgh.pa.us 45 [ # # ]:UBC 0 : elog(ERROR, "invalid set size for BipartiteMatch");
46 : :
3766 andres@anarazel.de 47 :CBC 412 : state->u_size = u_size;
48 : 412 : state->v_size = v_size;
49 : 412 : state->adjacency = adjacency;
3667 tgl@sss.pgh.pa.us 50 : 412 : state->matching = 0;
51 : 412 : state->pair_uv = (short *) palloc0((u_size + 1) * sizeof(short));
52 : 412 : state->pair_vu = (short *) palloc0((v_size + 1) * sizeof(short));
53 : 412 : state->distance = (short *) palloc((u_size + 1) * sizeof(short));
54 : 412 : state->queue = (short *) palloc((u_size + 2) * sizeof(short));
55 : :
3766 andres@anarazel.de 56 [ + + ]: 1023 : while (hk_breadth_search(state))
57 : : {
58 : : int u;
59 : :
3667 tgl@sss.pgh.pa.us 60 [ + + ]: 796 : for (u = 1; u <= u_size; u++)
61 : : {
3766 andres@anarazel.de 62 [ + - ]: 597 : if (state->pair_uv[u] == 0)
3667 tgl@sss.pgh.pa.us 63 [ + + ]: 597 : if (hk_depth_search(state, u))
3766 andres@anarazel.de 64 : 285 : state->matching++;
65 : : }
66 : :
3759 bruce@momjian.us 67 [ - + ]: 199 : CHECK_FOR_INTERRUPTS(); /* just in case */
68 : : }
69 : :
3766 andres@anarazel.de 70 : 412 : 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 : 412 : BipartiteMatchFree(BipartiteMatchState *state)
79 : : {
80 : : /* adjacency matrix is treated as owned by the caller */
81 : 412 : pfree(state->pair_uv);
82 : 412 : pfree(state->pair_vu);
83 : 412 : pfree(state->distance);
84 : 412 : pfree(state->queue);
85 : 412 : pfree(state);
86 : 412 : }
87 : :
88 : : /*
89 : : * Perform the breadth-first search step of H-K matching.
90 : : * Returns true if successful.
91 : : */
92 : : static bool
93 : 611 : hk_breadth_search(BipartiteMatchState *state)
94 : : {
95 : 611 : int usize = state->u_size;
96 : 611 : short *queue = state->queue;
3667 tgl@sss.pgh.pa.us 97 : 611 : short *distance = state->distance;
3766 andres@anarazel.de 98 : 611 : int qhead = 0; /* we never enqueue any node more than once */
99 : 611 : int qtail = 0; /* so don't have to worry about wrapping */
100 : : int u;
101 : :
3667 tgl@sss.pgh.pa.us 102 : 611 : distance[0] = HK_INFINITY;
103 : :
104 [ + + ]: 2191 : for (u = 1; u <= usize; u++)
105 : : {
3766 andres@anarazel.de 106 [ + + ]: 1580 : if (state->pair_uv[u] == 0)
107 : : {
108 : 1295 : distance[u] = 0;
109 : 1295 : queue[qhead++] = u;
110 : : }
111 : : else
3667 tgl@sss.pgh.pa.us 112 : 285 : distance[u] = HK_INFINITY;
113 : : }
114 : :
3766 andres@anarazel.de 115 [ + + ]: 2119 : while (qtail < qhead)
116 : : {
117 : 1508 : u = queue[qtail++];
118 : :
119 [ + + ]: 1508 : if (distance[u] < distance[0])
120 : : {
3759 bruce@momjian.us 121 : 1309 : short *u_adj = state->adjacency[u];
122 [ + + ]: 1309 : int i = u_adj ? u_adj[0] : 0;
123 : :
3667 tgl@sss.pgh.pa.us 124 [ + + ]: 1892 : for (; i > 0; i--)
125 : : {
3759 bruce@momjian.us 126 : 583 : int u_next = state->pair_vu[u_adj[i]];
127 : :
3667 tgl@sss.pgh.pa.us 128 [ + + ]: 583 : if (distance[u_next] == HK_INFINITY)
129 : : {
3766 andres@anarazel.de 130 : 213 : distance[u_next] = 1 + distance[u];
3667 tgl@sss.pgh.pa.us 131 [ - + ]: 213 : Assert(qhead < usize + 2);
3766 andres@anarazel.de 132 : 213 : queue[qhead++] = u_next;
133 : : }
134 : : }
135 : : }
136 : : }
137 : :
3667 tgl@sss.pgh.pa.us 138 : 611 : 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 : 882 : hk_depth_search(BipartiteMatchState *state, int u)
147 : : {
148 : 882 : short *distance = state->distance;
3766 andres@anarazel.de 149 : 882 : short *pair_uv = state->pair_uv;
150 : 882 : short *pair_vu = state->pair_vu;
151 : 882 : short *u_adj = state->adjacency[u];
152 [ + + ]: 882 : int i = u_adj ? u_adj[0] : 0;
153 : : short nextdist;
154 : :
155 [ + + ]: 882 : if (u == 0)
156 : 285 : return true;
3667 tgl@sss.pgh.pa.us 157 [ - + ]: 597 : if (distance[u] == HK_INFINITY)
3667 tgl@sss.pgh.pa.us 158 :UBC 0 : return false;
3667 tgl@sss.pgh.pa.us 159 :CBC 597 : nextdist = distance[u] + 1;
160 : :
161 : 597 : check_stack_depth();
162 : :
163 [ + + ]: 715 : for (; i > 0; i--)
164 : : {
3759 bruce@momjian.us 165 : 403 : int v = u_adj[i];
166 : :
3667 tgl@sss.pgh.pa.us 167 [ + + ]: 403 : if (distance[pair_vu[v]] == nextdist)
168 : : {
169 [ + - ]: 285 : if (hk_depth_search(state, pair_vu[v]))
170 : : {
3766 andres@anarazel.de 171 : 285 : pair_vu[v] = u;
172 : 285 : pair_uv[u] = v;
173 : 285 : return true;
174 : : }
175 : : }
176 : : }
177 : :
3667 tgl@sss.pgh.pa.us 178 : 312 : distance[u] = HK_INFINITY;
3766 andres@anarazel.de 179 : 312 : return false;
180 : : }
|
