igraph Reference Manual

For using the igraph C library

Chapter 10. Games on Graphs

1. Microscopic Update Rules

1.1. igraph_deterministic_optimal_imitation — Adopt a strategy via deterministic optimal imitation.

int igraph_deterministic_optimal_imitation(const igraph_t *graph,
                                           igraph_integer_t vid,
                                           igraph_optimal_t optimality,
                                           const igraph_vector_t *quantities,
                                           igraph_vector_t *strategies,
                                           igraph_neimode_t mode);

A simple deterministic imitation strategy where a vertex revises its strategy to that which yields a local optimal. Here "local" is with respect to the immediate neighbours of the vertex. The vertex retains its current strategy where this strategy yields a locally optimal quantity. The quantity in this case could be a measure such as fitness.

Arguments: 

graph:

The graph object representing the game network. This cannot be the empty or trivial graph, but must have at least two vertices and one edge. If graph has one vertex, then no strategy update would take place. Furthermore, if graph has at least two vertices but zero edges, then strategy update would also not take place.

vid:

The vertex whose strategy is to be updated. It is assumed that vid represents a vertex in graph. No checking is performed and it is your responsibility to ensure that vid is indeed a vertex of graph. If an isolated vertex is provided, i.e. the input vertex has degree 0, then no strategy update would take place and vid would retain its current strategy. Strategy update would also not take place if the local neighbourhood of vid are its in-neighbours (respectively out-neighbours), but vid has zero in-neighbours (respectively out-neighbours). Loops are ignored in computing the degree (in, out, all) of vid.

optimality:

Logical; controls the type of optimality to be used. Supported values are:

IGRAPH_MAXIMUM

Use maximum deterministic imitation, where the strategy of the vertex with maximum quantity (e.g. fitness) would be adopted. We update the strategy of vid to that which yields a local maximum.

IGRAPH_MINIMUM

Use minimum deterministic imitation. That is, the strategy of the vertex with minimum quantity would be imitated. In other words, update to the strategy that yields a local minimum.

quantities:

A vector of quantities providing the quantity of each vertex in graph. Think of each entry of the vector as being generated by a function such as the fitness function for the game. So if the vector represents fitness quantities, then each vector entry is the fitness of some vertex. The length of this vector must be the same as the number of vertices in the vertex set of graph.

strategies:

A vector of the current strategies for the vertex population. The updated strategy for vid would be stored here. Each strategy is identified with a nonnegative integer, whose interpretation depends on the payoff matrix of the game. Generally we use the strategy ID as a row or column index of the payoff matrix. The length of this vector must be the same as the number of vertices in the vertex set of graph.

mode:

Defines the sort of neighbourhood to consider for vid. If graph is undirected, then we use all the immediate neighbours of vid. Thus if you know that graph is undirected, then it is safe to pass the value IGRAPH_ALL here. Supported values are:

IGRAPH_OUT

Use the out-neighbours of vid. This option is only relevant when graph is a directed graph.

IGRAPH_IN

Use the in-neighbours of vid. Again this option is only relevant when graph is a directed graph.

IGRAPH_ALL

Use both the in- and out-neighbours of vid. This option is only relevant if graph is a digraph. Also use this value if graph is undirected.

Returns: 

The error code IGRAPH_EINVAL is returned in each of the following cases: (1) Any of the parameters graph, quantities, or strategies is a null pointer. (2) The vector quantities or strategies has a length different from the number of vertices in graph. (3) The parameter graph is the empty or null graph, i.e. the graph with zero vertices and edges.

Time complexity: O(2d), where d is the degree of the vertex vid.

Example 10.1.  File examples/simple/igraph_deterministic_optimal_imitation.c

/* -*- mode: C -*-  */
/*
  Test suite for deterministic optimal imitation.
  Copyright (C) 2011 Minh Van Nguyen <nguyenminh2@gmail.com>

  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 <stdio.h>

/* test parameters structure */
typedef struct {
  igraph_t *graph;
  igraph_integer_t vertex;
  igraph_optimal_t optimality;
  igraph_vector_t *quantities;
  igraph_vector_t *strategies;
  igraph_neimode_t mode;
  int retval;
} strategy_test_t;

/* Error tests. That is, we expect error codes to be returned from such tests.
 */
int error_tests() {
  igraph_t g, h;
  igraph_vector_t quant, strat;
  int i, n, ret;
  strategy_test_t *test;

  /* nonempty graph */
  igraph_small(&g, 0, IGRAPH_UNDIRECTED, 0,1, 1,2, 2,0, -1);
  igraph_empty(&h, 0, 0);         /* empty graph */
  igraph_vector_init(&quant, 1);  /* quantities vector */
  igraph_vector_init(&strat, 2);  /* strategies vector */

  {
    /* test parameters */
    /*--graph--vertex--optimality--quantities--strategies--mode--retval--*/
    /* null pointer for graph */
    strategy_test_t null_graph = { NULL, 0, 0, NULL, NULL, IGRAPH_ALL, 
				   IGRAPH_EINVAL };
    /* null pointer for quantities vector */
    strategy_test_t null_quant = { &g, 0, 0, NULL, NULL, IGRAPH_ALL, 
				   IGRAPH_EINVAL };
    /* null pointer for strategies vector */
    strategy_test_t null_strat = { &g, 0, 0, &quant, NULL, IGRAPH_ALL, 
				   IGRAPH_EINVAL };
    /* empty graph */
    strategy_test_t empty_graph = {&h, 0, 0, &quant, &strat, IGRAPH_ALL, 
				   IGRAPH_EINVAL };
    /* length of quantities vector different from number of vertices */
    strategy_test_t qdiff_length = {&g, 0, 0, &quant, &strat, IGRAPH_ALL, 
				    IGRAPH_EINVAL };
    /* length of strategies vector different from number of vertices */
    strategy_test_t sdiff_length = {&g, 0, 0, &quant, &strat, IGRAPH_ALL, 
				    IGRAPH_EINVAL };
    strategy_test_t *all_checks[] = {/* 1 */ &null_graph,
				     /* 2 */ &null_quant,
				     /* 3 */ &null_strat,
				     /* 4 */ &empty_graph,
				     /* 5 */ &qdiff_length,
				     /* 6 */ &sdiff_length};
    n = 6;
    /* Run the error tests. We expect an error to be raised for each test. */
    igraph_set_error_handler(igraph_error_handler_ignore);
    i = 0;
    while (i < n) {
      test = all_checks[i];
      ret = igraph_deterministic_optimal_imitation(test->graph,
						   test->vertex,
						   test->optimality,
						   test->quantities,
						   test->strategies,
						   test->mode);
      if (ret != test->retval) {
	printf("Error test no. %d failed.\n", (int)(i + 1));
	return IGRAPH_FAILURE;
      }
      i++;
    }
  }
  /* clean up */
  igraph_destroy(&g);
  igraph_destroy(&h);
  igraph_vector_destroy(&quant);
  igraph_vector_destroy(&strat);

  return IGRAPH_SUCCESS;
}

/* Updating the strategy of an isolated vertex. In this case, the strategies
 * vector should not change at all.
 */
