igraph Reference Manual

For using the igraph C library

Chapter 11. Vertex and Edge Selectors and Sequences, Iterators

1.  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 igraph_vs_all() and the graph independence means that igraph_vs_all() is not parametrized by a graph object. That is, igraph_vs_all() is the general 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 immediate versions. These have the prefix igraph_vss instead of igraph_vs, e.g. igraph_vss_all() instead of igraph_vs_all(). The immediate versions are to be used in the parameter list of the igraph functions, such as igraph_degree(). These functions are not associated with any igraph_vs_t object, so they have no separate constructors and destructors (destroy functions).

2. Vertex selector constructors

Vertex selectors are created by vertex selector constructors, can be instantiated with igraph_vit_create(), and are destroyed with igraph_vs_destroy().

2.1. igraph_vs_all — Vertex set, all vertices of a graph.

int igraph_vs_all(igraph_vs_t *vs);

Arguments: 

vs:

Pointer to an uninitialized igraph_vs_t object.

Returns: 

Error code.

See also: 

This selector includes all vertices of a given graph in increasing vertex id order.

Time complexity: O(1).

2.2. igraph_vs_adj — Adjacent vertices of a vertex.

int igraph_vs_adj(igraph_vs_t *vs, 
		  igraph_integer_t vid, igraph_neimode_t mode);

All neighboring vertices of a given vertex are selected by this selector. The 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.

Arguments: 

vs:

Pointer to an uninitialized vertex selector object.

vid:

Vertex ID, the center of the neighborhood.

mode:

Decides the type of the neighborhood for directed graphs. This parameter is ignored for undirected graphs. Possible values:

IGRAPH_OUT

All vertices to which there is a directed edge from vid. That is, all the out-neighbors of vid.

IGRAPH_IN

All vertices from which there is a directed edge to vid. In other words, all the in-neighbors of vid.

IGRAPH_ALL

All vertices to which or from which there is a directed edge from/to vid. That is, all the neighbors of vid considered as if the graph is undirected.

Returns: 

Error code.

See also: 

Time complexity: O(1).

2.3. igraph_vs_nonadj — Non-adjacent vertices of a vertex.

int igraph_vs_nonadj(igraph_vs_t *vs, igraph_integer_t vid, 
		     igraph_neimode_t mode);

All non-neighboring vertices of a given vertex. The mode argument controls the type of neighboring vertices not to select. Instead of selecting immediate neighbors of vid as is done by igraph_vs_adj(), the current function selects vertices that are not immediate neighbors of vid.

Arguments: 

vs:

Pointer to an uninitialized vertex selector object.

vid:

Vertex ID, the center of the non-neighborhood.

mode:

The type of neighborhood not to select in directed graphs. Possible values:

IGRAPH_OUT

All vertices will be selected except those to which there is a directed edge from vid. That is, we select all vertices excluding the out-neighbors of vid.

IGRAPH_IN

All vertices will be selected except those from which there is a directed edge to vid. In other words, we select all vertices but the in-neighbors of vid.

IGRAPH_ALL

All vertices will be selected except those from or to which there is a directed edge to or from vid. That is, we select all vertices of vid except for its immediate neighbors.

Returns: 

Error code.

See also: 

Time complexity: O(1).

Example 11.1.  File examples/simple/igraph_vs_nonadj.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, 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.h>

int main () {

  igraph_t g;
  igraph_vs_t vs;
  igraph_vit_t vit;  
  igraph_integer_t size;

  /* empty graph, all vertices */
  igraph_empty(&g, 10, IGRAPH_DIRECTED);
  igraph_vs_nonadj(&vs, 0, IGRAPH_ALL);
  igraph_vs_size(&g, &vs, &size);
  printf("%li ", (long int) size);
  igraph_vit_create(&g, vs, &vit);
  while (!IGRAPH_VIT_END(vit)) {
    printf("%li ", (long int) IGRAPH_VIT_GET(vit));
    IGRAPH_VIT_NEXT(vit);
  }
  printf("\n");
  
  igraph_vit_destroy(&vit);
  igraph_vs_destroy(&vs);
  igraph_destroy(&g);

  /* full graph, no vertices */
  igraph_full(&g, 10, IGRAPH_UNDIRECTED, IGRAPH_LOOPS);
  igraph_vs_nonadj(&vs, 0, IGRAPH_ALL);
  igraph_vit_create(&g, vs, &vit);
  while (!IGRAPH_VIT_END(vit)) {
    printf("%li ", (long int) IGRAPH_VIT_GET(vit));
    IGRAPH_VIT_NEXT(vit);
  }
  printf("\n");
  
  igraph_vit_destroy(&vit);
  igraph_vs_destroy(&vs);
  igraph_destroy(&g);


  return 0;
}


