/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2005-2012 Gabor Csardi 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 */ #include "igraph_iterators.h" #include "igraph_memory.h" #include "igraph_random.h" #include "igraph_interface.h" #include "config.h" #include #include /** * \section about_iterators About selectors, iterators * * Everything about vertices and vertex selectors also applies * to edges and edge selectors unless explicitly noted otherwise. * * The vertex (and edge) selector notion was introduced in igraph 0.2. * It is a way to reference a sequence of vertices or edges * independently of the graph. * * While this might sound quite mysterious, it is actually very * simple. For example, all vertices of a graph can be selected by * \ref igraph_vs_all() and the graph independence means that * \ref igraph_vs_all() is not parametrized by a graph object. That is, * \ref igraph_vs_all() is the general \em concept of selecting all vertices * of a graph. A vertex selector is then a way to specify the class of vertices * to be visited. The selector might specify that all vertices of a graph or * all the neighbours of a vertex are to be visited. A vertex selector is a * way of saying that you want to visit a bunch of vertices, as opposed to a * vertex iterator which is a concrete plan for visiting each of the * chosen vertices of a specific graph. * * To determine the actual vertex IDs implied by a vertex selector, you * need to apply the concept of selecting vertices to a specific graph object. * This can be accomplished by instantiating a vertex iterator using a * specific vertex selection concept and a specific graph object. The notion * of vertex iterators can be thought of in the following way. Given a * specific graph object and the class of vertices to be visited, a vertex * iterator is a road map, plan or route for how to visit the chosen * vertices. * * Some vertex selectors have \em immediate versions. These have the * prefix \c igraph_vss instead of \c igraph_vs, e.g. \ref igraph_vss_all() * instead of \ref igraph_vs_all(). The immediate versions are to be used in * the parameter list of the igraph functions, such as \ref igraph_degree(). * These functions are not associated with any \type igraph_vs_t object, so * they have no separate constructors and destructors * (destroy functions). */ /** * \section about_vertex_selectors * * Vertex selectors are created by vertex selector constructors, * can be instantiated with \ref igraph_vit_create(), and are * destroyed with \ref igraph_vs_destroy(). */ /** * \function igraph_vs_all * \brief Vertex set, all vertices of a graph. * * \param vs Pointer to an uninitialized \type igraph_vs_t object. * \return Error code. * \sa \ref igraph_vss_all(), \ref igraph_vs_destroy() * * This selector includes all vertices of a given graph in * increasing vertex id order. * * * Time complexity: O(1). */ int igraph_vs_all(igraph_vs_t *vs) { vs->type = IGRAPH_VS_ALL; return 0; } /** * \function igraph_vss_all * \brief All vertices of a graph (immediate version). * * Immediate vertex selector for all vertices in a graph. It can * be used conveniently when some vertex property (eg. betweenness, * degree, etc.) should be calculated for all vertices. * * \return A vertex selector for all vertices in a graph. * \sa \ref igraph_vs_all() * * Time complexity: O(1). */ igraph_vs_t igraph_vss_all(void) { igraph_vs_t allvs; allvs.type = IGRAPH_VS_ALL; return allvs; } /** * \function igraph_vs_adj * \brief Adjacent vertices of a vertex. * * All neighboring vertices of a given vertex are selected by this * selector. The \c mode argument controls the type of the neighboring * vertices to be selected. The vertices are visited in increasing vertex * ID order, as of igraph version 0.4. * * \param vs Pointer to an uninitialized vertex selector object. * \param vid Vertex ID, the center of the neighborhood. * \param mode Decides the type of the neighborhood for directed * graphs. This parameter is ignored for undirected graphs. * Possible values: * \clist * \cli IGRAPH_OUT * All vertices to which there is a directed edge from \c vid. That * is, all the out-neighbors of \c vid. * \cli IGRAPH_IN * All vertices from which there is a directed edge to \c vid. In * other words, all the in-neighbors of \c vid. * \cli IGRAPH_ALL * All vertices to which or from which there is a directed edge * from/to \c vid. That is, all the neighbors of \c vid considered * as if the graph is undirected. * \endclist * \return Error code. * \sa \ref igraph_vs_destroy() * * Time complexity: O(1). */ int igraph_vs_adj(igraph_vs_t *vs, igraph_integer_t vid, igraph_neimode_t mode) { vs->type = IGRAPH_VS_ADJ; vs->data.adj.vid = vid; vs->data.adj.mode = mode; return 0; } /** * \function igraph_vs_nonadj * \brief Non-adjacent vertices of a vertex. * * All non-neighboring vertices of a given vertex. The \p mode * argument controls the type of neighboring vertices \em not to * select. Instead of selecting immediate neighbors of \c vid as is done by * \ref igraph_vs_adj(), the current function selects vertices that are \em not * immediate neighbors of \c vid. * * \param vs Pointer to an uninitialized vertex selector object. * \param vid Vertex ID, the \quote center \endquote of the * non-neighborhood. * \param mode The type of neighborhood not to select in directed * graphs. Possible values: * \clist * \cli IGRAPH_OUT * All vertices will be selected except those to which there is a * directed edge from \c vid. That is, we select all vertices * excluding the out-neighbors of \c vid. * \cli IGRAPH_IN * All vertices will be selected except those from which there is a * directed edge to \c vid. In other words, we select all vertices * but the in-neighbors of \c vid. * \cli IGRAPH_ALL * All vertices will be selected except those from or to which there * is a directed edge to or from \c vid. That is, we select all * vertices of \c vid except for its immediate neighbors. * \endclist * \return Error code. * \sa \ref igraph_vs_destroy() * * Time complexity: O(1). * * \example examples/simple/igraph_vs_nonadj.c */ int igraph_vs_nonadj(igraph_vs_t *vs, igraph_integer_t vid, igraph_neimode_t mode) { vs->type = IGRAPH_VS_NONADJ; vs->data.adj.vid = vid; vs->data.adj.mode = mode; return 0; } /** * \function igraph_vs_none * \brief Empty vertex set. * * Creates an empty vertex selector. * * \param vs Pointer to an uninitialized vertex selector object. * \return Error code. * \sa \ref igraph_vss_none(), \ref igraph_vs_destroy() * * Time complexity: O(1). */ int igraph_vs_none(igraph_vs_t *vs) { vs->type = IGRAPH_VS_NONE; return 0; } /** * \function igraph_vss_none * \brief Empty vertex set (immediate version). * * The immediate version of the empty vertex selector. * * \return An empty vertex selector. * \sa \ref igraph_vs_none() * * Time complexity: O(1). */ igraph_vs_t igraph_vss_none(void) { igraph_vs_t nonevs; nonevs.type = IGRAPH_VS_NONE; return nonevs; } /** * \function igraph_vs_1 * \brief Vertex set with a single vertex. * * This vertex selector selects a single vertex. * * \param vs Pointer to an uninitialized vertex selector object. * \param vid The vertex id to be selected. * \return Error Code. * \sa \ref igraph_vss_1(), \ref igraph_vs_destroy() * * Time complexity: O(1). */ int igraph_vs_1(igraph_vs_t *vs, igraph_integer_t vid) { vs->type = IGRAPH_VS_1; vs->data.vid = vid; return 0; } /** * \function igraph_vss_1 * \brief Vertex set with a single vertex (immediate version). * * The immediate version of the single-vertex selector. * * \param vid The vertex to be selected. * \return A vertex selector containing a single vertex. * \sa \ref igraph_vs_1() * * Time complexity: O(1). */ igraph_vs_t igraph_vss_1(igraph_integer_t vid) { igraph_vs_t onevs; onevs.type = IGRAPH_VS_1; onevs.data.vid = vid; return onevs; } /** * \function igraph_vs_vector * \brief Vertex set based on a vector. * * This function makes it possible to handle a \type vector_t * temporarily as a vertex selector. The vertex selector should be * thought of like a \em view to the vector. If you make changes to * the vector that also affects the vertex selector. Destroying the * vertex selector does not destroy the vector. (Of course.) Do not * destroy the vector before destroying the vertex selector, or you * might get strange behavior. * * \param vs Pointer to an uninitialized vertex selector. * \param v Pointer to a \type igraph_vector_t object. * \return Error code. * \sa \ref igraph_vss_vector(), \ref igraph_vs_destroy() * * Time complexity: O(1). * * \example examples/simple/igraph_vs_vector.c */ int igraph_vs_vector(igraph_vs_t *vs, const igraph_vector_t *v) { vs->type = IGRAPH_VS_VECTORPTR; vs->data.vecptr = v; return 0; } /** * \function igraph_vss_vector * \brief Vertex set based on a vector (immediate version). * * This is the immediate version of \ref igraph_vs_vector. * * \param v Pointer to a \type igraph_vector_t object. * \return A vertex selector object containing the vertices in the * vector. * \sa \ref igraph_vs_vector() * * Time complexity: O(1). */ igraph_vs_t igraph_vss_vector(const igraph_vector_t *v) { igraph_vs_t vecvs; vecvs.type = IGRAPH_VS_VECTORPTR; vecvs.data.vecptr = v; return vecvs; } /** * \function igraph_vs_vector_small * \brief Create a vertex set by giving its elements. * * This function can be used to create a vertex selector with a couple * of vertices. Do not forget to include a -1 after the * last vertex id. The behavior of the function is undefined if you * don't use a -1 properly. * * * Note that the vertex ids supplied will be parsed as * int's so you cannot supply arbitrarily large (too * large for int) vertex ids here. * * \param vs Pointer to an uninitialized vertex selector object. * \param ... Additional parameters, these will be the vertex ids to * be included in the vertex selector. Supply a -1 * after the last vertex id. * \return Error code. * \sa \ref igraph_vs_destroy() * * Time complexity: O(n), the number of vertex ids supplied. */ int igraph_vs_vector_small(igraph_vs_t *vs, ...) { va_list ap; long int i, n = 0; vs->type = IGRAPH_VS_VECTOR; vs->data.vecptr = igraph_Calloc(1, igraph_vector_t); if (vs->data.vecptr == 0) { IGRAPH_ERROR("Cannot create vertex selector", IGRAPH_ENOMEM); } IGRAPH_FINALLY(igraph_free, (igraph_vector_t*)vs->data.vecptr); va_start(ap, vs); while (1) { int num = va_arg(ap, int); if (num == -1) { break; } n++; } va_end(ap); IGRAPH_VECTOR_INIT_FINALLY((igraph_vector_t*)vs->data.vecptr, n); va_start(ap, vs); for (i = 0; i < n; i++) { VECTOR(*vs->data.vecptr)[i] = (igraph_real_t) va_arg(ap, int); } va_end(ap); IGRAPH_FINALLY_CLEAN(2); return 0; } /** * \function igraph_vs_vector_copy * \brief Vertex set based on a vector, with copying. * * This function makes it possible to handle a \type vector_t * permanently as a vertex selector. The vertex selector creates a * copy of the original vector, so the vector can safely be destroyed * after creating the vertex selector. Changing the original vector * will not affect the vertex selector. The vertex selector is * responsible for deleting the copy made by itself. * * \param vs Pointer to an uninitialized vertex selector. * \param v Pointer to a \type igraph_vector_t object. * \return Error code. * \sa \ref igraph_vs_destroy() * * Time complexity: O(1). */ int igraph_vs_vector_copy(igraph_vs_t *vs, const igraph_vector_t *v) { vs->type = IGRAPH_VS_VECTOR; vs->data.vecptr = igraph_Calloc(1, igraph_vector_t); if (vs->data.vecptr == 0) { IGRAPH_ERROR("Cannot create vertex selector", IGRAPH_ENOMEM); } IGRAPH_FINALLY(igraph_free, (igraph_vector_t*)vs->data.vecptr); IGRAPH_CHECK(igraph_vector_copy((igraph_vector_t*)vs->data.vecptr, v)); IGRAPH_FINALLY_CLEAN(1); return 0; } /** * \function igraph_vs_seq * \brief Vertex set, an interval of vertices. * * Creates a vertex selector containing all vertices with vertex id * equal to or bigger than \c from and equal to or smaller than \c * to. * * \param vs Pointer to an uninitialized vertex selector object. * \param from The first vertex id to be included in the vertex * selector. * \param to The last vertex id to be included in the vertex * selector. * \return Error code. * \sa \ref igraph_vss_seq(), \ref igraph_vs_destroy() * * Time complexity: O(1). * * \example examples/simple/igraph_vs_seq.c */ int igraph_vs_seq(igraph_vs_t *vs, igraph_integer_t from, igraph_integer_t to) { vs->type = IGRAPH_VS_SEQ; vs->data.seq.from = from; vs->data.seq.to = to + 1; return 0; } /** * \function igraph_vss_seq * \brief An interval of vertices (immediate version). * * The immediate version of \ref igraph_vs_seq(). * * \param from The first vertex id to be included in the vertex * selector. * \param to The last vertex id to be included in the vertex * selector. * \return Error code. * \sa \ref igraph_vs_seq() * * Time complexity: O(1). */ igraph_vs_t igraph_vss_seq(igraph_integer_t from, igraph_integer_t to) { igraph_vs_t vs; vs.type = IGRAPH_VS_SEQ; vs.data.seq.from = from; vs.data.seq.to = to + 1; return vs; } /** * \function igraph_vs_destroy * \brief Destroy a vertex set. * * This function should be called for all vertex selectors when they * are not needed. The memory allocated for the vertex selector will * be deallocated. Do not call this function on vertex selectors * created with the immediate versions of the vertex selector * constructors (starting with igraph_vss). * * \param vs Pointer to a vertex selector object. * * Time complexity: operating system dependent, usually O(1). */ void igraph_vs_destroy(igraph_vs_t *vs) { switch (vs->type) { case IGRAPH_VS_ALL: case IGRAPH_VS_ADJ: case IGRAPH_VS_NONE: case IGRAPH_VS_1: case IGRAPH_VS_VECTORPTR: case IGRAPH_VS_SEQ: case IGRAPH_VS_NONADJ: break; case IGRAPH_VS_VECTOR: igraph_vector_destroy((igraph_vector_t*)vs->data.vecptr); igraph_Free(vs->data.vecptr); break; default: break; } } /** * \function igraph_vs_is_all * \brief Check whether all vertices are included. * * This function checks whether the vertex selector object was created * by \ref igraph_vs_all() or \ref igraph_vss_all(). Note that the * vertex selector might contain all vertices in a given graph but if * it wasn't created by the two constructors mentioned here the return * value will be FALSE. * * \param vs Pointer to a vertex selector object. * \return TRUE (1) if the vertex selector contains all vertices and * FALSE (0) otherwise. * * Time complexity: O(1). */ igraph_bool_t igraph_vs_is_all(const igraph_vs_t *vs) { return vs->type == IGRAPH_VS_ALL; } int igraph_vs_as_vector(const igraph_t *graph, igraph_vs_t vs, igraph_vector_t *v) { igraph_vit_t vit; IGRAPH_CHECK(igraph_vit_create(graph, vs, &vit)); IGRAPH_FINALLY(igraph_vit_destroy, &vit); IGRAPH_CHECK(igraph_vit_as_vector(&vit, v)); igraph_vit_destroy(&vit); IGRAPH_FINALLY_CLEAN(1); return 0; } /** * \function igraph_vs_copy * \brief Creates a copy of a vertex selector. * \param src The selector being copied. * \param dest An uninitialized selector that will contain the copy. */ int igraph_vs_copy(igraph_vs_t* dest, const igraph_vs_t* src) { memcpy(dest, src, sizeof(igraph_vs_t)); switch (dest->type) { case IGRAPH_VS_VECTOR: dest->data.vecptr = igraph_Calloc(1, igraph_vector_t); if (!dest->data.vecptr) { IGRAPH_ERROR("Cannot copy vertex selector", IGRAPH_ENOMEM); } IGRAPH_CHECK(igraph_vector_copy((igraph_vector_t*)dest->data.vecptr, (igraph_vector_t*)src->data.vecptr)); break; } return 0; } /** * \function igraph_vs_type * \brief Returns the type of the vertex selector. */ int igraph_vs_type(const igraph_vs_t *vs) { return vs->type; } /** * \function igraph_vs_size * \brief Returns the size of the vertex selector. * * The size of the vertex selector is the number of vertices it will * yield when it is iterated over. * * \param graph The graph over which we will iterate. * \param result The result will be returned here. */ int igraph_vs_size(const igraph_t *graph, const igraph_vs_t *vs, igraph_integer_t *result) { igraph_vector_t vec; igraph_bool_t *seen; long i; switch (vs->type) { case IGRAPH_VS_NONE: *result = 0; return 0; case IGRAPH_VS_1: *result = 0; if (vs->data.vid < igraph_vcount(graph) && vs->data.vid >= 0) { *result = 1; } return 0; case IGRAPH_VS_SEQ: *result = vs->data.seq.to - vs->data.seq.from; return 0; case IGRAPH_VS_ALL: *result = igraph_vcount(graph); return 0; case IGRAPH_VS_ADJ: IGRAPH_VECTOR_INIT_FINALLY(&vec, 0); IGRAPH_CHECK(igraph_neighbors(graph, &vec, vs->data.adj.vid, vs->data.adj.mode)); *result = (igraph_integer_t) igraph_vector_size(&vec); igraph_vector_destroy(&vec); IGRAPH_FINALLY_CLEAN(1); return 0; case IGRAPH_VS_NONADJ: IGRAPH_VECTOR_INIT_FINALLY(&vec, 0); IGRAPH_CHECK(igraph_neighbors(graph, &vec, vs->data.adj.vid, vs->data.adj.mode)); *result = igraph_vcount(graph); seen = igraph_Calloc(*result, igraph_bool_t); if (seen == 0) { IGRAPH_ERROR("Cannot calculate selector length", IGRAPH_ENOMEM); } IGRAPH_FINALLY(igraph_free, seen); for (i = 0; i < igraph_vector_size(&vec); i++) { if (!seen[(long int)VECTOR(vec)[i]]) { (*result)--; seen[(long int)VECTOR(vec)[i]] = 1; } } igraph_free(seen); igraph_vector_destroy(&vec); IGRAPH_FINALLY_CLEAN(2); return 0; case IGRAPH_VS_VECTOR: case IGRAPH_VS_VECTORPTR: *result = (igraph_integer_t) igraph_vector_size((igraph_vector_t*)vs->data.vecptr); return 0; } IGRAPH_ERROR("Cannot calculate selector length, invalid selector type", IGRAPH_EINVAL); } /***************************************************/ /** * \function igraph_vit_create * \brief Creates a vertex iterator from a vertex selector. * * This function instantiates a vertex selector object with a given * graph. This is the step when the actual vertex ids are created from * the \em logical notion of the vertex selector based on the graph. * Eg. a vertex selector created with \ref igraph_vs_all() contains * knowledge that \em all vertices are included in a (yet indefinite) * graph. When instantiating it a vertex iterator object is created, * this contains the actual vertex ids in the graph supplied as a * parameter. * * * The same vertex selector object can be used to instantiate any * number vertex iterators. * * \param graph An \type igraph_t object, a graph. * \param vs A vertex selector object. * \param vit Pointer to an uninitialized vertex iterator object. * \return Error code. * \sa \ref igraph_vit_destroy(). * * Time complexity: it depends on the vertex selector type. O(1) for * vertex selectors created with \ref igraph_vs_all(), \ref * igraph_vs_none(), \ref igraph_vs_1, \ref igraph_vs_vector, \ref * igraph_vs_seq(), \ref igraph_vs_vector(), \ref * igraph_vs_vector_small(). O(d) for \ref igraph_vs_adj(), d is the * number of vertex ids to be included in the iterator. O(|V|) for * \ref igraph_vs_nonadj(), |V| is the number of vertices in the graph. */ int igraph_vit_create(const igraph_t *graph, igraph_vs_t vs, igraph_vit_t *vit) { igraph_vector_t vec; igraph_bool_t *seen; long int i, j, n; switch (vs.type) { case IGRAPH_VS_ALL: vit->type = IGRAPH_VIT_SEQ; vit->pos = 0; vit->start = 0; vit->end = igraph_vcount(graph); break; case IGRAPH_VS_ADJ: vit->type = IGRAPH_VIT_VECTOR; vit->pos = 0; vit->start = 0; vit->vec = igraph_Calloc(1, igraph_vector_t); if (vit->vec == 0) { IGRAPH_ERROR("Cannot create iterator", IGRAPH_ENOMEM); } IGRAPH_FINALLY(igraph_free, (igraph_vector_t*) vit->vec); IGRAPH_VECTOR_INIT_FINALLY((igraph_vector_t*)vit->vec, 0); IGRAPH_CHECK(igraph_neighbors(graph, (igraph_vector_t*)vit->vec, vs.data.adj.vid, vs.data.adj.mode)); vit->end = igraph_vector_size(vit->vec); IGRAPH_FINALLY_CLEAN(2); break; case IGRAPH_VS_NONADJ: vit->type = IGRAPH_VIT_VECTOR; vit->pos = 0; vit->start = 0; vit->vec = igraph_Calloc(1, igraph_vector_t); if (vit->vec == 0) { IGRAPH_ERROR("Cannot create iterator", IGRAPH_ENOMEM); } IGRAPH_FINALLY(igraph_free, (igraph_vector_t*) vit->vec); IGRAPH_VECTOR_INIT_FINALLY((igraph_vector_t *) vit->vec, 0); IGRAPH_VECTOR_INIT_FINALLY(&vec, 0); IGRAPH_CHECK(igraph_neighbors(graph, &vec, vs.data.adj.vid, vs.data.adj.mode)); n = igraph_vcount(graph); seen = igraph_Calloc(n, igraph_bool_t); if (seen == 0) { IGRAPH_ERROR("Cannot create iterator", IGRAPH_ENOMEM); } IGRAPH_FINALLY(igraph_free, seen); for (i = 0; i < igraph_vector_size(&vec); i++) { if (! seen [ (long int) VECTOR(vec)[i] ] ) { n--; seen[ (long int) VECTOR(vec)[i] ] = 1; } } IGRAPH_CHECK(igraph_vector_resize((igraph_vector_t*)vit->vec, n)); for (i = 0, j = 0; j < n; i++) { if (!seen[i]) { VECTOR(*vit->vec)[j++] = i; } } igraph_Free(seen); igraph_vector_destroy(&vec); vit->end = n; IGRAPH_FINALLY_CLEAN(4); break; case IGRAPH_VS_NONE: vit->type = IGRAPH_VIT_SEQ; vit->pos = 0; vit->start = 0; vit->end = 0; break; case IGRAPH_VS_1: vit->type = IGRAPH_VIT_SEQ; vit->pos = vs.data.vid; vit->start = vs.data.vid; vit->end = vs.data.vid + 1; if (vit->pos >= igraph_vcount(graph)) { IGRAPH_ERROR("Cannot create iterator, invalid vertex id", IGRAPH_EINVVID); } break; case IGRAPH_VS_VECTORPTR: case IGRAPH_VS_VECTOR: vit->type = IGRAPH_VIT_VECTORPTR; vit->pos = 0; vit->start = 0; vit->vec = vs.data.vecptr; vit->end = igraph_vector_size(vit->vec); if (!igraph_vector_isininterval(vit->vec, 0, igraph_vcount(graph) - 1)) { IGRAPH_ERROR("Cannot create iterator, invalid vertex id", IGRAPH_EINVVID); } break; case IGRAPH_VS_SEQ: vit->type = IGRAPH_VIT_SEQ; vit->pos = vs.data.seq.from; vit->start = vs.data.seq.from; vit->end = vs.data.seq.to; break; default: IGRAPH_ERROR("Cannot create iterator, invalid selector", IGRAPH_EINVAL); break; } return 0; } /** * \function igraph_vit_destroy * \brief Destroys a vertex iterator. * * * Deallocates memory allocated for a vertex iterator. * * \param vit Pointer to an initialized vertex iterator object. * \sa \ref igraph_vit_create() * * Time complexity: operating system dependent, usually O(1). */ void igraph_vit_destroy(const igraph_vit_t *vit) { switch (vit->type) { case IGRAPH_VIT_SEQ: case IGRAPH_VIT_VECTORPTR: break; case IGRAPH_VIT_VECTOR: igraph_vector_destroy((igraph_vector_t*)vit->vec); igraph_free((igraph_vector_t*)vit->vec); break; default: /* IGRAPH_ERROR("Cannot destroy iterator, unknown type", IGRAPH_EINVAL); */ break; } } int igraph_vit_as_vector(const igraph_vit_t *vit, igraph_vector_t *v) { long int i; IGRAPH_CHECK(igraph_vector_resize(v, IGRAPH_VIT_SIZE(*vit))); switch (vit->type) { case IGRAPH_VIT_SEQ: for (i = 0; i < IGRAPH_VIT_SIZE(*vit); i++) { VECTOR(*v)[i] = vit->start + i; } break; case IGRAPH_VIT_VECTOR: case IGRAPH_VIT_VECTORPTR: for (i = 0; i < IGRAPH_VIT_SIZE(*vit); i++) { VECTOR(*v)[i] = VECTOR(*vit->vec)[i]; } break; default: IGRAPH_ERROR("Cannot convert to vector, unknown iterator type", IGRAPH_EINVAL); break; } return 0; } /*******************************************************/ /** * \function igraph_es_all * \brief Edge set, all edges. * * \param es Pointer to an uninitialized edge selector object. * \param order Constant giving the order in which the edges will be * included in the selector. Possible values: * \c IGRAPH_EDGEORDER_ID, edge id order. * \c IGRAPH_EDGEORDER_FROM, vertex id order, the id of the * \em source vertex counts for directed graphs. The order * of the incident edges of a given vertex is arbitrary. * \c IGRAPH_EDGEORDER_TO, vertex id order, the id of the \em * target vertex counts for directed graphs. The order * of the incident edges of a given vertex is arbitrary. * For undirected graph the latter two is the same. * \return Error code. * \sa \ref igraph_ess_all(), \ref igraph_es_destroy() * * Time complexity: O(1). */ int igraph_es_all(igraph_es_t *es, igraph_edgeorder_type_t order) { switch (order) { case IGRAPH_EDGEORDER_ID: es->type = IGRAPH_ES_ALL; break; case IGRAPH_EDGEORDER_FROM: es->type = IGRAPH_ES_ALLFROM; break; case IGRAPH_EDGEORDER_TO: es->type = IGRAPH_ES_ALLTO; break; default: IGRAPH_ERROR("Invalid edge order, cannot create selector", IGRAPH_EINVAL); break; } return 0; } /** * \function igraph_ess_all * \brief Edge set, all edges (immediate version) * * The immediate version of the all-vertices selector. * * \param order Constant giving the order of the edges in the edge * selector. See \ref igraph_es_all() for the possible values. * \return The edge selector. * \sa \ref igraph_es_all() * * Time complexity: O(1). */ igraph_es_t igraph_ess_all(igraph_edgeorder_type_t order) { igraph_es_t es; igraph_es_all(&es, order); /* cannot fail */ return es; } /** * \function igraph_es_adj * \brief Adjacent edges of a vertex. * * This function was superseded by \ref igraph_es_incident() in igraph 0.6. * Please use \ref igraph_es_incident() instead of this function. * * * Deprecated in version 0.6. */ int igraph_es_adj(igraph_es_t *es, igraph_integer_t vid, igraph_neimode_t mode) { IGRAPH_WARNING("igraph_es_adj is deprecated, use igraph_es_incident"); return igraph_es_incident(es, vid, mode); } /** * \function igraph_es_incident * \brief Edges incident on a given vertex. * * \param es Pointer to an uninitialized edge selector object. * \param vid Vertex id, of which the incident edges will be * selected. * \param mode Constant giving the type of the incident edges to * select. This is ignored for undirected graphs. Possible values: * \c IGRAPH_OUT, outgoing edges; * \c IGRAPH_IN, incoming edges; * \c IGRAPH_ALL, all edges. * \return Error code. * \sa \ref igraph_es_destroy() * * Time complexity: O(1). * * \example examples/simple/igraph_es_adj.c */ int igraph_es_incident(igraph_es_t *es, igraph_integer_t vid, igraph_neimode_t mode) { es->type = IGRAPH_ES_INCIDENT; es->data.incident.vid = vid; es->data.incident.mode = mode; return 0; } /** * \function igraph_es_none * \brief Empty edge selector. * * \param es Pointer to an uninitialized edge selector object to * initialize. * \return Error code. * \sa \ref igraph_ess_none(), \ref igraph_es_destroy() * * Time complexity: O(1). */ int igraph_es_none(igraph_es_t *es) { es->type = IGRAPH_ES_NONE; return 0; } /** * \function igraph_ess_none * \brief Immediate empty edge selector. * * * Immediate version of the empty edge selector. * * \return Initialized empty edge selector. * \sa \ref igraph_es_none() * * Time complexity: O(1). */ igraph_es_t igraph_ess_none(void) { igraph_es_t es; es.type = IGRAPH_ES_NONE; return es; } /** * \function igraph_es_1 * \brief Edge selector containing a single edge. * * \param es Pointer to an uninitialized edge selector object. * \param eid Edge id of the edge to select. * \return Error code. * \sa \ref igraph_ess_1(), \ref igraph_es_destroy() * * Time complexity: O(1). */ int igraph_es_1(igraph_es_t *es, igraph_integer_t eid) { es->type = IGRAPH_ES_1; es->data.eid = eid; return 0; } /** * \function igraph_ess_1 * \brief Immediate version of the single edge edge selector. * * \param eid The id of the edge. * \return The edge selector. * \sa \ref igraph_es_1() * * Time complexity: O(1). */ igraph_es_t igraph_ess_1(igraph_integer_t eid) { igraph_es_t es; es.type = IGRAPH_ES_1; es.data.eid = eid; return es; } /** * \function igraph_es_vector * \brief Handle a vector as an edge selector. * * * Creates an edge selector which serves as a view to a vector * containing edge ids. Do not destroy the vector before destroying * the view. * * Many views can be created to the same vector. * * \param es Pointer to an uninitialized edge selector. * \param v Vector containing edge ids. * \return Error code. * \sa \ref igraph_ess_vector(), \ref igraph_es_destroy() * * Time complexity: O(1). */ int igraph_es_vector(igraph_es_t *es, const igraph_vector_t *v) { es->type = IGRAPH_ES_VECTORPTR; es->data.vecptr = v; return 0; } /** * \function igraph_es_vector_copy * \brief Edge set, based on a vector, with copying. * * * This function makes it possible to handle a \type vector_t * permanently as an edge selector. The edge selector creates a * copy of the original vector, so the vector can safely be destroyed * after creating the edge selector. Changing the original vector * will not affect the edge selector. The edge selector is * responsible for deleting the copy made by itself. * * \param es Pointer to an uninitialized edge selector. * \param v Pointer to a \type igraph_vector_t object. * \return Error code. * \sa \ref igraph_es_destroy() * * Time complexity: O(1). */ int igraph_es_vector_copy(igraph_es_t *es, const igraph_vector_t *v) { es->type = IGRAPH_ES_VECTOR; es->data.vecptr = igraph_Calloc(1, igraph_vector_t); if (es->data.vecptr == 0) { IGRAPH_ERROR("Cannot create edge selector", IGRAPH_ENOMEM); } IGRAPH_FINALLY(igraph_free, (igraph_vector_t*)es->data.vecptr); IGRAPH_CHECK(igraph_vector_copy((igraph_vector_t*)es->data.vecptr, v)); IGRAPH_FINALLY_CLEAN(1); return 0; } /** * \function igraph_ess_vector * \brief Immediate vector view edge selector. * * * This is the immediate version of the vector of edge ids edge * selector. * * \param v The vector of edge ids. * \return Edge selector, initialized. * \sa \ref igraph_es_vector() * * Time complexity: O(1). */ igraph_es_t igraph_ess_vector(const igraph_vector_t *v) { igraph_es_t es; es.type = IGRAPH_ES_VECTORPTR; es.data.vecptr = v; return es; } /** * \function igraph_es_fromto * \brief Edge selector, all edges between two vertex sets. * * * This function is not implemented yet. * * \param es Pointer to an uninitialized edge selector. * \param from Vertex selector, their outgoing edges will be * selected. * \param to Vertex selector, their incoming edges will be selected * from the previous selection. * \return Error code. * \sa \ref igraph_es_destroy() * * Time complexity: O(1). * * \example examples/simple/igraph_es_fromto.c */ int igraph_es_fromto(igraph_es_t *es, igraph_vs_t from, igraph_vs_t to) { IGRAPH_UNUSED(es); IGRAPH_UNUSED(from); IGRAPH_UNUSED(to); IGRAPH_ERROR("igraph_es_fromto not implemented yet", IGRAPH_UNIMPLEMENTED); /* TODO */ return 0; } /** * \function igraph_es_seq * \brief Edge selector, a sequence of edge ids. * * All edge ids between from and to will be * included in the edge selection. * * \param es Pointer to an uninitialized edge selector object. * \param from The first edge id to be included. * \param to The last edge id to be included. * \return Error code. * \sa \ref igraph_ess_seq(), \ref igraph_es_destroy() * * Time complexity: O(1). */ int igraph_es_seq(igraph_es_t *es, igraph_integer_t from, igraph_integer_t to) { es->type = IGRAPH_ES_SEQ; es->data.seq.from = from; es->data.seq.to = to; return 0; } /** * \function igraph_ess_seq * \brief Immediate version of the sequence edge selector. * * \param from The first edge id to include. * \param to The last edge id to include. * \return The initialized edge selector. * \sa \ref igraph_es_seq() * * Time complexity: O(1). */ igraph_es_t igraph_ess_seq(igraph_integer_t from, igraph_integer_t to) { igraph_es_t es; es.type = IGRAPH_ES_SEQ; es.data.seq.from = from; es.data.seq.to = to; return es; } /** * \function igraph_es_pairs * \brief Edge selector, multiple edges defined by their endpoints in a vector. * * The edges between the given pairs of vertices will be included in the * edge selection. The vertex pairs must be defined in the vector v, * the first element of the vector is the first vertex of the first edge * to be selected, the second element is the second vertex of the first * edge, the third element is the first vertex of the second edge and * so on. * * \param es Pointer to an uninitialized edge selector object. * \param v The vector containing the endpoints of the edges. * \param directed Whether the graph is directed or not. * \return Error code. * \sa \ref igraph_es_pairs_small(), \ref igraph_es_destroy() * * Time complexity: O(n), the number of edges being selected. * * \example examples/simple/igraph_es_pairs.c */ int igraph_es_pairs(igraph_es_t *es, const igraph_vector_t *v, igraph_bool_t directed) { es->type = IGRAPH_ES_PAIRS; es->data.path.mode = directed; es->data.path.ptr = igraph_Calloc(1, igraph_vector_t); if (es->data.path.ptr == 0) { IGRAPH_ERROR("Cannot create edge selector", IGRAPH_ENOMEM); } IGRAPH_FINALLY(igraph_free, (igraph_vector_t*) es->data.path.ptr); IGRAPH_CHECK(igraph_vector_copy((igraph_vector_t*) es->data.path.ptr, v)); IGRAPH_FINALLY_CLEAN(1); return 0; } /** * \function igraph_es_pairs_small * \brief Edge selector, multiple edges defined by their endpoints as arguments. * * The edges between the given pairs of vertices will be included in the * edge selection. The vertex pairs must be given as the arguments of the * function call, the third argument is the first vertex of the first edge, * the fourth argument is the second vertex of the first edge, the fifth * is the first vertex of the second edge and so on. The last element of the * argument list must be -1 to denote the end of the argument list. * * \param es Pointer to an uninitialized edge selector object. * \param directed Whether the graph is directed or not. * \return Error code. * \sa \ref igraph_es_pairs(), \ref igraph_es_destroy() * * Time complexity: O(n), the number of edges being selected. */ int igraph_es_pairs_small(igraph_es_t *es, igraph_bool_t directed, ...) { va_list ap; long int i, n = 0; es->type = IGRAPH_ES_PAIRS; es->data.path.mode = directed; es->data.path.ptr = igraph_Calloc(1, igraph_vector_t); if (es->data.path.ptr == 0) { IGRAPH_ERROR("Cannot create edge selector", IGRAPH_ENOMEM); } IGRAPH_FINALLY(igraph_free, (igraph_vector_t*)es->data.path.ptr); va_start(ap, directed); while (1) { int num = va_arg(ap, int); if (num == -1) { break; } n++; } va_end(ap); IGRAPH_VECTOR_INIT_FINALLY( (igraph_vector_t*) es->data.path.ptr, n); va_start(ap, directed); for (i = 0; i < n; i++) { VECTOR(*es->data.path.ptr)[i] = (igraph_real_t) va_arg(ap, int); } va_end(ap); IGRAPH_FINALLY_CLEAN(2); return 0; } int igraph_es_multipairs(igraph_es_t *es, const igraph_vector_t *v, igraph_bool_t directed) { es->type = IGRAPH_ES_MULTIPAIRS; es->data.path.mode = directed; es->data.path.ptr = igraph_Calloc(1, igraph_vector_t); if (es->data.path.ptr == 0) { IGRAPH_ERROR("Cannot create edge selector", IGRAPH_ENOMEM); } IGRAPH_FINALLY(igraph_free, (igraph_vector_t*) es->data.path.ptr); IGRAPH_CHECK(igraph_vector_copy((igraph_vector_t*) es->data.path.ptr, v)); IGRAPH_FINALLY_CLEAN(1); return 0; } /** * \example examples/simple/igraph_es_path.c */ int igraph_es_path(igraph_es_t *es, const igraph_vector_t *v, igraph_bool_t directed) { es->type = IGRAPH_ES_PATH; es->data.path.mode = directed; es->data.path.ptr = igraph_Calloc(1, igraph_vector_t); if (es->data.path.ptr == 0) { IGRAPH_ERROR("Cannot create edge selector", IGRAPH_ENOMEM); } IGRAPH_FINALLY(igraph_free, (igraph_vector_t*) es->data.path.ptr); IGRAPH_CHECK(igraph_vector_copy((igraph_vector_t*) es->data.path.ptr, v)); IGRAPH_FINALLY_CLEAN(1); return 0; } int igraph_es_path_small(igraph_es_t *es, igraph_bool_t directed, ...) { va_list ap; long int i, n = 0; es->type = IGRAPH_ES_PATH; es->data.path.mode = directed; es->data.path.ptr = igraph_Calloc(1, igraph_vector_t); if (es->data.path.ptr == 0) { IGRAPH_ERROR("Cannot create edge selector", IGRAPH_ENOMEM); } IGRAPH_FINALLY(igraph_free, (igraph_vector_t*)es->data.path.ptr); va_start(ap, directed); while (1) { int num = va_arg(ap, int); if (num == -1) { break; } n++; } va_end(ap); IGRAPH_VECTOR_INIT_FINALLY( (igraph_vector_t*) es->data.path.ptr, n); va_start(ap, directed); for (i = 0; i < n; i++) { VECTOR(*es->data.path.ptr)[i] = (igraph_real_t) va_arg(ap, int); } va_end(ap); IGRAPH_FINALLY_CLEAN(2); return 0; } /** * \function igraph_es_destroy * \brief Destroys an edge selector object. * * * Call this function on an edge selector when it is not needed any * more. Do \em not call this function on edge selectors created by * immediate constructors, those don't need to be destroyed. * * \param es Pointer to an edge selector object. * * Time complexity: operating system dependent, usually O(1). */ void igraph_es_destroy(igraph_es_t *es) { switch (es->type) { case IGRAPH_ES_ALL: case IGRAPH_ES_ALLFROM: case IGRAPH_ES_ALLTO: case IGRAPH_ES_INCIDENT: case IGRAPH_ES_NONE: case IGRAPH_ES_1: case IGRAPH_ES_VECTORPTR: case IGRAPH_ES_SEQ: break; case IGRAPH_ES_VECTOR: igraph_vector_destroy((igraph_vector_t*)es->data.vecptr); igraph_Free(es->data.vecptr); break; case IGRAPH_ES_PAIRS: case IGRAPH_ES_PATH: case IGRAPH_ES_MULTIPAIRS: igraph_vector_destroy((igraph_vector_t*)es->data.path.ptr); igraph_Free(es->data.path.ptr); break; default: break; } } /** * \function igraph_es_is_all * \brief Check whether an edge selector includes all edges. * * \param es Pointer to an edge selector object. * \return TRUE (1) if es was created with \ref * igraph_es_all() or \ref igraph_ess_all(), and FALSE (0) otherwise. * * Time complexity: O(1). */ igraph_bool_t igraph_es_is_all(const igraph_es_t *es) { return es->type == IGRAPH_ES_ALL; } /** * \function igraph_es_copy * \brief Creates a copy of an edge selector. * \param src The selector being copied. * \param dest An uninitialized selector that will contain the copy. * \sa \ref igraph_es_destroy() */ int igraph_es_copy(igraph_es_t* dest, const igraph_es_t* src) { memcpy(dest, src, sizeof(igraph_es_t)); switch (dest->type) { case IGRAPH_ES_VECTOR: dest->data.vecptr = igraph_Calloc(1, igraph_vector_t); if (!dest->data.vecptr) { IGRAPH_ERROR("Cannot copy edge selector", IGRAPH_ENOMEM); } IGRAPH_CHECK(igraph_vector_copy((igraph_vector_t*)dest->data.vecptr, (igraph_vector_t*)src->data.vecptr)); break; case IGRAPH_ES_PATH: case IGRAPH_ES_PAIRS: case IGRAPH_ES_MULTIPAIRS: dest->data.path.ptr = igraph_Calloc(1, igraph_vector_t); if (!dest->data.path.ptr) { IGRAPH_ERROR("Cannot copy edge selector", IGRAPH_ENOMEM); } IGRAPH_CHECK(igraph_vector_copy((igraph_vector_t*)dest->data.path.ptr, (igraph_vector_t*)src->data.path.ptr)); break; } return 0; } int igraph_es_as_vector(const igraph_t *graph, igraph_es_t es, igraph_vector_t *v) { igraph_eit_t eit; IGRAPH_CHECK(igraph_eit_create(graph, es, &eit)); IGRAPH_FINALLY(igraph_eit_destroy, &eit); IGRAPH_CHECK(igraph_eit_as_vector(&eit, v)); igraph_eit_destroy(&eit); IGRAPH_FINALLY_CLEAN(1); return 0; } /** * \function igraph_es_type * \brief Returns the type of the edge selector. */ int igraph_es_type(const igraph_es_t *es) { return es->type; } int igraph_i_es_pairs_size(const igraph_t *graph, const igraph_es_t *es, igraph_integer_t *result); int igraph_i_es_path_size(const igraph_t *graph, const igraph_es_t *es, igraph_integer_t *result); int igraph_i_es_multipairs_size(const igraph_t *graph, const igraph_es_t *es, igraph_integer_t *result); /** * \function igraph_es_size * \brief Returns the size of the edge selector. * * The size of the edge selector is the number of edges it will * yield when it is iterated over. * * \param graph The graph over which we will iterate. * \param result The result will be returned here. */ int igraph_es_size(const igraph_t *graph, const igraph_es_t *es, igraph_integer_t *result) { igraph_vector_t v; switch (es->type) { case IGRAPH_ES_ALL: *result = igraph_ecount(graph); return 0; case IGRAPH_ES_ALLFROM: *result = igraph_ecount(graph); return 0; case IGRAPH_ES_ALLTO: *result = igraph_ecount(graph); return 0; case IGRAPH_ES_INCIDENT: IGRAPH_VECTOR_INIT_FINALLY(&v, 0); IGRAPH_CHECK(igraph_incident(graph, &v, es->data.incident.vid, es->data.incident.mode)); *result = (igraph_integer_t) igraph_vector_size(&v); igraph_vector_destroy(&v); IGRAPH_FINALLY_CLEAN(1); return 0; case IGRAPH_ES_NONE: *result = 0; return 0; case IGRAPH_ES_1: if (es->data.eid < igraph_ecount(graph) && es->data.eid >= 0) { *result = 1; } else { *result = 0; } return 0; case IGRAPH_ES_VECTOR: case IGRAPH_ES_VECTORPTR: *result = (igraph_integer_t) igraph_vector_size((igraph_vector_t*)es->data.vecptr); return 0; case IGRAPH_ES_SEQ: *result = es->data.seq.to - es->data.seq.from; return 0; case IGRAPH_ES_PAIRS: IGRAPH_CHECK(igraph_i_es_pairs_size(graph, es, result)); return 0; case IGRAPH_ES_PATH: IGRAPH_CHECK(igraph_i_es_path_size(graph, es, result)); return 0; case IGRAPH_ES_MULTIPAIRS: IGRAPH_CHECK(igraph_i_es_multipairs_size(graph, es, result)); return 0; default: IGRAPH_ERROR("Cannot calculate selector length, invalid selector type", IGRAPH_EINVAL); } return 0; } int igraph_i_es_pairs_size(const igraph_t *graph, const igraph_es_t *es, igraph_integer_t *result) { long int n = igraph_vector_size(es->data.path.ptr); long int no_of_nodes = igraph_vcount(graph); long int i; if (n % 2 != 0) { IGRAPH_ERROR("Cannot calculate edge selector length from odd number of vertices", IGRAPH_EINVAL); } if (!igraph_vector_isininterval(es->data.path.ptr, 0, no_of_nodes - 1)) { IGRAPH_ERROR("Cannot calculate edge selector length", IGRAPH_EINVVID); } *result = (igraph_integer_t) (n / 2); /* Check for the existence of all edges */ for (i = 0; i < *result; i++) { long int from = (long int) VECTOR(*es->data.path.ptr)[2 * i]; long int to = (long int) VECTOR(*es->data.path.ptr)[2 * i + 1]; igraph_integer_t eid; IGRAPH_CHECK(igraph_get_eid(graph, &eid, (igraph_integer_t) from, (igraph_integer_t) to, es->data.path.mode, /*error=*/ 1)); } return 0; } int igraph_i_es_path_size(const igraph_t *graph, const igraph_es_t *es, igraph_integer_t *result) { long int n = igraph_vector_size(es->data.path.ptr); long int no_of_nodes = igraph_vcount(graph); long int i; if (!igraph_vector_isininterval(es->data.path.ptr, 0, no_of_nodes - 1)) { IGRAPH_ERROR("Cannot calculate selector length", IGRAPH_EINVVID); } if (n <= 1) { *result = 0; } else { *result = (igraph_integer_t) (n - 1); } for (i = 0; i < *result; i++) { long int from = (long int) VECTOR(*es->data.path.ptr)[i]; long int to = (long int) VECTOR(*es->data.path.ptr)[i + 1]; igraph_integer_t eid; IGRAPH_CHECK(igraph_get_eid(graph, &eid, (igraph_integer_t) from, (igraph_integer_t) to, es->data.path.mode, /*error=*/ 1)); } return 0; } int igraph_i_es_multipairs_size(const igraph_t *graph, const igraph_es_t *es, igraph_integer_t *result) { IGRAPH_UNUSED(graph); IGRAPH_UNUSED(es); IGRAPH_UNUSED(result); IGRAPH_ERROR("Cannot calculate edge selector length", IGRAPH_UNIMPLEMENTED); } /**************************************************/ int igraph_i_eit_create_allfromto(const igraph_t *graph, igraph_eit_t *eit, igraph_neimode_t mode); int igraph_i_eit_pairs(const igraph_t *graph, igraph_es_t es, igraph_eit_t *eit); int igraph_i_eit_multipairs(const igraph_t *graph, igraph_es_t es, igraph_eit_t *eit); int igraph_i_eit_path(const igraph_t *graph, igraph_es_t es, igraph_eit_t *eit); int igraph_i_eit_create_allfromto(const igraph_t *graph, igraph_eit_t *eit, igraph_neimode_t mode) { igraph_vector_t *vec; long int no_of_nodes = igraph_vcount(graph); long int i; vec = igraph_Calloc(1, igraph_vector_t); if (vec == 0) { IGRAPH_ERROR("Cannot create edge iterator", IGRAPH_ENOMEM); } IGRAPH_FINALLY(igraph_free, vec); IGRAPH_VECTOR_INIT_FINALLY(vec, 0); IGRAPH_CHECK(igraph_vector_reserve(vec, igraph_ecount(graph))); if (igraph_is_directed(graph)) { igraph_vector_t adj; IGRAPH_VECTOR_INIT_FINALLY(&adj, 0); for (i = 0; i < no_of_nodes; i++) { igraph_incident(graph, &adj, (igraph_integer_t) i, mode); igraph_vector_append(vec, &adj); } igraph_vector_destroy(&adj); IGRAPH_FINALLY_CLEAN(1); } else { igraph_vector_t adj; igraph_bool_t *added; long int j; IGRAPH_VECTOR_INIT_FINALLY(&adj, 0); added = igraph_Calloc(igraph_ecount(graph), igraph_bool_t); if (added == 0) { IGRAPH_ERROR("Cannot create edge iterator", IGRAPH_ENOMEM); } IGRAPH_FINALLY(igraph_free, added); for (i = 0; i < no_of_nodes; i++) { igraph_incident(graph, &adj, (igraph_integer_t) i, IGRAPH_ALL); for (j = 0; j < igraph_vector_size(&adj); j++) { if (!added[ (long int)VECTOR(adj)[j] ]) { igraph_vector_push_back(vec, VECTOR(adj)[j]); added[ (long int)VECTOR(adj)[j] ] += 1; } } } igraph_vector_destroy(&adj); igraph_Free(added); IGRAPH_FINALLY_CLEAN(2); } eit->type = IGRAPH_EIT_VECTOR; eit->pos = 0; eit->start = 0; eit->vec = vec; eit->end = igraph_vector_size(eit->vec); IGRAPH_FINALLY_CLEAN(2); return 0; } int igraph_i_eit_pairs(const igraph_t *graph, igraph_es_t es, igraph_eit_t *eit) { long int n = igraph_vector_size(es.data.path.ptr); long int no_of_nodes = igraph_vcount(graph); long int i; if (n % 2 != 0) { IGRAPH_ERROR("Cannot create edge iterator from odd number of vertices", IGRAPH_EINVAL); } if (!igraph_vector_isininterval(es.data.path.ptr, 0, no_of_nodes - 1)) { IGRAPH_ERROR("Cannot create edge iterator", IGRAPH_EINVVID); } eit->type = IGRAPH_EIT_VECTOR; eit->pos = 0; eit->start = 0; eit->end = n / 2; eit->vec = igraph_Calloc(1, igraph_vector_t); if (eit->vec == 0) { IGRAPH_ERROR("Cannot create edge iterator", IGRAPH_ENOMEM); } IGRAPH_FINALLY(igraph_free, (igraph_vector_t*)eit->vec); IGRAPH_VECTOR_INIT_FINALLY((igraph_vector_t*)eit->vec, n / 2); for (i = 0; i < igraph_vector_size(eit->vec); i++) { long int from = (long int) VECTOR(*es.data.path.ptr)[2 * i]; long int to = (long int) VECTOR(*es.data.path.ptr)[2 * i + 1]; igraph_integer_t eid; IGRAPH_CHECK(igraph_get_eid(graph, &eid, (igraph_integer_t) from, (igraph_integer_t) to, es.data.path.mode, /*error=*/ 1)); VECTOR(*eit->vec)[i] = eid; } IGRAPH_FINALLY_CLEAN(2); return 0; } int igraph_i_eit_multipairs(const igraph_t *graph, igraph_es_t es, igraph_eit_t *eit) { long int n = igraph_vector_size(es.data.path.ptr); long int no_of_nodes = igraph_vcount(graph); if (n % 2 != 0) { IGRAPH_ERROR("Cannot create edge iterator from odd number of vertices", IGRAPH_EINVAL); } if (!igraph_vector_isininterval(es.data.path.ptr, 0, no_of_nodes - 1)) { IGRAPH_ERROR("Cannot create edge iterator", IGRAPH_EINVVID); } eit->type = IGRAPH_EIT_VECTOR; eit->pos = 0; eit->start = 0; eit->end = n / 2; eit->vec = igraph_Calloc(1, igraph_vector_t); if (eit->vec == 0) { IGRAPH_ERROR("Cannot create edge iterator", IGRAPH_ENOMEM); } IGRAPH_FINALLY(igraph_free, (igraph_vector_t*)eit->vec); IGRAPH_VECTOR_INIT_FINALLY((igraph_vector_t*)eit->vec, n / 2); IGRAPH_CHECK(igraph_get_eids_multi(graph, (igraph_vector_t *) eit->vec, /*pairs=*/ es.data.path.ptr, /*path=*/ 0, es.data.path.mode, /*error=*/ 1)); IGRAPH_FINALLY_CLEAN(2); return 0; } int igraph_i_eit_path(const igraph_t *graph, igraph_es_t es, igraph_eit_t *eit) { long int n = igraph_vector_size(es.data.path.ptr); long int no_of_nodes = igraph_vcount(graph); long int i, len; if (!igraph_vector_isininterval(es.data.path.ptr, 0, no_of_nodes - 1)) { IGRAPH_ERROR("Cannot create edge iterator", IGRAPH_EINVVID); } if (n <= 1) { len = 0; } else { len = n - 1; } eit->type = IGRAPH_EIT_VECTOR; eit->pos = 0; eit->start = 0; eit->end = len; eit->vec = igraph_Calloc(1, igraph_vector_t); if (eit->vec == 0) { IGRAPH_ERROR("Cannot create edge iterator", IGRAPH_ENOMEM); } IGRAPH_FINALLY(igraph_free, (igraph_vector_t*)eit->vec); IGRAPH_VECTOR_INIT_FINALLY((igraph_vector_t *)eit->vec, len); for (i = 0; i < len; i++) { long int from = (long int) VECTOR(*es.data.path.ptr)[i]; long int to = (long int) VECTOR(*es.data.path.ptr)[i + 1]; igraph_integer_t eid; IGRAPH_CHECK(igraph_get_eid(graph, &eid, (igraph_integer_t) from, (igraph_integer_t) to, es.data.path.mode, /*error=*/ 1)); VECTOR(*eit->vec)[i] = eid; } IGRAPH_FINALLY_CLEAN(2); return 0; } /** * \function igraph_eit_create * \brief Creates an edge iterator from an edge selector. * * * This function creates an edge iterator based on an edge selector * and a graph. * * * The same edge selector can be used to create many edge iterators, * also for different graphs. * * \param graph An \type igraph_t object for which the edge selector * will be instantiated. * \param es The edge selector to instantiate. * \param eit Pointer to an uninitialized edge iterator. * \return Error code. * \sa \ref igraph_eit_destroy() * * Time complexity: depends on the type of the edge selector. For edge * selectors created by \ref igraph_es_all(), \ref igraph_es_none(), * \ref igraph_es_1(), igraph_es_vector(), igraph_es_seq() it is * O(1). For \ref igraph_es_incident() it is O(d) where d is the number of * incident edges of the vertex. */ int igraph_eit_create(const igraph_t *graph, igraph_es_t es, igraph_eit_t *eit) { switch (es.type) { case IGRAPH_ES_ALL: eit->type = IGRAPH_EIT_SEQ; eit->pos = 0; eit->start = 0; eit->end = igraph_ecount(graph); break; case IGRAPH_ES_ALLFROM: IGRAPH_CHECK(igraph_i_eit_create_allfromto(graph, eit, IGRAPH_OUT)); break; case IGRAPH_ES_ALLTO: IGRAPH_CHECK(igraph_i_eit_create_allfromto(graph, eit, IGRAPH_IN)); break; case IGRAPH_ES_INCIDENT: eit->type = IGRAPH_EIT_VECTOR; eit->pos = 0; eit->start = 0; eit->vec = igraph_Calloc(1, igraph_vector_t); if (eit->vec == 0) { IGRAPH_ERROR("Cannot create iterator", IGRAPH_ENOMEM); } IGRAPH_FINALLY(igraph_free, (igraph_vector_t*) eit->vec); IGRAPH_VECTOR_INIT_FINALLY((igraph_vector_t*)eit->vec, 0); IGRAPH_CHECK(igraph_incident(graph, (igraph_vector_t*)eit->vec, es.data.incident.vid, es.data.incident.mode)); eit->end = igraph_vector_size(eit->vec); IGRAPH_FINALLY_CLEAN(2); break; case IGRAPH_ES_NONE: eit->type = IGRAPH_EIT_SEQ; eit->pos = 0; eit->start = 0; eit->end = 0; break; case IGRAPH_ES_1: eit->type = IGRAPH_EIT_SEQ; eit->pos = es.data.eid; eit->start = es.data.eid; eit->end = es.data.eid + 1; if (eit->pos >= igraph_ecount(graph)) { IGRAPH_ERROR("Cannot create iterator, invalid edge id", IGRAPH_EINVVID); } break; case IGRAPH_ES_VECTOR: case IGRAPH_ES_VECTORPTR: eit->type = IGRAPH_EIT_VECTORPTR; eit->pos = 0; eit->start = 0; eit->vec = es.data.vecptr; eit->end = igraph_vector_size(eit->vec); if (!igraph_vector_isininterval(eit->vec, 0, igraph_ecount(graph) - 1)) { IGRAPH_ERROR("Cannot create iterator, invalid edge id", IGRAPH_EINVVID); } break; case IGRAPH_ES_SEQ: eit->type = IGRAPH_EIT_SEQ; eit->pos = es.data.seq.from; eit->start = es.data.seq.from; eit->end = es.data.seq.to; break; case IGRAPH_ES_PAIRS: IGRAPH_CHECK(igraph_i_eit_pairs(graph, es, eit)); break; case IGRAPH_ES_MULTIPAIRS: IGRAPH_CHECK(igraph_i_eit_multipairs(graph, es, eit)); break; case IGRAPH_ES_PATH: IGRAPH_CHECK(igraph_i_eit_path(graph, es, eit)); break; default: IGRAPH_ERROR("Cannot create iterator, invalid selector", IGRAPH_EINVAL); break; } return 0; } /** * \function igraph_eit_destroy * \brief Destroys an edge iterator. * * \param eit Pointer to an edge iterator to destroy. * \sa \ref igraph_eit_create() * * Time complexity: operating system dependent, usually O(1). */ void igraph_eit_destroy(const igraph_eit_t *eit) { switch (eit->type) { case IGRAPH_EIT_SEQ: case IGRAPH_EIT_VECTORPTR: break; case IGRAPH_EIT_VECTOR: igraph_vector_destroy((igraph_vector_t*)eit->vec); igraph_free((igraph_vector_t*)eit->vec); break; default: /* IGRAPH_ERROR("Cannot destroy iterator, unknown type", IGRAPH_EINVAL); */ break; } } int igraph_eit_as_vector(const igraph_eit_t *eit, igraph_vector_t *v) { long int i; IGRAPH_CHECK(igraph_vector_resize(v, IGRAPH_EIT_SIZE(*eit))); switch (eit->type) { case IGRAPH_EIT_SEQ: for (i = 0; i < IGRAPH_EIT_SIZE(*eit); i++) { VECTOR(*v)[i] = eit->start + i; } break; case IGRAPH_EIT_VECTOR: case IGRAPH_EIT_VECTORPTR: for (i = 0; i < IGRAPH_EIT_SIZE(*eit); i++) { VECTOR(*v)[i] = VECTOR(*eit->vec)[i]; } break; default: IGRAPH_ERROR("Cannot convert to vector, unknown iterator type", IGRAPH_EINVAL); break; } return 0; }