int isolated_vertex_test() {
  igraph_t g;
  igraph_vector_t quant, strat, v;
  int i, ret;

  /* graph with one isolated vertex */
  igraph_small(&g, 0, IGRAPH_UNDIRECTED, 0,1, 1,2, 2,0, -1);
  igraph_add_vertices(&g, 1, 0);  /* new vertex 3 is isolated */
  /* quantities vector: all vertices have the same fitness */
  igraph_vector_init_real(&quant, 4, 0.25, 0.25, 0.25, 0.25);
  /* strategies vector: 0 means aggressive strategy; 1 means passive */
  igraph_vector_init_real(&strat, 4, 1., 0., 1., 0.);
  /* make a copy of the original strategies vector for comparison later on */
  igraph_vector_copy(&v, &strat);
  /* Now update strategy of vertex 3. Since this vertex is isolated, no */
  /* strategy update would take place. The resulting strategies vector */
  /* would be the same as it was originally. */
  ret = igraph_deterministic_optimal_imitation(/*graph*/ &g,
  					       /*vertex*/ 3,
  					       /*optimality*/ IGRAPH_MAXIMUM,
  					       /*quantities*/ &quant,
  					       /*strategies*/ &strat,
  					       /*mode*/ IGRAPH_ALL);
  if (ret) {
    printf("Isolated vertex test failed.\n");
    return IGRAPH_FAILURE;
  }
  for (i = 0; i < igraph_vector_size(&strat); i++) {
    if (VECTOR(strat)[i] != VECTOR(v)[i]) {
      printf("Isolated vertex test failed.\n");
      return IGRAPH_FAILURE;
    }
  }
  /* clean up */
  igraph_destroy(&g);
  igraph_vector_destroy(&quant);
  igraph_vector_destroy(&strat);
  igraph_vector_destroy(&v);

  return IGRAPH_SUCCESS;
}

/* A game on the Petersen graph. This graph has 10 vertices and 15 edges.
 * The Petersen graph is initialized with a default quantities vector and a
 * default strategies vector. For each vertex v in the graph, we update the
 * strategy of v via deterministic optimal imitation. The resulting updated
 * strategies vector is compared with the known result vector. A mismatch would
 * raise an error code. If the updated strategies vector matches the known
 * result vector, we reset the strategies vector to its default state and
 * repeat the game with another vertex.
 */
int petersen_game_test() {
  igraph_t g;
  igraph_vector_t known_max_v, known_min_v, quant, strat, stratcopy;
  int i, nedge, nvert;  

  /* the Petersen graph */
  igraph_small(&g, /*n=*/ 0, IGRAPH_UNDIRECTED, 
	       0,1,0,4,0,5, 1,2,1,6, 2,3,2,7, 3,4,3,8, 4,9,
	       5,7,5,8, 6,8,6,9, 7,9, -1);
  nedge = igraph_ecount(&g);
  nvert = igraph_vcount(&g);
  /* Strategies vector, one strategy for each vertex. Thus vec[i] is the */
  /* strategy of vertex i. The strategy space is: {0, 1, 2, 3}. */
  igraph_vector_init_real(&strat, nvert, 
			  1., 1., 2., 2., 0.,
			  0., 0., 1., 2., 3.);
  /* Quantities vector, one quantity per vertex. Thus vec[i] is the */
  /* quantity for vertex i. */
  igraph_vector_init_real(&quant, nvert, 
			  0.3, 1.1, 0.5, 1.0, 0.9, 
			  0.8, 0.4, 0.1, 0.7, 0.7);
  /* Known strategies that would be adopted. Thus vec[i] means that in */
  /* game i where we revise the strategy of vertex i, the strategy */
  /* vec[i] would be adopted by i. */
  /*maximum deterministic imitation*/
  igraph_vector_init_real(&known_max_v, nvert, 
			  1., 1., 1., 2., 2., 
			  0., 1., 0., 2., 0.);
  /*minimum deterministic imitation*/
  igraph_vector_init_real(&known_min_v, nvert,
			  1., 1., 1., 2., 1.,
			  1., 0., 1., 0., 1.);
  /* play game and compare resulting updated strategies */
  for (i = 0; i < nvert; i++) {
    /* maximum deterministic imitation */
    igraph_vector_copy(&stratcopy, &strat);
    igraph_deterministic_optimal_imitation(/*graph*/ &g,
					   /*vertex*/ (igraph_integer_t)i,
					   /*optimality*/ IGRAPH_MAXIMUM,
					   /*quantities*/ &quant,
					   /*strategies*/ &stratcopy,
					   /*neighbours*/ IGRAPH_ALL);
    if (VECTOR(stratcopy)[i] != VECTOR(known_max_v)[i]) {
      printf("Maximum deterministic imitation failed for vertex %d.\n", i);
      return IGRAPH_FAILURE;
    }
    igraph_vector_destroy(&stratcopy);
    /* minimum deterministic imitation */
    igraph_vector_copy(&stratcopy, &strat);
    igraph_deterministic_optimal_imitation(/*graph*/ &g,
					   /*vertex*/ (igraph_integer_t)i,
					   /*optimality*/ IGRAPH_MINIMUM,
					   /*quantities*/ &quant,
					   /*strategies*/ &stratcopy,
					   /*neighbours*/ IGRAPH_ALL);
    if (VECTOR(stratcopy)[i] != VECTOR(known_min_v)[i]) {
      printf("Minimum deterministic imitation failed for vertex %d.\n", i);
      return IGRAPH_FAILURE;
    }
    igraph_vector_destroy(&stratcopy);
  }
  /* clean up */
  igraph_destroy(&g);
  igraph_vector_destroy(&known_max_v);
  igraph_vector_destroy(&known_min_v);
  igraph_vector_destroy(&quant);
  igraph_vector_destroy(&strat);

  return IGRAPH_SUCCESS;
}

int main() {
  int ret;

  ret = error_tests();
  if (ret)
    return ret;
  ret = isolated_vertex_test();
  if (ret)
    return ret;
  ret = petersen_game_test();
  if (ret)
    return ret;

  return IGRAPH_SUCCESS;
}


1.2. igraph_moran_process — The Moran process in a network setting.

int igraph_moran_process(const igraph_t *graph,
                         const igraph_vector_t *weights,
                         igraph_vector_t *quantities,
                         igraph_vector_t *strategies,
                         igraph_neimode_t mode);

This is an extension of the classic Moran process to a network setting. The Moran process is a model of haploid (asexual) reproduction within a population having a fixed size. In the network setting, the Moran process operates on a weighted graph. At each time step a vertex a is chosen for reproduction and another vertex b is chosen for death. Vertex a gives birth to an identical clone c, which replaces b. Vertex c is a clone of a in that c inherits both the current quantity (e.g. fitness) and current strategy of a.

The graph G representing the game network is assumed to be simple, i.e. free of loops and without multiple edges. If, on the other hand, G has a loop incident on some vertex v, then it is possible that when v is chosen for reproduction it would forgo this opportunity. In particular, when v is chosen for reproduction and v is also chosen for death, the clone of v would be v itself with its current vertex ID. In effect v forgoes its chance for reproduction.

Arguments: 

graph:

