granicus.if.org Git - postgresql/blob - src/include/lib/bipartite_match.h

   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 */
  40 } BipartiteMatchState;
  41
  42 extern BipartiteMatchState *BipartiteMatch(int u_size, int v_size, short **adjacency);
  43
  44 extern void BipartiteMatchFree(BipartiteMatchState *state);
  45
  46 #endif   /* BIPARTITE_MATCH_H */