haskell-igraph-0.8.0: igraph/src/microscopic_update.c
/* -*- mode: C -*- */
/*
Microscopic update rules for dealing with agent-level strategy revision.
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_iterators.h"
#include "igraph_interface.h"
#include "igraph_microscopic_update.h"
#include "igraph_nongraph.h"
#include "igraph_random.h"
#include <assert.h>
/*
* Internal use only.
* Compute the cumulative proportionate values of a vector. The vector is
* assumed to hold values associated with edges.
*
* \param graph The graph object representing the game network. No error
* checks will be performed on this graph. You are responsible for
* ensuring that this is a valid graph for the particular
* microscopic update rule at hand.
* \param U A vector of edge values for which we want to compute cumulative
* proportionate values. So U[i] is the value of the edge with ID i.
* With a local perspective, we would only compute cumulative
* proportionate values for some combination of U. This vector could
* be, for example, a vector of weights for edges in \p graph. It is
* assumed that each value of U is nonnegative; it is your
* responsibility to ensure this. Furthermore, this vector must have a
* length the same as the number of edges in \p graph; you are
* responsible for ensuring this condition holds.
* \param V Pointer to an uninitialized vector. The cumulative proportionate
* values will be computed and stored here. No error checks will be
* performed on this parameter.
* \param islocal Boolean; this flag controls which perspective to use. If
* true then we use the local perspective; otherwise we use the global
* perspective. In the context of this function, the local perspective
* for a vertex v consists of all edges incident on v. In contrast, the
* global perspective for v consists of all edges in \p graph.
* \param vid The vertex to use if we are considering a local perspective,
* i.e. if \p islocal is true. This vertex will be ignored if
* \p islocal is false. That is, if \p islocal is false then it is safe
* pass the value -1 here. On the other hand, if \p islocal is true then
* it is assumed that this is indeed a vertex of \p graph.
* \param mode Defines the sort of neighbourhood to consider for \p vid. This
* is only relevant if we are considering the local perspective, i.e. if
* \p islocal is true. If we are considering the global perspective,
* then this parameter would be ignored. In other words, if \p islocal
* is false then it is safe to pass the value \p IGRAPH_ALL here. If
* \p graph is undirected, then we use all the immediate neighbours of
* \p vid. Thus if you know that \p graph is undirected, then it is
* safe to pass the value \p IGRAPH_ALL here. Supported values are:
* \clist
* \cli IGRAPH_OUT
* Use the out-neighbours of \p vid. This option is only relevant
* when \p graph is a digraph and we are considering the local
* perspective.
* \cli IGRAPH_IN
* Use the in-neighbours of \p vid. Again this option is only relevant
* when \p graph is a directed graph and we are considering the local
* perspective.
* \cli IGRAPH_ALL
* Use both the in- and out-neighbours of \p vid. This option is only
* relevant if \p graph is a digraph and we are considering a local
* perspective. Also use this value if \p graph is undirected or we
* are considering the global perspective.
* \endclist
* \return Codes:
* \clist
* \cli IGRAPH_EINVAL
* This error code is returned in the following case: The vector
* \p U, or some combination of its values, sums to zero.
* \cli IGRAPH_SUCCESS
* This signal is returned if the cumulative proportionate values
* were successfully computed.
* \endclist
*
* Time complexity: O(2n) where n is the number of edges in the perspective
* of \p vid.
*/
int igraph_ecumulative_proportionate_values(const igraph_t *graph,
const igraph_vector_t *U,
igraph_vector_t *V,
igraph_bool_t islocal,
igraph_integer_t vid,
igraph_neimode_t mode) {
igraph_eit_t A; /* all edges in v's perspective */
igraph_es_t es;
igraph_integer_t e;
igraph_real_t C; /* cumulative probability */
igraph_real_t P; /* probability */
igraph_real_t S; /* sum of values */
long int i;
/* Set the perspective. Let v be the vertex under consideration. The local */
/* perspective for v consists of edges incident on it. In contrast, the */
/* global perspective for v are all edges in the given graph. Hence in the */
/* global perspective, we will ignore the given vertex and the given */
/* neighbourhood type, but instead consider all edges in the given graph. */
if (islocal) {
IGRAPH_CHECK(igraph_es_incident(&es, vid, mode));
} else {
IGRAPH_CHECK(igraph_es_all(&es, IGRAPH_EDGEORDER_ID));
}
IGRAPH_FINALLY(igraph_es_destroy, &es);
/* Sum up all the values of vector U in the perspective for v. This sum */
/* will be used in normalizing each value. */
/* NOTE: Here we assume that each value to be summed is nonnegative, */
/* and at least one of the values is nonzero. The behaviour resulting */
/* from all values being zero would be division by zero later on when */
/* we normalize each value. We check to see that the values sum to zero. */
/* NOTE: In this function, the order in which we iterate through the */
/* edges of interest should be the same as the order in which we do so */
/* in the caller function. If the caller function doesn't care about the */
/* order of values in the resulting vector V, then there's no need to take */
/* special notice of that order. But in some cases the order of values in */
/* V is taken into account, for example, in the Moran process. */
S = 0.0;
IGRAPH_CHECK(igraph_eit_create(graph, es, &A));
IGRAPH_FINALLY(igraph_eit_destroy, &A);
while (!IGRAPH_EIT_END(A)) {
e = (igraph_integer_t)IGRAPH_EIT_GET(A);
S += (igraph_real_t)VECTOR(*U)[e];
IGRAPH_EIT_NEXT(A);
}
/* avoid division by zero later on */
if (S == (igraph_real_t)0.0) {
igraph_eit_destroy(&A);
igraph_es_destroy(&es);
IGRAPH_FINALLY_CLEAN(2);
IGRAPH_ERROR("Vector of values sums to zero", IGRAPH_EINVAL);
}
/* Get cumulative probability and relative value for each edge in the */
/* perspective of v. The vector V holds the cumulative proportionate */
/* values of all edges in v's perspective. The value V[0] is the */
/* cumulative proportionate value of the first edge in the edge iterator */
/* A. The value V[1] is the cumulative proportionate value of the second */
/* edge in the iterator A. And so on. */
C = 0.0;
i = 0;
IGRAPH_EIT_RESET(A);
IGRAPH_VECTOR_INIT_FINALLY(V, IGRAPH_EIT_SIZE(A));
while (!IGRAPH_EIT_END(A)) {
e = (igraph_integer_t)IGRAPH_EIT_GET(A);
/* NOTE: Beware of division by zero here. This can happen if the vector */
/* of values, or the combination of interest, sums to zero. */
P = (igraph_real_t)VECTOR(*U)[e] / S;
C += P;
VECTOR(*V)[i] = C;
i++;
IGRAPH_EIT_NEXT(A);
}
igraph_eit_destroy(&A);
igraph_es_destroy(&es);
/* Pop V, A and es from the finally stack -- that's three items */
IGRAPH_FINALLY_CLEAN(3);
return IGRAPH_SUCCESS;
}
/*
* Internal use only.
* Compute the cumulative proportionate values of a vector. The vector is
* assumed to hold values associated with vertices.
*
* \param graph The graph object representing the game network. No error
* checks will be performed on this graph. You are responsible for
* ensuring that this is a valid graph for the particular
* microscopic update rule at hand.
* \param U A vector of vertex values for which we want to compute cumulative
* proportionate values. The vector could be, for example, a vector of
* fitness for vertices of \p graph. It is assumed that each value of U
* is nonnegative; it is your responsibility to ensure this. Also U, or
* a combination of interest, is assumed to sum to a positive value;
* this condition will be checked.
* \param V Pointer to an uninitialized vector. The cumulative proportionate
* values will be computed and stored here. No error checks will be
* performed on this parameter.
* \param islocal Boolean; this flag controls which perspective to use. If
* true then we use the local perspective; otherwise we use the global
* perspective. The local perspective for a vertex v is the set of all
* immediate neighbours of v. In contrast, the global perspective
* for v is the vertex set of \p graph.
* \param vid The vertex to use if we are considering a local perspective,
* i.e. if \p islocal is true. This vertex will be ignored if
* \p islocal is false. That is, if \p islocal is false then it is safe
* pass the value -1 here. On the other hand, if \p islocal is true then
* it is assumed that this is indeed a vertex of \p graph.
* \param mode Defines the sort of neighbourhood to consider for \p vid. This
* is only relevant if we are considering the local perspective, i.e. if
* \p islocal is true. If we are considering the global perspective,
* then this parameter would be ignored. In other words, if \p islocal
* is false then it is safe to pass the value \p IGRAPH_ALL here. If
* \p graph is undirected, then we use all the immediate neighbours of
* \p vid. Thus if you know that \p graph is undirected, then it is
* safe to pass the value \p IGRAPH_ALL here. Supported values are:
* \clist
* \cli IGRAPH_OUT
* Use the out-neighbours of \p vid. This option is only relevant
* when \p graph is a digraph and we are considering the local
* perspective.
* \cli IGRAPH_IN
* Use the in-neighbours of \p vid. Again this option is only relevant
* when \p graph is a directed graph and we are considering the local
* perspective.
* \cli IGRAPH_ALL
* Use both the in- and out-neighbours of \p vid. This option is only
* relevant if \p graph is a digraph and we are considering a local
* perspective. Also use this value if \p graph is undirected or we
* are considering the global perspective.
* \endclist
* \return Codes:
* \clist
* \cli IGRAPH_EINVAL
* This error code is returned in the following case: The vector
* \p U, or some combination of its values, sums to zero.
* \cli IGRAPH_SUCCESS
* This signal is returned if the cumulative proportionate values
* were successfully computed.
* \endclist
*
* Time complexity: O(2n) where n is the number of vertices in the
* perspective of vid.
*/
int igraph_vcumulative_proportionate_values(const igraph_t *graph,
const igraph_vector_t *U,
igraph_vector_t *V,
igraph_bool_t islocal,
igraph_integer_t vid,
igraph_neimode_t mode) {
igraph_integer_t v;
igraph_real_t C; /* cumulative probability */
igraph_real_t P; /* probability */
igraph_real_t S; /* sum of values */
igraph_vit_t A; /* all vertices in v's perspective */
igraph_vs_t vs;
long int i;
/* Set the perspective. Let v be the vertex under consideration; it might */
/* be that we want to update v's strategy. The local perspective for v */
/* consists of its immediate neighbours. In contrast, the global */
/* perspective for v are all the vertices in the given graph. Hence in the */
/* global perspective, we will ignore the given vertex and the given */
/* neighbourhood type, but instead consider all vertices in the given */
/* graph. */
if (islocal) {
IGRAPH_CHECK(igraph_vs_adj(&vs, vid, mode));
} else {
IGRAPH_CHECK(igraph_vs_all(&vs));
}
IGRAPH_FINALLY(igraph_vs_destroy, &vs);
/* Sum up all the values of vector U in the perspective for v. This */
/* sum will be used in normalizing each value. If we are using a local */
/* perspective, then we also need to consider the quantity of v in */
/* computing the sum. */
/* NOTE: Here we assume that each value to be summed is nonnegative, */
/* and at least one of the values is nonzero. The behaviour resulting */
/* from all values being zero would be division by zero later on when */
/* we normalize each value. We check to see that the values sum to zero. */
/* NOTE: In this function, the order in which we iterate through the */
/* vertices of interest should be the same as the order in which we do so */
/* in the caller function. If the caller function doesn't care about the */
/* order of values in the resulting vector V, then there's no need to take */
/* special notice of that order. But in some cases the order of values in */
/* V is taken into account, for example, in roulette wheel selection. */
S = 0.0;
IGRAPH_CHECK(igraph_vit_create(graph, vs, &A));
IGRAPH_FINALLY(igraph_vit_destroy, &A);
while (!IGRAPH_VIT_END(A)) {
v = (igraph_integer_t)IGRAPH_VIT_GET(A);
S += (igraph_real_t)VECTOR(*U)[v];
IGRAPH_VIT_NEXT(A);
}
if (islocal) {
S += (igraph_real_t)VECTOR(*U)[vid];
}
/* avoid division by zero later on */
if (S == (igraph_real_t)0.0) {
igraph_vit_destroy(&A);
igraph_vs_destroy(&vs);
IGRAPH_FINALLY_CLEAN(2);
IGRAPH_ERROR("Vector of values sums to zero", IGRAPH_EINVAL);
}
/* Get cumulative probability and relative value for each vertex in the */
/* perspective of v. The vector V holds the cumulative proportionate */
/* values of all vertices in v's perspective. The value V[0] is the */
/* cumulative proportionate value of the first vertex in the vertex */
/* iterator A. The value V[1] is the cumulative proportionate value of */
/* the second vertex in the iterator A. And so on. If we are using the */
/* local perspective, then we also need to consider the cumulative */
/* proportionate value of v. In the case of the local perspective, we */
/* don't need to compute and store v's cumulative proportionate value, */
/* but we pretend that such value is appended to the vector V. */
C = 0.0;
i = 0;
IGRAPH_VIT_RESET(A);
IGRAPH_VECTOR_INIT_FINALLY(V, IGRAPH_VIT_SIZE(A));
while (!IGRAPH_VIT_END(A)) {
v = (igraph_integer_t)IGRAPH_VIT_GET(A);
/* NOTE: Beware of division by zero here. This can happen if the vector */
/* of values, or a combination of interest, sums to zero. */
P = (igraph_real_t)VECTOR(*U)[v] / S;
C += P;
VECTOR(*V)[i] = C;
i++;
IGRAPH_VIT_NEXT(A);
}
igraph_vit_destroy(&A);
igraph_vs_destroy(&vs);
/* Pop V, A and vs from the finally stack -- that's three items */
IGRAPH_FINALLY_CLEAN(3);
return IGRAPH_SUCCESS;
}
/*
* Internal use only.
* A set of standard tests to be performed prior to strategy updates. The
* tests contained in this function are common to many strategy revision
* functions in this file. This function is meant to be invoked from within
* a specific strategy update function in order to perform certain common
* tests, including sanity checks and conditions under which no strategy
* updates are necessary.
*
* \param 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 \p graph has one vertex, then no strategy update
* would take place. Furthermore, if \p graph has at least two vertices
* but zero edges, then strategy update would also not take place.
* \param vid The vertex whose strategy is to be updated. It is assumed that
* \p vid represents a vertex in \p graph. No checking is performed and
* it is your responsibility to ensure that \p vid is indeed a vertex
* of \p graph. If an isolated vertex is provided, i.e. the input
* vertex has degree 0, then no strategy update would take place and
* \p vid would retain its current strategy. Strategy update would also
* not take place if the local neighbourhood of \p vid are its
* in-neighbours (respectively out-neighbours), but \p vid has zero
* in-neighbours (respectively out-neighbours). Loops are ignored in
* computing the degree (in, out, all) of \p vid.
* \param quantities A vector of quantities providing the quantity of each
* vertex in \p 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 \p graph.
* \param strategies A vector of the current strategies for the vertex
* population. 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 \p graph.
* \param mode Defines the sort of neighbourhood to consider for \p vid. If
* \p graph is undirected, then we use all the immediate neighbours of
* \p vid. Thus if you know that \p graph is undirected, then it is safe
* to pass the value \p IGRAPH_ALL here. Supported values are:
* \clist
* \cli IGRAPH_OUT
* Use the out-neighbours of \p vid. This option is only relevant
* when \p graph is a directed graph.
* \cli IGRAPH_IN
* Use the in-neighbours of \p vid. Again this option is only relevant
* when \p graph is a directed graph.
* \cli IGRAPH_ALL
* Use both the in- and out-neighbours of \p vid. This option is only
* relevant if \p graph is a digraph. Also use this value if
* \p graph is undirected.
* \endclist
* \param updates Boolean; at the end of this test suite, this flag
* indicates whether to proceed with strategy revision. If true then
* strategy revision should proceed; otherwise there is no need to
* continue with revising a vertex's strategy. A caller function that
* invokes this function would use the value of \p updates to
* determine whether to proceed with strategy revision.
* \param islocal Boolean; this flag controls which perspective to use. If
* true then we use the local perspective; otherwise we use the global
* perspective. The local perspective for \p vid is the set of all
* immediate neighbours of \p vid. In contrast, the global perspective
* for \p vid is the vertex set of \p graph.
* \return Codes:
* \clist
* \cli IGRAPH_EINVAL
* This error code is returned in each of the following cases:
* (1) Any of the parameters \p graph, \p quantities, or
* \p strategies is a null pointer. (2) The vector \p quantities
* or \p strategies has a length different from the number of
* vertices in \p graph. (3) The parameter \p graph is the empty
* or null graph, i.e. the graph with zero vertices and edges.
* \cli IGRAPH_SUCCESS
* This signal is returned if no errors were raised. You should use
* the value of the boolean \p updates to decide whether to go
* ahead with updating a vertex's strategy.
* \endclist
*/
int igraph_microscopic_standard_tests(const igraph_t *graph,
igraph_integer_t vid,
const igraph_vector_t *quantities,
const igraph_vector_t *strategies,
igraph_neimode_t mode,
igraph_bool_t *updates,
igraph_bool_t islocal) {
igraph_integer_t nvert;
igraph_vector_t degv;
*updates = 1;
/* sanity checks */
if (graph == NULL) {
IGRAPH_ERROR("Graph is a null pointer", IGRAPH_EINVAL);
}
if (quantities == NULL) {
IGRAPH_ERROR("Quantities vector is a null pointer", IGRAPH_EINVAL);
}
if (strategies == NULL) {
IGRAPH_ERROR("Strategies vector is a null pointer", IGRAPH_EINVAL);
}
/* the empty graph */
nvert = igraph_vcount(graph);
if (nvert < 1) {
IGRAPH_ERROR("Graph cannot be the empty graph", IGRAPH_EINVAL);
}
/* invalid vector length */
if (nvert != (igraph_integer_t)igraph_vector_size(quantities)) {
IGRAPH_ERROR("Size of quantities vector different from number of vertices",
IGRAPH_EINVAL);
}
if (nvert != (igraph_integer_t)igraph_vector_size(strategies)) {
IGRAPH_ERROR("Size of strategies vector different from number of vertices",
IGRAPH_EINVAL);
}
/* Various conditions under which no strategy updates will take place. That
* is, the vertex retains its current strategy.
*/
/* given graph has < 2 vertices */
if (nvert < 2) {
*updates = 0;
}
/* graph has >= 2 vertices, but no edges */
if (igraph_ecount(graph) < 1) {
*updates = 0;
}
/* Test for vertex isolation, depending on the perspective given. For
* undirected graphs, a given vertex v is isolated if its degree is zero.
* If we are considering in-neighbours (respectively out-neighbours), then
* we say that v is isolated if its in-degree (respectively out-degree) is
* zero. In general, this vertex isolation test is only relevant if we are
* using a local perspective, i.e. if we only consider the immediate
* neighbours (local perspective) of v as opposed to all vertices in the
* vertex set of the graph (global perspective).
*/
if (islocal) {
/* Moving on ahead with vertex isolation test, since local perspective */
/* is requested. */
IGRAPH_VECTOR_INIT_FINALLY(°v, 1);
IGRAPH_CHECK(igraph_degree(graph, °v, igraph_vss_1(vid),
mode, IGRAPH_NO_LOOPS));
if (VECTOR(degv)[0] < 1) {
*updates = 0;
}
igraph_vector_destroy(°v);
IGRAPH_FINALLY_CLEAN(1);
}
return IGRAPH_SUCCESS;
}
/**
* \ingroup spatialgames
* \function igraph_deterministic_optimal_imitation
* \brief Adopt a strategy via deterministic optimal imitation.
*
* 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.
*
* \param 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 \p graph has one vertex, then no strategy update
* would take place. Furthermore, if \p graph has at least two vertices
* but zero edges, then strategy update would also not take place.
* \param vid The vertex whose strategy is to be updated. It is assumed that
* \p vid represents a vertex in \p graph. No checking is performed and
* it is your responsibility to ensure that \p vid is indeed a vertex
* of \p graph. If an isolated vertex is provided, i.e. the input
* vertex has degree 0, then no strategy update would take place and
* \p vid would retain its current strategy. Strategy update would also
* not take place if the local neighbourhood of \p vid are its
* in-neighbours (respectively out-neighbours), but \p vid has zero
* in-neighbours (respectively out-neighbours). Loops are ignored in
* computing the degree (in, out, all) of \p vid.
* \param optimality Logical; controls the type of optimality to be used.
* Supported values are:
* \clist
* \cli 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 \p vid to that which yields a local
* maximum.
* \cli 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.
* \endclist
* \param quantities A vector of quantities providing the quantity of each
* vertex in \p 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 \p graph.
* \param strategies A vector of the current strategies for the vertex
* population. The updated strategy for \p 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 \p graph.
* \param mode Defines the sort of neighbourhood to consider for \p vid. If
* \p graph is undirected, then we use all the immediate neighbours of
* \p vid. Thus if you know that \p graph is undirected, then it is safe
* to pass the value \p IGRAPH_ALL here. Supported values are:
* \clist
* \cli IGRAPH_OUT
* Use the out-neighbours of \p vid. This option is only relevant
* when \p graph is a directed graph.
* \cli IGRAPH_IN
* Use the in-neighbours of \p vid. Again this option is only relevant
* when \p graph is a directed graph.
* \cli IGRAPH_ALL
* Use both the in- and out-neighbours of \p vid. This option is only
* relevant if \p graph is a digraph. Also use this value if
* \p graph is undirected.
* \endclist
* \return The error code \p IGRAPH_EINVAL is returned in each of the
* following cases: (1) Any of the parameters \p graph, \p quantities,
* or \p strategies is a null pointer. (2) The vector \p quantities
* or \p strategies has a length different from the number of vertices
* in \p graph. (3) The parameter \p 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 \p vid.
*
* \example examples/simple/igraph_deterministic_optimal_imitation.c
*/
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) {
igraph_integer_t i, k, v;
igraph_real_t q;
igraph_vector_t adj;
igraph_bool_t updates;
IGRAPH_CHECK(igraph_microscopic_standard_tests(graph, vid, quantities,
strategies, mode, &updates,
/*is local?*/ 1));
if (!updates) {
return IGRAPH_SUCCESS; /* Nothing to do */
}
/* Choose a locally optimal strategy to imitate. This can be either maximum
* or minimum deterministic imitation. By now we know that the given vertex v
* has degree >= 1 and at least 1 edge. Then within its immediate
* neighbourhood adj(v) and including v itself, there exists a vertex whose
* strategy yields a local optimal quantity.
*/
/* Random permutation of adj(v). This ensures that if there are multiple */
/* candidates with an optimal strategy, then we choose one such candidate */
/* at random. */
IGRAPH_VECTOR_INIT_FINALLY(&adj, 0);
IGRAPH_CHECK(igraph_neighbors(graph, &adj, vid, mode));
IGRAPH_CHECK(igraph_vector_shuffle(&adj));
/* maximum deterministic imitation */
i = vid;
q = (igraph_real_t)VECTOR(*quantities)[vid];
if (optimality == IGRAPH_MAXIMUM) {
for (k = 0; k < igraph_vector_size(&adj); k++) {
v = (igraph_integer_t) VECTOR(adj)[k];
if ((igraph_real_t)VECTOR(*quantities)[v] > q) {
i = v;
q = (igraph_real_t)VECTOR(*quantities)[v];
}
}
} else { /* minimum deterministic imitation */
for (k = 0; k < igraph_vector_size(&adj); k++) {
v = (igraph_integer_t) VECTOR(adj)[k];
if ((igraph_real_t)VECTOR(*quantities)[v] < q) {
i = v;
q = (igraph_real_t)VECTOR(*quantities)[v];
}
}
}
/* Now i is a vertex with a locally optimal quantity, the value of which */
/* is q. Update the strategy of vid to that of i. */
VECTOR(*strategies)[vid] = VECTOR(*strategies)[i];
igraph_vector_destroy(&adj);
IGRAPH_FINALLY_CLEAN(1);
return IGRAPH_SUCCESS;
}
/**
* \ingroup spatialgames
* \function igraph_moran_process
* \brief The Moran process in a network setting.
*
* 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.
*
* </para><para>
* 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.
*
* \param 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 \p graph has one vertex. (2) If \p graph has
* at least two vertices but zero edges.
* \param weights A vector of all edge weights for \p 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 \p graph.
* \param quantities A vector of quantities providing the quantity of each
* vertex in \p 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 \p 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.
* \param 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 \p graph.
* \param mode Defines the sort of neighbourhood to consider for the vertex a
* chosen for reproduction. This is only relevant if \p graph is
* directed. If \p graph is undirected, then it is safe to pass the
* value \p IGRAPH_ALL here. Supported values are:
* \clist
* \cli IGRAPH_OUT
* Use the out-neighbours of a. This option is only relevant when
* \p graph is directed.
* \cli IGRAPH_IN
* Use the in-neighbours of a. Again this option is only relevant
* when \p graph is directed.
* \cli IGRAPH_ALL
* Use both the in- and out-neighbours of a. This option is only
* relevant if \p graph is directed. Also use this value if
* \p graph is undirected.
* \endclist
* \return The error code \p IGRAPH_EINVAL is returned in each of the following
* cases: (1) Any of the parameters \p graph, \p weights,
* \p quantities or \p strategies is a null pointer. (2) The vector
* \p quantities or \p strategies has a length different from the
* number of vertices in \p graph. (3) The vector \p weights has a
* length different from the number of edges in \p graph. (4) The
* parameter \p graph is the empty or null graph, i.e. the graph with
* zero vertices and edges. (5) The vector \p weights, or the
* combination of interest, sums to zero. (6) The vector \p 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 \p graph.
*
* </para><para>
* References:
* \clist
* \cli (Lieberman et al. 2005)
* E. Lieberman, C. Hauert, and M. A. Nowak. Evolutionary dynamics on
* graphs. \emb Nature, \eme 433(7023):312--316, 2005.
* \cli (Moran 1958)
* P. A. P. Moran. Random processes in genetics. \emb Mathematical
* Proceedings of the Cambridge Philosophical Society, \eme 54(1):60--71,
* 1958.
* \endclist
*
* \example examples/simple/igraph_moran_process.c
*/
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) {
igraph_bool_t updates;
igraph_integer_t a = -1; /* vertex chosen for reproduction */
igraph_integer_t b = -1; /* vertex chosen for death */
igraph_integer_t e, nedge, u, v;
igraph_real_t r; /* random number */
igraph_vector_t deg;
igraph_vector_t V; /* vector of cumulative proportionate values */
igraph_vit_t vA; /* vertex list */
igraph_eit_t eA; /* edge list */
igraph_vs_t vs;
igraph_es_t es;
long int i;
/* don't test for vertex isolation, hence vid = -1 and islocal = 0 */
IGRAPH_CHECK(igraph_microscopic_standard_tests(graph, /*vid*/ -1,
quantities, strategies, mode,
&updates, /*is local?*/ 0));
if (!updates) {
return IGRAPH_SUCCESS; /* nothing more to do */
}
if (weights == NULL) {
IGRAPH_ERROR("Weights vector is a null pointer", IGRAPH_EINVAL);
}
nedge = igraph_ecount(graph);
if (nedge != (igraph_integer_t)igraph_vector_size(weights)) {
IGRAPH_ERROR("Size of weights vector different from number of edges",
IGRAPH_EINVAL);
}
/* Cumulative proportionate quantities. We are using the global */
/* perspective, hence islocal = 0, vid = -1 and mode = IGRAPH_ALL. */
IGRAPH_CHECK(igraph_vcumulative_proportionate_values(graph, quantities, &V,
/*is local?*/ 0,
/*vid*/ -1,
/*mode*/ IGRAPH_ALL));
/* Choose a vertex for reproduction from among all vertices in the graph. */
/* The vertex is chosen proportionate to its quantity and such that its */
/* degree is >= 1. In case we are considering in-neighbours (respectively */
/* out-neighbours), the chosen vertex must have in-degree (respectively */
/* out-degree) >= 1. All loops will be ignored. At this point, we know */
/* that the graph has at least one edge, which may be directed or not. */
/* Furthermore the quantities of all vertices sum to a positive value. */
/* Hence at least one vertex will be chosen for reproduction. */
IGRAPH_CHECK(igraph_vs_all(&vs));
IGRAPH_FINALLY(igraph_vs_destroy, &vs);
IGRAPH_CHECK(igraph_vit_create(graph, vs, &vA));
IGRAPH_FINALLY(igraph_vit_destroy, &vA);
RNG_BEGIN();
r = RNG_UNIF01();
RNG_END();
i = 0;
IGRAPH_VECTOR_INIT_FINALLY(°, 1);
while (!IGRAPH_VIT_END(vA)) {
u = (igraph_integer_t)IGRAPH_VIT_GET(vA);
IGRAPH_CHECK(igraph_degree(graph, °, igraph_vss_1(u), mode,
IGRAPH_NO_LOOPS));
if (VECTOR(deg)[0] < 1) {
i++;
IGRAPH_VIT_NEXT(vA);
continue;
}
if (r <= VECTOR(V)[i]) {
/* we have found our candidate vertex for reproduction */
a = u;
break;
}
i++;
IGRAPH_VIT_NEXT(vA);
}
/* By now we should have chosen a vertex for reproduction. Check this. */
assert(a >= 0);
/* Cumulative proportionate weights. We are using the local perspective */
/* with respect to vertex a, which has been chosen for reproduction. */
/* The degree of a is deg(a) >= 1 with respect to the mode "mode", which */
/* can flag either the in-degree, out-degree or all degree of a. But it */
/* still might happen that the edge weights of interest would sum to zero. */
/* An error would be raised in that case. */
igraph_vector_destroy(&V);
IGRAPH_CHECK(igraph_ecumulative_proportionate_values(graph, weights, &V,
/*is local?*/ 1,
/*vertex*/ a, mode));
/* Choose a vertex for death from among all vertices in a's perspective. */
/* Let E be all the edges in the perspective of a. If (u,v) \in E is any */
/* such edge, then we have a = u or a = v. That is, any edge in E has a */
/* for one of its endpoints. As G is assumed to be a simple graph, then */
/* exactly one of u or v is the vertex a. Without loss of generality, we */
/* assume that each edge in E has the form (a, v_i). Then the vertex v_j */
/* chosen for death is chosen proportionate to the weight of the edge */
/* (a, v_j). */
IGRAPH_CHECK(igraph_es_incident(&es, a, mode));
IGRAPH_FINALLY(igraph_es_destroy, &es);
IGRAPH_CHECK(igraph_eit_create(graph, es, &eA));
IGRAPH_FINALLY(igraph_eit_destroy, &eA);
RNG_BEGIN();
r = RNG_UNIF01();
RNG_END();
i = 0;
while (!IGRAPH_EIT_END(eA)) {
e = (igraph_integer_t)IGRAPH_EIT_GET(eA);
if (r <= VECTOR(V)[i]) {
/* We have found our candidate vertex for death; call this vertex b. */
/* As G is simple, then a =/= b. Check the latter condition. */
IGRAPH_CHECK(igraph_edge(graph, /*edge ID*/ e,
/*tail vertex*/ &u, /*head vertex*/ &v));
if (a == u) {
b = v;
} else {
b = u;
}
assert(a != b); /* always true if G is simple */
break;
}
i++;
IGRAPH_EIT_NEXT(eA);
}
/* By now a vertex a is chosen for reproduction and a vertex b is chosen */
/* for death. Check that b has indeed been chosen. Clone vertex a and kill */
/* vertex b. Let the clone c have the vertex ID of b, and the strategy and */
/* quantity of a. */
assert(b >= 0);
VECTOR(*quantities)[b] = VECTOR(*quantities)[a];
VECTOR(*strategies)[b] = VECTOR(*strategies)[a];
igraph_vector_destroy(°);
igraph_vector_destroy(&V);
igraph_vit_destroy(&vA);
igraph_eit_destroy(&eA);
igraph_vs_destroy(&vs);
igraph_es_destroy(&es);
IGRAPH_FINALLY_CLEAN(6);
return IGRAPH_SUCCESS;
}
/**
* \ingroup spatialgames
* \function igraph_roulette_wheel_imitation
* \brief Adopt a strategy via roulette wheel selection.
*
* 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.
*
* \param 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 \p graph has one vertex, then no strategy update
* would take place. Furthermore, if \p graph has at least two vertices
* but zero edges, then strategy update would also not take place.
* \param vid The vertex whose strategy is to be updated. It is assumed that
* \p vid represents a vertex in \p graph. No checking is performed and
* it is your responsibility to ensure that \p vid is indeed a vertex
* of \p graph. If an isolated vertex is provided, i.e. the input
* vertex has degree 0, then no strategy update would take place and
* \p vid would retain its current strategy. Strategy update would also
* not take place if the local neighbourhood of \p vid are its
* in-neighbours (respectively out-neighbours), but \p vid has zero
* in-neighbours (respectively out-neighbours). Loops are ignored in
* computing the degree (in, out, all) of \p vid.
* \param 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 \p vid is the set of all immediate neighbours of
* \p vid. In contrast, the global perspective for \p vid is the
* vertex set of \p graph.
* \param quantities A vector of quantities providing the quantity of each
* vertex in \p 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 \p 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.
* \param strategies A vector of the current strategies for the vertex
* population. The updated strategy for \p 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 \p graph.
* \param mode Defines the sort of neighbourhood to consider for \p vid. This
* is only relevant if we are considering the local perspective, i.e. if
* \p islocal is true. If we are considering the global perspective,
* then it is safe to pass the value \p IGRAPH_ALL here. If \p graph is
* undirected, then we use all the immediate neighbours of \p vid. Thus
* if you know that \p graph is undirected, then it is safe to pass the
* value \p IGRAPH_ALL here. Supported values are:
* \clist
* \cli IGRAPH_OUT
* Use the out-neighbours of \p vid. This option is only relevant
* when \p graph is a digraph and we are considering the local
* perspective.
* \cli IGRAPH_IN
* Use the in-neighbours of \p vid. Again this option is only relevant
* when \p graph is a directed graph and we are considering the local
* perspective.
* \cli IGRAPH_ALL
* Use both the in- and out-neighbours of \p vid. This option is only
* relevant if \p graph is a digraph. Also use this value if
* \p graph is undirected or we are considering the global
* perspective.
* \endclist
* \return The error code \p IGRAPH_EINVAL is returned in each of the following
* cases: (1) Any of the parameters \p graph, \p quantities, or
* \p strategies is a null pointer. (2) The vector \p quantities or
* \p strategies has a length different from the number of vertices
* in \p graph. (3) The parameter \p graph is the empty or null graph,
* i.e. the graph with zero vertices and edges. (4) The vector
* \p 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 \p graph. On the other hand, for the local
* perspective n is the degree of \p vid, excluding loops.
*
* </para><para>
* Reference:
* \clist
* \cli (Yu & Gen 2010)
* X. Yu and M. Gen. \emb Introduction to Evolutionary Algorithms. \eme
* Springer, 2010, pages 18--20.
* \endclist
*
* \example examples/simple/igraph_roulette_wheel_imitation.c
*/
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) {
igraph_bool_t updates;
igraph_integer_t u;
igraph_real_t r; /* random number */
igraph_vector_t V; /* vector of cumulative proportionate quantities */
igraph_vit_t A; /* all vertices in v's perspective */
igraph_vs_t vs;
long int i;
IGRAPH_CHECK(igraph_microscopic_standard_tests(graph, vid, quantities,
strategies, mode, &updates,
islocal));
if (!updates) {
return IGRAPH_SUCCESS; /* nothing further to do */
}
/* set the perspective */
if (islocal) {
IGRAPH_CHECK(igraph_vs_adj(&vs, vid, mode));
} else {
IGRAPH_CHECK(igraph_vs_all(&vs));
}
IGRAPH_FINALLY(igraph_vs_destroy, &vs);
IGRAPH_CHECK(igraph_vit_create(graph, vs, &A));
IGRAPH_FINALLY(igraph_vit_destroy, &A);
IGRAPH_CHECK(igraph_vcumulative_proportionate_values(graph, quantities, &V,
islocal, vid, mode));
/* Finally, choose a vertex u to imitate. The vertex u is chosen */
/* proportionate to its quantity. In the case of a local perspective, we */
/* pretend that v's cumulative proportionate quantity has been appended to */
/* the vector V. Let V be of length n so that V[n-1] is the last element */
/* of V, and let r be a real number chosen uniformly at random from the */
/* unit interval [0,1]. If r > V[i] for all i < n, then v defaults to */
/* retaining its current strategy. Similarly in the case of the global */
/* perspective, if r > V[i] for all i < n - 1 then v would adopt the */
/* strategy of the vertex whose cumulative proportionate quantity is */
/* V[n-1]. */
/* NOTE: Here we assume that the order in which we iterate through the */
/* vertices in A is the same as the order in which we do so in the */
/* invoked function igraph_vcumulative_proportionate_values(). */
/* Otherwise we would incorrectly associate each V[i] with a vertex in A. */
RNG_BEGIN();
r = RNG_UNIF01();
RNG_END();
i = 0;
while (!IGRAPH_VIT_END(A)) {
if (r <= VECTOR(V)[i]) {
/* We have found our candidate vertex for imitation. Update strategy */
/* of v to that of u, and exit the selection loop. */
u = (igraph_integer_t)IGRAPH_VIT_GET(A);
VECTOR(*strategies)[vid] = VECTOR(*strategies)[u];
break;
}
i++;
IGRAPH_VIT_NEXT(A);
}
/* By now, vertex v should either retain its current strategy or it has */
/* adopted the strategy of a vertex in its perspective. Nothing else to */
/* do, but clean up. */
igraph_vector_destroy(&V);
igraph_vit_destroy(&A);
igraph_vs_destroy(&vs);
IGRAPH_FINALLY_CLEAN(3);
return IGRAPH_SUCCESS;
}
/**
* \ingroup spatialgames
* \function igraph_stochastic_imitation
* \brief Adopt a strategy via stochastic imitation with uniform selection.
*
* 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.
*
* \param 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 \p graph has one vertex, then no strategy update
* would take place. Furthermore, if \p graph has at least two vertices
* but zero edges, then strategy update would also not take place.
* \param vid The vertex whose strategy is to be updated. It is assumed that
* \p vid represents a vertex in \p graph. No checking is performed and
* it is your responsibility to ensure that \p vid is indeed a vertex
* of \p graph. If an isolated vertex is provided, i.e. the input
* vertex has degree 0, then no strategy update would take place and
* \p vid would retain its current strategy. Strategy update would also
* not take place if the local neighbourhood of \p vid are its
* in-neighbours (respectively out-neighbours), but \p vid has zero
* in-neighbours (respectively out-neighbours). Loops are ignored in
* computing the degree (in, out, all) of \p vid.
* \param algo This flag controls which algorithm to use in stochastic
* imitation. Supported values are:
* \clist
* \cli IGRAPH_IMITATE_AUGMENTED
* Augmented imitation. Vertex \p vid imitates the strategy of the
* chosen vertex u provided that doing so would increase the
* quantity (e.g. fitness) of \p vid. Augmented imitation can be
* thought of as "imitate if better".
* \cli IGRAPH_IMITATE_BLIND
* Blind imitation. Vertex \p vid blindly imitates the strategy of
* the chosen vertex u, regardless of whether doing so would
* increase or decrease the quantity of \p vid.
* \cli IGRAPH_IMITATE_CONTRACTED
* Contracted imitation. Here vertex \p vid imitates the strategy of
* the chosen vertex u if doing so would decrease the quantity of
* \p vid. Think of contracted imitation as "imitate if worse".
* \endclist
* \param quantities A vector of quantities providing the quantity of each
* vertex in \p 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 \p graph.
* \param strategies A vector of the current strategies for the vertex
* population. The updated strategy for \p 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 \p graph.
* \param mode Defines the sort of neighbourhood to consider for \p vid. If
* \p graph is undirected, then we use all the immediate neighbours of
* \p vid. Thus if you know that \p graph is undirected, then it is safe
* to pass the value \p IGRAPH_ALL here. Supported values are:
* \clist
* \cli IGRAPH_OUT
* Use the out-neighbours of \p vid. This option is only relevant
* when \p graph is a directed graph.
* \cli IGRAPH_IN
* Use the in-neighbours of \p vid. Again this option is only relevant
* when \p graph is a directed graph.
* \cli IGRAPH_ALL
* Use both the in- and out-neighbours of \p vid. This option is only
* relevant if \p graph is a digraph. Also use this value if
* \p graph is undirected.
* \endclist
* \return The error code \p IGRAPH_EINVAL is returned in each of the following
* cases: (1) Any of the parameters \p graph, \p quantities, or
* \p strategies is a null pointer. (2) The vector \p quantities or
* \p strategies has a length different from the number of vertices
* in \p graph. (3) The parameter \p graph is the empty or null graph,
* i.e. the graph with zero vertices and edges. (4) The parameter
* \p algo refers to an unsupported stochastic imitation algorithm.
*
* Time complexity: depends on the uniform random number generator, but should
* usually be O(1).
*
* \example examples/simple/igraph_stochastic_imitation.c
*/
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) {
igraph_bool_t updates;
igraph_integer_t u;
igraph_vector_t adj;
int i;
/* sanity checks */
if (algo != IGRAPH_IMITATE_AUGMENTED &&
algo != IGRAPH_IMITATE_BLIND &&
algo != IGRAPH_IMITATE_CONTRACTED) {
IGRAPH_ERROR("Unsupported stochastic imitation algorithm",
IGRAPH_EINVAL);
}
IGRAPH_CHECK(igraph_microscopic_standard_tests(graph, vid, quantities,
strategies, mode, &updates,
/*is local?*/ 1));
if (!updates) {
return IGRAPH_SUCCESS; /* nothing more to do */
}
/* immediate neighbours of v */
IGRAPH_VECTOR_INIT_FINALLY(&adj, 0);
IGRAPH_CHECK(igraph_neighbors(graph, &adj, vid, mode));
/* Blind imitation. Let v be the vertex whose strategy we want to revise. */
/* Choose a vertex u uniformly at random from the immediate neighbours of */
/* v, including v itself. Then blindly update the strategy of v to that of */
/* u, irrespective of whether doing so would increase or decrease the */
/* quantity (e.g. fitness) of v. Here v retains its current strategy if */
/* the chosen vertex u is indeed v itself. */
if (algo == IGRAPH_IMITATE_BLIND) {
IGRAPH_CHECK(igraph_vector_push_back(&adj, vid));
RNG_BEGIN();
i = (int) RNG_INTEGER(0, igraph_vector_size(&adj) - 1);
RNG_END();
u = (igraph_integer_t) VECTOR(adj)[i];
VECTOR(*strategies)[vid] = VECTOR(*strategies)[u];
}
/* Augmented imitation. Let v be the vertex whose strategy we want to */
/* revise. Let f be the quantity function for the game. Choose a vertex u */
/* uniformly at random from the immediate neighbours of v; do not include */
/* v. Then v imitates the strategy of u if f(u) > f(v). Otherwise v */
/* retains its current strategy. */
else if (algo == IGRAPH_IMITATE_AUGMENTED) {
RNG_BEGIN();
i = (int) RNG_INTEGER(0, igraph_vector_size(&adj) - 1);
RNG_END();
u = (igraph_integer_t) VECTOR(adj)[i];
if (VECTOR(*quantities)[u] > VECTOR(*quantities)[vid]) {
VECTOR(*strategies)[vid] = VECTOR(*strategies)[u];
}
}
/* Contracted imitation. Let v be the vertex whose strategy we want to */
/* update and let f be the quantity function for the game. Choose a vertex */
/* u uniformly at random from the immediate neighbours of v, excluding v */
/* itself. Then v imitates the strategy of u provided that f(u) < f(v). */
/* Otherwise v retains its current strategy. */
else if (algo == IGRAPH_IMITATE_CONTRACTED) {
RNG_BEGIN();
i = (int) RNG_INTEGER(0, igraph_vector_size(&adj) - 1);
RNG_END();
u = (igraph_integer_t) VECTOR(adj)[i];
if (VECTOR(*quantities)[u] < VECTOR(*quantities)[vid]) {
VECTOR(*strategies)[vid] = VECTOR(*strategies)[u];
}
}
/* clean up */
igraph_vector_destroy(&adj);
IGRAPH_FINALLY_CLEAN(1);
return IGRAPH_SUCCESS;
}