The graph object representing the game network. This cannot be the empty or trivial graph, but must have at least two vertices and one edge. The Moran process will not take place in each of the following cases: (1) If graph has one vertex. (2) If graph has at least two vertices but zero edges.

weights:

A vector of all edge weights for graph. Thus weights[i] means the weight of the edge with edge ID i. For the purpose of the Moran process, each weight is assumed to be positive; it is your responsibility to ensure this condition holds. The length of this vector must be the same as the number of edges in graph.

quantities:

A vector of quantities providing the quantity of each vertex in graph. The quantity of the new clone will be stored here. Think of each entry of the vector as being generated by a function such as the fitness function for the game. So if the vector represents fitness quantities, then each vector entry is the fitness of some vertex. The length of this vector must be the same as the number of vertices in the vertex set of graph. For the purpose of the Moran process, each vector entry is assumed to be nonnegative; no checks will be performed for this. It is your responsibility to ensure that at least one entry is positive. Furthermore, this vector cannot be a vector of zeros; this condition will be checked.

strategies:

A vector of the current strategies for the vertex population. The strategy of the new clone will be stored here. Each strategy is identified with a nonnegative integer, whose interpretation depends on the payoff matrix of the game. Generally we use the strategy ID as a row or column index of the payoff matrix. The length of this vector must be the same as the number of vertices in the vertex set of graph.

mode:

Defines the sort of neighbourhood to consider for the vertex a chosen for reproduction. This is only relevant if graph is directed. If graph is undirected, then it is safe to pass the value IGRAPH_ALL here. Supported values are:

IGRAPH_OUT

Use the out-neighbours of a. This option is only relevant when graph is directed.

IGRAPH_IN

Use the in-neighbours of a. Again this option is only relevant when graph is directed.

IGRAPH_ALL

Use both the in- and out-neighbours of a. This option is only relevant if graph is directed. Also use this value if graph is undirected.

Returns: 

The error code IGRAPH_EINVAL is returned in each of the following cases: (1) Any of the parameters graph, weights, quantities or strategies is a null pointer. (2) The vector quantities or strategies has a length different from the number of vertices in graph. (3) The vector weights has a length different from the number of edges in graph. (4) The parameter graph is the empty or null graph, i.e. the graph with zero vertices and edges. (5) The vector weights, or the combination of interest, sums to zero. (6) The vector quantities, or the combination of interest, sums to zero.

Time complexity: depends on the random number generator, but is usually O(n) where n is the number of vertices in graph.

References:

(Lieberman et al. 2005)

E. Lieberman, C. Hauert, and M. A. Nowak. Evolutionary dynamics on graphs. Nature, 433(7023):312--316, 2005.

(Moran 1958)

P. A. P. Moran. Random processes in genetics. Mathematical Proceedings of the Cambridge Philosophical Society, 54(1):60--71, 1958.

Example 10.2.  File examples/simple/igraph_moran_process.c

/* -*- mode: C -*-  */
/*
  Test suite for the Moran process in a network setting.
  Copyright (C) 2011 Minh Van Nguyen <nguyenminh2@gmail.com>

  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 <assert.h>
#include <igraph.h>
#include <stdio.h>

/* test parameters structure */
typedef struct {
  igraph_t *graph;
  igraph_vector_t *weights;
  igraph_vector_t *quantities;
  igraph_vector_t *strategies;
  igraph_neimode_t mode;
  int retval;
} strategy_test_t;

/* Error tests, i.e. we expect errors to be raised for each test.
 */
int error_tests() {
  igraph_t g, gzero, h;
  igraph_vector_t quant, quantnvert, quantzero;
  igraph_vector_t strat, stratnvert, stratzero;
  igraph_vector_t wgt, wgtnedge, wgtzero;
  int i, n, nvert, ret;
  strategy_test_t *test;

  igraph_empty(&h, 0, 0);  /* empty graph */
  /* nonempty graph */
  igraph_small(&g, /*nvert=*/ 0, IGRAPH_UNDIRECTED, 0,1, 1,2, 2,0, -1);
  nvert = igraph_vcount(&g);
  /* weights vectors */
  igraph_vector_init(&wgt, 0);
  igraph_vector_init(&wgtnedge, igraph_ecount(&g));
  /* quantities vectors */
  igraph_vector_init(&quant, 1);
  igraph_vector_init_real(&quantnvert, nvert, 0.1, 0.2, 0.3);
  /* strategies vectors */
  igraph_vector_init(&strat, 2);
  igraph_vector_init_real(&stratnvert, nvert, 0.0, 1.0, 2.0);

  igraph_small(&gzero, /*nvert=*/ 0, IGRAPH_UNDIRECTED,
               0,3, 0,4, 1,2, 1,4, 1,5, 2,3, 2,4, 3,4, -1);
  nvert = igraph_vcount(&gzero);
  igraph_vector_init(&quantzero, nvert);                /* vector of zeros */
  igraph_vector_init(&stratzero, nvert);                /* vector of zeros */
  igraph_vector_init(&wgtzero, igraph_ecount(&gzero));  /* vector of zeros */
  /* igraph_vector_init_real(&stratzero, nvert, 1.0, 0.0, 1.0, 2.0, 0.0, 3.0); */

  /* test parameters */
  /*------graph--weights--quantities--strategies--mode--retval------*/
  /* null pointer for graph */
  strategy_test_t null_graph = {NULL, NULL, NULL, NULL, IGRAPH_ALL, IGRAPH_EINVAL};
  /* null pointer for weights vector */
  strategy_test_t null_wgt = {&g, NULL, &quantnvert, &stratnvert, IGRAPH_ALL, IGRAPH_EINVAL};
  /* null pointer for quantities vector */
  strategy_test_t null_quant = {&g, &wgt, NULL, NULL, IGRAPH_ALL, IGRAPH_EINVAL};
  /* null pointer for strategies vector */
  strategy_test_t null_strat = {&g, &wgt, &quant, NULL, IGRAPH_ALL, IGRAPH_EINVAL};
  /* empty graph */
  strategy_test_t empty_graph = {&h, &wgt, &quant, &strat, IGRAPH_ALL, IGRAPH_EINVAL};
  /* length of quantities vector different from number of vertices */
  strategy_test_t qdiff_length = {&g, &wgtnedge, &quant, &strat, IGRAPH_ALL, IGRAPH_EINVAL};
  /* length of strategies vector different from number of vertices */
  strategy_test_t sdiff_length = {&g, &wgtnedge, &quantnvert, &strat, IGRAPH_ALL, IGRAPH_EINVAL};
  /* length of weights vector different from number of edges */
  strategy_test_t wdiff_length = {&g, &wgt, &quantnvert, &stratnvert, IGRAPH_ALL, IGRAPH_EINVAL};
  /* weights vector contains all zeros */
  strategy_test_t zero_wgt = {&g, &wgtnedge, &quantnvert, &stratnvert, IGRAPH_ALL, IGRAPH_EINVAL};
  /* quantities vector contains all zeros */
  strategy_test_t zero_quant = {&gzero, &wgtzero, &quantzero, &stratzero, IGRAPH_ALL, IGRAPH_EINVAL};
  strategy_test_t *all_checks[] = {/* 1 */  &null_graph,
                                   /* 2 */  &null_quant,
                                   /* 3 */  &null_strat,
                                   /* 4 */  &null_wgt,
                                   /* 5 */  &empty_graph,
                                   /* 6 */  &qdiff_length,
                                   /* 7 */  &sdiff_length,
                                   /* 8 */  &wdiff_length,
                                   /* 9 */  &zero_quant,
                                   /* 10 */ &zero_wgt};

  /* Run the error tests. We expect error to be raised for each test. */
  igraph_set_error_handler(igraph_error_handler_ignore);
  n = 10;
  i = 0;
  while (i < n) {
    test = all_checks[i];
    ret = igraph_moran_process(test->graph, test->weights, test->quantities,
                               test->strategies, test->mode);
    if (ret != test->retval) {
      printf("Error test no. %d failed.\n", (int)(i + 1));
      return IGRAPH_FAILURE;
    }
    i++;
  }
  /* clean up */
  igraph_destroy(&g);
  igraph_destroy(&gzero);
  igraph_destroy(&h);
  igraph_vector_destroy(&quant);
  igraph_vector_destroy(&quantnvert);
  igraph_vector_destroy(&quantzero);
  igraph_vector_destroy(&strat);
  igraph_vector_destroy(&stratnvert);
  igraph_vector_destroy(&stratzero);
  igraph_vector_destroy(&wgt);
  igraph_vector_destroy(&wgtnedge);
  igraph_vector_destroy(&wgtzero);

  return IGRAPH_SUCCESS;
}

