PostgreSQL Source Code  git master
bipartite_match.h
Go to the documentation of this file.
1 /*
2  * bipartite_match.h
3  *
4  * Copyright (c) 2015-2017, 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  */
27 typedef 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 */
41 
42 extern BipartiteMatchState *BipartiteMatch(int u_size, int v_size, short **adjacency);
43 
45 
46 #endif /* BIPARTITE_MATCH_H */
void BipartiteMatchFree(BipartiteMatchState *state)
struct BipartiteMatchState BipartiteMatchState
Definition: regguts.h:298
BipartiteMatchState * BipartiteMatch(int u_size, int v_size, short **adjacency)