PostgreSQL Source Code  git master
bipartite_match.c
Go to the documentation of this file.
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-2024, 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 
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  */
39 BipartiteMatch(int u_size, int v_size, short **adjacency)
40 {
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
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
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
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 
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 }
static bool hk_depth_search(BipartiteMatchState *state, int u)
#define HK_INFINITY
void BipartiteMatchFree(BipartiteMatchState *state)
static bool hk_breadth_search(BipartiteMatchState *state)
BipartiteMatchState * BipartiteMatch(int u_size, int v_size, short **adjacency)
#define Assert(condition)
Definition: c.h:861
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
int i
Definition: isn.c:72
void pfree(void *pointer)
Definition: mcxt.c:1521
void * palloc0(Size size)
Definition: mcxt.c:1347
void * palloc(Size size)
Definition: mcxt.c:1317
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:122
void check_stack_depth(void)
Definition: postgres.c:3563
Definition: regguts.h:323