/* One iteration of the Moran process on a simple digraph.
 */
int moran_one_test() {
  igraph_t g;
  igraph_integer_t u = -1;  /* vertex chosen for reproduction */
  igraph_integer_t v = -1;  /* clone of u */
  igraph_integer_t nedge, nvert;
  igraph_real_t q = 0.0;
  igraph_vector_t quant, quantcp;
  igraph_vector_t strat, stratcp;
  igraph_vector_t wgt;
  long int i;

  /* graph representing the game network; quantities and strategies vectors */
  igraph_small(&g, /*nvert*/ 0, IGRAPH_DIRECTED,
               0,1, 0,4, 1,2, 1,4, 2,1, 3,2, 4,0, 4,3, -1);
  nvert = igraph_vcount(&g);
  nedge = igraph_ecount(&g);
  igraph_vector_init_real(&quant, nvert, 0.77, 0.83, 0.64, 0.81, 0.05);
  igraph_vector_init_real(&strat, nvert, 2.0, 0.0, 0.0, 1.0, 2.0);
  /* Set the edge weights. Here we assume the following correspondence */
  /* between edge IDs and directed edges: */
  /* edge 0: 0 -> 1 */
  /* edge 1: 0 -> 4 */
  /* edge 2: 1 -> 2 */
  /* edge 3: 1 -> 4 */
  /* edge 4: 2 -> 1 */
  /* edge 5: 3 -> 2 */
  /* edge 6: 4 -> 0 */
  /* edge 7: 4 -> 3 */
  igraph_vector_init_real(&wgt, nedge, 1.9, 0.8, 6.2, 2.4, 1.1, 5.2, 7.3, 8.8);

  /* play game */
  igraph_vector_copy(&quantcp, &quant);
  igraph_vector_copy(&stratcp, &strat);
  igraph_moran_process(&g, &wgt, &quantcp, &stratcp, IGRAPH_OUT);

  /* Determine which vertex was chosen for death. The original quantities */
  /* vector contain unique values, i.e. no duplicates. Thus we compare the */
  /* updated quantities with the original one. */
  for (i = 0; i < igraph_vector_size(&quant); i++) {
    if (VECTOR(quant)[i] != VECTOR(quantcp)[i]) {
      /* found the new clone vertex */
      v = (igraph_integer_t)i;
      q = (igraph_real_t)VECTOR(quantcp)[i];
      break;
    }
  }
  assert(v >= 0);
  assert(q != 0.0);

  /* Now we know that v is a clone of some vertex. Determine the vertex that */
  /* v is a clone of. */
  for (i = 0; i < igraph_vector_size(&quant); i++) {
    if (VECTOR(quant)[i] == q) {
      /* found the vertex chosen for reproduction */
      u = (igraph_integer_t)i;
      break;
    }
  }
  assert(u >= 0);

  /* check that v is indeed a clone of u */
  if (VECTOR(quant)[u] != VECTOR(quantcp)[v])
    return IGRAPH_FAILURE;
  if (VECTOR(strat)[u] != VECTOR(stratcp)[v])
    return IGRAPH_FAILURE;

  igraph_destroy(&g);
  igraph_vector_destroy(&quant);
  igraph_vector_destroy(&quantcp);
  igraph_vector_destroy(&strat);
  igraph_vector_destroy(&stratcp);
  igraph_vector_destroy(&wgt);

  return IGRAPH_SUCCESS;
}

int main() {
  int ret;

  ret = error_tests();
  if (ret)
    return IGRAPH_FAILURE;
  ret = moran_one_test();
  if (ret)
    return IGRAPH_FAILURE;

  return IGRAPH_SUCCESS;
}


1.3. igraph_roulette_wheel_imitation — Adopt a strategy via roulette wheel selection.

int igraph_roulette_wheel_imitation(const igraph_t *graph,
                                    igraph_integer_t vid,
                                    igraph_bool_t islocal,
                                    const igraph_vector_t *quantities,
                                    igraph_vector_t *strategies,
                                    igraph_neimode_t mode);

A simple stochastic imitation strategy where a vertex revises its strategy to that of a vertex u chosen proportionate to u's quantity (e.g. fitness). This is a special case of stochastic imitation, where a candidate is not chosen uniformly at random but proportionate to its quantity.

Arguments: 

graph:

The graph object representing the game network. This cannot be the empty or trivial graph, but must have at least two vertices and one edge. If graph has one vertex, then no strategy update would take place. Furthermore, if graph has at least two vertices but zero edges, then strategy update would also not take place.

vid:

The vertex whose strategy is to be updated. It is assumed that vid represents a vertex in graph. No checking is performed and it is your responsibility to ensure that vid is indeed a vertex of graph. If an isolated vertex is provided, i.e. the input vertex has degree 0, then no strategy update would take place and vid would retain its current strategy. Strategy update would also not take place if the local neighbourhood of vid are its in-neighbours (respectively out-neighbours), but vid has zero in-neighbours (respectively out-neighbours). Loops are ignored in computing the degree (in, out, all) of vid.

islocal:

Boolean; this flag controls which perspective to use in computing the relative quantity. If true then we use the local perspective; otherwise we use the global perspective. The local perspective for vid is the set of all immediate neighbours of vid. In contrast, the global perspective for vid is the vertex set of graph.

quantities:

A vector of quantities providing the quantity of each vertex in graph. Think of each entry of the vector as being generated by a function such as the fitness function for the game. So if the vector represents fitness quantities, then each vector entry is the fitness of some vertex. The length of this vector must be the same as the number of vertices in the vertex set of graph. For the purpose of roulette wheel selection, each vector entry is assumed to be nonnegative; no checks will be performed for this. It is your responsibility to ensure that at least one entry is nonzero. Furthermore, this vector cannot be a vector of zeros; this condition will be checked.

