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