codekingpro/portable-devtools

1/*2 * bipartite_match.h3 *4 * Copyright (c) 2015-2023, PostgreSQL Global Development Group5 *6 * src/include/lib/bipartite_match.h7 */8#ifndef BIPARTITE_MATCH_H9#define BIPARTITE_MATCH_H10 11/*12 * Given a bipartite graph consisting of nodes U numbered 1..nU, nodes V13 * numbered 1..nV, and an adjacency map of undirected edges in the form14 * adjacency[u] = [k, v1, v2, v3, ... vk], we wish to find a "maximum15 * cardinality matching", which is defined as follows: a matching is a subset16 * of the original edges such that no node has more than one edge, and a17 * matching has maximum cardinality if there exists no other matching with a18 * greater number of edges.19 *20 * This matching has various applications in graph theory, but the motivating21 * example here is Dilworth's theorem: a partially-ordered set can be divided22 * into the minimum number of chains (i.e. subsets X where x1 < x2 < x3 ...) by23 * a bipartite graph construction. This gives us a polynomial-time solution to24 * the problem of planning a collection of grouping sets with the provably25 * minimal number of sort operations.26 */27typedef struct BipartiteMatchState28{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