1 /* -*- mode: C -*- */ 2 /* 3 IGraph library. 4 Copyright (C) 2009-2012 Gabor Csardi <csardi.gabor@gmail.com> 5 334 Harvard street, Cambridge, MA 02139 USA 6 7 This program is free software; you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 2 of the License, or 10 (at your option) any later version. 11 12 This program is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with this program; if not, write to the Free Software 19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 20 02110-1301 USA 21 22 */ 23 24 #ifndef IGRAPH_ITERATORS_H 25 #define IGRAPH_ITERATORS_H 26 27 #include "igraph_decls.h" 28 #include "igraph_constants.h" 29 30 __BEGIN_DECLS 31 32 /* -------------------------------------------------- */ 33 /* Vertex selectors */ 34 /* -------------------------------------------------- */ 35 36 #define IGRAPH_VS_ALL 0 37 #define IGRAPH_VS_ADJ 1 38 #define IGRAPH_VS_NONE 2 39 #define IGRAPH_VS_1 3 40 #define IGRAPH_VS_VECTORPTR 4 41 #define IGRAPH_VS_VECTOR 5 42 #define IGRAPH_VS_SEQ 6 43 #define IGRAPH_VS_NONADJ 7 44 45 typedef struct igraph_vs_t { 46 int type; 47 union { 48 igraph_integer_t vid; /* single vertex */ 49 const igraph_vector_t *vecptr; /* vector of vertices */ 50 struct { 51 igraph_integer_t vid; 52 igraph_neimode_t mode; 53 } adj; /* adjacent vertices */ 54 struct { 55 igraph_integer_t from; 56 igraph_integer_t to; 57 } seq; /* sequence of vertices from:to */ 58 } data; 59 } igraph_vs_t; 60 61 DECLDIR int igraph_vs_all(igraph_vs_t *vs); 62 DECLDIR igraph_vs_t igraph_vss_all(void); 63 64 DECLDIR int igraph_vs_adj(igraph_vs_t *vs, 65 igraph_integer_t vid, igraph_neimode_t mode); 66 DECLDIR igraph_vs_t igraph_vss_adj(igraph_integer_t vid, igraph_neimode_t mode); 67 68 DECLDIR int igraph_vs_nonadj(igraph_vs_t *vs, igraph_integer_t vid, 69 igraph_neimode_t mode); 70 71 DECLDIR int igraph_vs_none(igraph_vs_t *vs); 72 DECLDIR igraph_vs_t igraph_vss_none(void); 73 74 DECLDIR int igraph_vs_1(igraph_vs_t *vs, igraph_integer_t vid); 75 DECLDIR igraph_vs_t igraph_vss_1(igraph_integer_t vid); 76 77 DECLDIR int igraph_vs_vector(igraph_vs_t *vs, 78 const igraph_vector_t *v); 79 DECLDIR igraph_vs_t igraph_vss_vector(const igraph_vector_t *v); 80 81 DECLDIR int igraph_vs_vector_small(igraph_vs_t *vs, ...); 82 83 DECLDIR int igraph_vs_vector_copy(igraph_vs_t *vs, 84 const igraph_vector_t *v); 85 86 DECLDIR int igraph_vs_seq(igraph_vs_t *vs, igraph_integer_t from, igraph_integer_t to); 87 DECLDIR igraph_vs_t igraph_vss_seq(igraph_integer_t from, igraph_integer_t to); 88 89 DECLDIR void igraph_vs_destroy(igraph_vs_t *vs); 90 91 DECLDIR igraph_bool_t igraph_vs_is_all(const igraph_vs_t *vs); 92 93 DECLDIR int igraph_vs_copy(igraph_vs_t* dest, const igraph_vs_t* src); 94 95 DECLDIR int igraph_vs_as_vector(const igraph_t *graph, igraph_vs_t vs, 96 igraph_vector_t *v); 97 DECLDIR int igraph_vs_size(const igraph_t *graph, const igraph_vs_t *vs, 98 igraph_integer_t *result); 99 DECLDIR int igraph_vs_type(const igraph_vs_t *vs); 100 101 /* -------------------------------------------------- */ 102 /* Vertex iterators */ 103 /* -------------------------------------------------- */ 104 105 #define IGRAPH_VIT_SEQ 0 106 #define IGRAPH_VIT_VECTOR 1 107 #define IGRAPH_VIT_VECTORPTR 2 108 109 typedef struct igraph_vit_t { 110 int type; 111 long int pos; 112 long int start; 113 long int end; 114 const igraph_vector_t *vec; 115 } igraph_vit_t; 116 117 /** 118 * \section IGRAPH_VIT Stepping over the vertices 119 * 120 * <para>After creating an iterator with \ref igraph_vit_create(), it 121 * points to the first vertex in the vertex determined by the vertex 122 * selector (if there is any). The \ref IGRAPH_VIT_NEXT() macro steps 123 * to the next vertex, \ref IGRAPH_VIT_END() checks whether there are 124 * more vertices to visit, \ref IGRAPH_VIT_SIZE() gives the total size 125 * of the vertices visited so far and to be visited. \ref 126 * IGRAPH_VIT_RESET() resets the iterator, it will point to the first 127 * vertex again. Finally \ref IGRAPH_VIT_GET() gives the current vertex 128 * pointed to by the iterator (call this only if \ref IGRAPH_VIT_END() 129 * is false). 130 * </para> 131 * <para> 132 * Here is an example on how to step over the neighbors of vertex 0: 133 * <informalexample><programlisting> 134 * igraph_vs_t vs; 135 * igraph_vit_t vit; 136 * ... 137 * igraph_vs_adj(&vs, 0, IGRAPH_ALL); 138 * igraph_vit_create(&graph, vs, &vit); 139 * while (!IGRAPH_VIT_END(vit)) { 140 * printf(" %li", (long int) IGRAPH_VIT_GET(vit)); 141 * IGRAPH_VIT_NEXT(vit); 142 * } 143 * printf("\n"); 144 * ... 145 * igraph_vit_destroy(&vit); 146 * igraph_vs_destroy(&vs); 147 * </programlisting></informalexample> 148 * </para> 149 */ 150 151 /** 152 * \define IGRAPH_VIT_NEXT 153 * \brief Next vertex. 154 * 155 * Steps the iterator to the next vertex. Only call this function if 156 * \ref IGRAPH_VIT_END() returns false. 157 * \param vit The vertex iterator to step. 158 * 159 * Time complexity: O(1). 160 */ 161 #define IGRAPH_VIT_NEXT(vit) (++((vit).pos)) 162 /** 163 * \define IGRAPH_VIT_END 164 * \brief Are we at the end? 165 * 166 * Checks whether there are more vertices to step to. 167 * \param vit The vertex iterator to check. 168 * \return Logical value, if true there are no more vertices to step 169 * to. 170 * 171 * Time complexity: O(1). 172 */ 173 #define IGRAPH_VIT_END(vit) ((vit).pos >= (vit).end) 174 /** 175 * \define IGRAPH_VIT_SIZE 176 * \brief Size of a vertex iterator. 177 * 178 * Gives the number of vertices in a vertex iterator. 179 * \param vit The vertex iterator. 180 * \return The number of vertices. 181 * 182 * Time complexity: O(1). 183 */ 184 #define IGRAPH_VIT_SIZE(vit) ((vit).end - (vit).start) 185 /** 186 * \define IGRAPH_VIT_RESET 187 * \brief Reset a vertex iterator. 188 * 189 * Resets a vertex iterator. After calling this macro the iterator 190 * will point to the first vertex. 191 * \param vit The vertex iterator. 192 * 193 * Time complexity: O(1). 194 */ 195 #define IGRAPH_VIT_RESET(vit) ((vit).pos = (vit).start) 196 /** 197 * \define IGRAPH_VIT_GET 198 * \brief Query the current position. 199 * 200 * Gives the vertex id of the current vertex pointed to by the 201 * iterator. 202 * \param vit The vertex iterator. 203 * \return The vertex id of the current vertex. 204 * 205 * Time complexity: O(1). 206 */ 207 #define IGRAPH_VIT_GET(vit) \ 208 ((igraph_integer_t)(((vit).type == IGRAPH_VIT_SEQ) ? (vit).pos : \ 209 VECTOR(*(vit).vec)[(vit).pos])) 210 211 DECLDIR int igraph_vit_create(const igraph_t *graph, 212 igraph_vs_t vs, igraph_vit_t *vit); 213 DECLDIR void igraph_vit_destroy(const igraph_vit_t *vit); 214 215 DECLDIR int igraph_vit_as_vector(const igraph_vit_t *vit, igraph_vector_t *v); 216 217 /* -------------------------------------------------- */ 218 /* Edge Selectors */ 219 /* -------------------------------------------------- */ 220 221 #define IGRAPH_ES_ALL 0 222 #define IGRAPH_ES_ALLFROM 1 223 #define IGRAPH_ES_ALLTO 2 224 #define IGRAPH_ES_INCIDENT 3 225 #define IGRAPH_ES_NONE 4 226 #define IGRAPH_ES_1 5 227 #define IGRAPH_ES_VECTORPTR 6 228 #define IGRAPH_ES_VECTOR 7 229 #define IGRAPH_ES_SEQ 8 230 #define IGRAPH_ES_PAIRS 9 231 #define IGRAPH_ES_PATH 10 232 #define IGRAPH_ES_MULTIPAIRS 11 233 234 typedef struct igraph_es_t { 235 int type; 236 union { 237 igraph_integer_t vid; 238 igraph_integer_t eid; 239 const igraph_vector_t *vecptr; 240 struct { 241 igraph_integer_t vid; 242 igraph_neimode_t mode; 243 } incident; 244 struct { 245 igraph_integer_t from; 246 igraph_integer_t to; 247 } seq; 248 struct { 249 const igraph_vector_t *ptr; 250 igraph_bool_t mode; 251 } path; 252 } data; 253 } igraph_es_t; 254 255 DECLDIR int igraph_es_all(igraph_es_t *es, 256 igraph_edgeorder_type_t order); 257 DECLDIR igraph_es_t igraph_ess_all(igraph_edgeorder_type_t order); 258 259 DECLDIR int igraph_es_adj(igraph_es_t *es, 260 igraph_integer_t vid, igraph_neimode_t mode); /* deprecated */ 261 DECLDIR int igraph_es_incident(igraph_es_t *es, 262 igraph_integer_t vid, igraph_neimode_t mode); 263 264 DECLDIR int igraph_es_none(igraph_es_t *es); 265 DECLDIR igraph_es_t igraph_ess_none(void); 266 267 DECLDIR int igraph_es_1(igraph_es_t *es, igraph_integer_t eid); 268 DECLDIR igraph_es_t igraph_ess_1(igraph_integer_t eid); 269 270 DECLDIR int igraph_es_vector(igraph_es_t *es, 271 const igraph_vector_t *v); 272 DECLDIR igraph_es_t igraph_ess_vector(const igraph_vector_t *v); 273 274 DECLDIR int igraph_es_fromto(igraph_es_t *es, 275 igraph_vs_t from, igraph_vs_t to); 276 277 DECLDIR int igraph_es_seq(igraph_es_t *es, igraph_integer_t from, igraph_integer_t to); 278 DECLDIR igraph_es_t igraph_ess_seq(igraph_integer_t from, igraph_integer_t to); 279 280 DECLDIR int igraph_es_vector_copy(igraph_es_t *es, const igraph_vector_t *v); 281 282 DECLDIR int igraph_es_pairs(igraph_es_t *es, const igraph_vector_t *v, 283 igraph_bool_t directed); 284 DECLDIR int igraph_es_pairs_small(igraph_es_t *es, igraph_bool_t directed, ...); 285 286 DECLDIR int igraph_es_multipairs(igraph_es_t *es, const igraph_vector_t *v, 287 igraph_bool_t directed); 288 289 DECLDIR int igraph_es_path(igraph_es_t *es, const igraph_vector_t *v, 290 igraph_bool_t directed); 291 DECLDIR int igraph_es_path_small(igraph_es_t *es, igraph_bool_t directed, ...); 292 293 DECLDIR void igraph_es_destroy(igraph_es_t *es); 294 295 DECLDIR igraph_bool_t igraph_es_is_all(const igraph_es_t *es); 296 297 DECLDIR int igraph_es_copy(igraph_es_t* dest, const igraph_es_t* src); 298 299 DECLDIR int igraph_es_as_vector(const igraph_t *graph, igraph_es_t es, 300 igraph_vector_t *v); 301 DECLDIR int igraph_es_size(const igraph_t *graph, const igraph_es_t *es, 302 igraph_integer_t *result); 303 DECLDIR int igraph_es_type(const igraph_es_t *es); 304 305 306 /* -------------------------------------------------- */ 307 /* Edge Iterators */ 308 /* -------------------------------------------------- */ 309 310 #define IGRAPH_EIT_SEQ 0 311 #define IGRAPH_EIT_VECTOR 1 312 #define IGRAPH_EIT_VECTORPTR 2 313 314 typedef struct igraph_eit_t { 315 int type; 316 long int pos; 317 long int start; 318 long int end; 319 const igraph_vector_t *vec; 320 } igraph_eit_t; 321 322 /** 323 * \section IGRAPH_EIT Stepping over the edges 324 * 325 * <para>Just like for vertex iterators, macros are provided for 326 * stepping over a sequence of edges: \ref IGRAPH_EIT_NEXT() goes to 327 * the next edge, \ref IGRAPH_EIT_END() checks whether there are more 328 * edges to visit, \ref IGRAPH_EIT_SIZE() gives the number of edges in 329 * the edge sequence, \ref IGRAPH_EIT_RESET() resets the iterator to 330 * the first edge and \ref IGRAPH_EIT_GET() returns the id of the 331 * current edge.</para> 332 */ 333 334 /** 335 * \define IGRAPH_EIT_NEXT 336 * \brief Next edge. 337 * 338 * Steps the iterator to the next edge. Call this function only if 339 * \ref IGRAPH_EIT_END() returns false. 340 * \param eit The edge iterator to step. 341 * 342 * Time complexity: O(1). 343 */ 344 #define IGRAPH_EIT_NEXT(eit) (++((eit).pos)) 345 /** 346 * \define IGRAPH_EIT_END 347 * \brief Are we at the end? 348 * 349 * Checks whether there are more edges to step to. 350 * \param wit The edge iterator to check. 351 * \return Logical value, if true there are no more edges 352 * to step to. 353 * 354 * Time complexity: O(1). 355 */ 356 #define IGRAPH_EIT_END(eit) ((eit).pos >= (eit).end) 357 /** 358 * \define IGRAPH_EIT_SIZE 359 * \brief Number of edges in the iterator. 360 * 361 * Gives the number of edges in an edge iterator. 362 * \param eit The edge iterator. 363 * \return The number of edges. 364 * 365 * Time complexity: O(1). 366 */ 367 #define IGRAPH_EIT_SIZE(eit) ((eit).end - (eit).start) 368 /** 369 * \define IGRAPH_EIT_RESET 370 * \brief Reset an edge iterator. 371 * 372 * Resets an edge iterator. After calling this macro the iterator will 373 * point to the first edge. 374 * \param eit The edge iterator. 375 * 376 * Time complexity: O(1). 377 */ 378 #define IGRAPH_EIT_RESET(eit) ((eit).pos = (eit).start) 379 /** 380 * \define IGRAPH_EIT_GET 381 * \brief Query an edge iterator. 382 * 383 * Gives the edge id of the current edge pointed to by an iterator. 384 * \param eit The edge iterator. 385 * \return The id of the current edge. 386 * 387 * Time complexity: O(1). 388 */ 389 #define IGRAPH_EIT_GET(eit) \ 390 (igraph_integer_t)((((eit).type == IGRAPH_EIT_SEQ) ? (eit).pos : \ 391 VECTOR(*(eit).vec)[(eit).pos])) 392 393 DECLDIR int igraph_eit_create(const igraph_t *graph, 394 igraph_es_t es, igraph_eit_t *eit); 395 DECLDIR void igraph_eit_destroy(const igraph_eit_t *eit); 396 397 DECLDIR int igraph_eit_as_vector(const igraph_eit_t *eit, igraph_vector_t *v); 398 399 __END_DECLS 400 401 #endif 402