libFirm
Bipartite Matching

Solved bipartite matching problem. More...

Typedefs

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

Functions

bipartite_tbipartite_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)