tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
1/*
2 * Implementation of matching.h.
3 */
4
5#include <assert.h>
6#include <stdlib.h>
7#include <stdio.h>
8
9#include "puzzles.h"
10#include "matching.h"
11
12struct scratch {
13 /*
14 * Current contents of the in-progress matching. LtoR is an array
15 * of nl integers, each of which holds a value in {0,1,...,nr-1},
16 * or -1 for no current assignment. RtoL is exactly the reverse.
17 *
18 * Invariant: LtoR[i] is non-empty and equal to j if and only if
19 * RtoL[j] is non-empty and equal to i.
20 */
21 int *LtoR, *RtoL;
22
23 /*
24 * Arrays of nl and nr integer respectively, giving the layer
25 * assigned to each integer in the breadth-first search step of
26 * the algorithm.
27 */
28 int *Llayer, *Rlayer;
29
30 /*
31 * Arrays of nl and nr integers respectively, used to hold the
32 * to-do queues in the breadth-first search.
33 */
34 int *Lqueue, *Rqueue;
35
36 /*
37 * An augmenting path of vertices, alternating between L vertices
38 * (in the even-numbered positions, starting at 0) and R (in the
39 * odd positions). Must be long enough to hold any such path that
40 * never repeats a vertex, i.e. must be at least 2*min(nl,nr) in
41 * size.
42 */
43 int *augpath;
44
45 /*
46 * Track the progress of the depth-first search at each
47 * even-numbered layer. Has one element for each even-numbered
48 * position in augpath.
49 */
50 int *dfsstate;
51
52 /*
53 * Store a random permutation of the L vertex indices, if we're
54 * randomising the dfs phase.
55 */
56 int *Lorder;
57};
58
59size_t matching_scratch_size(int nl, int nr)
60{
61 size_t n;
62 int nmin = (nl < nr ? nl : nr);
63
64 n = (sizeof(struct scratch) + sizeof(int)-1)/sizeof(int);
65 n += nl; /* LtoR */
66 n += nr; /* RtoL */
67 n += nl; /* Llayer */
68 n += nr; /* Rlayer */
69 n += nl; /* Lqueue */
70 n += nr; /* Rqueue */
71 n += 2*nmin; /* augpath */
72 n += nmin; /* dfsstate */
73 n += nl; /* Lorder */
74 return n * sizeof(int);
75}
76
77int matching_with_scratch(void *scratchv,
78 int nl, int nr, int **adjlists, int *adjsizes,
79 random_state *rs, int *outl, int *outr)
80{
81 struct scratch *s = (struct scratch *)scratchv;
82 int L, R, i, j;
83
84 /*
85 * Set up the various array pointers in the scratch space.
86 */
87 {
88 int *p = scratchv;
89 int nmin = (nl < nr ? nl : nr);
90
91 p += (sizeof(struct scratch) + sizeof(int)-1)/sizeof(int);
92 s->LtoR = p; p += nl;
93 s->RtoL = p; p += nr;
94 s->Llayer = p; p += nl;
95 s->Rlayer = p; p += nr;
96 s->Lqueue = p; p += nl;
97 s->Rqueue = p; p += nr;
98 s->augpath = p; p += 2*nmin;
99 s->dfsstate = p; p += nmin;
100 s->Lorder = p; p += nl;
101 }
102
103 /*
104 * Set up the initial matching, which is empty.
105 */
106 for (L = 0; L < nl; L++)
107 s->LtoR[L] = -1;
108 for (R = 0; R < nr; R++)
109 s->RtoL[R] = -1;
110
111 while (1) {
112 /*
113 * Breadth-first search starting from the unassigned left
114 * vertices, traversing edges from left to right only if they
115 * are _not_ part of the matching, and from right to left only
116 * if they _are_. We assign a 'layer number' to all vertices
117 * visited by this search, with the starting vertices being
118 * layer 0 and every successor of a layer-n node being layer
119 * n+1.
120 */
121 int Lqs, Rqs, layer, target_layer;
122
123 for (L = 0; L < nl; L++)
124 s->Llayer[L] = -1;
125 for (R = 0; R < nr; R++)
126 s->Rlayer[R] = -1;
127
128 Lqs = 0;
129 for (L = 0; L < nl; L++) {
130 if (s->LtoR[L] == -1) {
131 s->Llayer[L] = 0;
132 s->Lqueue[Lqs++] = L;
133 }
134 }
135
136 layer = 0;
137 while (1) {
138 bool found_free_R_vertex = false;
139
140 Rqs = 0;
141 for (i = 0; i < Lqs; i++) {
142 L = s->Lqueue[i];
143 assert(s->Llayer[L] == layer);
144
145 for (j = 0; j < adjsizes[L]; j++) {
146 R = adjlists[L][j];
147 if (R != s->LtoR[L] && s->Rlayer[R] == -1) {
148 s->Rlayer[R] = layer+1;
149 s->Rqueue[Rqs++] = R;
150 if (s->RtoL[R] == -1)
151 found_free_R_vertex = true;
152 }
153 }
154 }
155 layer++;
156
157 if (found_free_R_vertex)
158 break;
159
160 if (Rqs == 0)
161 goto done;
162
163 Lqs = 0;
164 for (j = 0; j < Rqs; j++) {
165 R = s->Rqueue[j];
166 assert(s->Rlayer[R] == layer);
167 if ((L = s->RtoL[R]) != -1 && s->Llayer[L] == -1) {
168 s->Llayer[L] = layer+1;
169 s->Lqueue[Lqs++] = L;
170 }
171 }
172 layer++;
173
174 if (Lqs == 0)
175 goto done;
176 }
177
178 target_layer = layer;
179
180 /*
181 * Vertices in the target layer are only interesting if
182 * they're actually unassigned. Blanking out the others here
183 * will save us a special case in the dfs loop below.
184 */
185 for (R = 0; R < nr; R++)
186 if (s->Rlayer[R] == target_layer && s->RtoL[R] != -1)
187 s->Rlayer[R] = -1;
188
189 /*
190 * Choose an ordering in which to try the L vertices at the
191 * start of the next pass.
192 */
193 for (L = 0; L < nl; L++)
194 s->Lorder[L] = L;
195 if (rs)
196 shuffle(s->Lorder, nl, sizeof(*s->Lorder), rs);
197
198 /*
199 * Now depth-first search through that layered set of vertices
200 * to find as many (vertex-)disjoint augmenting paths as we
201 * can, and for each one we find, augment the matching.
202 */
203 s->dfsstate[0] = 0;
204 i = 0;
205 while (1) {
206 /*
207 * Find the next vertex to go on the end of augpath.
208 */
209 if (i == 0) {
210 /* In this special case, we're just looking for L
211 * vertices that are not yet assigned. */
212 if (s->dfsstate[i] == nl)
213 break; /* entire DFS has finished */
214
215 L = s->Lorder[s->dfsstate[i]++];
216
217 if (s->Llayer[L] != 2*i)
218 continue; /* skip this vertex */
219 } else {
220 /* In the more usual case, we're going through the
221 * adjacency list for the previous L vertex. */
222 L = s->augpath[2*i-2];
223 j = s->dfsstate[i]++;
224 if (j == adjsizes[L]) {
225 /* Run out of neighbours of the previous vertex. */
226 i--;
227 continue;
228 }
229 if (rs && adjsizes[L] - j > 1) {
230 int which = j + random_upto(rs, adjsizes[L] - j);
231 int tmp = adjlists[L][which];
232 adjlists[L][which] = adjlists[L][j];
233 adjlists[L][j] = tmp;
234 }
235 R = adjlists[L][j];
236
237 if (s->Rlayer[R] != 2*i-1)
238 continue; /* skip this vertex */
239
240 s->augpath[2*i-1] = R;
241 s->Rlayer[R] = -1; /* mark vertex as visited */
242
243 if (2*i-1 == target_layer) {
244 /*
245 * We've found an augmenting path, in the form of
246 * an even-sized list of vertices alternating
247 * L,R,...,L,R, with the initial L and final R
248 * vertex free and otherwise each R currently
249 * connected to the next L. Adjust so that each L
250 * connects to the next R, increasing the edge
251 * count in the matching by 1.
252 */
253 for (j = 0; j < 2*i; j += 2) {
254 s->LtoR[s->augpath[j]] = s->augpath[j+1];
255 s->RtoL[s->augpath[j+1]] = s->augpath[j];
256 }
257
258 /*
259 * Having dealt with that path, and already marked
260 * all its vertices as visited, rewind right to
261 * the start and resume our DFS from a new
262 * starting L-vertex.
263 */
264 i = 0;
265 continue;
266 }
267
268 L = s->RtoL[R];
269 if (s->Llayer[L] != 2*i)
270 continue; /* skip this vertex */
271 }
272
273 s->augpath[2*i] = L;
274 s->Llayer[L] = -1; /* mark vertex as visited */
275 i++;
276 s->dfsstate[i] = 0;
277 }
278 }
279
280 done:
281 /*
282 * Fill in the output arrays.
283 */
284 if (outl) {
285 for (i = 0; i < nl; i++)
286 outl[i] = s->LtoR[i];
287 }
288 if (outr) {
289 for (j = 0; j < nr; j++)
290 outr[j] = s->RtoL[j];
291 }
292
293 /*
294 * Return the number of matching edges.
295 */
296 for (i = j = 0; i < nl; i++)
297 if (s->LtoR[i] != -1)
298 j++;
299 return j;
300}
301
302int matching(int nl, int nr, int **adjlists, int *adjsizes,
303 random_state *rs, int *outl, int *outr)
304{
305 void *scratch;
306 int size;
307 int ret;
308
309 size = matching_scratch_size(nl, nr);
310 scratch = malloc(size);
311 if (!scratch)
312 return -1;
313
314 ret = matching_with_scratch(scratch, nl, nr, adjlists, adjsizes,
315 rs, outl, outr);
316
317 free(scratch);
318
319 return ret;
320}
321
322void matching_witness(void *scratchv, int nl, int nr, int *witness)
323{
324 struct scratch *s = (struct scratch *)scratchv;
325 int i, j;
326
327 for (i = 0; i < nl; i++)
328 witness[i] = s->Llayer[i] == -1;
329 for (j = 0; j < nr; j++)
330 witness[nl + j] = s->Rlayer[j] == -1;
331}