2.4. igraph_vs_none — Empty vertex set.

int igraph_vs_none(igraph_vs_t *vs);

Creates an empty vertex selector.

Arguments: 

vs:

Pointer to an uninitialized vertex selector object.

Returns: 

Error code.

See also: 

Time complexity: O(1).

2.5. igraph_vs_1 — Vertex set with a single vertex.

int igraph_vs_1(igraph_vs_t *vs, igraph_integer_t vid);

This vertex selector selects a single vertex.

Arguments: 

vs:

Pointer to an uninitialized vertex selector object.

vid:

The vertex id to be selected.

Returns: 

Error Code.

See also: 

Time complexity: O(1).

2.6. igraph_vs_vector — Vertex set based on a vector.

int igraph_vs_vector(igraph_vs_t *vs,
		     const igraph_vector_t *v);

This function makes it possible to handle a vector_t temporarily as a vertex selector. The vertex selector should be thought of like a 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.

Arguments: 

vs:

Pointer to an uninitialized vertex selector.

v:

Pointer to a igraph_vector_t object.

Returns: 

Error code.

See also: 

Time complexity: O(1).

Example 11.2.  File examples/simple/igraph_vs_vector.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, 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.h>

int main() {

  igraph_t g;
  igraph_vector_t v=IGRAPH_VECTOR_NULL;
  igraph_real_t edges[] = { 0,1, 1,2, 2,2, 2,3, 2,4, 3,4 };
  igraph_vector_t v2;
  long int i;
  igraph_vit_t vit;
  igraph_vs_t vs;
  igraph_integer_t size;

  igraph_vector_view(&v, edges, sizeof(edges)/sizeof(igraph_real_t));
  igraph_create(&g, &v, 0, IGRAPH_DIRECTED);

  /* Create iterator based on a vector (view) */
  igraph_vector_init(&v2, 6);
  VECTOR(v2)[0]=0;   VECTOR(v2)[1]=2;
  VECTOR(v2)[2]=4;   VECTOR(v2)[3]=0;
  VECTOR(v2)[4]=2;   VECTOR(v2)[5]=4;

  igraph_vit_create(&g, igraph_vss_vector(&v2), &vit);

  i=0;
  while (!IGRAPH_VIT_END(vit)) {
    if (IGRAPH_VIT_GET(vit) != VECTOR(v2)[i]) {
      return 1;
    }
    IGRAPH_VIT_NEXT(vit);
    i++;
  }
  if (i != igraph_vector_size(&v2)) {
    return 2;
  }

  igraph_vit_destroy(&vit);
  igraph_vector_destroy(&v2);

  /* Create small vector iterator */

  igraph_vs_vector_small(&vs, 0, 2, 4, 0, 2, 4, 2, -1);
  igraph_vit_create(&g, vs, &vit);
  igraph_vs_size(&g, &vs, &size);
  printf("%li ", (long int) size);
  for (; !IGRAPH_VIT_END(vit); IGRAPH_VIT_NEXT(vit)) {
    printf("%li ", (long int) IGRAPH_VIT_GET(vit));
  }
  printf("\n");
  
  igraph_vit_destroy(&vit);
  igraph_vs_destroy(&vs);

  /* Clean up */

  igraph_destroy(&g);

  return 0;
}


2.7. igraph_vs_vector_small — Create a vertex set by giving its elements.

int igraph_vs_vector_small(igraph_vs_t *vs, ...);

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.

Arguments: 

vs:

Pointer to an uninitialized vertex selector object.

...:

Additional parameters, these will be the vertex ids to be included in the vertex selector. Supply a -1 after the last vertex id.

Returns: 

Error code.

See also: 

Time complexity: O(n), the number of vertex ids supplied.

2.8. igraph_vs_vector_copy — Vertex set based on a vector, with copying.

int igraph_vs_vector_copy(igraph_vs_t *vs,
			  const igraph_vector_t *v);

This function makes it possible to handle a 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.

Arguments: 

vs:

Pointer to an uninitialized vertex selector.

v:

Pointer to a igraph_vector_t object.

Returns: 

Error code.

See also: 

