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