bipartite_match.h Source File (original) (raw)

1/*

2 * bipartite_match.h

3 *

5 *

6 * src/include/lib/bipartite_match.h

7 */

8#ifndef BIPARTITE_MATCH_H

9#define BIPARTITE_MATCH_H

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 */

28{

29 /* inputs: */

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: */

39 short *queue; /* queue storage for breadth search */

46#endif /* BIPARTITE_MATCH_H */

struct BipartiteMatchState BipartiteMatchState

BipartiteMatchState * BipartiteMatch(int u_size, int v_size, short **adjacency)

void BipartiteMatchFree(BipartiteMatchState *state)