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 (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_free (bipartite_t *gr)
	Free memory occupied by bipartite matching problem.
void	bipartite_add (bipartite_t *gr, unsigned i, unsigned j)
	Add edge from i (on the left side) to j (on the 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)
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_matching (bipartite_t const *gr, int *matching)
	Solve bipartite matching problem.
void	bipartite_dump_f (FILE *f, bipartite_t const *gr)
	Dumps a bipartite graph to a file stream.
void	bipartite_dump (char const *name, bipartite_t const *gr)
	Dumps a bipartite graph to file name.

Detailed Description

Solved bipartite matching problem.

(Variant with only 0/1 costs)

Typedef Documentation

bipartite_t

typedef struct bipartite_t bipartite_t

internal representation of bipartite matching problem

Definition at line 28 of file bipartite.h.

Function Documentation

bipartite_add()

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

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

bipartite_adj()

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.

bipartite_dump()

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

Dumps a bipartite graph to file name.

bipartite_dump_f()

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

Dumps a bipartite graph to a file stream.

bipartite_free()

void bipartite_free

(

bipartite_t *

gr

)

Free memory occupied by bipartite matching problem.

bipartite_matching()

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

Solve bipartite matching problem.

bipartite_new()

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.

bipartite_remv()

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

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