libFirm 1.20
Bipartite Matching

Solved bipartite matching problem. More...

Typedefs

typedef struct bipartite_t bipartite_t
 internal representation of bipartite matching problem

Functions

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