strategies:

A vector of the current strategies for the vertex population. The updated strategy for vid would be stored here. Each strategy is identified with a nonnegative integer, whose interpretation depends on the payoff matrix of the game. Generally we use the strategy ID as a row or column index of the payoff matrix. The length of this vector must be the same as the number of vertices in the vertex set of graph.

mode:

Defines the sort of neighbourhood to consider for vid. This is only relevant if we are considering the local perspective, i.e. if islocal is true. If we are considering the global perspective, then it is safe to pass the value IGRAPH_ALL here. If graph is undirected, then we use all the immediate neighbours of vid. Thus if you know that graph is undirected, then it is safe to pass the value IGRAPH_ALL here. Supported values are:

IGRAPH_OUT

Use the out-neighbours of vid. This option is only relevant when graph is a digraph and we are considering the local perspective.

IGRAPH_IN

Use the in-neighbours of vid. Again this option is only relevant when graph is a directed graph and we are considering the local perspective.

IGRAPH_ALL

Use both the in- and out-neighbours of vid. This option is only relevant if graph is a digraph. Also use this value if graph is undirected or we are considering the global perspective.

Returns: 

The error code IGRAPH_EINVAL is returned in each of the following cases: (1) Any of the parameters graph, quantities, or strategies is a null pointer. (2) The vector quantities or strategies has a length different from the number of vertices in graph. (3) The parameter graph is the empty or null graph, i.e. the graph with zero vertices and edges. (4) The vector quantities sums to zero.

Time complexity: O(n) where n is the number of vertices in the perspective to consider. If we consider the global perspective, then n is the number of vertices in the vertex set of graph. On the other hand, for the local perspective n is the degree of vid, excluding loops.

Reference:

(Yu & Gen 2010)

X. Yu and M. Gen. Introduction to Evolutionary Algorithms. Springer, 2010, pages 18--20.

Example 10.3.  File examples/simple/igraph_roulette_wheel_imitation.c

/* -*- mode: C -*-  */
/*
  Test suite for stochastic imitation via roulette wheel selection.
  Copyright (C) 2011 Minh Van Nguyen <nguyenminh2@gmail.com>

  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 <stdio.h>
#include <time.h>

#define R_INTEGER(a,b) (igraph_rng_get_integer(igraph_rng_default(), (a), (b)))

/* test parameters structure */
typedef struct {
  igraph_t *graph;
  igraph_integer_t vertex;
  igraph_bool_t islocal;
  igraph_vector_t *quantities;
  igraph_vector_t *strategies;
  igraph_vector_t *known_strats;
  igraph_neimode_t mode;
  int retval;
} strategy_test_t;

/* Error tests. That is, we expect error codes to be returned from such tests.
 */
int error_tests() {
  igraph_t g, gzero, h;
  igraph_vector_t quant, quantzero, strat, stratzero;
  int i, n, nvert, ret;
  strategy_test_t *test;

  /* nonempty graph */
  igraph_small(&g, /*nvert=*/ 0, IGRAPH_UNDIRECTED, 0,1, 1,2, 2,0, -1);
  igraph_empty(&h, 0, 0);         /* empty graph */
  igraph_vector_init(&quant, 1);  /* quantities vector */
  igraph_vector_init(&strat, 2);  /* strategies vector */
  igraph_small(&gzero, /*nvert=*/ 0, IGRAPH_UNDIRECTED,
               0,3, 0,4, 1,2, 1,4, 1,5, 2,3, 2,4, 3,4, -1);
  nvert = igraph_vcount(&gzero);
  igraph_vector_init_real(&stratzero, nvert, 1.0, 0.0, 1.0, 2.0, 0.0, 3.0);
  igraph_vector_init(&quantzero, nvert);  /* vector of zeros */

  /* test parameters */
  /*graph--vert--islocal--quantities--strategies--known_strats--mode--retval*/
  /* null pointer for graph */
  strategy_test_t null_graph = {NULL, 0, 1, NULL, NULL, NULL, IGRAPH_ALL, IGRAPH_EINVAL};
  /* null pointer for quantities vector */
  strategy_test_t null_quant = {&g, 0, 1, NULL, NULL, NULL, IGRAPH_ALL, IGRAPH_EINVAL};
  /* null pointer for strategies vector */
  strategy_test_t null_strat = {&g, 0, 1, &quant, NULL, NULL, IGRAPH_ALL, IGRAPH_EINVAL};
  /* empty graph */
  strategy_test_t empty_graph = {&h, 0, 1, &quant, &strat, NULL, IGRAPH_ALL, IGRAPH_EINVAL};
  /* length of quantities vector different from number of vertices */
  strategy_test_t qdiff_length = {&g, 0, 1, &quant, &strat, NULL, IGRAPH_ALL, IGRAPH_EINVAL};
  /* length of strategies vector different from number of vertices */
  strategy_test_t sdiff_length = {&g, 0, 1, &quant, &strat, NULL, IGRAPH_ALL, IGRAPH_EINVAL};
  /* quantities vector contains all zeros */
  strategy_test_t zero_quant = {&gzero, 4, 1, &quantzero, &stratzero, NULL, IGRAPH_ALL, IGRAPH_EINVAL};
  strategy_test_t *all_checks[] = {/* 1 */ &null_graph,
                                   /* 2 */ &null_quant,
                                   /* 3 */ &null_strat,
                                   /* 4 */ &empty_graph,
                                   /* 5 */ &qdiff_length,
                                   /* 6 */ &sdiff_length,
                                   /* 7 */ &zero_quant};

  /* Run the error tests. We expect error to be raised for each test. */
  igraph_set_error_handler(igraph_error_handler_ignore);
  n = 7;
  i = 0;
  while (i < n) {
    test = all_checks[i];
    ret = igraph_roulette_wheel_imitation(test->graph, test->vertex,
                                          test->islocal, test->quantities,
                                          test->strategies, test->mode);
    if (ret != test->retval) {
      printf("Error test no. %d failed.\n", (int)(i + 1));
      return IGRAPH_FAILURE;
    }
    i++;
  }
  /* clean up */
  igraph_destroy(&g);
  igraph_destroy(&gzero);
  igraph_destroy(&h);
  igraph_vector_destroy(&quant);
  igraph_vector_destroy(&quantzero);
  igraph_vector_destroy(&strat);
  igraph_vector_destroy(&stratzero);

  return IGRAPH_SUCCESS;
}

/* A game on a graph with 5 vertices and 7 edges. Use roulette wheel selection
 * to update strategies. This example also illustrates how a choice of
 * perspective (whether local or global) could affect the range of
 * possible strategies a vertex could adopt.
 */
