c_cpp/lib/klib/kgraph.h

   1 #ifndef AC_KGRAPH_H
   2 #define AC_KGRAPH_H
   3
   4 #include <stdint.h>
   5 #include <stdlib.h>
   6 #include "khash.h"
   7 #include "kbtree.h"
   8
   9 typedef unsigned kgint_t;
  10
  11 #define kgraph_t(name) kh_##name##_t
  12
  13 #define __KG_BASIC(name, SCOPE, vertex_t, arc_t, ehn) \
  14         SCOPE kgraph_t(name) *kg_init_##name(void) { return kh_init(name); } \
  15         SCOPE void kg_destroy_##name(kgraph_t(name) *g) { \
  16                 khint_t k; \
  17                 if (g == 0) return; \
  18                 for (k = kh_begin(g); k != kh_end(g); ++k) \
  19                         if (kh_exist(g, k)) kh_destroy(ehn, kh_val(g, k)._arc); \
  20                 kh_destroy(name, g); \
  21         } \
  22         SCOPE vertex_t *kg_get_v_##name(kgraph_t(name) *g, kgint_t v) { \
  23                 khint_t k = kh_get(name, g, v); \
  24                 return k == kh_end(g)? 0 : &kh_val(g, k); \
  25         } \
  26         SCOPE vertex_t *kg_put_v_##name(kgraph_t(name) *g, kgint_t v, int *absent) { \
  27                 khint_t k; \
  28                 k = kh_put(name, g, v, absent); \
  29                 if (*absent) kh_val(g, k)._arc = kh_init(ehn); \
  30                 return &kh_val(g, k); \
  31         } \
  32         SCOPE void kg_put_a_##name(kgraph_t(name) *g, kgint_t vbeg, kgint_t vend, int dir, arc_t **pb, arc_t **pe) { \
  33                 vertex_t *p; \
  34                 khint_t k; \
  35                 int absent; \
  36                 p = kg_put_v_##name(g, vbeg, &absent); \
  37                 k = kh_put(ehn, p->_arc, vend<<2|dir, &absent); \
  38                 *pb = &kh_val(p->_arc, k); \
  39                 p = kg_put_v_##name(g, vend, &absent); \
  40                 k = kh_put(ehn, p->_arc, vbeg<<2|(~dir&3), &absent); \
  41                 *pe = &kh_val(p->_arc, k); \
  42         } \
  43         SCOPE vertex_t *kg_del_v_##name(kgraph_t(name) *g, kgint_t v) { \
  44                 khint_t k, k0, k2, k3; \
  45                 khash_t(ehn) *h; \
  46                 k0 = k = kh_get(name, g, v); \
  47                 if (k == kh_end(g)) return 0; /* not present in the graph */ \
  48                 h = kh_val(g, k)._arc; \
  49                 for (k = kh_begin(h); k != kh_end(h); ++k) /* remove v from its neighbors */ \
  50                         if (kh_exist(h, k)) { \
  51                                 k2 = kh_get(name, g, kh_key(h, k)>>2); \
  52                                 /* assert(k2 != kh_end(g)); */ \
  53                                 k3 = kh_get(ehn, kh_val(g, k2)._arc, v<<2|(~kh_key(h, k)&3)); \
  54                                 /* assert(k3 != kh_end(kh_val(g, k2)._arc)); */ \
  55                                 kh_del(ehn, kh_val(g, k2)._arc, k3); \
  56                         } \
  57                 kh_destroy(ehn, h); \
  58                 kh_del(name, g, k0); \
  59                 return &kh_val(g, k0); \
  60         }
  61
  62 #define KGRAPH_PRINT(name, SCOPE) \
  63         SCOPE void kg_print_##name(kgraph_t(name) *g) { \
  64                 khint_t k, k2; \
  65                 for (k = kh_begin(g); k != kh_end(g); ++k) \
  66                         if (kh_exist(g, k)) { \
  67                                 printf("v %u\n", kh_key(g, k)); \
  68                                 for (k2 = kh_begin(kh_val(g, k)._arc); k2 != kh_end(kh_val(g, k)._arc); ++k2) \
  69                                         if (kh_exist(kh_val(g, k)._arc, k2) && kh_key(g, k) < kh_key(kh_val(g, k)._arc, k2)>>2) \
  70                                                 printf("a %u%c%c%u\n", kh_key(g, k), "><"[kh_key(kh_val(g, k)._arc, k2)>>1&1], \
  71                                                                 "><"[kh_key(kh_val(g, k)._arc, k2)&1], kh_key(kh_val(g, k)._arc, k2)>>2); \
  72                         } \
  73         }
  74
  75 #define KGRAPH_INIT(name, SCOPE, vertex_t, arc_t, ehn) \
  76         KHASH_INIT2(name, SCOPE, kgint_t, vertex_t, 1, kh_int_hash_func, kh_int_hash_equal) \
  77         __KG_BASIC(name, SCOPE, vertex_t, arc_t, ehn)
  78
  79 #endif