Time complexity: O(1).

2.9. igraph_vs_seq — Vertex set, an interval of vertices.

int igraph_vs_seq(igraph_vs_t *vs, 
		  igraph_integer_t from, igraph_integer_t to);

Creates a vertex selector containing all vertices with vertex id equal to or bigger than from and equal to or smaller than to.

Arguments: 

vs:

Pointer to an uninitialized vertex selector object.

from:

The first vertex id to be included in the vertex selector.

to:

The last vertex id to be included in the vertex selector.

Returns: 

Error code.

See also: 

Time complexity: O(1).

Example 11.3.  File examples/simple/igraph_vs_seq.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2007-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, 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.h>

int main() {
  
  igraph_vs_t vs;
  igraph_vit_t vit;
  igraph_t g;
  igraph_integer_t size;

  igraph_ring(&g, 10, IGRAPH_UNDIRECTED, 0, 1);
  igraph_vs_seq(&vs, 0, 9);
  igraph_vit_create(&g, vs, &vit);
  igraph_vs_size(&g, &vs, &size);
  printf("%li", (long int) size);
  
  while (!IGRAPH_VIT_END(vit)) {
    printf(" %li", (long int)IGRAPH_VIT_GET(vit));
    IGRAPH_VIT_NEXT(vit);
  }
  printf("\n");

  igraph_vit_destroy(&vit);
  igraph_vs_destroy(&vs);
  igraph_destroy(&g);
  
  return 0;
}


3. Generic vertex selector operations

3.1. igraph_vs_copy — Creates a copy of a vertex selector.

int igraph_vs_copy(igraph_vs_t* dest, const igraph_vs_t* src);

Arguments: 

src:

The selector being copied.

dest:

An uninitialized selector that will contain the copy.

3.2. igraph_vs_destroy — Destroy a vertex set.

void igraph_vs_destroy(igraph_vs_t *vs);

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 ).

Arguments: 

vs:

Pointer to a vertex selector object.

Time complexity: operating system dependent, usually O(1).

3.3. igraph_vs_is_all — Check whether all vertices are included.

igraph_bool_t igraph_vs_is_all(const igraph_vs_t *vs);

This function checks whether the vertex selector object was created by igraph_vs_all() or 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.

Arguments: 

vs:

Pointer to a vertex selector object.

Returns: 

TRUE (1) if the vertex selector contains all vertices and FALSE (0) otherwise.

Time complexity: O(1).

3.4. igraph_vs_size — Returns the size of the vertex selector.

int igraph_vs_size(const igraph_t *graph, const igraph_vs_t *vs,
  igraph_integer_t *result);

The size of the vertex selector is the number of vertices it will yield when it is iterated over.

Arguments: 

graph:

The graph over which we will iterate.

result:

The result will be returned here.

3.5. igraph_vs_type — Returns the type of the vertex selector.

int igraph_vs_type(const igraph_vs_t *vs);

4. Immediate vertex selectors

4.1. igraph_vss_all — All vertices of a graph (immediate version).

igraph_vs_t igraph_vss_all(void);

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.

Returns: 

A vertex selector for all vertices in a graph.

See also: 

Time complexity: O(1).

4.2. igraph_vss_none — Empty vertex set (immediate version).

igraph_vs_t igraph_vss_none(void);

The immediate version of the empty vertex selector.

Returns: 

An empty vertex selector.

See also: 

Time complexity: O(1).

4.3. igraph_vss_1 — Vertex set with a single vertex (immediate version).

igraph_vs_t igraph_vss_1(igraph_integer_t vid);

The immediate version of the single-vertex selector.

Arguments: 

vid:

The vertex to be selected.

Returns: 

A vertex selector containing a single vertex.

See also: 

Time complexity: O(1).

4.4. igraph_vss_vector — Vertex set based on a vector (immediate version).

igraph_vs_t igraph_vss_vector(const igraph_vector_t *v);

This is the immediate version of igraph_vs_vector.

Arguments: 

v:

Pointer to a igraph_vector_t object.

Returns: 

A vertex selector object containing the vertices in the vector.

See also: 

Time complexity: O(1).

4.5. igraph_vss_seq — An interval of vertices (immediate version).

igraph_vs_t igraph_vss_seq(igraph_integer_t from, igraph_integer_t to);

The immediate version of igraph_vs_seq().

Arguments: 

from:

The first vertex id to be included in the vertex selector.

to:

The last vertex id to be included in the vertex selector.

