1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395
|
/* -*- mode: C -*- */
/*
IGraph library.
Copyright (C) 2009-2012 Gabor Csardi <csardi.gabor@gmail.com>
334 Harvard street, Cambridge, MA 02139 USA
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA
*/
#ifndef IGRAPH_TYPES_INTERNAL_H
#define IGRAPH_TYPES_INTERNAL_H
#undef __BEGIN_DECLS
#undef __END_DECLS
#ifdef __cplusplus
# define __BEGIN_DECLS extern "C" {
# define __END_DECLS }
#else
# define __BEGIN_DECLS /* empty */
# define __END_DECLS /* empty */
#endif
#include "igraph_types.h"
#include "igraph_matrix.h"
#include "igraph_stack.h"
#include "igraph_strvector.h"
#include "igraph_vector.h"
#include "igraph_vector_ptr.h"
__BEGIN_DECLS
/* -------------------------------------------------- */
/* Indexed heap */
/* -------------------------------------------------- */
/**
* Indexed heap data type.
* \ingroup internal
*/
typedef struct s_indheap {
igraph_real_t* stor_begin;
igraph_real_t* stor_end;
igraph_real_t* end;
int destroy;
long int* index_begin;
} igraph_indheap_t;
#define IGRAPH_INDHEAP_NULL { 0,0,0,0,0 }
int igraph_indheap_init (igraph_indheap_t* h, long int size);
int igraph_indheap_init_array (igraph_indheap_t *t, igraph_real_t* data, long int len);
void igraph_indheap_destroy (igraph_indheap_t* h);
int igraph_indheap_clear(igraph_indheap_t *h);
igraph_bool_t igraph_indheap_empty (igraph_indheap_t* h);
int igraph_indheap_push (igraph_indheap_t* h, igraph_real_t elem);
int igraph_indheap_push_with_index(igraph_indheap_t* h, long int idx, igraph_real_t elem);
int igraph_indheap_modify(igraph_indheap_t* h, long int idx, igraph_real_t elem);
igraph_real_t igraph_indheap_max (igraph_indheap_t* h);
igraph_real_t igraph_indheap_delete_max(igraph_indheap_t* h);
long int igraph_indheap_size (igraph_indheap_t* h);
int igraph_indheap_reserve (igraph_indheap_t* h, long int size);
long int igraph_indheap_max_index(igraph_indheap_t *h);
void igraph_indheap_i_build(igraph_indheap_t* h, long int head);
void igraph_indheap_i_shift_up(igraph_indheap_t* h, long int elem);
void igraph_indheap_i_sink(igraph_indheap_t* h, long int head);
void igraph_indheap_i_switch(igraph_indheap_t* h, long int e1, long int e2);
/* -------------------------------------------------- */
/* Doubly indexed heap */
/* -------------------------------------------------- */
/* This is a heap containing double elements and
two indices, its intended usage is the storage of
weighted edges.
*/
/**
* Doubly indexed heap data type.
* \ingroup internal
*/
typedef struct s_indheap_d {
igraph_real_t* stor_begin;
igraph_real_t* stor_end;
igraph_real_t* end;
int destroy;
long int* index_begin;
long int* index2_begin;
} igraph_d_indheap_t;
#define IGRAPH_D_INDHEAP_NULL { 0,0,0,0,0,0 }
int igraph_d_indheap_init (igraph_d_indheap_t* h, long int size);
void igraph_d_indheap_destroy (igraph_d_indheap_t* h);
igraph_bool_t igraph_d_indheap_empty (igraph_d_indheap_t* h);
int igraph_d_indheap_push (igraph_d_indheap_t* h, igraph_real_t elem,
long int idx, long int idx2);
igraph_real_t igraph_d_indheap_max (igraph_d_indheap_t* h);
igraph_real_t igraph_d_indheap_delete_max(igraph_d_indheap_t* h);
long int igraph_d_indheap_size (igraph_d_indheap_t* h);
int igraph_d_indheap_reserve (igraph_d_indheap_t* h, long int size);
void igraph_d_indheap_max_index(igraph_d_indheap_t *h, long int *idx, long int *idx2);
void igraph_d_indheap_i_build(igraph_d_indheap_t* h, long int head);
void igraph_d_indheap_i_shift_up(igraph_d_indheap_t* h, long int elem);
void igraph_d_indheap_i_sink(igraph_d_indheap_t* h, long int head);
void igraph_d_indheap_i_switch(igraph_d_indheap_t* h, long int e1, long int e2);
/* -------------------------------------------------- */
/* Two-way indexed heap */
/* -------------------------------------------------- */
/* This is a smart indexed heap. In addition to the "normal" indexed heap
it allows to access every element through its index in O(1) time.
In other words, for this heap the _modify operation is O(1), the
normal heap does this in O(n) time.... */
typedef struct igraph_2wheap_t {
long int size;
igraph_vector_t data;
igraph_vector_long_t index;
igraph_vector_long_t index2;
} igraph_2wheap_t;
int igraph_2wheap_init(igraph_2wheap_t *h, long int size);
void igraph_2wheap_destroy(igraph_2wheap_t *h);
int igraph_2wheap_clear(igraph_2wheap_t *h);
int igraph_2wheap_push_with_index(igraph_2wheap_t *h,
long int idx, igraph_real_t elem);
igraph_bool_t igraph_2wheap_empty(const igraph_2wheap_t *h);
long int igraph_2wheap_size(const igraph_2wheap_t *h);
long int igraph_2wheap_max_size(const igraph_2wheap_t *h);
igraph_real_t igraph_2wheap_max(const igraph_2wheap_t *h);
long int igraph_2wheap_max_index(const igraph_2wheap_t *h);
igraph_real_t igraph_2wheap_deactivate_max(igraph_2wheap_t *h);
igraph_bool_t igraph_2wheap_has_elem(const igraph_2wheap_t *h, long int idx);
igraph_bool_t igraph_2wheap_has_active(const igraph_2wheap_t *h, long int idx);
igraph_real_t igraph_2wheap_get(const igraph_2wheap_t *h, long int idx);
igraph_real_t igraph_2wheap_delete_max(igraph_2wheap_t *h);
igraph_real_t igraph_2wheap_delete_max_index(igraph_2wheap_t *h, long int *idx);
int igraph_2wheap_modify(igraph_2wheap_t *h, long int idx, igraph_real_t elem);
int igraph_2wheap_check(igraph_2wheap_t *h);
/**
* Trie data type
* \ingroup internal
*/
typedef struct s_igraph_trie_node {
igraph_strvector_t strs;
igraph_vector_ptr_t children;
igraph_vector_t values;
} igraph_trie_node_t;
typedef struct s_igraph_trie {
igraph_strvector_t strs;
igraph_vector_ptr_t children;
igraph_vector_t values;
long int maxvalue;
igraph_bool_t storekeys;
igraph_strvector_t keys;
} igraph_trie_t;
#define IGRAPH_TRIE_NULL { IGRAPH_STRVECTOR_NULL, IGRAPH_VECTOR_PTR_NULL, \
IGRAPH_VECTOR_NULL, 0, 0, IGRAPH_STRVECTOR_NULL }
#define IGRAPH_TRIE_INIT_FINALLY(tr, sk) \
do { IGRAPH_CHECK(igraph_trie_init(tr, sk)); \
IGRAPH_FINALLY(igraph_trie_destroy, tr); } while (0)
int igraph_trie_init(igraph_trie_t *t, igraph_bool_t storekeys);
void igraph_trie_destroy(igraph_trie_t *t);
int igraph_trie_get(igraph_trie_t *t, const char *key, long int *id);
int igraph_trie_check(igraph_trie_t *t, const char *key, long int *id);
int igraph_trie_get2(igraph_trie_t *t, const char *key, long int length,
long int *id);
void igraph_trie_idx(igraph_trie_t *t, long int idx, char **str);
int igraph_trie_getkeys(igraph_trie_t *t, const igraph_strvector_t **strv);
long int igraph_trie_size(igraph_trie_t *t);
/**
* 2d grid containing points
*/
typedef struct igraph_2dgrid_t {
igraph_matrix_t *coords;
igraph_real_t minx, maxx, deltax;
igraph_real_t miny, maxy, deltay;
long int stepsx, stepsy;
igraph_matrix_t startidx;
igraph_vector_t next;
igraph_vector_t prev;
igraph_real_t massx, massy; /* The sum of the coordinates */
long int vertices; /* Number of active vertices */
} igraph_2dgrid_t;
int igraph_2dgrid_init(igraph_2dgrid_t *grid, igraph_matrix_t *coords,
igraph_real_t minx, igraph_real_t maxx, igraph_real_t deltax,
igraph_real_t miny, igraph_real_t maxy, igraph_real_t deltay);
void igraph_2dgrid_destroy(igraph_2dgrid_t *grid);
void igraph_2dgrid_add(igraph_2dgrid_t *grid, long int elem,
igraph_real_t xc, igraph_real_t yc);
void igraph_2dgrid_add2(igraph_2dgrid_t *grid, long int elem);
void igraph_2dgrid_move(igraph_2dgrid_t *grid, long int elem,
igraph_real_t xc, igraph_real_t yc);
void igraph_2dgrid_getcenter(const igraph_2dgrid_t *grid,
igraph_real_t *massx, igraph_real_t *massy);
igraph_bool_t igraph_2dgrid_in(const igraph_2dgrid_t *grid, long int elem);
igraph_real_t igraph_2dgrid_dist(const igraph_2dgrid_t *grid,
long int e1, long int e2);
int igraph_2dgrid_neighbors(igraph_2dgrid_t *grid, igraph_vector_t *eids,
igraph_integer_t vid, igraph_real_t r);
typedef struct igraph_2dgrid_iterator_t {
long int vid, x, y;
long int nei;
long int nx[4], ny[4], ncells;
} igraph_2dgrid_iterator_t;
void igraph_2dgrid_reset(igraph_2dgrid_t *grid, igraph_2dgrid_iterator_t *it);
igraph_integer_t igraph_2dgrid_next(igraph_2dgrid_t *grid,
igraph_2dgrid_iterator_t *it);
igraph_integer_t igraph_2dgrid_next_nei(igraph_2dgrid_t *grid,
igraph_2dgrid_iterator_t *it);
/* Another type of grid, each cell is owned by exactly one graph */
typedef struct igraph_i_layout_mergegrid_t {
long int *data;
long int stepsx, stepsy;
igraph_real_t minx, maxx, deltax;
igraph_real_t miny, maxy, deltay;
} igraph_i_layout_mergegrid_t;
int igraph_i_layout_mergegrid_init(igraph_i_layout_mergegrid_t *grid,
igraph_real_t minx, igraph_real_t maxx, long int stepsx,
igraph_real_t miny, igraph_real_t maxy, long int stepsy);
void igraph_i_layout_mergegrid_destroy(igraph_i_layout_mergegrid_t *grid);
int igraph_i_layout_merge_place_sphere(igraph_i_layout_mergegrid_t *grid,
igraph_real_t x, igraph_real_t y, igraph_real_t r,
long int id);
long int igraph_i_layout_mergegrid_get(igraph_i_layout_mergegrid_t *grid,
igraph_real_t x, igraph_real_t y);
long int igraph_i_layout_mergegrid_get_sphere(igraph_i_layout_mergegrid_t *g,
igraph_real_t x, igraph_real_t y, igraph_real_t r);
/* string -> string hash table */
typedef struct igraph_hashtable_t {
igraph_trie_t keys;
igraph_strvector_t elements;
igraph_strvector_t defaults;
} igraph_hashtable_t;
int igraph_hashtable_init(igraph_hashtable_t *ht);
void igraph_hashtable_destroy(igraph_hashtable_t *ht);
int igraph_hashtable_addset(igraph_hashtable_t *ht,
const char *key, const char *def,
const char *elem);
int igraph_hashtable_addset2(igraph_hashtable_t *ht,
const char *key, const char *def,
const char *elem, int elemlen);
int igraph_hashtable_get(igraph_hashtable_t *ht,
const char *key, char **elem);
int igraph_hashtable_getkeys(igraph_hashtable_t *ht,
const igraph_strvector_t **sv);
int igraph_hashtable_reset(igraph_hashtable_t *ht);
/* Buckets, needed for the maximum flow algorithm */
typedef struct igraph_buckets_t {
igraph_vector_long_t bptr;
igraph_vector_long_t buckets;
igraph_integer_t max, no;
} igraph_buckets_t;
int igraph_buckets_init(igraph_buckets_t *b, long int bsize, long int size);
void igraph_buckets_destroy(igraph_buckets_t *b);
void igraph_buckets_clear(igraph_buckets_t *b);
long int igraph_buckets_popmax(igraph_buckets_t *b);
long int igraph_buckets_pop(igraph_buckets_t *b, long int bucket);
igraph_bool_t igraph_buckets_empty(const igraph_buckets_t *b);
igraph_bool_t igraph_buckets_empty_bucket(const igraph_buckets_t *b,
long int bucket);
void igraph_buckets_add(igraph_buckets_t *b, long int bucket,
long int elem);
typedef struct igraph_dbuckets_t {
igraph_vector_long_t bptr;
igraph_vector_long_t next, prev;
igraph_integer_t max, no;
} igraph_dbuckets_t;
int igraph_dbuckets_init(igraph_dbuckets_t *b, long int bsize, long int size);
void igraph_dbuckets_destroy(igraph_dbuckets_t *b);
void igraph_dbuckets_clear(igraph_dbuckets_t *b);
long int igraph_dbuckets_popmax(igraph_dbuckets_t *b);
long int igraph_dbuckets_pop(igraph_dbuckets_t *b, long int bucket);
igraph_bool_t igraph_dbuckets_empty(const igraph_dbuckets_t *b);
igraph_bool_t igraph_dbuckets_empty_bucket(const igraph_dbuckets_t *b,
long int bucket);
void igraph_dbuckets_add(igraph_dbuckets_t *b, long int bucket,
long int elem);
void igraph_dbuckets_delete(igraph_dbuckets_t *b, long int bucket,
long int elem);
/* Special maximum heap, needed for the minimum cut algorithm */
typedef struct igraph_i_cutheap_t {
igraph_vector_t heap;
igraph_vector_t index;
igraph_vector_t hptr;
long int dnodes;
} igraph_i_cutheap_t;
int igraph_i_cutheap_init(igraph_i_cutheap_t *ch, igraph_integer_t nodes);
void igraph_i_cutheap_destroy(igraph_i_cutheap_t *ch);
igraph_bool_t igraph_i_cutheap_empty(igraph_i_cutheap_t *ch);
igraph_integer_t igraph_i_cutheap_active_size(igraph_i_cutheap_t *ch);
igraph_integer_t igraph_i_cutheap_size(igraph_i_cutheap_t *ch);
igraph_real_t igraph_i_cutheap_maxvalue(igraph_i_cutheap_t *ch);
igraph_integer_t igraph_i_cutheap_popmax(igraph_i_cutheap_t *ch);
int igraph_i_cutheap_update(igraph_i_cutheap_t *ch, igraph_integer_t index,
igraph_real_t add);
int igraph_i_cutheap_reset_undefine(igraph_i_cutheap_t *ch, long int vertex);
/* -------------------------------------------------- */
/* Flexible set */
/* -------------------------------------------------- */
/**
* Set containing integer numbers regardless of the order
* \ingroup types
*/
typedef struct s_set {
igraph_integer_t* stor_begin;
igraph_integer_t* stor_end;
igraph_integer_t* end;
} igraph_set_t;
#define IGRAPH_SET_NULL { 0,0,0 }
#define IGRAPH_SET_INIT_FINALLY(v, size) \
do { IGRAPH_CHECK(igraph_set_init(v, size)); \
IGRAPH_FINALLY(igraph_set_destroy, v); } while (0)
int igraph_set_init (igraph_set_t* set, long int size);
void igraph_set_destroy (igraph_set_t* set);
igraph_bool_t igraph_set_inited (igraph_set_t* set);
int igraph_set_reserve (igraph_set_t* set, long int size);
igraph_bool_t igraph_set_empty (const igraph_set_t* set);
void igraph_set_clear (igraph_set_t* set);
long int igraph_set_size (const igraph_set_t* set);
int igraph_set_add (igraph_set_t* v, igraph_integer_t e);
igraph_bool_t igraph_set_contains (igraph_set_t* set, igraph_integer_t e);
igraph_bool_t igraph_set_iterate (igraph_set_t* set, long int* state,
igraph_integer_t* element);
/* -------------------------------------------------- */
/* Vectorlist, fixed length */
/* -------------------------------------------------- */
typedef struct igraph_fixed_vectorlist_t {
igraph_vector_t *vecs;
igraph_vector_ptr_t v;
long int length;
} igraph_fixed_vectorlist_t;
void igraph_fixed_vectorlist_destroy(igraph_fixed_vectorlist_t *l);
int igraph_fixed_vectorlist_convert(igraph_fixed_vectorlist_t *l,
const igraph_vector_t *from,
long int size);
__END_DECLS
#endif
|