ref: b5e02b0b9c1b35b0b907bf6d63e62b9fafd9cb7e
dir: /matching.h/
/* * Hopcroft-Karp algorithm for finding a maximal matching in a * bipartite graph. */ #ifndef MATCHING_MATCHING_H #define MATCHING_MATCHING_H /* * The actual algorithm. * * Inputs: * * - 'scratch' is previously allocated scratch space of a size * previously determined by calling 'matching_scratch_size'. * * - 'nl' is the number of vertices on the left side of the graph. * Left vertices are numbered from 0 to nl-1. * * - 'nr' is the number of vertices on the left side of the graph. * Right vertices are numbered from 0 to nr-1. * * - 'adjlists' and 'adjsizes' represents the graph in adjacency-list * form. For each left vertex L, adjlists[L] points to an array of * adjsizes[L] integers giving the list of right vertices adjacent * to L. * * - 'rs', if not NULL, is a random_state used to perturb the * progress of the algorithm so as to choose randomly from the * possible matchings if there's more than one. (The exact * probability distribution can't be guaranteed, but at the very * least, any matching that exists should be a _possible_ output.) * * If 'rs' is not NULL, then each list in adjlists[] will be permuted * during the course of the algorithm as a side effect. (That's why * it's not an array of _const_ int pointers.) * * Output: * * - 'outl' may be NULL. If non-NULL, it is an array of 'nl' * integers, and outl[L] will be assigned the index of the right * vertex that the output matching paired with the left vertex L, * or -1 if L is unpaired. * * - 'outr' may be NULL. If non-NULL, it is an array of 'nr' * integers, and outr[R] will be assigned the index of the left * vertex that the output matching paired with the right vertex R, * or -1 if R is unpaired. * * - the returned value from the function is the total number of * edges in the matching. */ int matching_with_scratch(void *scratch, int nl, int nr, int **adjlists, int *adjsizes, random_state *rs, int *outl, int *outr); /* * The above function expects its 'scratch' parameter to have already * been set up. This function tells you how much space is needed for a * given size of graph, so that you can allocate a single instance of * scratch space and run the algorithm multiple times without the * overhead of an alloc and free every time. */ size_t matching_scratch_size(int nl, int nr); /* * Simplified version of the above function. All parameters are the * same, except that 'scratch' is constructed internally and freed on * exit. This is the simplest way to call the algorithm as a one-off; * however, if you need to call it multiple times on the same size of * graph, it is probably better to call the above version directly so * that you only construct 'scratch' once. * * Additional return value is now -1, meaning that scratch space * could not be allocated. */ int matching(int nl, int nr, int **adjlists, int *adjsizes, random_state *rs, int *outl, int *outr); #endif /* MATCHING_MATCHING_H */