Returns: 

Error code.

See also: 

Time complexity: O(1).

5. Vertex iterators

5.1. igraph_vit_create — Creates a vertex iterator from a vertex selector.

int igraph_vit_create(const igraph_t *graph, 
		      igraph_vs_t vs, igraph_vit_t *vit);

This function instantiates a vertex selector object with a given graph. This is the step when the actual vertex ids are created from the logical notion of the vertex selector based on the graph. Eg. a vertex selector created with igraph_vs_all() contains knowledge that 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.

Arguments: 

graph:

An igraph_t object, a graph.

vs:

A vertex selector object.

vit:

Pointer to an uninitialized vertex iterator object.

Returns: 

Error code.

See also: 

Time complexity: it depends on the vertex selector type. O(1) for vertex selectors created with igraph_vs_all(), igraph_vs_none(), igraph_vs_1, igraph_vs_vector, igraph_vs_seq(), igraph_vs_vector(), igraph_vs_vector_small(). O(d) for igraph_vs_adj(), d is the number of vertex ids to be included in the iterator. O(|V|) for igraph_vs_nonadj(), |V| is the number of vertices in the graph.

5.2. igraph_vit_destroy — Destroys a vertex iterator.

void igraph_vit_destroy(const igraph_vit_t *vit);

Deallocates memory allocated for a vertex iterator.

Arguments: 

vit:

Pointer to an initialized vertex iterator object.

See also: 

Time complexity: operating system dependent, usually O(1).

5.3.  Stepping over the vertices

After creating an iterator with igraph_vit_create(), it points to the first vertex in the vertex determined by the vertex selector (if there is any). The IGRAPH_VIT_NEXT() macro steps to the next vertex, IGRAPH_VIT_END() checks whether there are more vertices to visit, IGRAPH_VIT_SIZE() gives the total size of the vertices visited so far and to be visited. IGRAPH_VIT_RESET() resets the iterator, it will point to the first vertex again. Finally IGRAPH_VIT_GET() gives the current vertex pointed to by the iterator (call this only if IGRAPH_VIT_END() is false).

Here is an example on how to step over the neighbors of vertex 0:

igraph_vs_t vs;
igraph_vit_t vit;
...
igraph_vs_adj(&vs, 0, IGRAPH_ALL);
igraph_vit_create(&graph, vs, &vit);
while (!IGRAPH_VIT_END(vit)) {
  printf(" %li", (long int) IGRAPH_VIT_GET(vit));
  IGRAPH_VIT_NEXT(vit);
}
printf("\n");
...
igraph_vit_destroy(&vit);
igraph_vs_destroy(&vs);

5.4. IGRAPH_VIT_NEXT — Next vertex.

#define IGRAPH_VIT_NEXT(vit)

Steps the iterator to the next vertex. Only call this function if IGRAPH_VIT_END() returns false.

Arguments: 

vit:

The vertex iterator to step.

Time complexity: O(1).

5.5. IGRAPH_VIT_END — Are we at the end?

#define IGRAPH_VIT_END(vit)

Checks whether there are more vertices to step to.

Arguments: 

vit:

The vertex iterator to check.

Returns: 

Logical value, if true there are no more vertices to step to.

Time complexity: O(1).

5.6. IGRAPH_VIT_SIZE — Size of a vertex iterator.

#define IGRAPH_VIT_SIZE(vit)

Gives the number of vertices in a vertex iterator.

Arguments: 

vit:

The vertex iterator.

Returns: 

The number of vertices.

Time complexity: O(1).

5.7. IGRAPH_VIT_RESET — Reset a vertex iterator.

#define IGRAPH_VIT_RESET(vit)

Resets a vertex iterator. After calling this macro the iterator will point to the first vertex.

Arguments: 

vit:

The vertex iterator.

Time complexity: O(1).

5.8. IGRAPH_VIT_GET — Query the current position.

#define IGRAPH_VIT_GET(vit)

Gives the vertex id of the current vertex pointed to by the iterator.

Arguments: 

vit:

The vertex iterator.

Returns: 

The vertex id of the current vertex.

Time complexity: O(1).

6. Edge selector constructors

6.1. igraph_es_all — Edge set, all edges.

int igraph_es_all(igraph_es_t *es, 
		  igraph_edgeorder_type_t order);

Arguments: 

es:

Pointer to an uninitialized edge selector object.

order:

