Bipartite Matching

Solved bipartite matching problem. More...

Typedefs
typedef struct bipartite_t	bipartite_t
	internal representation of bipartite matching problem More...

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

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 28 of file bipartite.h.

Function Documentation

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

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

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

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

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

Dumps a bipartite graph to file name.

void bipartite_dump_f	(	FILE *	f,
		bipartite_t const *	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	(	bipartite_t const *	gr,
		int *	matching
	)

Solve bipartite matching problem.

bipartite_t* bipartite_new	(	unsigned	n_left,
		unsigned	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,
		unsigned	i,
		unsigned	j
	)

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