int roulette_test() {
  igraph_t g;
  igraph_bool_t success;
  igraph_vector_t *known, quant, strat, stratcopy;
  igraph_vector_t known0, known1, known2, known3, known4, known5;
  int i, k, n, nvert, ret;;
  strategy_test_t *test;

  /* the game network */
  igraph_small(&g, /*nvert=*/ 0, IGRAPH_UNDIRECTED,
               0,3, 0,4, 1,2, 1,4, 1,5, 2,3, 2,4, 3,4, -1);
  nvert = igraph_vcount(&g);
  /* strategies vector; the strategy space is {0, 1, 2, 3} */
  /* V[i] is strategy of vertex i */
  igraph_vector_init_real(&strat, nvert, 1.0, 0.0, 1.0, 2.0, 0.0, 3.0);
  /* quantities vector; V[i] is quantity of vertex i */
  igraph_vector_init_real(&quant, nvert, 0.56, 0.13, 0.26, 0.73, 0.67, 0.82);
  /* possible strategies each vertex can adopt */
  igraph_vector_init_real(&known0, /*n=*/ 3, 0.0, 1.0, 2.0);       /* local */
  igraph_vector_init_real(&known1, /*n=*/ 3, 0.0, 1.0, 3.0);       /* local */
  igraph_vector_init_real(&known2, /*n=*/ 3, 0.0, 1.0, 2.0);       /* local */
  igraph_vector_init_real(&known3, /*n=*/ 3, 0.0, 1.0, 2.0);       /* local */
  igraph_vector_init_real(&known4, /*n=*/ 3, 0.0, 1.0, 2.0);       /* local */
  igraph_vector_init_real(&known5, /*n=*/ 4, 0.0, 1.0, 2.0, 3.0);  /* global */

  /* test parameters */
  /*graph--vert--islocal--quantities--strategies--known_strats--mode-retval*/
  strategy_test_t game0 = {&g, 0, 1, &quant, NULL, &known0, IGRAPH_ALL, IGRAPH_SUCCESS};
  strategy_test_t game1 = {&g, 1, 1, &quant, NULL, &known1, IGRAPH_ALL, IGRAPH_SUCCESS};
  strategy_test_t game2 = {&g, 2, 1, &quant, NULL, &known2, IGRAPH_ALL, IGRAPH_SUCCESS};
  strategy_test_t game3 = {&g, 3, 1, &quant, NULL, &known3, IGRAPH_ALL, IGRAPH_SUCCESS};
  strategy_test_t game4 = {&g, 4, 1, &quant, NULL, &known4, IGRAPH_ALL, IGRAPH_SUCCESS};
  strategy_test_t game5 = {&g, 5, 0, &quant, NULL, &known5, IGRAPH_ALL, IGRAPH_SUCCESS};
  strategy_test_t *all_checks[] = {/* 1 */ &game0,
                                   /* 2 */ &game1,
                                   /* 3 */ &game2,
                                   /* 4 */ &game3,
                                   /* 5 */ &game4,
                                   /* 6 */ &game5};

  /* play game */
  n = 6;
  i = 0;
  while (i < n) {
    test = all_checks[i];
    igraph_vector_copy(&stratcopy, &strat);
    ret = igraph_roulette_wheel_imitation(test->graph, test->vertex,
                                          test->islocal, test->quantities,
                                          &stratcopy, test->mode);
    if (ret != test->retval) {
      printf("Test no. %d failed.\n", i + 1);
      return IGRAPH_FAILURE;
    }
    /* If the revised strategy s matches one of the candidate strategies, */
    /* then success. If s doesn't match any of the possible strategies, then */
    /* failure. Default to failure. */
    success = 0;
    known = test->known_strats;
    for (k = 0; k < igraph_vector_size(known); k++) {
      if (VECTOR(*known)[k] == VECTOR(stratcopy)[test->vertex]) {
        success = 1;
        break;
      }
    }
    if (!success) {
      printf("Roulette wheel imitation failed for vertex %d.\n",
             (int)test->vertex);
      return IGRAPH_FAILURE;
    }
    igraph_vector_destroy(&stratcopy);
    i++;
  }
  /* game finished; pack up */
  igraph_destroy(&g);
  igraph_vector_destroy(&known0);
  igraph_vector_destroy(&known1);
  igraph_vector_destroy(&known2);
  igraph_vector_destroy(&known3);
  igraph_vector_destroy(&known4);
  igraph_vector_destroy(&known5);
  igraph_vector_destroy(&quant);
  igraph_vector_destroy(&strat);

  return IGRAPH_SUCCESS;
}

/* It is possible for a vertex to retain its current strategy. This can
 * happen both in the local and global perspectives.
 */
int retain_strategy_test() {
  igraph_t g;
  igraph_integer_t max, min, v;
  igraph_vector_t quant, strat, stratcp;
  int i, ntry, nvert;

  /* the game network */
  igraph_small(&g, /*nvert=*/ 0, IGRAPH_UNDIRECTED,
               0,3, 0,4, 1,2, 1,4, 1,5, 2,3, 2,4, 3,4, -1);
  nvert = igraph_vcount(&g);
  /* strategies vector; the strategy space is {0, 1, 2, 3} */
  /* V[i] is strategy of vertex i */
  igraph_vector_init_real(&strat, nvert, 1.0, 0.0, 1.0, 2.0, 0.0, 3.0);
  /* quantities vector; V[i] is quantity of vertex i */
  igraph_vector_init_real(&quant, nvert, 0.56, 0.13, 0.26, 0.73, 0.67, 0.82);

  /* random vertex */
  min = 0;
  max = 5;
  igraph_rng_seed(igraph_rng_default(), time(0));
  v = R_INTEGER(min, max);  /* min <= v <= max */
  /* Ensure that it is possible for v to retain its current strategy. We */
  /* will try to do this at most ntry times. As there are at most 6 vertices */
  /* to choose from, it shouldn't take long before we encounter a strategy */
  /* revision round where v retains its current strategy. */
  /* With local perspective. */
  i = 0;
  ntry = 100;
  igraph_vector_init(&stratcp, 0);
  do {
    i++;
    if (i > ntry)
      return IGRAPH_FAILURE;  /* ideally this should never happen */
    igraph_vector_destroy(&stratcp);
    igraph_vector_copy(&stratcp, &strat);
    igraph_roulette_wheel_imitation(&g, v, /*is local?*/ 1, &quant, &stratcp,
                                    IGRAPH_ALL);
  }
  while (VECTOR(stratcp)[v] != VECTOR(strat)[v]);
  /* If we get to this point, we know that there was an update round */
  /* i <= ntry as a result of which v retains its current strategy. */
  /* Now try again, but this time with the global perspective. */
  i = 0;
  do {
    i++;
    if (i > ntry)
      return IGRAPH_FAILURE;  /* ideally this should never happen */
    igraph_vector_destroy(&stratcp);
    igraph_vector_copy(&stratcp, &strat);
    igraph_roulette_wheel_imitation(&g, v, /*is local?*/ 0, &quant, &stratcp,
                                    IGRAPH_ALL);
  }
  while (VECTOR(stratcp)[v] != VECTOR(strat)[v]);
  /* nothing further to do, but housekeeping */
  igraph_destroy(&g);
  igraph_vector_destroy(&quant);
  igraph_vector_destroy(&strat);
  igraph_vector_destroy(&stratcp);

  return IGRAPH_SUCCESS;
}