Constant giving the order in which the edges will be included in the selector. Possible values: IGRAPH_EDGEORDER_ID, edge id order. IGRAPH_EDGEORDER_FROM, vertex id order, the id of the source vertex counts for directed graphs. The order of the incident edges of a given vertex is arbitrary. IGRAPH_EDGEORDER_TO, vertex id order, the id of the 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.

Returns: 

Error code.

See also: 

Time complexity: O(1).

6.2. igraph_es_incident — Edges incident on a given vertex.

int igraph_es_incident(igraph_es_t *es, 
		  igraph_integer_t vid, igraph_neimode_t mode);

Arguments: 

es:

Pointer to an uninitialized edge selector object.

vid:

Vertex id, of which the incident edges will be selected.

mode:

Constant giving the type of the incident edges to select. This is ignored for undirected graphs. Possible values: IGRAPH_OUT, outgoing edges; IGRAPH_IN, incoming edges; IGRAPH_ALL, all edges.

Returns: 

Error code.

See also: 

Time complexity: O(1).

Example 11.4.  File examples/simple/igraph_es_adj.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, 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.h>

void igraph_vector_print(const igraph_vector_t *v) {
  long int i;
  for (i=0; i<igraph_vector_size(v); i++) {
    printf("%li ", (long int)VECTOR(*v)[i]);
  }
  printf("\n");
}

int main() {
  
  igraph_t g;
  const igraph_vector_t v=IGRAPH_VECTOR_NULL;
  igraph_real_t edges1[] = { 0,1, 1,2, 2,2, 2,3, 2,4, 3,4 };
  igraph_vector_t was;
  igraph_integer_t size;
  igraph_es_t it;
  long int i;
  
  igraph_vector_view(&v, edges1, sizeof(edges1)/sizeof(igraph_real_t));
  igraph_vector_init(&was, 0);

  /******************************************/
  /* Directed graph                         */
  /******************************************/
 
  igraph_create(&g, &v, 0, IGRAPH_DIRECTED);
  
  /* Simple test, all neighbors */
  for (i=0; i<=igraph_vector_max(&v); i++) {
    igraph_vector_clear(&was);
    igraph_es_adj(&g, &it, i, IGRAPH_ALL);
    igraph_es_size(&g, &it, &size);
    printf("%ld\n", (long)size);
    while (!igraph_es_end(&g, &it)) {
      igraph_vector_push_back(&was, igraph_es_adj_vertex(&g, &it));
      igraph_es_next(&g, &it);
    }
    igraph_es_destroy(&it);
    igraph_vector_sort(&was);
    igraph_vector_print(&was);
  }

  /* Simple test, outgoing neighbors */
  for (i=0; i<=igraph_vector_max(&v); i++) {
    igraph_vector_clear(&was);
    igraph_es_adj(&g, &it, i, IGRAPH_OUT);
    igraph_es_size(&g, &it, &size);
    printf("%ld\n", (long)size);
    while (!igraph_es_end(&g, &it)) {
      igraph_vector_push_back(&was, igraph_es_adj_vertex(&g, &it));
      igraph_es_next(&g, &it);
    }
    igraph_es_destroy(&it);
    igraph_vector_sort(&was);
    igraph_vector_print(&was);
  }


  /* Simple test, incoming neighbors */
  for (i=0; i<=igraph_vector_max(&v); i++) {
    igraph_vector_clear(&was);
    igraph_es_adj(&g, &it, i, IGRAPH_IN);
    igraph_es_size(&g, &it, &size);
    printf("%ld\n", (long)size);
    while (!igraph_es_end(&g, &it)) {
      igraph_vector_push_back(&was, igraph_es_adj_vertex(&g, &it));
      igraph_es_next(&g, &it);
    }
    igraph_es_destroy(&it);
    igraph_vector_sort(&was);
    igraph_vector_print(&was);
  }
		       
  igraph_destroy(&g);

  /******************************************/
  /* Undirected graph                       */
  /******************************************/

  igraph_create(&g, &v, 0, IGRAPH_UNDIRECTED);

  /* Simple test, all neighbors */
  for (i=0; i<=igraph_vector_max(&v); i++) {
    igraph_vector_clear(&was);
    igraph_es_adj(&g, &it, i, IGRAPH_ALL);
    igraph_es_size(&g, &it, &size);
    printf("%ld\n", (long)size);
    while (!igraph_es_end(&g, &it)) {
      igraph_vector_push_back(&was, igraph_es_adj_vertex(&g, &it));
      igraph_es_next(&g, &it);
    }
    igraph_es_destroy(&it);
    igraph_vector_sort(&was);
    igraph_vector_print(&was);
  }

  igraph_destroy(&g);
  igraph_vector_destroy(&was);
  
  return 0;
}


