/* -*- mode: C -*- */
/*
IGraph library.
Copyright (C) 2005 Gabor Csardi <csardi@rmki.kfki.hu>
MTA RMKI, Konkoly-Thege Miklos st. 29-33, Budapest 1121, Hungary
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.h"
#include "memory.h"
#include "random.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,
* and it is a way to reference to 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 vertex of graph can be selected by
* \ref igraph_vs_all(), and the graph indenpendence means that
* \ref igraph_vs_all() is not parametrized by a graph object. Ie.
* \ref igraph_vs_all() is the \em concept of selecting all vertices
* of a graph.</para>
*
* <para>This means that for determining the actual vertex id's implied
* by a vertex selector it needs to be instantiated with a graph
* object, the instantiation results a vertex iterator.</para>
*
* <para>Some vertex selectors have \em immediate versions, these have
* prefix <code>igraph_vss</code> instead of <code>igraph_vs</code>, eg.
* \ref igraph_vss_all() instead of \ref igraph_vs_all().
* These immediate versions are to be used in the parameter list of the igraph
* functions, like \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
*
* \param vs Pointer to an uninitialized \type igraph_vs_t object.
* \return Error code.
* \sa \ref igraph_vss_all().
*
* 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
*
* 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
*
* 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. Possible values:
* \c IGRAPH_OUT, all vertices to which there is a directed edge
* from \c vid.
* \c IGRAPH_IN, all vertices from which there is a directed
* edge from \c vid.
* \c IGRAPH_ALL, all vertices to which or from which there is
* a directed edge from/to \c vid.
* This parameter is ignored for undirected graphs.
* \return Error code.
*
* 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
*
* All non-neighboring vertices of a given vertex. The \p mode
* argument controls the type of neighboring vertics \em not to
* select.
* \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:
* \c IGRAPH_OUT, all vertices will be selected except those to
* which there is a directed edge from \p vid.
* \c IGRAPH_IN, all vertices will be selected except those
* from which there is a directed edge to \p vid.
* \c IGRAPH_ALL, all vertices will be selected exvept those
* from or to which there is a directed edge to or from \p
* vid.
* \return Error code.
*
* Time complexity: O(1).
*/
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
*
* Creates an empty vertex selector.
*
* \param vs Pointer to an uninitialized vertex selector object.
* \return Error code.
* \sa \ref igraph_vss_none.
*
* Time complexity: O(1).
*/
int igraph_vs_none(igraph_vs_t *vs) {
vs->type=IGRAPH_VS_NONE;
return 0;
}
/**
* \function igraph_vss_none
*
* 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
*
* 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()
*
* 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
*
* 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
*
* 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()
*
* Time complexity: O(1).
*/
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
*
* 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
*
* 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.
*
* 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=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
*
* 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.
*
* 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=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
*
* 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()
*
* Time complexity: O(1).
*/
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
*
* 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
*
* 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 complecity: 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);
Free(vs->data.vecptr);
break;
default:
break;
}
}
/**
* \function igraph_vs_is_all
*
* This function checks whether the vertex selector object was created
* by \ref igraph_vs_all() of \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 (1) otherwise.
*
* Time complexity: O(1).
*/
igraph_bool_t igraph_vs_is_all(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_FINALLY_CLEAN(1);
return 0;
}
/***************************************************/
/**
* \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=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=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=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;
}
}
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
*
* \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 adjacent 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 adjacent edges of a given vertex is arbitrary.
* For undirected graph the latter two is the same.
* \return Error code.
* \sa \ref igraph_ess_all()
*
* 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
*
* 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.
*
* \param es Pointer to an uninitialized edge selector object.
* \param vid Vertex id, of which the adjacent edges will be
* selected.
* \param mode Constant giving the type of the adjacent 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.
*
* Time complexity: O(1).
*/
int igraph_es_adj(igraph_es_t *es,
igraph_integer_t vid, igraph_neimode_t mode) {
es->type=IGRAPH_ES_ADJ;
es->data.adj.vid=vid;
es->data.adj.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()
*
* 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()
*
* 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()
*
* 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_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.
*
* Time complexity: O(1).
*/
int igraph_es_fromto(igraph_es_t *es,
igraph_vs_t from, igraph_vs_t to) {
/* 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()
*
* 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;
}
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=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_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=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=Calloc(1, igraph_vector_t);
if (es->data.path.ptr==0) {
IGRAPH_ERROR("Cannor 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(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=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=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_ADJ:
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);
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);
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(igraph_es_t *es) {
return es->type == IGRAPH_ES_ALL;
}
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_FINALLY_CLEAN(1);
return 0;
}
/**************************************************/
int igraph_i_eit_create_allfromto(const igraph_t *graph,
igraph_es_t es, igraph_eit_t *eit,
igraph_neimode_t mode) {
igraph_vector_t *vec;
long int no_of_nodes=igraph_vcount(graph);
long int i;
vec=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_adjacent(graph, &adj, 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=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_adjacent(graph, &adj, 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);
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=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=VECTOR(*es.data.path.ptr)[2*i];
long int to=VECTOR(*es.data.path.ptr)[2*i+1];
igraph_integer_t eid;
IGRAPH_CHECK(igraph_get_eid(graph, &eid, from, to, es.data.path.mode));
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=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(graph, (igraph_vector_t *) eit->vec,
es.data.path.ptr, es.data.path.mode));
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=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=VECTOR(*es.data.path.ptr)[i];
long int to=VECTOR(*es.data.path.ptr)[i+1];
igraph_integer_t eid;
IGRAPH_CHECK(igraph_get_eid(graph, &eid, from, to, es.data.path.mode));
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.
*
* 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_adj() it is O(d) where d is the number of
* adjacent 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, es, eit, IGRAPH_OUT));
break;
case IGRAPH_ES_ALLTO:
IGRAPH_CHECK(igraph_i_eit_create_allfromto(graph, es, eit, IGRAPH_IN));
break;
case IGRAPH_ES_ADJ:
eit->type=IGRAPH_EIT_VECTOR;
eit->pos=0;
eit->start=0;
eit->vec=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_adjacent(graph, (igraph_vector_t*)eit->vec,
es.data.adj.vid, es.data.adj.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_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;
}
syntax highlighted by Code2HTML, v. 0.9.1