diff options
Diffstat (limited to 'src/backend/lib/bipartite_match.c')
| -rw-r--r-- | src/backend/lib/bipartite_match.c | 180 |
1 files changed, 180 insertions, 0 deletions
diff --git a/src/backend/lib/bipartite_match.c b/src/backend/lib/bipartite_match.c new file mode 100644 index 0000000..baa1c13 --- /dev/null +++ b/src/backend/lib/bipartite_match.c @@ -0,0 +1,180 @@ +/*------------------------------------------------------------------------- + * + * bipartite_match.c + * Hopcroft-Karp maximum cardinality algorithm for bipartite graphs + * + * This implementation is based on pseudocode found at: + * + * https://en.wikipedia.org/w/index.php?title=Hopcroft%E2%80%93Karp_algorithm&oldid=593898016 + * + * Copyright (c) 2015-2021, PostgreSQL Global Development Group + * + * IDENTIFICATION + * src/backend/lib/bipartite_match.c + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include <limits.h> + +#include "lib/bipartite_match.h" +#include "miscadmin.h" + +/* + * The distances computed in hk_breadth_search can easily be seen to never + * exceed u_size. Since we restrict u_size to be less than SHRT_MAX, we + * can therefore use SHRT_MAX as the "infinity" distance needed as a marker. + */ +#define HK_INFINITY SHRT_MAX + +static bool hk_breadth_search(BipartiteMatchState *state); +static bool hk_depth_search(BipartiteMatchState *state, int u); + +/* + * Given the size of U and V, where each is indexed 1..size, and an adjacency + * list, perform the matching and return the resulting state. + */ +BipartiteMatchState * +BipartiteMatch(int u_size, int v_size, short **adjacency) +{ + BipartiteMatchState *state = palloc(sizeof(BipartiteMatchState)); + + if (u_size < 0 || u_size >= SHRT_MAX || + v_size < 0 || v_size >= SHRT_MAX) + elog(ERROR, "invalid set size for BipartiteMatch"); + + state->u_size = u_size; + state->v_size = v_size; + state->adjacency = adjacency; + state->matching = 0; + state->pair_uv = (short *) palloc0((u_size + 1) * sizeof(short)); + state->pair_vu = (short *) palloc0((v_size + 1) * sizeof(short)); + state->distance = (short *) palloc((u_size + 1) * sizeof(short)); + state->queue = (short *) palloc((u_size + 2) * sizeof(short)); + + while (hk_breadth_search(state)) + { + int u; + + for (u = 1; u <= u_size; u++) + { + if (state->pair_uv[u] == 0) + if (hk_depth_search(state, u)) + state->matching++; + } + + CHECK_FOR_INTERRUPTS(); /* just in case */ + } + + return state; +} + +/* + * Free a state returned by BipartiteMatch, except for the original adjacency + * list, which is owned by the caller. This only frees memory, so it's optional. + */ +void +BipartiteMatchFree(BipartiteMatchState *state) +{ + /* adjacency matrix is treated as owned by the caller */ + pfree(state->pair_uv); + pfree(state->pair_vu); + pfree(state->distance); + pfree(state->queue); + pfree(state); +} + +/* + * Perform the breadth-first search step of H-K matching. + * Returns true if successful. + */ +static bool +hk_breadth_search(BipartiteMatchState *state) +{ + int usize = state->u_size; + short *queue = state->queue; + short *distance = state->distance; + int qhead = 0; /* we never enqueue any node more than once */ + int qtail = 0; /* so don't have to worry about wrapping */ + int u; + + distance[0] = HK_INFINITY; + + for (u = 1; u <= usize; u++) + { + if (state->pair_uv[u] == 0) + { + distance[u] = 0; + queue[qhead++] = u; + } + else + distance[u] = HK_INFINITY; + } + + while (qtail < qhead) + { + u = queue[qtail++]; + + if (distance[u] < distance[0]) + { + short *u_adj = state->adjacency[u]; + int i = u_adj ? u_adj[0] : 0; + + for (; i > 0; i--) + { + int u_next = state->pair_vu[u_adj[i]]; + + if (distance[u_next] == HK_INFINITY) + { + distance[u_next] = 1 + distance[u]; + Assert(qhead < usize + 2); + queue[qhead++] = u_next; + } + } + } + } + + return (distance[0] != HK_INFINITY); +} + +/* + * Perform the depth-first search step of H-K matching. + * Returns true if successful. + */ +static bool +hk_depth_search(BipartiteMatchState *state, int u) +{ + short *distance = state->distance; + short *pair_uv = state->pair_uv; + short *pair_vu = state->pair_vu; + short *u_adj = state->adjacency[u]; + int i = u_adj ? u_adj[0] : 0; + short nextdist; + + if (u == 0) + return true; + if (distance[u] == HK_INFINITY) + return false; + nextdist = distance[u] + 1; + + check_stack_depth(); + + for (; i > 0; i--) + { + int v = u_adj[i]; + + if (distance[pair_vu[v]] == nextdist) + { + if (hk_depth_search(state, pair_vu[v])) + { + pair_vu[v] = u; + pair_uv[u] = v; + return true; + } + } + } + + distance[u] = HK_INFINITY; + return false; +} |