int main() {
  int ret;

  ret = error_tests();
  if (ret)
    return IGRAPH_FAILURE;
  ret = roulette_test();
  if (ret)
    return IGRAPH_FAILURE;
  ret = retain_strategy_test();
  if (ret)
    return IGRAPH_FAILURE;

  return IGRAPH_SUCCESS;
}


1.4. igraph_stochastic_imitation — Adopt a strategy via stochastic imitation with uniform selection.

int igraph_stochastic_imitation(const igraph_t *graph,
                                igraph_integer_t vid,
                                igraph_imitate_algorithm_t algo,
                                const igraph_vector_t *quantities,
                                igraph_vector_t *strategies,
                                igraph_neimode_t mode);

A simple stochastic imitation strategy where a vertex revises its strategy to that of a vertex chosen uniformly at random from its local neighbourhood. This is called stochastic imitation via uniform selection, where the strategy to imitate is chosen via some random process. For the purposes of this function, we use uniform selection from a pool of candidates.

Arguments: 

graph:

The graph object representing the game network. This cannot be the empty or trivial graph, but must have at least two vertices and one edge. If graph has one vertex, then no strategy update would take place. Furthermore, if graph has at least two vertices but zero edges, then strategy update would also not take place.

vid:

The vertex whose strategy is to be updated. It is assumed that vid represents a vertex in graph. No checking is performed and it is your responsibility to ensure that vid is indeed a vertex of graph. If an isolated vertex is provided, i.e. the input vertex has degree 0, then no strategy update would take place and vid would retain its current strategy. Strategy update would also not take place if the local neighbourhood of vid are its in-neighbours (respectively out-neighbours), but vid has zero in-neighbours (respectively out-neighbours). Loops are ignored in computing the degree (in, out, all) of vid.

algo:

This flag controls which algorithm to use in stochastic imitation. Supported values are:

IGRAPH_IMITATE_AUGMENTED

Augmented imitation. Vertex vid imitates the strategy of the chosen vertex u provided that doing so would increase the quantity (e.g. fitness) of vid. Augmented imitation can be thought of as "imitate if better".

IGRAPH_IMITATE_BLIND

Blind imitation. Vertex vid blindly imitates the strategy of the chosen vertex u, regardless of whether doing so would increase or decrease the quantity of vid.

IGRAPH_IMITATE_CONTRACTED

Contracted imitation. Here vertex vid imitates the strategy of the chosen vertex u if doing so would decrease the quantity of vid. Think of contracted imitation as "imitate if worse".

quantities:

A vector of quantities providing the quantity of each vertex in graph. Think of each entry of the vector as being generated by a function such as the fitness function for the game. So if the vector represents fitness quantities, then each vector entry is the fitness of some vertex. The length of this vector must be the same as the number of vertices in the vertex set of graph.

strategies:

A vector of the current strategies for the vertex population. The updated strategy for vid would be stored here. Each strategy is identified with a nonnegative integer, whose interpretation depends on the payoff matrix of the game. Generally we use the strategy ID as a row or column index of the payoff matrix. The length of this vector must be the same as the number of vertices in the vertex set of graph.

mode:

Defines the sort of neighbourhood to consider for vid. If graph is undirected, then we use all the immediate neighbours of vid. Thus if you know that graph is undirected, then it is safe to pass the value IGRAPH_ALL here. Supported values are:

IGRAPH_OUT

Use the out-neighbours of vid. This option is only relevant when graph is a directed graph.

IGRAPH_IN

Use the in-neighbours of vid. Again this option is only relevant when graph is a directed graph.

IGRAPH_ALL

Use both the in- and out-neighbours of vid. This option is only relevant if graph is a digraph. Also use this value if graph is undirected.

Returns: 

The error code IGRAPH_EINVAL is returned in each of the following cases: (1) Any of the parameters graph, quantities, or strategies is a null pointer. (2) The vector quantities or strategies has a length different from the number of vertices in graph. (3) The parameter graph is the empty or null graph, i.e. the graph with zero vertices and edges. (4) The parameter algo refers to an unsupported stochastic imitation algorithm.

Time complexity: depends on the uniform random number generator, but should usually be O(1).

Example 10.4.  File examples/simple/igraph_stochastic_imitation.c

/* -*- mode: C -*-  */
/*
  Test suite for stochastic imitation via uniform selection.
  Copyright (C) 2011 Minh Van Nguyen <nguyenminh2@gmail.com>

  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 <stdio.h>

/* test parameters structure */
typedef struct {
  igraph_t *graph;
  igraph_integer_t vertex;
  igraph_imitate_algorithm_t algo;
  igraph_vector_t *quantities;
  igraph_vector_t *strategies;
  igraph_vector_t *known_strats;
  igraph_neimode_t mode;
  int retval;
} strategy_test_t;

/* Error tests. That is, we expect error codes to be returned from such tests.
 */
int error_tests() {
  igraph_t g, h;
  igraph_vector_t quant, strat;
  int i, n, ret;
  strategy_test_t *test;

  /* nonempty graph */
  igraph_small(&g, /*n vertices*/ 0, IGRAPH_UNDIRECTED, 0,1, 1,2, 2,0, -1);
  igraph_empty(&h, 0, 0);         /* empty graph */
  igraph_vector_init(&quant, 1);  /* quantities vector */
  igraph_vector_init(&strat, 2);  /* strategies vector */

  /* test parameters */
  /*graph--vertex--algo--quantities--strategies--known_strats--mode--retval*/
  /* null pointer for graph */
  strategy_test_t null_graph = {NULL, 0, IGRAPH_IMITATE_BLIND, NULL, NULL, NULL, IGRAPH_ALL, IGRAPH_EINVAL};
  /* null pointer for quantities vector */
  strategy_test_t null_quant = {&g, 0, IGRAPH_IMITATE_BLIND, NULL, NULL, NULL, IGRAPH_ALL, IGRAPH_EINVAL};
  /* null pointer for strategies vector */
  strategy_test_t null_strat = {&g, 0, IGRAPH_IMITATE_BLIND, &quant, NULL, NULL, IGRAPH_ALL, IGRAPH_EINVAL};
  /* empty graph */
  strategy_test_t empty_graph = {&h, 0, IGRAPH_IMITATE_BLIND, &quant, &strat, NULL, IGRAPH_ALL, IGRAPH_EINVAL};
  /* length of quantities vector different from number of vertices */
  strategy_test_t qdiff_length = {&g, 0, IGRAPH_IMITATE_BLIND, &quant, &strat, NULL, IGRAPH_ALL, IGRAPH_EINVAL};
  /* length of strategies vector different from number of vertices */
  strategy_test_t sdiff_length = {&g, 0, IGRAPH_IMITATE_BLIND, &quant, &strat, NULL, IGRAPH_ALL, IGRAPH_EINVAL};
  strategy_test_t unknown_algo = {&g, 0, -1, &quant, &strat, NULL, IGRAPH_ALL, IGRAPH_EINVAL};
  strategy_test_t *all_checks[] = {/* 1 */ &null_graph,
                                   /* 2 */ &null_quant,
                                   /* 3 */ &null_strat,
                                   /* 4 */ &empty_graph,
                                   /* 5 */ &qdiff_length,
                                   /* 6 */ &sdiff_length,
                                   /* 7 */ &unknown_algo};
  /* Run the error tests. We expect error to be raised for each test. */
  igraph_set_error_handler(igraph_error_handler_ignore);
  n = 7;
  i = 0;
  while (i < n) {
    test = all_checks[i];
    ret = igraph_stochastic_imitation(test->graph, test->vertex, test->algo,
                                      test->quantities, test->strategies,
                                      test->mode);
    if (ret != test->retval) {
      printf("Error test no. %d failed.\n", (int)(i + 1));
      return IGRAPH_FAILURE;
    }
    i++;
  }
  /* clean up */
  igraph_destroy(&g);
  igraph_destroy(&h);
  igraph_vector_destroy(&quant);
  igraph_vector_destroy(&strat);

  return IGRAPH_SUCCESS;
}