6.3. igraph_es_none — Empty edge selector.

int igraph_es_none(igraph_es_t *es);

Arguments: 

es:

Pointer to an uninitialized edge selector object to initialize.

Returns: 

Error code.

See also: 

Time complexity: O(1).

6.4. igraph_es_1 — Edge selector containing a single edge.

int igraph_es_1(igraph_es_t *es, igraph_integer_t eid);

Arguments: 

es:

Pointer to an uninitialized edge selector object.

eid:

Edge id of the edge to select.

Returns: 

Error code.

See also: 

Time complexity: O(1).

6.5. igraph_es_vector — Handle a vector as an edge selector.

int igraph_es_vector(igraph_es_t *es,
		     const igraph_vector_t *v);

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.

Arguments: 

es:

Pointer to an uninitialized edge selector.

v:

Vector containing edge ids.

Returns: 

Error code.

See also: 

Time complexity: O(1).

6.6. igraph_es_fromto — Edge selector, all edges between two vertex sets.

int igraph_es_fromto(igraph_es_t *es,
		     igraph_vs_t from, igraph_vs_t to);

This function is not implemented yet.

Arguments: 

es:

Pointer to an uninitialized edge selector.

from:

Vertex selector, their outgoing edges will be selected.

to:

Vertex selector, their incoming edges will be selected from the previous selection.

Returns: 

Error code.

See also: 

Time complexity: O(1).

Example 11.5.  File examples/simple/igraph_es_fromto.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, 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.h>

void igraph_vector_print(const igraph_vector_t *v) {
  long int i;
  for (i=0; i<igraph_vector_size(v); i++) {
    printf("%li ", (long int)VECTOR(*v)[i]);
  }
  printf("\n");
}

int main() {
  
  igraph_t g;
  const igraph_vector_t v=IGRAPH_VECTOR_NULL;
  igraph_real_t edges1[] = { 0,1, 1,2, 2,2, 2,3, 2,4, 3,4 };
  igraph_vector_t from, to;  
  igraph_es_t it;
  igraph_integer_t size;
  long int i;

  igraph_vector_view(&v, edges1, sizeof(edges1)/sizeof(igraph_real_t));

  /******************************************/
  /* Directed graph                         */
  /******************************************/
  
  igraph_create(&g, &v, 0, IGRAPH_DIRECTED);
  
  /* {0,1} -> {2,3}, result should be { 1->2 } */
  igraph_vector_init(&from, 2); VECTOR(from)[0]=0; VECTOR(from)[1]=1;
  igraph_vector_init(&to, 2);   VECTOR(to)  [0]=2; VECTOR(to)  [1]=3;
  igraph_es_fromto(&g, &it, IGRAPH_VS_VECTOR(&g, &from), 
		   IGRAPH_VS_VECTOR(&g, &to), IGRAPH_DIRECTED);
  igraph_vector_clear(&from); igraph_vector_clear(&to);
  igraph_es_size(&g, &it, &size);
  printf("%ld\n", (long)size);
  while (!igraph_es_end(&g, &it)) {
    igraph_vector_push_back(&from, igraph_es_from(&g, &it));
    igraph_vector_push_back(&to, igraph_es_to(&g, &it));
    igraph_es_next(&g, &it);
  }
  igraph_vector_sort(&from); igraph_vector_sort(&to);
  igraph_vector_print(&from); igraph_vector_print(&to);

  igraph_es_destroy(&it);

  igraph_vector_destroy(&from);
  igraph_vector_destroy(&to);
  
  return 0;
}


6.7. igraph_es_seq — Edge selector, a sequence of edge ids.

int igraph_es_seq(igraph_es_t *es, 
		  igraph_integer_t from, igraph_integer_t to);

All edge ids between from and to will be included in the edge selection.

Arguments: 

es:

Pointer to an uninitialized edge selector object.

from:

The first edge id to be included.

to:

The last edge id to be included.

Returns: 

Error code.

See also: 

Time complexity: O(1).

6.8. igraph_es_pairs — Edge selector, multiple edges defined by their endpoints in a vector.

int igraph_es_pairs(igraph_es_t *es, const igraph_vector_t *v, 
		    igraph_bool_t directed);

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.

