Bipartite Matching

Solved bipartite matching problem. More...

Typedefs
typedef struct bipartite_t	bipartite_t
	internal representation of bipartite matching problem

Functions
bipartite_t *	bipartite_new (int n_left, int n_right)
	Create new bipartite matching problem with n_left elements on left side and n_right elements on right side.
void	bipartite_free (bipartite_t *gr)
	Free memory occupied by bipartite matching problem.
void	bipartite_add (bipartite_t *gr, int i, int j)
	Add edge from i (on the left side) to j (on the right side)
void	bipartite_remv (bipartite_t *gr, int i, int j)
	Remove edge from i (on the left side) to j (on the right side)
int	bipartite_adj (const bipartite_t *gr, int i, int j)
	Return 1 if edge from i (on the left side) to j (on the right side) exists, 0 otherwise.
void	bipartite_matching (const bipartite_t *gr, int *matching)
	Solve bipartite matching problem.
void	bipartite_dump_f (FILE *f, const bipartite_t *gr)
	Dumps a bipartite graph to a file stream.
void	bipartite_dump (const char *name, const bipartite_t *gr)
	Dumps a bipartite graph to file name.

Detailed Description

Solved bipartite matching problem.

(Variant with only 0/1 costs)

Typedef Documentation

typedef struct bipartite_t bipartite_t

internal representation of bipartite matching problem

Definition at line 40 of file bipartite.h.

Function Documentation

void bipartite_add	(	bipartite_t *	gr,
		int	i,
		int	j
	)

Add edge from i (on the left side) to j (on the right side)

int bipartite_adj	(	const bipartite_t *	gr,
		int	i,
		int	j
	)

Return 1 if edge from i (on the left side) to j (on the right side) exists, 0 otherwise.

void bipartite_dump	(	const char *	name,
		const bipartite_t *	gr
	)

Dumps a bipartite graph to file name.

void bipartite_dump_f	(	FILE *	f,
		const bipartite_t *	gr
	)

Dumps a bipartite graph to a file stream.

void bipartite_free

(

bipartite_t *

gr

)

Free memory occupied by bipartite matching problem.

void bipartite_matching	(	const bipartite_t *	gr,
		int *	matching
	)

Solve bipartite matching problem.

bipartite_t* bipartite_new	(	int	n_left,
		int	n_right
	)

Create new bipartite matching problem with n_left elements on left side and n_right elements on right side.

void bipartite_remv	(	bipartite_t *	gr,
		int	i,
		int	j
	)

Remove edge from i (on the left side) to j (on the right side)