/* Updating the strategy of an isolated vertex. In this case, the strategies
 * vector should not change at all.
 */
int isolated_vertex_test() {
  igraph_t g;
  igraph_vector_t quant, strat, v;
  int i, ret;

  /* graph with one isolated vertex */
  igraph_small(&g, /*n vertices*/ 0, IGRAPH_UNDIRECTED, 0,1, 1,2, 2,0, -1);
  igraph_add_vertices(&g, 1, 0);  /* new vertex 3 is isolated */
  /* quantities vector: all vertices have the same fitness */
  igraph_vector_init_real(&quant, 4, 0.25, 0.25, 0.25, 0.25);
  /* strategies vector: 0 means aggressive strategy; 1 means passive */
  igraph_vector_init_real(&strat, 4, 1.0, 0.0, 1.0, 0.0);
  /* make a copy of the original strategies vector for comparison later on */
  igraph_vector_copy(&v, &strat);
  /* Now update strategy of vertex 3. Since this vertex is isolated, no */
  /* strategy update would take place. The resulting strategies vector */
  /* would be the same as it was originally. */
  ret = igraph_stochastic_imitation(/*graph*/ &g,
                                    /*vertex*/ 3,
                                    /*algorithm*/ IGRAPH_IMITATE_BLIND,
                                    /*quantities*/ &quant,
                                    /*strategies*/ &strat,
                                    /*mode*/ IGRAPH_ALL);
  if (ret) {
    printf("Isolated vertex test failed.\n");
    return IGRAPH_FAILURE;
  }
  for (i = 0; i < igraph_vector_size(&strat); i++) {
    if (VECTOR(strat)[i] != VECTOR(v)[i]) {
      printf("Isolated vertex test failed.\n");
      return IGRAPH_FAILURE;
    }
  }
  /* clean up */
  igraph_destroy(&g);
  igraph_vector_destroy(&quant);
  igraph_vector_destroy(&strat);
  igraph_vector_destroy(&v);

  return IGRAPH_SUCCESS;
}

/* A game on the Petersen graph. This graph has 10 vertices and 15 edges. The
 * Petersen graph is initialized with a default quantities vector and a
 * default strategies vector. Some vertices are chosen for strategy revision,
 * each one via a different stochastic imitation rule.
 */
int petersen_game_test() {
  igraph_t g;
  igraph_bool_t success;
  igraph_vector_t quant, strat, stratcopy, *knownstrats;
  igraph_vector_t known0, known2, known4;
  int i, k, n, nedge, nvert, ret;
  strategy_test_t *test;

  /* the Petersen graph */
  igraph_small(&g, /*n vertices*/ 0, IGRAPH_UNDIRECTED,
               0,1,0,4,0,5, 1,2,1,6, 2,3,2,7, 3,4,3,8, 4,9,
               5,7,5,8, 6,8,6,9, 7,9, -1);
  nedge = igraph_ecount(&g);
  nvert = igraph_vcount(&g);
  /* Strategies vector, one strategy for each vertex. Thus vec[i] is the */
  /* strategy of vertex i. The strategy space is: {0, 1, 2, 3}. */
  /* Each strategy should be an integer. */
  igraph_vector_init_real(&strat, nvert,
                          1.0, 1.0, 2.0, 2.0, 0.0,
                          0.0, 0.0, 1.0, 2.0, 3.0);
  /* Quantities vector, one quantity per vertex. Thus vec[i] is the */
  /* quantity for vertex i. */
  igraph_vector_init_real(&quant, nvert,
                          0.3, 1.1, 0.5, 1.0, 0.9,
                          0.8, 0.4, 0.1, 0.7, 0.7);
  /* parameter settings and known results */
  igraph_vector_init_real(&known0, 2, 0.0, 1.0);
  igraph_vector_init_real(&known2, 2, 1.0, 2.0);
  igraph_vector_init_real(&known4, 2, 0.0, 2.0);
  /*graph--vertex--algo--quantities--strategies--known_strats--mode--retval*/
  strategy_test_t blind0 = {&g, 0, IGRAPH_IMITATE_BLIND, &quant, NULL, &known0, IGRAPH_ALL, IGRAPH_SUCCESS};
  strategy_test_t augmented4 = {&g, 4, IGRAPH_IMITATE_AUGMENTED, &quant, NULL, &known4, IGRAPH_ALL, IGRAPH_SUCCESS};
  strategy_test_t contracted2 = {&g, 2, IGRAPH_IMITATE_CONTRACTED, &quant, NULL, &known2, IGRAPH_ALL, IGRAPH_SUCCESS};
  strategy_test_t *all_checks[] = {/* 1 */ &blind0,
                                   /* 2 */ &augmented4,
                                   /* 3 */ &contracted2};
  /* run the tests */
  n = 3;
  i = 0;
  while (i < n) {
    test = all_checks[i];
    igraph_vector_copy(&stratcopy, &strat);
    ret = igraph_stochastic_imitation(test->graph, test->vertex, test->algo,
                                      test->quantities, &stratcopy,
                                      test->mode);
    if (ret) {
      printf("Stochastic imitation failed for vertex %d.\n",
             (int)test->vertex);
      return IGRAPH_FAILURE;
    }
    /* If the updated strategy for the vertex matches one of the known */
    /* strategies, then success. Default to failure. */
    success = 0;
    knownstrats = test->known_strats;
    for (k = 0; k < igraph_vector_size(knownstrats); k++) {
      if (VECTOR(*knownstrats)[k] == VECTOR(stratcopy)[test->vertex]) {
        success = 1;
        break;
      }
    }
    if (!success) {
      printf("Stochastic imitation failed for vertex %d.\n",
             (int)test->vertex);
      return IGRAPH_FAILURE;
    }
    igraph_vector_destroy(&stratcopy);
    i++;
  }
  /* clean up */
  igraph_destroy(&g);
  igraph_vector_destroy(&known0);
  igraph_vector_destroy(&known2);
  igraph_vector_destroy(&known4);
  igraph_vector_destroy(&quant);
  igraph_vector_destroy(&strat);

  return IGRAPH_SUCCESS;
}

int main() {
  int ret;

  ret = error_tests();
  if (ret)
    return ret;
  ret = isolated_vertex_test();
  if (ret)
    return ret;
  ret = petersen_game_test();
  if (ret)
    return ret;

  return IGRAPH_SUCCESS;
}