Arguments: 

es:

Pointer to an uninitialized edge selector object.

v:

The vector containing the endpoints of the edges.

directed:

Whether the graph is directed or not.

Returns: 

Error code.

See also: 

Time complexity: O(n), the number of edges being selected.

Example 11.6.  File examples/simple/igraph_es_pairs.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, 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.h>

int main() {
  
  igraph_t g;
  long int i;
  igraph_integer_t size;

  /* DIRECTED */
  
  igraph_star(&g, 10, IGRAPH_STAR_OUT, 0);  

  for (i=0; i<100; i++) {
    igraph_es_t es;
    igraph_eit_t it;
    igraph_es_pairs_small(&es, IGRAPH_DIRECTED, 
			  0,1,0,2,0,5,0,2,0,3,0,4,0,7,0,9, -1);
    igraph_eit_create(&g, es, &it);
    igraph_es_size(&g, &es, &size);
    IGRAPH_EIT_RESET(it);
    while (!IGRAPH_EIT_END(it)) {
      (void) IGRAPH_EIT_GET(it);
      IGRAPH_EIT_NEXT(it);
      size--;
    }
    if (size != 0) return 1;
    igraph_eit_destroy(&it);
    igraph_es_destroy(&es);
  }

  igraph_destroy(&g);

  /* UNDIRECTED */
  
  igraph_star(&g, 10, IGRAPH_STAR_UNDIRECTED, 0);
  
  for (i=0; i<100; i++) {
    igraph_es_t es;
    igraph_eit_t it;
    igraph_es_pairs_small(&es, IGRAPH_DIRECTED,
			  0,1,2,0,5,0,0,2,3,0,0,4,7,0,0,9, -1);
    igraph_eit_create(&g, es, &it);
    IGRAPH_EIT_RESET(it);
    while (!IGRAPH_EIT_END(it)) {
      (void) IGRAPH_EIT_GET(it);
      IGRAPH_EIT_NEXT(it);
    }
    igraph_eit_destroy(&it);
    igraph_es_destroy(&es);
  }

  igraph_destroy(&g);

  return 0;
}


6.9. igraph_es_pairs_small — Edge selector, multiple edges defined by their endpoints as arguments.

int igraph_es_pairs_small(igraph_es_t *es, igraph_bool_t directed, ...);

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.

Arguments: 

es:

Pointer to an uninitialized edge selector object.

directed:

Whether the graph is directed or not.

Returns: 

Error code.

See also: 

Time complexity: O(n), the number of edges being selected.

6.10. igraph_es_vector_copy — Edge set, based on a vector, with copying.

int igraph_es_vector_copy(igraph_es_t *es, const igraph_vector_t *v);

This function makes it possible to handle a 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.

Arguments: 

es:

Pointer to an uninitialized edge selector.

v:

Pointer to a igraph_vector_t object.

Returns: 

Error code.

See also: 

Time complexity: O(1).

7. Immediate edge selectors

7.1. igraph_ess_all — Edge set, all edges (immediate version)

igraph_es_t igraph_ess_all(igraph_edgeorder_type_t order);

The immediate version of the all-vertices selector.

Arguments: 

order:

Constant giving the order of the edges in the edge selector. See igraph_es_all() for the possible values.

Returns: 

The edge selector.

See also: 

Time complexity: O(1).

7.2. igraph_ess_none — Immediate empty edge selector.

igraph_es_t igraph_ess_none(void);

Immediate version of the empty edge selector.

Returns: 

Initialized empty edge selector.

See also: 

Time complexity: O(1).

7.3. igraph_ess_1 — Immediate version of the single edge edge selector.

igraph_es_t igraph_ess_1(igraph_integer_t eid);

Arguments: 

eid:

The id of the edge.

Returns: 

The edge selector.

See also: 

Time complexity: O(1).

7.4. igraph_ess_vector — Immediate vector view edge selector.

igraph_es_t igraph_ess_vector(const igraph_vector_t *v);

This is the immediate version of the vector of edge ids edge selector.

Arguments: 

v:

The vector of edge ids.

Returns: 

Edge selector, initialized.

See also: 

Time complexity: O(1).

7.5. igraph_ess_seq — Immediate version of the sequence edge selector.

igraph_es_t igraph_ess_seq(igraph_integer_t from, igraph_integer_t to);

Arguments: 

from:

The first edge id to include.

to:

