src/backend/lib/bipartite_match.c

   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-2022, 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 }