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-2018, 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 * 39 BipartiteMatch(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 */ 77 void 78 BipartiteMatchFree(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 */ 92 static bool 93 hk_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 */ 145 static bool 146 hk_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