The last edge id to include.

Returns: 

The initialized edge selector.

See also: 

Time complexity: O(1).

8. Generic edge selector operations

8.1. igraph_es_copy — Creates a copy of an edge selector.

int igraph_es_copy(igraph_es_t* dest, const igraph_es_t* src);

Arguments: 

src:

The selector being copied.

dest:

An uninitialized selector that will contain the copy.

See also: 

8.2. igraph_es_destroy — Destroys an edge selector object.

void igraph_es_destroy(igraph_es_t *es);

Call this function on an edge selector when it is not needed any more. Do not call this function on edge selectors created by immediate constructors, those don't need to be destroyed.

Arguments: 

es:

Pointer to an edge selector object.

Time complexity: operating system dependent, usually O(1).

8.3. igraph_es_is_all — Check whether an edge selector includes all edges.

igraph_bool_t igraph_es_is_all(const igraph_es_t *es);

Arguments: 

es:

Pointer to an edge selector object.

Returns: 

TRUE (1) if es was created with igraph_es_all() or igraph_ess_all(), and FALSE (0) otherwise.

Time complexity: O(1).

8.4. igraph_es_size — Returns the size of the edge selector.

int igraph_es_size(const igraph_t *graph, const igraph_es_t *es,
  igraph_integer_t *result);

The size of the edge selector is the number of edges it will yield when it is iterated over.

Arguments: 

graph:

The graph over which we will iterate.

result:

The result will be returned here.

8.5. igraph_es_type — Returns the type of the edge selector.

int igraph_es_type(const igraph_es_t *es);

9. Edge iterators

9.1. igraph_eit_create — Creates an edge iterator from an edge selector.

int igraph_eit_create(const igraph_t *graph, 
		      igraph_es_t es, igraph_eit_t *eit);

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.

Arguments: 

graph:

An igraph_t object for which the edge selector will be instantiated.

es:

The edge selector to instantiate.

eit:

Pointer to an uninitialized edge iterator.

Returns: 

Error code.

See also: 

Time complexity: depends on the type of the edge selector. For edge selectors created by igraph_es_all(), igraph_es_none(), igraph_es_1(), igraph_es_vector(), igraph_es_seq() it is O(1). For igraph_es_incident() it is O(d) where d is the number of incident edges of the vertex.

9.2. igraph_eit_destroy — Destroys an edge iterator.

void igraph_eit_destroy(const igraph_eit_t *eit);

Arguments: 

eit:

Pointer to an edge iterator to destroy.

See also: 

Time complexity: operating system dependent, usually O(1).

9.3.  Stepping over the edges

Just like for vertex iterators, macros are provided for stepping over a sequence of edges: IGRAPH_EIT_NEXT() goes to the next edge, IGRAPH_EIT_END() checks whether there are more edges to visit, IGRAPH_EIT_SIZE() gives the number of edges in the edge sequence, IGRAPH_EIT_RESET() resets the iterator to the first edge and IGRAPH_EIT_GET() returns the id of the current edge.

9.4. IGRAPH_EIT_NEXT — Next edge.

#define IGRAPH_EIT_NEXT(eit)

Steps the iterator to the next edge. Call this function only if IGRAPH_EIT_END() returns false.

Arguments: 

eit:

The edge iterator to step.

Time complexity: O(1).

9.5. IGRAPH_EIT_END — Are we at the end?

#define IGRAPH_EIT_END(eit)

Checks whether there are more edges to step to.

Arguments: 

wit:

The edge iterator to check.

Returns: 

Logical value, if true there are no more edges to step to.

Time complexity: O(1).

9.6. IGRAPH_EIT_SIZE — Number of edges in the iterator.

#define IGRAPH_EIT_SIZE(eit)

Gives the number of edges in an edge iterator.

Arguments: 

eit:

The edge iterator.

Returns: 

The number of edges.

Time complexity: O(1).

9.7. IGRAPH_EIT_RESET — Reset an edge iterator.

#define IGRAPH_EIT_RESET(eit)

Resets an edge iterator. After calling this macro the iterator will point to the first edge.

Arguments: 

eit:

The edge iterator.

Time complexity: O(1).

9.8. IGRAPH_EIT_GET — Query an edge iterator.

#define IGRAPH_EIT_GET(eit)

Gives the edge id of the current edge pointed to by an iterator.

Arguments: 

eit:

The edge iterator.

Returns: 

The id of the current edge.

Time complexity: O(1).