Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 80 lines (72 sloc) 2.793 kb
5eab54b Graph related routines. Unfinished. DON'T USE!
Heng Li authored
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
Something went wrong with that request. Please try again.