1/*
2 * bipartite_match.h
3 *
4 * Copyright (c) 2015-2019, PostgreSQL Global Development Group
5 *
6 * src/include/lib/bipartite_match.h
7 */
8#ifndef BIPARTITE_MATCH_H
9#define BIPARTITE_MATCH_H
10
11/*
12 * Given a bipartite graph consisting of nodes U numbered 1..nU, nodes V
13 * numbered 1..nV, and an adjacency map of undirected edges in the form
14 * adjacency[u] = [k, v1, v2, v3, ... vk], we wish to find a "maximum
15 * cardinality matching", which is defined as follows: a matching is a subset
16 * of the original edges such that no node has more than one edge, and a
17 * matching has maximum cardinality if there exists no other matching with a
18 * greater number of edges.
19 *
20 * This matching has various applications in graph theory, but the motivating
21 * example here is Dilworth's theorem: a partially-ordered set can be divided
22 * into the minimum number of chains (i.e. subsets X where x1 < x2 < x3 ...) by
23 * a bipartite graph construction. This gives us a polynomial-time solution to
24 * the problem of planning a collection of grouping sets with the provably
25 * minimal number of sort operations.
26 */
27typedef struct BipartiteMatchState
28{
29 /* inputs: */
30 int u_size; /* size of U */
31 int v_size; /* size of V */
32 short **adjacency; /* adjacency[u] = [k, v1,v2,v3,...,vk] */
33 /* outputs: */
34 int matching; /* number of edges in matching */
35 short *pair_uv; /* pair_uv[u] -> v */
36 short *pair_vu; /* pair_vu[v] -> u */
37 /* private state for matching algorithm: */
38 short *distance; /* distance[u] */
39 short *queue; /* queue storage for breadth search */
40} BipartiteMatchState;
41
42extern BipartiteMatchState *BipartiteMatch(int u_size, int v_size, short **adjacency);
43
44extern void BipartiteMatchFree(BipartiteMatchState *state);
45
46#endif /* BIPARTITE_MATCH_H */
47