haskell-igraph-0.8.0: igraph/src/iterators.c
/* -*- mode: C -*- */
/*
IGraph library.
Copyright (C) 2005-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
*/
#include "igraph_iterators.h"
#include "igraph_memory.h"
#include "igraph_random.h"
#include "igraph_interface.h"
#include "config.h"
#include <string.h>
#include <stdarg.h>
/**
* \section about_iterators About selectors, iterators
*
* <para>Everything about vertices and vertex selectors also applies
* to edges and edge selectors unless explicitly noted otherwise.</para>
*
* <para>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.</para>
*
* <para>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.</para>
*
* <para>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.</para>
*
* <para>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).</para>
*/
/**
* \section about_vertex_selectors
*
* <para>Vertex selectors are created by vertex selector constructors,
* can be instantiated with \ref igraph_vit_create(), and are
* destroyed with \ref igraph_vs_destroy().</para>
*/
/**
* \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.
*
* </para><para>
* 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 <code>-1</code> after the
* last vertex id. The behavior of the function is undefined if you
* don't use a <code>-1</code> properly.
*
* </para><para>
* Note that the vertex ids supplied will be parsed as
* <code>int</code>'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 <code>-1</code>
* 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 <code>igraph_vss</code>).
*
* \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.
*
* </para><para>
* 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.
*
* </para><para>
* 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.
*
* </para><para>
* 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.
*
* </para><para>
* 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.
*
* </para><para>
* 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.
*
* </para><para>
* 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.
*
* </para><para>
* 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 <code>from</code> and <code>to</code> 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 <code>v</code>,
* 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.
*
* </para><para>
* 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 <code>es</code> 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.
*
* </para><para>
* This function creates an edge iterator based on an edge selector
* and a graph.
*
* </para><para>
* 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;
}