nsz Git - libfirm/blob - include/libfirm/adt/bipartite.h

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @date   26.01.2006
   9  * @author Sebastian Hack
  10  * @brief Implements bipartite matchings.
  11  */
  12 #ifndef FIRM_ADT_BIPARTITE_H
  13 #define FIRM_ADT_BIPARTITE_H
  14
  15 #include <stdio.h>
  16
  17 #include "../begin.h"
  18
  19 /**
  20  * @ingroup algorithms
  21  * @defgroup bipartite Bipartite Matching
  22  * Solved bipartite matching problem.
  23  * (Variant with only 0/1 costs)
  24  * @{
  25  */
  26
  27 /** internal representation of bipartite matching problem */
  28 typedef struct bipartite_t bipartite_t;
  29
  30 /** Create new bipartite matching problem with @p n_left elements on left side
  31  * and @p n_right elements on right side */
  32 FIRM_API bipartite_t *bipartite_new(int n_left, int n_right);
  33 /** Free memory occupied by bipartite matching problem */
  34 FIRM_API void bipartite_free(bipartite_t *gr);
  35 /** Add edge from @p i (on the left side) to @p j (on the right side) */
  36 FIRM_API void bipartite_add(bipartite_t *gr, int i, int j);
  37 /** Remove edge from @p i (on the left side) to @p j (on the right side) */
  38 FIRM_API void bipartite_remv(bipartite_t *gr, int i, int j);
  39 /** Return 1 if edge from @p i (on the left side) to @p j (on the right side)
  40  * exists, 0 otherwise */
  41 FIRM_API int bipartite_adj(const bipartite_t *gr, int i, int j);
  42 /** Solve bipartite matching problem */
  43 FIRM_API void bipartite_matching(const bipartite_t *gr, int *matching);
  44
  45 /**
  46  * Dumps a bipartite graph to a file stream.
  47  */
  48 FIRM_API void bipartite_dump_f(FILE *f, const bipartite_t *gr);
  49
  50 /**
  51  * Dumps a bipartite graph to file name.
  52  */
  53 FIRM_API void bipartite_dump(const char *name, const bipartite_t *gr);
  54
  55 /** @} */
  56
  57 #include "../end.h"
  58
  59 #endif /* _BIPARTITE_H */