igraph Reference Manual

For using the igraph C library

Chapter 9. Graph Generators

Graph generators create graphs.

Almost all functions which create graph objects are documented here. The exceptions are igraph_subgraph() and alike, these create graphs based on another graph.

1. Deterministic Graph Generators

1.1. igraph_create — Creates a graph with the specified edges.

int igraph_create(igraph_t *graph, const igraph_vector_t *edges,
		igraph_integer_t n, igraph_bool_t directed);

Arguments: 

graph:

An uninitialized graph object.

edges:

The edges to add, the first two elements are the first edge, etc.

n:

The number of vertices in the graph, if smaller or equal to the highest vertex id in the edges vector it will be increased automatically. So it is safe to give 0 here.

directed:

Boolean, whether to create a directed graph or not. If yes, then the first edge points from the first vertex id in edges to the second, etc.

Returns: 

Error code: IGRAPH_EINVEVECTOR: invalid edges vector (odd number of vertices). IGRAPH_EINVVID: invalid (negative) vertex id.

Time complexity: O(|V|+|E|), |V| is the number of vertices, |E| the number of edges in the graph.

Example 9.1.  File examples/simple/igraph_create.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard street, Cambridge, MA 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>

int main() {
  
  igraph_t g;
  igraph_vector_t v1, v2;
  int ret;
  
  /* simple use */
  igraph_vector_init(&v1, 8);
  VECTOR(v1)[0]=0; VECTOR(v1)[1]=1;
  VECTOR(v1)[2]=1; VECTOR(v1)[3]=2;
  VECTOR(v1)[4]=2; VECTOR(v1)[5]=3;
  VECTOR(v1)[6]=2; VECTOR(v1)[7]=2;
  igraph_create(&g, &v1, 0, 0);
  if (igraph_vcount(&g) != 4) {
    return 1;
  }
  igraph_vector_init(&v2, 0);
  igraph_get_edgelist(&g, &v2, 0);
  igraph_vector_sort(&v1);
  igraph_vector_sort(&v2);
  if (!igraph_vector_all_e(&v1, &v2)) {
    return 2;
  }
  igraph_destroy(&g);
  
  /* higher number of vertices */
  igraph_create(&g, &v1, 10, 0);
  if (igraph_vcount(&g) != 10) {
    return 1;
  }
  igraph_get_edgelist(&g, &v2, 0);
  igraph_vector_sort(&v1);
  igraph_vector_sort(&v2);
  if (!igraph_vector_all_e(&v1, &v2)) {
    return 3;
  }
  igraph_destroy(&g);

  /* error: IGRAPH_EINVEVECTOR */
  igraph_set_error_handler(igraph_error_handler_ignore);
  igraph_vector_resize(&v1, 9);
  VECTOR(v1)[8]=0;
  ret=igraph_create(&g, &v1, 0, 0);
  if (ret != IGRAPH_EINVEVECTOR) {
    return 4;
  }
  
  /* error: IGRAPH_EINVVID */
  igraph_vector_resize(&v1, 8);
  VECTOR(v1)[7]=-1;
  ret=igraph_create(&g, &v1, 10, 1);
  if (ret != IGRAPH_EINVVID) {
    return 5;
  }
  igraph_vector_destroy(&v1);
  igraph_vector_destroy(&v2);

  return 0;
}


1.2. igraph_small — Shorthand to create a short graph, giving the edges as arguments.

int igraph_small(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed, 
		 ...);

This function is handy when a relatively small graph needs to be created. Instead of giving the edges as a vector, they are given simply as arguments and a '-1' needs to be given after the last meaningful edge argument.

Note that only graphs which have vertices less than the highest value of the 'int' type can be created this way. If you give larger values then the result is undefined.

Arguments: 

graph:

Pointer to an uninitialized graph object. The result will be stored here.

n:

The number of vertices in the graph; a nonnegative integer.

directed:

Logical constant; gives whether the graph should be directed. Supported values are:

IGRAPH_DIRECTED

The graph to be created will be directed.

IGRAPH_UNDIRECTED

The graph to be created will be undirected.

...:

The additional arguments giving the edges of the graph. Don't forget to supply an additional '-1' after the last (meaningful) argument.

Returns: 

Error code.

Time complexity: O(|V|+|E|), the number of vertices plus the number of edges in the graph to create.

Example 9.2.  File examples/simple/igraph_small.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>

int main() {
  
  igraph_t g;
  
  igraph_small(&g, 0, IGRAPH_DIRECTED, 0,1, 1,2, 2,3, 3,4, 6,1, -1);
  igraph_write_graph_edgelist(&g, stdout);
  igraph_destroy(&g);
  
  return 0;
}


1.3. igraph_adjacency — Creates a graph object from an adjacency matrix.

int igraph_adjacency(igraph_t *graph, igraph_matrix_t *adjmatrix,
		     igraph_adjacency_t mode);

The order of the vertices in the matrix is preserved, i.e. the vertex corresponding to the first row/column will be vertex with id 0, the next row is for vertex 1, etc.

Arguments: 

graph:

Pointer to an uninitialized graph object.

adjmatrix:

The adjacency matrix. How it is interpreted depends on the mode argument.

mode:

Constant to specify how the given matrix is interpreted as an adjacency matrix. Possible values (A(i,j) is the element in row i and column j in the adjacency matrix adjmatrix):

IGRAPH_ADJ_DIRECTED

the graph will be directed and an element gives the number of edges between two vertices.

IGRAPH_ADJ_UNDIRECTED

this is the same as IGRAPH_ADJ_MAX, for convenience.

IGRAPH_ADJ_MAX

undirected graph will be created and the number of edges between vertices i and j is max(A(i,j), A(j,i)).

IGRAPH_ADJ_MIN

undirected graph will be created with min(A(i,j), A(j,i)) edges between vertices i and j.

IGRAPH_ADJ_PLUS

undirected graph will be created with A(i,j)+A(j,i) edges between vertices i and j.

IGRAPH_ADJ_UPPER

undirected graph will be created, only the upper right triangle (including the diagonal) is used for the number of edges.

IGRAPH_ADJ_LOWER

undirected graph will be created, only the lower left triangle (including the diagonal) is used for creating the edges.

Returns: 

Error code, IGRAPH_NONSQUARE: non-square matrix.

Time complexity: O(|V||V|), |V| is the number of vertices in the graph.

Example 9.3.  File examples/simple/igraph_adjacency.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard street, Cambridge, MA 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>

int main() {

  return 0;
}


1.4. igraph_weighted_adjacency — Creates a graph object from a weighted adjacency matrix.

int igraph_weighted_adjacency(igraph_t *graph, igraph_matrix_t *adjmatrix,
			      igraph_adjacency_t mode, const char* attr, 
			      igraph_bool_t loops);

The order of the vertices in the matrix is preserved, i.e. the vertex corresponding to the first row/column will be vertex with id 0, the next row is for vertex 1, etc.

Arguments: 

graph:

Pointer to an uninitialized graph object.

adjmatrix:

The weighted adjacency matrix. How it is interpreted depends on the mode argument. The common feature is that edges with zero weights are considered nonexistent (however, negative weights are permitted).

mode:

Constant to specify how the given matrix is interpreted as an adjacency matrix. Possible values (A(i,j) is the element in row i and column j in the adjacency matrix adjmatrix):

IGRAPH_ADJ_DIRECTED

the graph will be directed and an element gives the weight of the edge between two vertices.

IGRAPH_ADJ_UNDIRECTED

this is the same as IGRAPH_ADJ_MAX, for convenience.

IGRAPH_ADJ_MAX

undirected graph will be created and the weight of the edge between vertices i and j is max(A(i,j), A(j,i)).

IGRAPH_ADJ_MIN

undirected graph will be created with edge weight min(A(i,j), A(j,i)) between vertices i and j.

IGRAPH_ADJ_PLUS

undirected graph will be created with edge weight A(i,j)+A(j,i) between vertices i and j.

IGRAPH_ADJ_UPPER

undirected graph will be created, only the upper right triangle (including the diagonal) is used for the edge weights.

IGRAPH_ADJ_LOWER

undirected graph will be created, only the lower left triangle (including the diagonal) is used for the edge weights.

attr:

the name of the attribute that will store the edge weights. If NULL , it will use weight as the attribute name.

loops:

Logical scalar, whether to ignore the diagonal elements in the adjacency matrix.

Returns: 

Error code, IGRAPH_NONSQUARE: non-square matrix.

Time complexity: O(|V||V|), |V| is the number of vertices in the graph.

Example 9.4.  File examples/simple/igraph_weighted_adjacency.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>
#include <stdarg.h>

void print(igraph_t *g) {
  igraph_vector_t el;
  long int i, j, n;
  char ch = igraph_is_directed(g) ? '>' : '-';

  igraph_vector_init(&el, 0);
  igraph_get_edgelist(g, &el, 0);
  n = igraph_ecount(g);

  for (i=0, j=0; i<n; i++, j+=2) {
    printf("%ld --%c %ld: %ld\n",
      (long)VECTOR(el)[j], ch, (long)VECTOR(el)[j+1], (long)EAN(g, "weight", i)); 
  }
  printf("\n");

  igraph_vector_destroy(&el);
}

int main() {
  igraph_t g;
  igraph_matrix_t mat;
  int m[4][4] = { { 0, 1, 2, 0 }, { 2, 0, 0, 1 }, { 0, 0, 1, 0 }, { 0, 1, 0, 0 } };
  long int i, j;

  igraph_matrix_init(&mat, 4, 4);
  for (i=0; i<4; i++) for (j=0; j<4; j++) MATRIX(mat, i, j) = m[i][j];
  igraph_i_set_attribute_table(&igraph_cattribute_table);

  /* [ 0 1 2 0 ]
     [ 2 0 0 1 ]
     [ 0 0 1 0 ]
     [ 0 1 0 0 ] */
  igraph_weighted_adjacency(&g, &mat, IGRAPH_ADJ_DIRECTED, 0, /*loops=*/ 1);
  print(&g);
  igraph_destroy(&g);

  /* [ 0 1 2 0 ]
     [ - 0 0 1 ]
     [ - - 1 0 ]
     [ - - - 0 ] */
  igraph_weighted_adjacency(&g, &mat, IGRAPH_ADJ_UPPER, 0, /*loops=*/ 1);
  print(&g);
  igraph_destroy(&g);

  /* [ 0 - - - ]
     [ 2 0 - - ]
     [ 0 0 1 - ]
     [ 0 1 0 0 ] */
  igraph_weighted_adjacency(&g, &mat, IGRAPH_ADJ_LOWER, 0, /*loops=*/ 1);
  print(&g);
  igraph_destroy(&g);

  /* [ 0 1 0 0 ]
     [ 1 0 0 1 ]
     [ 0 0 1 0 ]
     [ 0 1 0 0 ] */
  igraph_weighted_adjacency(&g, &mat, IGRAPH_ADJ_MIN, 0, /*loops=*/ 1);
  print(&g);
  igraph_destroy(&g);

  /* [ 0 2 2 0 ]
     [ 2 0 0 1 ]
     [ 2 0 1 0 ]
     [ 0 1 0 0 ] */
  igraph_weighted_adjacency(&g, &mat, IGRAPH_ADJ_MAX, 0, /*loops=*/ 1);
  print(&g);
  igraph_destroy(&g);

  /* [ 0 3 2 0 ]
     [ 3 0 0 2 ]
     [ 2 0 1 0 ]
     [ 0 2 0 0 ] */
  igraph_weighted_adjacency(&g, &mat, IGRAPH_ADJ_PLUS, 0, /*loops=*/ 1);
  print(&g);
  igraph_destroy(&g);

  igraph_matrix_destroy(&mat);

  if (IGRAPH_FINALLY_STACK_SIZE() != 0) return 1;

  return 0;
}


1.5. igraph_adjlist — Create a graph from an adjacency list

int igraph_adjlist(igraph_t *graph, const igraph_adjlist_t *adjlist,
		   igraph_neimode_t mode, igraph_bool_t duplicate);

An adjacency list is a list of vectors, containing the neighbors of all vertices. For operations that involve many changes to the graph structure, it is recommended that you convert the graph into an adjacency list via igraph_adjlist_init(), perform the modifications (these are cheap for an adjacency list) and then recreate the igraph graph via this function.

Arguments: 

graph:

Pointer to an uninitialized graph object.

adjlist:

The adjacency list.

mode:

Whether or not to create a directed graph. IGRAPH_ALL means an undirected graph, IGRAPH_OUT means a directed graph from an out-adjacency list (i.e. each list contains the successors of the corresponding vertices), IGRAPH_IN means a directed graph from an in-adjacency list

duplicate:

Logical, for undirected graphs this specified whether each edge is included twice, in the vectors of both adjacent vertices. If this is false (0), then it is assumed that every edge is included only once. This argument is ignored for directed graphs.

Returns: 

Error code.

See also: 

igraph_adjlist_init() for the opposite operation.

Time complexity: O(|V|+|E|).

1.6. igraph_star — Creates a star graph, every vertex connects only to the center.

int igraph_star(igraph_t *graph, igraph_integer_t n, igraph_star_mode_t mode, 
		igraph_integer_t center);

Arguments: 

graph:

Pointer to an uninitialized graph object, this will be the result.

n:

Integer constant, the number of vertices in the graph.

mode:

Constant, gives the type of the star graph to create. Possible values:

IGRAPH_STAR_OUT

directed star graph, edges point from the center to the other vertices.

IGRAPH_STAR_IN

directed star graph, edges point to the center from the other vertices.

IGRAPH_STAR_MUTUAL

directed star graph with mutual edges.

IGRAPH_STAR_UNDIRECTED

an undirected star graph is created.

center:

Id of the vertex which will be the center of the graph.

Returns: 

Error code:

IGRAPH_EINVVID

invalid number of vertices.

IGRAPH_EINVAL

invalid center vertex.

IGRAPH_EINVMODE

invalid mode argument.

Time complexity: O(|V|), the number of vertices in the graph.

See also: 

igraph_lattice(), igraph_ring(), igraph_tree() for creating other regular structures.

Example 9.5.  File examples/simple/igraph_star.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>

int main() {

  return 0;
}


1.7. igraph_lattice — Creates most kinds of lattices.

int igraph_lattice(igraph_t *graph, const igraph_vector_t *dimvector,
		igraph_integer_t nei, igraph_bool_t directed, igraph_bool_t mutual,
		igraph_bool_t circular);

Arguments: 

graph:

An uninitialized graph object.

dimvector:

Vector giving the sizes of the lattice in each of its dimensions. Ie. the dimension of the lattice will be the same as the length of this vector.

nei:

Integer value giving the distance (number of steps) within which two vertices will be connected.

directed:

Boolean, whether to create a directed graph. The direction of the edges is determined by the generation algorithm and is unlikely to suit you, so this isn't a very useful option.

mutual:

Boolean, if the graph is directed this gives whether to create all connections as mutual.

circular:

Boolean, defines whether the generated lattice is periodic.

Returns: 

Error code: IGRAPH_EINVAL: invalid (negative) dimension vector.

Time complexity: if nei is less than two then it is O(|V|+|E|) (as far as I remember), |V| and |E| are the number of vertices and edges in the generated graph. Otherwise it is O(|V|*d^o+|E|), d is the average degree of the graph, o is the nei argument.

1.8. igraph_ring — Creates a ring graph, a one dimensional lattice.

int igraph_ring(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed,
		igraph_bool_t mutual, igraph_bool_t circular);

An undirected (circular) ring on n vertices is commonly known in graph theory as the cycle graph C_n.

Arguments: 

graph:

Pointer to an uninitialized graph object.

n:

The number of vertices in the ring.

directed:

Logical, whether to create a directed ring.

mutual:

Logical, whether to create mutual edges in a directed ring. It is ignored for undirected graphs.

circular:

Logical, if false, the ring will be open (this is not a real ring actually).

Returns: 

Error code: IGRAPH_EINVAL: invalid number of vertices.

Time complexity: O(|V|), the number of vertices in the graph.

See also: 

igraph_lattice() for generating more general lattices.

Example 9.6.  File examples/simple/igraph_ring.c

/* -*- mode: C -*-  */
/*
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA

   Ring test suite
   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>

typedef struct {
  int n, m;
  igraph_bool_t directed, mutual, circular;
  igraph_real_t *edges;
} ring_test_t;

#define RING_TEST(id, n, m, di, mu, ci, ...) \
  igraph_real_t ring_ ## id ## _edges[] = { __VA_ARGS__ };		\
  ring_test_t ring_ ## id = { n, m, di, mu, ci, ring_ ## id ## _edges }

/*---------------n--m--di-mu-ci--edges-------------------------------------*/
RING_TEST(uc_6,  6, 6, 0, 0, 1,  0,1, 1,2, 2,3, 3,4, 4,5, 5,0 );
RING_TEST(uc_0,  0, 0, 0, 0, 1,  -1 );
RING_TEST(uc_1,  1, 0, 0, 0, 1,  -1 );
RING_TEST(uc_2,  2, 1, 0, 0, 1,  0,1 );

RING_TEST(u_6,   6, 5, 0, 0, 0,  0,1, 1,2, 2,3, 3,4, 4,5 );
RING_TEST(u_0,   0, 0, 0, 0, 0,  -1 );
RING_TEST(u_1,   1, 0, 0, 0, 0,  -1 );
RING_TEST(u_2,   2, 1, 0, 0, 0,  0,1 );

RING_TEST(umc_6, 6, 6, 0, 1, 1,  0,1, 1,2, 2,3, 3,4, 4,5, 5,0 );
RING_TEST(umc_0, 0, 0, 0, 1, 1,  -1 );
RING_TEST(umc_1, 1, 0, 0, 1, 1,  -1 );
RING_TEST(umc_2, 2, 1, 0, 1, 1,  0,1 );

RING_TEST(um_6,  6, 5, 0, 1, 0,  0,1, 1,2, 2,3, 3,4, 4,5 );
RING_TEST(um_0,  0, 0, 0, 1, 0,  -1 );
RING_TEST(um_1,  1, 0, 0, 1, 0,  -1 );
RING_TEST(um_2,  2, 1, 0, 1, 0,  0,1 );

RING_TEST(dc_6,  6, 6, 1, 0, 1,  0,1, 1,2, 2,3, 3,4, 4,5, 5,0 );
RING_TEST(dc_0,  0, 0, 1, 0, 1,  -1 );
RING_TEST(dc_1,  1, 0, 1, 0, 1,  -1 );
RING_TEST(dc_2,  2, 2, 1, 0, 1,  0,1, 1,0 );

RING_TEST(d_6,   6, 5, 1, 0, 1,  0,1, 1,2, 2,3, 3,4, 4,5 );
RING_TEST(d_0,   0, 0, 1, 0, 1,  -1 );
RING_TEST(d_1,   1, 0, 1, 0, 1,  -1 );
RING_TEST(d_2,   2, 1, 1, 0, 1,  0,1 );

RING_TEST(dmc_6,  6,12, 1, 1, 1, 0,1, 1,2, 2,3, 3,4, 4,5, 5,0,
                                 1,0, 2,1, 3,2, 4,3, 5,4, 0,5 );
RING_TEST(dmc_0,  0, 0, 1, 1, 1, -1 );
RING_TEST(dmc_1,  1, 0, 1, 1, 1, -1 );
RING_TEST(dmc_2,  2, 2, 1, 1, 1, 0,1, 1,0 );

RING_TEST(dm_6,  6,10, 1, 1, 0,  0,1, 1,2, 2,3, 3,4, 4,5,
                                 1,0, 2,1, 3,2, 4,3, 5,4 );
RING_TEST(dm_0,  0, 0, 1, 1, 0,  -1 );
RING_TEST(dm_1,  1, 0, 1, 1, 0,  -1 );
RING_TEST(dm_2,  2, 2, 1, 1, 0,  0,1, 1,0 );
/*---------------n--m--di-mu-ci--edges-------------------------------------*/

ring_test_t *all_checks[] = { /*  1 */ &ring_uc_6,   /*  2 */ &ring_uc_0,
			      /*  3 */ &ring_uc_1,   /*  4 */ &ring_uc_2,
			      /*  5 */ &ring_u_6,    /*  6 */ &ring_u_0,
			      /*  7 */ &ring_u_1,    /*  8 */ &ring_u_2,
			      /*  9 */ &ring_umc_6,  /* 10 */ &ring_umc_0,
			      /* 11 */ &ring_umc_1,  /* 12 */ &ring_umc_2,
			      /* 13 */ &ring_um_6,   /* 14 */ &ring_um_0,
			      /* 15 */ &ring_um_1,   /* 16 */ &ring_um_2,
			      /* 17 */ &ring_dc_6,   /* 18 */ &ring_dc_0,
			      /* 19 */ &ring_dc_1,   /* 20 */ &ring_dc_2,
			      /* 21 */ &ring_dmc_6,  /* 22 */ &ring_dmc_0,
			      /* 23 */ &ring_dmc_1,  /* 24 */ &ring_dmc_2,
			      /* 25 */ &ring_dm_6,   /* 26 */ &ring_dm_0,
			      /* 27 */ &ring_dm_1,   /* 28 */ &ring_dm_2,
			      0 };

int check_ring_properties(const igraph_t *ring, igraph_bool_t directed,
			  igraph_bool_t mutual, igraph_bool_t circular) {

  igraph_bool_t res;

  /* Connected */
  igraph_is_connected(ring, &res, IGRAPH_WEAK); 
  if (!res) {
    printf("Not connected\n");
    return 1;
  }

  /* Simple */
  igraph_is_simple(ring, &res); 
  if (!res) {
    printf("Not simple\n");
    return 2;
  }
  
  /* Girth, for big enough circular graphs */
  if (circular && igraph_vcount(ring) > 2) { 
    igraph_integer_t girth;
    igraph_girth(ring, &girth, NULL);
    if (girth != igraph_vcount(ring)) { 
      printf("Wrong girth\n");
      return 3; 
    }
  }
   
  return 0;
}

int check_ring(const ring_test_t *test) {
  igraph_t graph, othergraph;
  igraph_vector_t otheredges;
  igraph_bool_t iso;
  int ret;

  /* Create ring */
  igraph_ring(&graph, test->n, test->directed, test->mutual, test->circular);

  /* Check its properties */
  if ((ret=check_ring_properties(&graph, test->directed, test->mutual, 
				 test->circular))) { return ret;}

  /* Check that it is isomorphic to the stored graph */
  igraph_vector_view(&otheredges, test->edges, test->m * 2);
  igraph_create(&othergraph, &otheredges, test->n, test->directed);
  igraph_isomorphic(&graph, &othergraph, &iso);
  if (!iso) { return 50; }

  /* Clean up */
  igraph_destroy(&graph);
  igraph_destroy(&othergraph);

  return 0;
}

int main() {
  int i, ret;

  i=0;
  while (all_checks[i]) {
    if ((ret=check_ring(all_checks[i]))) { 
      printf("Check no #%d failed.\n", (int) (i+1));
      return ret;
    }
    i++;
  }

  return 0;
}


1.9. igraph_tree — Creates a tree in which almost all vertices have the same number of children.

int igraph_tree(igraph_t *graph, igraph_integer_t n, igraph_integer_t children, 
		igraph_tree_mode_t type);

Arguments: 

graph:

Pointer to an uninitialized graph object.

n:

Integer, the number of vertices in the graph.

children:

Integer, the number of children of a vertex in the tree.

type:

Constant, gives whether to create a directed tree, and if this is the case, also its orientation. Possible values:

IGRAPH_TREE_OUT

directed tree, the edges point from the parents to their children,

IGRAPH_TREE_IN

directed tree, the edges point from the children to their parents.

IGRAPH_TREE_UNDIRECTED

undirected tree.

Returns: 

Error code: IGRAPH_EINVAL: invalid number of vertices. IGRAPH_INVMODE: invalid mode argument.

Time complexity: O(|V|+|E|), the number of vertices plus the number of edges in the graph.

See also: 

igraph_lattice(), igraph_star() for creating other regular structures.

Example 9.7.  File examples/simple/igraph_tree.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>

int main() {

  return 0;
}


1.10. igraph_full — Creates a full graph (directed or undirected, with or without loops).

int igraph_full(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed,
		igraph_bool_t loops);

In a full graph every possible edge is present, every vertex is connected to every other vertex. A full graph in igraph should be distinguished from the concept of complete graphs as used in graph theory. If n is a positive integer, then the complete graph K_n on n vertices is the undirected simple graph with the following property. For any distinct pair (u,v) of vertices in K_n, uv (or equivalently vu) is an edge of K_n. In igraph, a full graph on n vertices can be K_n, a directed version of K_n, or K_n with at least one loop edge. In any case, if F is a full graph on n vertices as generated by igraph, then K_n is a subgraph of the undirected version of F.

Arguments: 

graph:

Pointer to an uninitialized graph object.

n:

Integer, the number of vertices in the graph.

directed:

Logical, whether to create a directed graph.

loops:

Logical, whether to include self-edges (loops).

Returns: 

Error code: IGRAPH_EINVAL: invalid number of vertices.

Time complexity: O(|V|+|E|), |V| is the number of vertices, |E| the number of edges in the graph. Of course this is the same as O(|E|)=O(|V||V|) here.

See also: 

igraph_lattice(), igraph_star(), igraph_tree() for creating other regular structures.

Example 9.8.  File examples/simple/igraph_full.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>

int main() {

  return 0;
}


1.11. igraph_full_citation — Creates a full citation graph

int igraph_full_citation(igraph_t *graph, igraph_integer_t n, 
			 igraph_bool_t directed);

This is a directed graph, where every i->j edge is present if and only if j<i . If the directed argument is zero then an undirected graph is created, and it is just a full graph.

Arguments: 

graph:

Pointer to an uninitialized graph object, the result is stored here.

n:

The number of vertices.

directed:

Whether to created a directed graph. If zero an undirected graph is created.

Returns: 

Error code.

Time complexity: O(|V|^2), as we have many edges.

1.12. igraph_famous — Create a famous graph by simply providing its name

int igraph_famous(igraph_t *graph, const char *name);

The name of the graph can be simply supplied as a string. Note that this function creates graphs which don't take any parameters, there are separate functions for graphs with parameters, eg. igraph_full() for creating a full graph.

The following graphs are supported:

Bull

The bull graph, 5 vertices, 5 edges, resembles the head of a bull if drawn properly.

Chvatal

This is the smallest triangle-free graph that is both 4-chromatic and 4-regular. According to the Grunbaum conjecture there exists an m-regular, m-chromatic graph with n vertices for every m>1 and n>2. The Chvatal graph is an example for m=4 and n=12. It has 24 edges.

Coxeter

A non-Hamiltonian cubic symmetric graph with 28 vertices and 42 edges.

Cubical

The Platonic graph of the cube. A convex regular polyhedron with 8 vertices and 12 edges.

Diamond

A graph with 4 vertices and 5 edges, resembles a schematic diamond if drawn properly.

Dodecahedral, Dodecahedron

Another Platonic solid with 20 vertices and 30 edges.

Folkman

The semisymmetric graph with minimum number of vertices, 20 and 40 edges. A semisymmetric graph is regular, edge transitive and not vertex transitive.

Franklin

This is a graph whose embedding to the Klein bottle can be colored with six colors, it is a counterexample to the necessity of the Heawood conjecture on a Klein bottle. It has 12 vertices and 18 edges.

Frucht

The Frucht Graph is the smallest cubical graph whose automorphism group consists only of the identity element. It has 12 vertices and 18 edges.

Grotzsch

The Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, and chromatic number 4. It is named after German mathematician Herbert Grötzsch, and its existence demonstrates that the assumption of planarity is necessary in Grötzsch's theorem that every triangle-free planar graph is 3-colorable.

Heawood

The Heawood graph is an undirected graph with 14 vertices and 21 edges. The graph is cubic, and all cycles in the graph have six or more edges. Every smaller cubic graph has shorter cycles, so this graph is the 6-cage, the smallest cubic graph of girth 6.

Herschel

The Herschel graph is the smallest nonhamiltonian polyhedral graph. It is the unique such graph on 11 nodes, and has 18 edges.

House

The house graph is a 5-vertex, 6-edge graph, the schematic draw of a house if drawn properly, basically a triangle on top of a square.

HouseX

The same as the house graph with an X in the square. 5 vertices and 8 edges.

Icosahedral, Icosahedron

A Platonic solid with 12 vertices and 30 edges.

Krackhardt_Kite

A social network with 10 vertices and 18 edges. Krackhardt, D. Assessing the Political Landscape: Structure, Cognition, and Power in Organizations. Admin. Sci. Quart. 35, 342-369, 1990.

Levi

The graph is a 4-arc transitive cubic graph, it has 30 vertices and 45 edges.

McGee

The McGee graph is the unique 3-regular 7-cage graph, it has 24 vertices and 36 edges.

Meredith

The Meredith graph is a quartic graph on 70 nodes and 140 edges that is a counterexample to the conjecture that every 4-regular 4-connected graph is Hamiltonian.

Noperfectmatching

A connected graph with 16 vertices and 27 edges containing no perfect matching. A matching in a graph is a set of pairwise non-incident edges; that is, no two edges share a common vertex. A perfect matching is a matching which covers all vertices of the graph.

Nonline

A graph whose connected components are the 9 graphs whose presence as a vertex-induced subgraph in a graph makes a nonline graph. It has 50 vertices and 72 edges.

Octahedral, Octahedron

Platonic solid with 6 vertices and 12 edges.

Petersen

A 3-regular graph with 10 vertices and 15 edges. It is the smallest hypohamiltonian graph, ie. it is non-hamiltonian but removing any single vertex from it makes it Hamiltonian.

Robertson

The unique (4,5)-cage graph, ie. a 4-regular graph of girth 5. It has 19 vertices and 38 edges.

Smallestcyclicgroup

A smallest nontrivial graph whose automorphism group is cyclic. It has 9 vertices and 15 edges.

Tetrahedral, Tetrahedron

Platonic solid with 4 vertices and 6 edges.

Thomassen

The smallest hypotraceable graph, on 34 vertices and 52 edges. A hypotracable graph does not contain a Hamiltonian path but after removing any single vertex from it the remainder always contains a Hamiltonian path. A graph containing a Hamiltonian path is called traceable.

Tutte

Tait's Hamiltonian graph conjecture states that every 3-connected 3-regular planar graph is Hamiltonian. This graph is a counterexample. It has 46 vertices and 69 edges.

Uniquely3colorable

Returns a 12-vertex, triangle-free graph with chromatic number 3 that is uniquely 3-colorable.

Walther

An identity graph with 25 vertices and 31 edges. An identity graph has a single graph automorphism, the trivial one.

Zachary

Social network of friendships between 34 members of a karate club at a US university in the 1970s. See W. W. Zachary, An information flow model for conflict and fission in small groups, Journal of Anthropological Research 33, 452-473 (1977).

Arguments: 

graph:

Pointer to an uninitialized graph object.

name:

Character constant, the name of the graph to be created, it is case insensitive.

Returns: 

Error code, IGRAPH_EINVAL if there is no graph with the given name.

See also: 

Other functions for creating graph structures: igraph_ring(), igraph_tree(), igraph_lattice(), igraph_full().

Time complexity: O(|V|+|E|), the number of vertices plus the number of edges in the graph.

1.13. igraph_lcf — Create a graph from LCF notation

int igraph_lcf(igraph_t *graph, igraph_integer_t n, ...);

LCF is short for Lederberg-Coxeter-Frucht, it is a concise notation for 3-regular Hamiltonian graphs. It consists of three parameters: the number of vertices in the graph, a list of shifts giving additional edges to a cycle backbone, and another integer giving how many times the shifts should be performed. See http://mathworld.wolfram.com/LCFNotation.html for details.

Arguments: 

graph:

Pointer to an uninitialized graph object.

n:

Integer, the number of vertices in the graph.

...:

The shifts and the number of repeats for the shifts, plus an additional 0 to mark the end of the arguments.

Returns: 

Error code.

See also: 

See igraph_lcf_vector() for a similar function using a vector_t instead of the variable length argument list.

Time complexity: O(|V|+|E|), the number of vertices plus the number of edges.

Example 9.9.  File examples/simple/igraph_lcf.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2007-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>

int main() {
  
  igraph_t g, g2;
  igraph_bool_t iso;
  
  igraph_lcf(&g, 12, 5, -5, 6, 0);
  igraph_famous(&g2, "franklin");
  
  igraph_isomorphic_vf2(&g, &g2, 
			/*vertex.color1=*/ 0, /*vertex.color2=*/ 0, 
			/*edge.color1=*/ 0, /*edge.color2=*/ 0,
			&iso, 0, 0, 0, 0, 0);
  if (!iso) {
    printf("OOOPS!\n");
    return 1;
  }
  
  igraph_destroy(&g);
  igraph_destroy(&g2);
  
  return 0;
}


1.14. igraph_lcf_vector — Create a graph from LCF notation

int igraph_lcf_vector(igraph_t *graph, igraph_integer_t n,
		      const igraph_vector_t *shifts, 
		      igraph_integer_t repeats);

This function is essentially the same as igraph_lcf(), only the way for giving the arguments is different. See igraph_lcf() for details.

Arguments: 

graph:

Pointer to an uninitialized graph object.

n:

Integer constant giving the number of vertices.

shifts:

A vector giving the shifts.

repeats:

An integer constant giving the number of repeats for the shifts.

Returns: 

Error code.

See also: 

Time complexity: O(|V|+|E|), linear in the number of vertices plus the number of edges.

1.15. igraph_atlas — Create a small graph from the Graph Atlas.

int igraph_atlas(igraph_t *graph, int number);

The number of the graph is given as a parameter. The graphs are listed:

  1. in increasing order of number of nodes;

  2. for a fixed number of nodes, in increasing order of the number of edges;

  3. for fixed numbers of nodes and edges, in increasing order of the degree sequence, for example 111223 < 112222;

  4. for fixed degree sequence, in increasing number of automorphisms.

The data was converted from the NetworkX software package, see http://networkx.github.io .

See An Atlas of Graphs by Ronald C. Read and Robin J. Wilson, Oxford University Press, 1998.

Arguments: 

graph:

Pointer to an uninitialized graph object.

number:

The number of the graph to generate.

Added in version 0.2.

Time complexity: O(|V|+|E|), the number of vertices plus the number of edges.

Example 9.10.  File examples/simple/igraph_atlas.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard street, Cambridge, MA 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>

int main() {

  igraph_t g;
  int ret;

  igraph_atlas(&g, 45);
  igraph_write_graph_edgelist(&g, stdout);
  printf("\n");
  igraph_destroy(&g);

  igraph_atlas(&g, 0);
  igraph_write_graph_edgelist(&g, stdout);
  printf("\n");
  igraph_destroy(&g);

  igraph_atlas(&g, 1252);
  igraph_write_graph_edgelist(&g, stdout);
  printf("\n");
  igraph_destroy(&g);

  igraph_set_error_handler(igraph_error_handler_ignore);
  ret=igraph_atlas(&g, -1);
  if (ret != IGRAPH_EINVAL) {
    return 1;
  }

  ret=igraph_atlas(&g, 1253);
  if (ret != IGRAPH_EINVAL) {
    return 2;
  }

  return 0;
}


1.16. igraph_de_bruijn — Generate a de Bruijn graph.

int igraph_de_bruijn(igraph_t *graph, igraph_integer_t m, igraph_integer_t n);

A de Bruijn graph represents relationships between strings. An alphabet of m letters are used and strings of length n are considered. A vertex corresponds to every possible string and there is a directed edge from vertex v to vertex w if the string of v can be transformed into the string of w by removing its first letter and appending a letter to it.

Please note that the graph will have m to the power n vertices and even more edges, so probably you don't want to supply too big numbers for m and n.

De Bruijn graphs have some interesting properties, please see another source, eg. Wikipedia for details.

Arguments: 

graph:

Pointer to an uninitialized graph object, the result will be stored here.

m:

Integer, the number of letters in the alphabet.

n:

Integer, the length of the strings.

Returns: 

Error code.

See also: 

Time complexity: O(|V|+|E|), the number of vertices plus the number of edges.

1.17. igraph_kautz — Generate a Kautz graph.

int igraph_kautz(igraph_t *graph, igraph_integer_t m, igraph_integer_t n);

A Kautz graph is a labeled graph, vertices are labeled by strings of length n+1 above an alphabet with m+1 letters, with the restriction that every two consecutive letters in the string must be different. There is a directed edge from a vertex v to another vertex w if it is possible to transform the string of v into the string of w by removing the first letter and appending a letter to it.

Kautz graphs have some interesting properties, see eg. Wikipedia for details.

Vincent Matossian wrote the first version of this function in R, thanks.

Arguments: 

graph:

Pointer to an uninitialized graph object, the result will be stored here.

m:

Integer, m+1 is the number of letters in the alphabet.

n:

Integer, n+1 is the length of the strings.

Returns: 

Error code.

See also: 

Time complexity: O(|V|* [(m+1)/m]^n +|E|), in practice it is more like O(|V|+|E|). |V| is the number of vertices, |E| is the number of edges and m and n are the corresponding arguments.

1.18. igraph_extended_chordal_ring — Create an extended chordal ring

int igraph_extended_chordal_ring(igraph_t *graph, igraph_integer_t nodes, 
				 const igraph_matrix_t *W);

An extended chordal ring is a regular graph, each node has the same degree. It can be obtained from a simple ring by adding some extra edges specified by a matrix. Let p denote the number of columns in the W matrix. The extra edges of vertex i are added according to column (i mod p) in W. The number of extra edges is the number of rows in W: for each row j an edge i->i+w[ij] is added if i+w[ij] is less than the number of total nodes.

See also Kotsis, G: Interconnection Topologies for Parallel Processing Systems, PARS Mitteilungen 11, 1-6, 1993.

Arguments: 

graph:

Pointer to an uninitialized graph object, the result will be stored here. The result is always an undirected graph.

nodes:

Integer constant, the number of vertices in the graph. It must be at least 3.

W:

The matrix specifying the extra edges. The number of columns should divide the number of total vertices.

Returns: 

Error code.

See also: 

Time complexity: O(|V|+|E|), the number of vertices plus the number of edges.

1.19. igraph_connect_neighborhood — Connects every vertex to its neighborhood

int igraph_connect_neighborhood(igraph_t *graph, igraph_integer_t order,
				igraph_neimode_t mode);

This function adds new edges to the input graph. For each vertex vertices reachable by at most order steps and not yet connected to the vertex a new edge is created.

Note that the input graph is modified in place, no new graph is created, call igraph_copy() if you want to keep the original graph as well.

For undirected graphs reachability is always symmetric: if vertex A can be reached from vertex B in at most order steps, then the opposite is also true. Only one undirected (A,B) edge will be added in this case.

Arguments: 

graph:

The input graph, this is the output graph as well.

order:

Integer constant, it gives the distance within which the vertices will be connected to the source vertex.

mode:

Constant, it specifies how the neighborhood search is performed for directed graphs. If IGRAPH_OUT then vertices reachable from the source vertex will be connected, IGRAPH_IN is the opposite. If IGRAPH_ALL then the directed graph is considered as an undirected one.

Returns: 

Error code.

See also: 

igraph_lattice() uses this function to connect the neighborhood of the vertices.

Time complexity: O(|V|*d^o), |V| is the number of vertices in the graph, d is the average degree and o is the order argument.

2. Games: Randomized Graph Generators

2.1. igraph_grg_game — Generating geometric random graphs.
2.2. igraph_barabasi_game — Generates a graph based on the Barabási-Albert model.
2.3. igraph_erdos_renyi_game — Generates a random (Erdos-Renyi) graph.
2.4. igraph_watts_strogatz_game — The Watts-Strogatz small-world model
2.5. igraph_rewire_edges — Rewire the edges of a graph with constant probability
2.6. igraph_degree_sequence_game — Generates a random graph with a given degree sequence
2.7. igraph_k_regular_game — Generates a random graph where each vertex has the same degree.
2.8. igraph_static_fitness_game — Generates a non-growing random graph with edge probabilities
2.9. igraph_static_power_law_game — Generates a non-growing random graph with expected power-law degree distributions.
2.10. igraph_forest_fire_game — Generates a network according to the forest fire game
2.11. igraph_rewire — Randomly rewires a graph while preserving the degree distribution.
2.12. igraph_growing_random_game — Generates a growing random graph.
2.13. igraph_callaway_traits_game — Simulate a growing network with vertex types.
2.14. igraph_establishment_game — Generates a graph with a simple growing model with vertex types.
2.15. igraph_preference_game — Generates a graph with vertex types and connection preferences
2.16. igraph_asymmetric_preference_game — Generates a graph with asymmetric vertex types and connection preferences
2.17. igraph_recent_degree_game — Stochastic graph generator based on the number of incident edges a node has gained recently
2.18. igraph_barabasi_aging_game — Preferential attachment with aging of vertices
2.19. igraph_recent_degree_aging_game — Preferential attachment based on the number of edges gained recently, with aging of vertices
2.20. igraph_cited_type_game — Simulate a citation based on vertex types.
2.21. igraph_citing_cited_type_game — Simulate a citation network based on vertex types.
2.22. igraph_sbm_game — Sample from a stochastic block model

Games are randomized graph generators. Randomization means that they generate a different graph every time you call them.

2.1. igraph_grg_game — Generating geometric random graphs.

int igraph_grg_game(igraph_t *graph, igraph_integer_t nodes,
		    igraph_real_t radius, igraph_bool_t torus,
		    igraph_vector_t *x, igraph_vector_t *y);

A geometric random graph is created by dropping points (=vertices) randomly to the unit square and then connecting all those pairs which are less than radius apart in Euclidean norm.

Original code contributed by Keith Briggs, thanks Keith.

Arguments: 

graph:

Pointer to an uninitialized graph object,

nodes:

The number of vertices in the graph.

radius:

The radius within which the vertices will be connected.

torus:

Logical constant, if true periodic boundary conditions will be used, ie. the vertices are assumed to be on a torus instead of a square.

Returns: 

Error code.

Time complexity: TODO, less than O(|V|^2+|E|).

Example 9.11.  File examples/simple/igraph_grg_game.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>

#include <unistd.h>
#include <sys/times.h>
#include <math.h>

int main() {
  
  igraph_t g;
  /* long int i; */
  /* struct tms time; */
  /* clock_t current_time,start_time; */
  /* long int runs=100, n=10000; */
  /* igraph_real_t r=0.01; */
  
  /* Empty graph */
  igraph_grg_game(&g, 100, 0, 0, 0, 0);
  if (igraph_ecount(&g) != 0) {
    return 1;
  }
  igraph_destroy(&g);
  
  /* Full graph */
  igraph_grg_game(&g, 10, sqrt(2.0)/2, 1, 0, 0);
  if (igraph_ecount(&g) != igraph_vcount(&g) * (igraph_vcount(&g)-1)/2) {
    return 2;
  }
  igraph_destroy(&g);

  /* Measure running time */
/*   tps=sysconf(_SC_CLK_TCK); // clock ticks per second  */
/*   times(&time); start_time=time.tms_utime; */
/*   for (i=0; i<runs; i++) { */
/*     igraph_grg_game2(&g, n, r, 1);  */
/*     igraph_destroy(&g); */
/*   } */
/*   times(&time); current_time=time.tms_utime; */
/*   fprintf(stdout,"    sorted: time=%.3fs\n",(current_time-start_time)/(double)tps); */

/*   tps=sysconf(_SC_CLK_TCK); // clock ticks per second  */
/*   times(&time); start_time=time.tms_utime; */
/*   for (i=0; i<runs; i++) { */
/*     igraph_grg_game(&g, n, r, 1); */
/*     igraph_destroy(&g); */
/*   } */
/*   times(&time); current_time=time.tms_utime; */
/*   fprintf(stdout,"non-sorted: time=%.3fs\n", */
/* 	  (current_time-start_time)/(double)tps); */


  return 0;
}


2.2. igraph_barabasi_game — Generates a graph based on the Barabási-Albert model.

int igraph_barabasi_game(igraph_t *graph, igraph_integer_t n,
			 igraph_real_t power, 
			 igraph_integer_t m,
			 const igraph_vector_t *outseq,
			 igraph_bool_t outpref,
			 igraph_real_t A,
			 igraph_bool_t directed,
			 igraph_barabasi_algorithm_t algo,
			 const igraph_t *start_from);

Arguments: 

graph:

An uninitialized graph object.

n:

The number of vertices in the graph.

power:

Power of the preferential attachment. The probability that a vertex is cited is proportional to d^power+A, where d is its degree (see also the outpref argument), power and A are given by arguments. In the classic preferential attachment model power=1.

m:

The number of outgoing edges generated for each vertex. (Only if outseq is NULL.)

outseq:

Gives the (out-)degrees of the vertices. If this is constant, this can be a NULL pointer or an empty (but initialized!) vector, in this case m contains the constant out-degree. The very first vertex has by definition no outgoing edges, so the first number in this vector is ignored.

outpref:

Boolean, if true not only the in- but also the out-degree of a vertex increases its citation probability. Ie. the citation probability is determined by the total degree of the vertices.

A:

The probability that a vertex is cited is proportional to d^power+A, where d is its degree (see also the outpref argument), power and A are given by arguments. In the previous versions of the function this parameter was implicitly set to one.

directed:

Boolean, whether to generate a directed graph.

algo:

The algorithm to use to generate the network. Possible values:

IGRAPH_BARABASI_BAG

This is the algorithm that was previously (before version 0.6) solely implemented in igraph. It works by putting the ids of the vertices into a bag (multiset, really), exactly as many times as their (in-)degree, plus once more. Then the required number of cited vertices are drawn from the bag, with replacement. This method might generate multiple edges. It only works if power=1 and A=1.

IGRAPH_BARABASI_PSUMTREE

This algorithm uses a partial prefix-sum tree to generate the graph. It does not generate multiple edges and works for any power and A values.

IGRAPH_BARABASI_PSUMTREE_MULTIPLE

This algorithm also uses a partial prefix-sum tree to generate the graph. The difference is, that now multiple edges are allowed. This method was implemented under the name igraph_nonlinear_barabasi_game before version 0.6.

start_from:

Either a null pointer, or a graph. In the latter case the graph as a starting configuration. The graph must be non-empty, i.e. it must have at least one vertex. If a graph is supplied here and the outseq argument is also given, then outseq should only contain information on the vertices that are not in the start_from graph.

Returns: 

Error code: IGRAPH_EINVAL: invalid n, m or outseq parameter.

Time complexity: O(|V|+|E|), the number of vertices plus the number of edges.

Example 9.12.  File examples/simple/igraph_barabasi_game.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard street, Cambridge, MA 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>

int main() {
  
  igraph_t g;
  igraph_vector_t v, v2;
  int i, ret;
  
  igraph_barabasi_game(&g, 10, /*power=*/ 1, 2, 0, 0, /*A=*/ 1, 1, 
		       IGRAPH_BARABASI_BAG, /*start_from=*/ 0);
  if (igraph_ecount(&g) != 18) {
    return 1;
  }
  if (igraph_vcount(&g) != 10) {
    return 2;
  }
  if (!igraph_is_directed(&g)) {
    return 3;
  }

  igraph_vector_init(&v, 0);
  igraph_get_edgelist(&g, &v, 0);
  for (i=0; i<igraph_ecount(&g); i++) {
    if (VECTOR(v)[2*i] <= VECTOR(v)[2*i+1]) {
      return 4;
    }
  }
  igraph_destroy(&g);
  
  /* out degree sequence */
  igraph_vector_resize(&v, 10);
  VECTOR(v)[0]=0; VECTOR(v)[1]=1;
  VECTOR(v)[2]=3; VECTOR(v)[3]=3;
  VECTOR(v)[4]=4; VECTOR(v)[5]=5;
  VECTOR(v)[6]=6; VECTOR(v)[7]=7;
  VECTOR(v)[8]=8; VECTOR(v)[9]=9;
  
  igraph_barabasi_game(&g, 10, /*power=*/ 1, 0, &v, 0, /*A=*/ 1, 1, 
		       IGRAPH_BARABASI_BAG, /*start_from=*/ 0);
  if (igraph_ecount(&g) != igraph_vector_sum(&v)) {
    return 5;
  }
  igraph_vector_init(&v2, 0);
  igraph_degree(&g, &v2, igraph_vss_all(), IGRAPH_OUT, 1);
  for (i=0; i<igraph_vcount(&g); i++) {
    if (VECTOR(v)[i] != VECTOR(v2)[i]) {
      igraph_vector_print(&v);
      printf("\n");
      igraph_vector_print(&v2);
      return 6;
    }
  }
  igraph_vector_destroy(&v);
  igraph_vector_destroy(&v2);
  igraph_destroy(&g);
  
  /* outpref, we cannot really test this quantitatively,
     would need to set random seed */
  igraph_barabasi_game(&g, 10, /*power=*/ 1, 2, 0, 1, /*A=*/ 1, 1,
		       IGRAPH_BARABASI_BAG, /*start_from=*/ 0);
  igraph_vector_init(&v, 0);
  igraph_get_edgelist(&g, &v, 0);
  for (i=0; i<igraph_ecount(&g); i++) {
    if (VECTOR(v)[2*i] <= VECTOR(v)[2*i+1]) {
      return 7;
    }
  }
  if (!igraph_is_directed(&g)) {
    return 8;
  }
  igraph_vector_destroy(&v);
  igraph_destroy(&g);

  /* Error tests */
  igraph_set_error_handler(igraph_error_handler_ignore);
  ret=igraph_barabasi_game(&g, -10, /*power=*/ 1, 1, 0, 0, /*A=*/ 1, 0, 
			   IGRAPH_BARABASI_BAG, /*start_from=*/ 0);
  if (ret != IGRAPH_EINVAL) {
    return 9;
  }
  ret=igraph_barabasi_game(&g, 10, /*power=*/ 1, -2, 0, 0, /*A=*/ 1, 0,
			   IGRAPH_BARABASI_BAG, /*start_from=*/ 0);
  if (ret != IGRAPH_EINVAL) {
    return 10;
  }
  igraph_vector_init(&v, 9);
  ret=igraph_barabasi_game(&g, 10, /*power=*/ 1, 0, &v, 0, /*A=*/ 1, 0,
			   IGRAPH_BARABASI_BAG, /*start_from=*/ 0);
  if (ret != IGRAPH_EINVAL) {
    return 11;
  }
  igraph_vector_destroy(&v);
  
  return 0;
}


Example 9.13.  File examples/simple/igraph_barabasi_game2.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2010-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard street, Cambridge, MA 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>
#include <stdio.h>

int main() {
  
  igraph_t g;
  igraph_bool_t simple;

  igraph_barabasi_game(/* graph=    */ &g, 
		       /* n=        */ 100,
		       /* power=    */ 1.0,
		       /* m=        */ 2,
		       /* outseq=   */ 0,
		       /* outpref=  */ 0,
		       /* A=        */ 1.0,
		       /* directed= */ IGRAPH_DIRECTED,
		       /* algo=     */ IGRAPH_BARABASI_PSUMTREE,
		       /* start_from= */ 0);
  
  if (igraph_ecount(&g) != 197) { return 1; }
  if (igraph_vcount(&g) != 100) { return 2; }
  igraph_is_simple(&g, &simple);
  if (!simple) { return 3; }
  
  igraph_destroy(&g);
  
  /* ============================== */

  igraph_barabasi_game(/* graph=    */ &g, 
		       /* n=        */ 100,
		       /* power=    */ 1.0,
		       /* m=        */ 2,
		       /* outseq=   */ 0,
		       /* outpref=  */ 0,
		       /* A=        */ 1.0,
		       /* directed= */ IGRAPH_DIRECTED,
		       /* algo=     */ IGRAPH_BARABASI_PSUMTREE_MULTIPLE,
		       /* start_from= */ 0);

  if (igraph_ecount(&g) != 198) { return 4; }
  if (igraph_vcount(&g) != 100) { return 5; }
  igraph_is_simple(&g, &simple);
  if (simple) { return 6; }
  
  igraph_destroy(&g);

  /* ============================== */

  igraph_barabasi_game(/* graph=    */ &g, 
		       /* n=        */ 100,
		       /* power=    */ 1.0,
		       /* m=        */ 2,
		       /* outseq=   */ 0,
		       /* outpref=  */ 0,
		       /* A=        */ 1.0,
		       /* directed= */ IGRAPH_DIRECTED,
		       /* algo=     */ IGRAPH_BARABASI_BAG,
		       /* start_from= */ 0);

  if (igraph_ecount(&g) != 198) { return 7; }
  if (igraph_vcount(&g) != 100) { return 8; }
  igraph_is_simple(&g, &simple);
  if (simple) { return 9; }
  
  igraph_destroy(&g);    
  
  return 0;
}


2.3. igraph_erdos_renyi_game — Generates a random (Erdos-Renyi) graph.

int igraph_erdos_renyi_game(igraph_t *graph, igraph_erdos_renyi_t type,
			    igraph_integer_t n, igraph_real_t p_or_m,
			    igraph_bool_t directed, igraph_bool_t loops);

Arguments: 

graph:

Pointer to an uninitialized graph object.

type:

The type of the random graph, possible values:

IGRAPH_ERDOS_RENYI_GNM

G(n,m) graph, m edges are selected uniformly randomly in a graph with n vertices.

IGRAPH_ERDOS_RENYI_GNP

G(n,p) graph, every possible edge is included in the graph with probability p.

n:

The number of vertices in the graph.

p_or_m:

This is the p parameter for G(n,p) graphs and the m parameter for G(n,m) graphs.

directed:

Logical, whether to generate a directed graph.

loops:

Logical, whether to generate loops (self) edges.

Returns: 

Error code: IGRAPH_EINVAL: invalid type, n, p or m parameter. IGRAPH_ENOMEM: there is not enough memory for the operation.

Time complexity: O(|V|+|E|), the number of vertices plus the number of edges in the graph.

See also: 

Example 9.14.  File examples/simple/igraph_erdos_renyi_game.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>

int main() {

  igraph_t g;
  int i;
  igraph_bool_t simple;
  
  /* G(n,p) */
  igraph_erdos_renyi_game(&g, IGRAPH_ERDOS_RENYI_GNP, 10, 0.0, 
			  IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);
  if (igraph_ecount(&g) != 0) {
    return 1;
  }
  if (igraph_is_directed(&g)) {
    return 2;
  }
  igraph_destroy(&g);
  
  igraph_erdos_renyi_game(&g, IGRAPH_ERDOS_RENYI_GNP, 10, 1.0,
			  IGRAPH_DIRECTED, IGRAPH_NO_LOOPS);
  if (igraph_ecount(&g) != 10*9) {
    return 3;
  }
  if (!igraph_is_directed(&g)) {
    return 4;
  }
  igraph_destroy(&g);

  /* More useful tests */
/*   printf("directed with loops\n"); */
  for (i=0; i<100; i++) {
    igraph_erdos_renyi_game(&g, IGRAPH_ERDOS_RENYI_GNP, 10, 0.9999999,
			    IGRAPH_DIRECTED, IGRAPH_LOOPS);
    if (igraph_vcount(&g) != 10) { return 5; }
    if (igraph_ecount(&g) != 10*10) { return 77; }
    igraph_simplify(&g, /*multiple=*/0, /*loops=*/1, /*edge_comb=*/ 0);
    if (igraph_ecount(&g) != 10*9) { return 77; }
    igraph_destroy(&g);
  }

/*   printf("directed without loops\n"); */
  for (i=0; i<100; i++) {
    igraph_erdos_renyi_game(&g, IGRAPH_ERDOS_RENYI_GNP, 10, 0.9999999,
			    IGRAPH_DIRECTED, IGRAPH_NO_LOOPS);
    if (igraph_vcount(&g) != 10) { return 7; }
    if (igraph_ecount(&g) != 10*(10-1)) { return 77; }
    igraph_simplify(&g, /*multiple=*/0, /*loops=*/1, /*edge_comb=*/ 0);
    if (igraph_ecount(&g) != 10*9) { return 77; }
    igraph_destroy(&g);
  }
  
/*   printf("undirected with loops\n"); */
  for (i=0; i<100; i++) {
    igraph_erdos_renyi_game(&g, IGRAPH_ERDOS_RENYI_GNP, 10, 0.9999999,
			    IGRAPH_UNDIRECTED, IGRAPH_LOOPS);
    if (igraph_vcount(&g) != 10) { return 9; }
    if (igraph_ecount(&g) != 10*(10+1)/2) { return 77; }
    igraph_simplify(&g, /*multiple=*/0, /*loops=*/1, /*edge_comb=*/ 0);
    if (igraph_ecount(&g) != 10*(10-1)/2) { return 77; }
    igraph_destroy(&g);
  }

/*   printf("undirected without loops\n"); */
  for (i=0; i<100; i++) {
    igraph_erdos_renyi_game(&g, IGRAPH_ERDOS_RENYI_GNP, 10, 0.9999999,
			    IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);
    if (igraph_vcount(&g) != 10) { return 11; }
    if (igraph_ecount(&g) != 10*(10-1)/2) { return 77; }
    igraph_simplify(&g, /*multiple=*/0, /*loops=*/1, /*edge_comb=*/ 0);
    if (igraph_ecount(&g) != 10*(10-1)/2) { return 77; }
    igraph_destroy(&g);
  }    

  /* Create a couple of large graphs too */
  igraph_erdos_renyi_game(&g, IGRAPH_ERDOS_RENYI_GNP, 100000, 2.0/100000,
			  IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);
  if (igraph_vcount(&g) != 100000) { return 25; }
  igraph_destroy(&g);
  igraph_erdos_renyi_game(&g, IGRAPH_ERDOS_RENYI_GNP, 100000, 2.0/100000,
			  IGRAPH_DIRECTED, IGRAPH_NO_LOOPS);
  if (igraph_vcount(&g) != 100000) { return 25; }
  igraph_destroy(&g);
  igraph_erdos_renyi_game(&g, IGRAPH_ERDOS_RENYI_GNP, 100000, 2.0/100000,
			  IGRAPH_UNDIRECTED, IGRAPH_LOOPS);
  if (igraph_vcount(&g) != 100000) { return 25; }
  igraph_destroy(&g);
  igraph_erdos_renyi_game(&g, IGRAPH_ERDOS_RENYI_GNP, 100000, 2.0/100000,
			  IGRAPH_DIRECTED, IGRAPH_LOOPS);
  if (igraph_vcount(&g) != 100000) { return 25; }
  igraph_destroy(&g);
  

  /* --------------------------------------------------------------------- */
  /* G(n,m) */
  
  igraph_erdos_renyi_game(&g, IGRAPH_ERDOS_RENYI_GNM, 10, 0.5,
			  IGRAPH_DIRECTED, IGRAPH_NO_LOOPS);
  igraph_destroy(&g);

  /* More useful tests */
/*   printf("directed with loops\n"); */
  for (i=0; i<100; i++) {
    long int ec;
    igraph_erdos_renyi_game(&g, IGRAPH_ERDOS_RENYI_GNM, 10, 10*10-1,
			    IGRAPH_DIRECTED, IGRAPH_LOOPS);
    if (igraph_vcount(&g) != 10) { return 13; }
    if (igraph_ecount(&g) != 10*10-1) { return 14; }
    igraph_simplify(&g, /*multiple=*/0, /*loops=*/1, /*edge_comb=*/ 0);
    igraph_is_simple(&g, &simple);
    if (!simple) { return 27; }
    ec=igraph_ecount(&g);
    if (ec != 10*9 && ec != 10*9-1) { return 15; }
    igraph_destroy(&g);
  }

/*   printf("directed without loops\n"); */
  for (i=0; i<100; i++) {
    igraph_erdos_renyi_game(&g, IGRAPH_ERDOS_RENYI_GNM, 10, 10*9-1,
			    IGRAPH_DIRECTED, IGRAPH_NO_LOOPS);
    igraph_is_simple(&g, &simple);
    if (!simple) { return 28; }
    if (igraph_vcount(&g) != 10) { return 16; }
    if (igraph_ecount(&g) != 10*(10-1)-1) { return 17; }
    igraph_simplify(&g, /*multiple=*/0, /*loops=*/1, /*edge_comb=*/ 0);
    if (igraph_ecount(&g) != 10*9-1) { return 18; }
    igraph_destroy(&g);
  }
  
/*   printf("undirected with loops\n"); */
  for (i=0; i<100; i++) {
    long int ec;
    igraph_erdos_renyi_game(&g, IGRAPH_ERDOS_RENYI_GNM, 10, 10*11/2-1,
			    IGRAPH_UNDIRECTED, IGRAPH_LOOPS);
    if (igraph_vcount(&g) != 10) { return 19; }
    if (igraph_ecount(&g) != 10*(10+1)/2-1) { return 20; }
    igraph_simplify(&g, /*multiple=*/0, /*loops=*/1, /*edge_comb=*/ 0);
    igraph_is_simple(&g, &simple);
    if (!simple) { return 29; }
    ec=igraph_ecount(&g);
    if (ec != 10*(10-1)/2 && ec != 10*9/2-1) { return 21; }
    igraph_destroy(&g);
  }

/*   printf("undirected without loops\n"); */
  for (i=0; i<100; i++) {
    igraph_erdos_renyi_game(&g, IGRAPH_ERDOS_RENYI_GNM, 10, 10*9/2-1,
			    IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);
    igraph_is_simple(&g, &simple);
    if (!simple) { return 30; }
    if (igraph_vcount(&g) != 10) { return 22; }
    if (igraph_ecount(&g) != 10*(10-1)/2-1) { return 23; }
    igraph_simplify(&g, /*multiple=*/0, /*loops=*/1, /*edge_comb=*/ 0);
    if (igraph_ecount(&g) != 10*(10-1)/2-1) { return 24; }
    igraph_destroy(&g);
  }  

  /* Create a couple of large graphs too */
  igraph_erdos_renyi_game(&g, IGRAPH_ERDOS_RENYI_GNM, 100000, 2.0*100000,
			  IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);
  if (igraph_vcount(&g) != 100000) { return 26; }
  if (igraph_ecount(&g) != 200000) { return 26; }
  igraph_is_simple(&g, &simple);
  if (!simple) { return 31; }
  igraph_destroy(&g);
  igraph_erdos_renyi_game(&g, IGRAPH_ERDOS_RENYI_GNM, 100000, 2.0*100000,
			  IGRAPH_DIRECTED, IGRAPH_NO_LOOPS);
  igraph_is_simple(&g, &simple);
  if (!simple) { return 32; }
  if (igraph_vcount(&g) != 100000) { return 26; }
  if (igraph_ecount(&g) != 200000) { return 26; }
  igraph_destroy(&g);
  igraph_erdos_renyi_game(&g, IGRAPH_ERDOS_RENYI_GNM, 100000, 2.0*100000,
			  IGRAPH_UNDIRECTED, IGRAPH_LOOPS);
  if (igraph_vcount(&g) != 100000) { return 26; }
  if (igraph_ecount(&g) != 200000) { return 26; }
  igraph_simplify(&g, 0, 1, /*edge_comb=*/ 0);	/* only remove loops */
  igraph_is_simple(&g, &simple);
  if (!simple) { return 33; }
  igraph_destroy(&g);
  igraph_erdos_renyi_game(&g, IGRAPH_ERDOS_RENYI_GNM, 100000, 2.0*100000,
			  IGRAPH_DIRECTED, IGRAPH_LOOPS);
  if (igraph_vcount(&g) != 100000) { return 26; }
  if (igraph_ecount(&g) != 200000) { return 26; }
  igraph_simplify(&g, 0, 1, /*edge_comb=*/ 0);	/* only remove loops */
  igraph_is_simple(&g, &simple);
  if (!simple) { return 34; }
  igraph_destroy(&g);

  return 0;
}


2.4. igraph_watts_strogatz_game — The Watts-Strogatz small-world model

int igraph_watts_strogatz_game(igraph_t *graph, igraph_integer_t dim,
			       igraph_integer_t size, igraph_integer_t nei,
			       igraph_real_t p, igraph_bool_t loops, 
			       igraph_bool_t multiple);

This function generates a graph according to the Watts-Strogatz model of small-world networks. The graph is obtained by creating a circular undirected lattice and then rewire the edges randomly with a constant probability.

See also: Duncan J Watts and Steven H Strogatz: Collective dynamics of small world networks, Nature 393, 440-442, 1998.

Arguments: 

graph:

The graph to initialize.

dim:

The dimension of the lattice.

size:

The size of the lattice along each dimension.

nei:

The size of the neighborhood for each vertex. This is the same as the nei argument of igraph_connect_neighborhood().

p:

The rewiring probability. A real number between zero and one (inclusive).

loops:

Logical, whether to generate loop edges.

multiple:

Logical, whether to allow multiple edges in the generated graph.

Returns: 

Error code.

See also: 

igraph_lattice(), igraph_connect_neighborhood() and igraph_rewire_edges() can be used if more flexibility is needed, eg. a different type of lattice.

Time complexity: O(|V|*d^o+|E|), |V| and |E| are the number of vertices and edges, d is the average degree, o is the nei argument.

2.5. igraph_rewire_edges — Rewire the edges of a graph with constant probability

int igraph_rewire_edges(igraph_t *graph, igraph_real_t prob, 
			igraph_bool_t loops, igraph_bool_t multiple);

This function rewires the edges of a graph with a constant probability. More precisely each end point of each edge is rewired to a uniformly randomly chosen vertex with constant probability prob.

Note that this function modifies the input graph, call igraph_copy() if you want to keep it.

Arguments: 

graph:

The input graph, this will be rewired, it can be directed or undirected.

prob:

The rewiring probability a constant between zero and one (inclusive).

loops:

Boolean, whether loop edges are allowed in the new graph, or not.

multiple:

Boolean, whether multiple edges are allowed in the new graph.

Returns: 

Error code.

See also: 

igraph_watts_strogatz_game() uses this function for the rewiring.

Time complexity: O(|V|+|E|).

2.6. igraph_degree_sequence_game — Generates a random graph with a given degree sequence

int igraph_degree_sequence_game(igraph_t *graph, const igraph_vector_t *out_deg,
				const igraph_vector_t *in_deg, 
				igraph_degseq_t method);

Arguments: 

graph:

Pointer to an uninitialized graph object.

out_deg:

The degree sequence for an undirected graph (if in_seq is of length zero), or the out-degree sequence of a directed graph (if in_deq is not of length zero.

in_deg:

It is either a zero-length vector or NULL (if an undirected graph is generated), or the in-degree sequence.

method:

The method to generate the graph. Possible values:

IGRAPH_DEGSEQ_SIMPLE

For undirected graphs, this method puts all vertex ids in a bag such that the multiplicity of a vertex in the bag is the same as its degree. Then it draws pairs from the bag until the bag becomes empty. This method can generate both loop (self) edges and multiple edges. For directed graphs, the algorithm is basically the same, but two separate bags are used for the in- and out-degrees.

IGRAPH_DEGSEQ_SIMPLE_NO_MULTIPLE

This method is similar to IGRAPH_DEGSEQ_SIMPLE but tries to avoid multiple and loop edges and restarts the generation from scratch if it gets stuck. It is not guaranteed to sample uniformly from the space of all possible graphs with the given sequence, but it is relatively fast and it will eventually succeed if the provided degree sequence is graphical, but there is no upper bound on the number of iterations.

IGRAPH_DEGSEQ_VL

This method is a much more sophisticated generator than the previous ones. It can sample undirected, connected simple graphs uniformly and uses Monte-Carlo methods to randomize the graphs. This generator should be favoured if undirected and connected graphs are to be generated and execution time is not a concern. igraph uses the original implementation of Fabien Viger; see http://www-rp.lip6.fr/~latapy/FV/generation.html and the paper cited on it for the details of the algorithm.

Returns: 

Error code: IGRAPH_ENOMEM: there is not enough memory to perform the operation. IGRAPH_EINVAL: invalid method parameter, or invalid in- and/or out-degree vectors. The degree vectors should be non-negative, out_deg should sum up to an even integer for undirected graphs; the length and sum of out_deg and in_deg should match for directed graphs.

Time complexity: O(|V|+|E|), the number of vertices plus the number of edges for IGRAPH_DEGSEQ_SIMPLE. The time complexity of the other modes is not known.

See also: 

Example 9.15.  File examples/simple/igraph_degree_sequence_game.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard street, Cambridge, MA 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>

int main() {
  igraph_t g;
  igraph_vector_t outdeg, indeg, vec;
  igraph_bool_t is_simple;

  igraph_vector_init_real(&outdeg, 10, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0);
  igraph_vector_init_real(&indeg, 10, 4.0, 4.0, 2.0, 2.0, 4.0, 4.0, 2.0, 2.0, 3.0, 3.0);
  igraph_vector_init(&vec, 0);

  /* checking the simple method, undirected graphs */
  igraph_degree_sequence_game(&g, &outdeg, 0, IGRAPH_DEGSEQ_SIMPLE);
  if (igraph_is_directed(&g) || igraph_vcount(&g) != 10)
	return 1;
  if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_OUT, 1))
	return 2;
  igraph_vector_print(&vec);
  igraph_destroy(&g);

  /* checking the Viger-Latapy method, undirected graphs */
  igraph_degree_sequence_game(&g, &outdeg, 0, IGRAPH_DEGSEQ_VL);
  if (igraph_is_directed(&g) || igraph_vcount(&g) != 10)
	return 3;
  if (igraph_is_simple(&g, &is_simple) || !is_simple)
	return 4;
  if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_OUT, 0))
	return 5;
  igraph_vector_print(&vec);
  igraph_destroy(&g);

  /* checking the simple method, directed graphs */
  igraph_degree_sequence_game(&g, &outdeg, &indeg, IGRAPH_DEGSEQ_SIMPLE);
  if (!igraph_is_directed(&g) || igraph_vcount(&g) != 10)
	return 6;
  if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_OUT, 1))
	return 7;
  igraph_vector_print(&vec);
  if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_IN, 1))
	return 8;
  igraph_vector_print(&vec);
  igraph_destroy(&g);

  /* checking the no multiple edges method, undirected graphs */
  igraph_degree_sequence_game(&g, &outdeg, 0, IGRAPH_DEGSEQ_SIMPLE_NO_MULTIPLE);
  if (igraph_is_directed(&g) || igraph_vcount(&g) != 10)
	return 9;
  if (igraph_is_simple(&g, &is_simple) || !is_simple)
	return 10;
  if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_OUT, 1))
	return 11;
  igraph_vector_print(&vec);
  igraph_destroy(&g);

  /* checking the no multiple edges method, directed graphs */
  igraph_degree_sequence_game(&g, &outdeg, &indeg, IGRAPH_DEGSEQ_SIMPLE_NO_MULTIPLE);
  if (!igraph_is_directed(&g) || igraph_vcount(&g) != 10)
	return 12;
  if (igraph_is_simple(&g, &is_simple) || !is_simple)
	return 13;
  if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_OUT, 1))
	return 14;
  igraph_vector_print(&vec);
  if (igraph_degree(&g, &vec, igraph_vss_all(), IGRAPH_IN, 1))
	return 15;
  igraph_vector_print(&vec);
  igraph_destroy(&g);

  igraph_vector_destroy(&vec);
  igraph_vector_destroy(&outdeg);
  igraph_vector_destroy(&indeg);

  return 0;
}


2.7. igraph_k_regular_game — Generates a random graph where each vertex has the same degree.

int igraph_k_regular_game(igraph_t *graph,
    igraph_integer_t no_of_nodes, igraph_integer_t k,
    igraph_bool_t directed, igraph_bool_t multiple);

This game generates a directed or undirected random graph where the degrees of vertices are equal to a predefined constant k. For undirected graphs, at least one of k and the number of vertices must be even.

The game simply uses igraph_degree_sequence_game with appropriately constructed degree sequences.

Arguments: 

graph:

Pointer to an uninitialized graph object.

no_of_nodes:

The number of nodes in the generated graph.

k:

The degree of each vertex in an undirected graph, or the out-degree and in-degree of each vertex in a directed graph.

directed:

Whether the generated graph will be directed.

multiple:

Whether to allow multiple edges in the generated graph.

Returns: 

Error code: IGRAPH_EINVAL: invalid parameter; e.g., negative number of nodes, or odd number of nodes and odd k for undirected graphs. IGRAPH_ENOMEM: there is not enough memory for the operation.

Time complexity: O(|V|+|E|) if multiple is true, otherwise not known.

2.8. igraph_static_fitness_game — Generates a non-growing random graph with edge probabilities

int igraph_static_fitness_game(igraph_t *graph, igraph_integer_t no_of_edges,
                igraph_vector_t* fitness_out, igraph_vector_t* fitness_in,
                igraph_bool_t loops, igraph_bool_t multiple);

proportional to node fitness scores. This game generates a directed or undirected random graph where the probability of an edge between vertices i and j depends on the fitness scores of the two vertices involved. For undirected graphs, each vertex has a single fitness score. For directed graphs, each vertex has an out- and an in-fitness, and the probability of an edge from i to j depends on the out-fitness of vertex i and the in-fitness of vertex j.

The generation process goes as follows. We start from N disconnected nodes (where N is given by the length of the fitness vector). Then we randomly select two vertices i and j, with probabilities proportional to their fitnesses. (When the generated graph is directed, i is selected according to the out-fitnesses and j is selected according to the in-fitnesses). If the vertices are not connected yet (or if multiple edges are allowed), we connect them; otherwise we select a new pair. This is repeated until the desired number of links are created.

It can be shown that the expected degree of each vertex will be proportional to its fitness, although the actual, observed degree will not be. If you need to generate a graph with an exact degree sequence, consider igraph_degree_sequence_game instead.

This model is commonly used to generate static scale-free networks. To achieve this, you have to draw the fitness scores from the desired power-law distribution. Alternatively, you may use igraph_static_power_law_game which generates the fitnesses for you with a given exponent.

Reference: Goh K-I, Kahng B, Kim D: Universal behaviour of load distribution in scale-free networks. Phys Rev Lett 87(27):278701, 2001.

Arguments: 

graph:

Pointer to an uninitialized graph object.

fitness_out:

A numeric vector containing the fitness of each vertex. For directed graphs, this specifies the out-fitness of each vertex.

fitness_in:

If NULL, the generated graph will be undirected. If not NULL, this argument specifies the in-fitness of each vertex.

no_of_edges:

The number of edges in the generated graph.

loops:

Whether to allow loop edges in the generated graph.

multiple:

Whether to allow multiple edges in the generated graph.

Returns: 

Error code: IGRAPH_EINVAL: invalid parameter IGRAPH_ENOMEM: there is not enough memory for the operation.

Time complexity: O(|V| + |E| log |E|).

2.9. igraph_static_power_law_game — Generates a non-growing random graph with expected power-law degree distributions.

int igraph_static_power_law_game(igraph_t *graph,
    igraph_integer_t no_of_nodes, igraph_integer_t no_of_edges,
    igraph_real_t exponent_out, igraph_real_t exponent_in,
    igraph_bool_t loops, igraph_bool_t multiple,
    igraph_bool_t finite_size_correction);

This game generates a directed or undirected random graph where the degrees of vertices follow power-law distributions with prescribed exponents. For directed graphs, the exponents of the in- and out-degree distributions may be specified separately.

The game simply uses igraph_static_fitness_game with appropriately constructed fitness vectors. In particular, the fitness of vertex i is i-alpha, where alpha = 1/(gamma-1) and gamma is the exponent given in the arguments.

To remove correlations between in- and out-degrees in case of directed graphs, the in-fitness vector will be shuffled after it has been set up and before igraph_static_fitness_game is called.

Note that significant finite size effects may be observed for exponents smaller than 3 in the original formulation of the game. This function provides an argument that lets you remove the finite size effects by assuming that the fitness of vertex i is (i+i0-1)-alpha, where i0 is a constant chosen appropriately to ensure that the maximum degree is less than the square root of the number of edges times the average degree; see the paper of Chung and Lu, and Cho et al for more details.

References:

Goh K-I, Kahng B, Kim D: Universal behaviour of load distribution in scale-free networks. Phys Rev Lett 87(27):278701, 2001.

Chung F and Lu L: Connected components in a random graph with given degree sequences. Annals of Combinatorics 6, 125-145, 2002.

Cho YS, Kim JS, Park J, Kahng B, Kim D: Percolation transitions in scale-free networks under the Achlioptas process. Phys Rev Lett 103:135702, 2009.

Arguments: 

graph:

Pointer to an uninitialized graph object.

no_of_nodes:

The number of nodes in the generated graph.

no_of_edges:

The number of edges in the generated graph.

exponent_out:

The power law exponent of the degree distribution. For directed graphs, this specifies the exponent of the out-degree distribution. It must be greater than or equal to 2. If you pass IGRAPH_INFINITY here, you will get back an Erdos-Renyi random network.

exponent_in:

If negative, the generated graph will be undirected. If greater than or equal to 2, this argument specifies the exponent of the in-degree distribution. If non-negative but less than 2, an error will be generated.

loops:

Whether to allow loop edges in the generated graph.

multiple:

Whether to allow multiple edges in the generated graph.

finite_size_correction:

Whether to use the proposed finite size correction of Cho et al.

Returns: 

Error code: IGRAPH_EINVAL: invalid parameter IGRAPH_ENOMEM: there is not enough memory for the operation.

Time complexity: O(|V| + |E| log |E|).

2.10. igraph_forest_fire_game — Generates a network according to the forest fire game

int igraph_forest_fire_game(igraph_t *graph, igraph_integer_t nodes,
			    igraph_real_t fw_prob, igraph_real_t bw_factor,
			    igraph_integer_t pambs, igraph_bool_t directed);

The forest fire model intends to reproduce the following network characteristics, observed in real networks:

  • Heavy-tailed in-degree distribution.

  • Heavy-tailed out-degree distribution.

  • Communities.

  • Densification power-law. The network is densifying in time, according to a power-law rule.

  • Shrinking diameter. The diameter of the network decreases in time.

The network is generated in the following way. One vertex is added at a time. This vertex connects to (cites) ambs vertices already present in the network, chosen uniformly random. Now, for each cited vertex v we do the following procedure:

  1. We generate two random number, x and y , that are geometrically distributed with means p/(1-p) and rp(1-rp) . ( p is fw_prob , r is bw_factor .) The new vertex cites x outgoing neighbors and y incoming neighbors of v , from those which are not yet cited by the new vertex. If there are less than x or y such vertices available then we cite all of them.

  2. The same procedure is applied to all the newly cited vertices.

See also: Jure Leskovec, Jon Kleinberg and Christos Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. KDD '05: Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining , 177--187, 2005.

Note however, that the version of the model in the published paper is incorrect in the sense that it cannot generate the kind of graphs the authors claim. A corrected version is available from http://cs.stanford.edu/people/jure/pubs/powergrowth-tkdd.pdf , our implementation is based on this.

Arguments: 

graph:

Pointer to an uninitialized graph object.

nodes:

The number of vertices in the graph.

fw_prob:

The forward burning probability.

bw_factor:

The backward burning ratio. The backward burning probability is calculated as bw.factor*fw.prob .

pambs:

The number of ambassador vertices.

directed:

Whether to create a directed graph.

Returns: 

Error code.

Time complexity: TODO.

2.11. igraph_rewire — Randomly rewires a graph while preserving the degree distribution.

int igraph_rewire(igraph_t *graph, igraph_integer_t n, igraph_rewiring_t mode);

This function generates a new graph based on the original one by randomly rewiring edges while preserving the original graph's degree distribution. Please note that the rewiring is done "in place", so no new graph will be allocated. If you would like to keep the original graph intact, use igraph_copy() beforehand.

Arguments: 

graph:

The graph object to be rewired.

n:

Number of rewiring trials to perform.

mode:

The rewiring algorithm to be used. It can be one of the following:

IGRAPH_REWIRING_SIMPLE

Simple rewiring algorithm which chooses two arbitrary edges in each step (namely (a,b) and (c,d)) and substitutes them with (a,d) and (c,b) if they don't exist. The method will neither destroy nor create self-loops.

IGRAPH_REWIRING_SIMPLE_LOOPS

Same as IGRAPH_REWIRING_SIMPLE but allows the creation or destruction of self-loops.

Returns: 

Error code:

IGRAPH_EINVMODE

Invalid rewiring mode.

IGRAPH_EINVAL

Graph unsuitable for rewiring (e.g. it has less than 4 nodes in case of IGRAPH_REWIRING_SIMPLE)

IGRAPH_ENOMEM

Not enough memory for temporary data.

Time complexity: TODO.

Example 9.16.  File examples/simple/igraph_rewire.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>

int main() {
  
  igraph_t g;
  igraph_vector_t res;
  long i, n;
  
  igraph_tree(&g, 10, 3, IGRAPH_TREE_OUT);
  igraph_rewire(&g, 1000, IGRAPH_REWIRING_SIMPLE);
  
  n=igraph_vcount(&g);
  igraph_vector_init(&res, 0);
  igraph_degree(&g, &res, igraph_vss_all(), IGRAPH_IN, 0);
  for (i=0; i<n; i++)
    printf("%ld ", (long)igraph_vector_e(&res, i));
  printf("\n");
  
  igraph_degree(&g, &res, igraph_vss_all(), IGRAPH_OUT, 0);
  for (i=0; i<n; i++)
    printf("%ld ", (long)igraph_vector_e(&res, i));
  printf("\n");
    
  igraph_destroy(&g);
  igraph_vector_destroy(&res);
  
  return 0;
}


2.12. igraph_growing_random_game — Generates a growing random graph.

int igraph_growing_random_game(igraph_t *graph, igraph_integer_t n, 
			       igraph_integer_t m, igraph_bool_t directed,
			       igraph_bool_t citation);

This function simulates a growing random graph. In each discrete time step a new vertex is added and a number of new edges are also added. These graphs are known to be different from standard (not growing) random graphs.

Arguments: 

graph:

Uninitialized graph object.

n:

The number of vertices in the graph.

m:

The number of edges to add in a time step (ie. after adding a vertex).

directed:

Boolean, whether to generate a directed graph.

citation:

Boolean, if TRUE, the edges always originate from the most recently added vertex.

Returns: 

Error code: IGRAPH_EINVAL: invalid n or m parameter.

Time complexity: O(|V|+|E|), the number of vertices plus the number of edges.

Example 9.17.  File examples/simple/igraph_growing_random_game.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>

int main() {

  return 0;
}


2.13. igraph_callaway_traits_game — Simulate a growing network with vertex types.

int igraph_callaway_traits_game (igraph_t *graph, igraph_integer_t nodes, 
				igraph_integer_t types, igraph_integer_t edges_per_step, 
				igraph_vector_t *type_dist,
				igraph_matrix_t *pref_matrix,
				igraph_bool_t directed);

The different types of vertices prefer to connect other types of vertices with a given probability.

The simulation goes like this: in each discrete time step a new vertex is added to the graph. The type of this vertex is generated based on type_dist. Then two vertices are selected uniformly randomly from the graph. The probability that they will be connected depends on the types of these vertices and is taken from pref_matrix. Then another two vertices are selected and this is repeated edges_per_step times in each time step.

Arguments: 

graph:

Pointer to an uninitialized graph.

nodes:

The number of nodes in the graph.

types:

Number of node types.

edges_per_step:

The number of edges to be add per time step.

type_dist:

Vector giving the distribution of the vertex types.

pref_matrix:

Matrix giving the connection probabilities for the vertex types.

directed:

Logical, whether to generate a directed graph.

Returns: 

Error code.

Added in version 0.2.

Time complexity: O(|V|e*log(|V|)), |V| is the number of vertices, e is edges_per_step.

2.14. igraph_establishment_game — Generates a graph with a simple growing model with vertex types.

int igraph_establishment_game(igraph_t *graph, igraph_integer_t nodes,
			      igraph_integer_t types, igraph_integer_t k,
			      igraph_vector_t *type_dist,
			      igraph_matrix_t *pref_matrix,
			      igraph_bool_t directed);

The simulation goes like this: a single vertex is added at each time step. This new vertex tries to connect to k vertices in the graph. The probability that such a connection is realized depends on the types of the vertices involved.

Arguments: 

graph:

Pointer to an uninitialized graph.

nodes:

The number of vertices in the graph.

types:

The number of vertex types.

k:

The number of connections tried in each time step.

type_dist:

Vector giving the distribution of vertex types.

pref_matrix:

Matrix giving the connection probabilities for different vertex types.

directed:

Logical, whether to generate a directed graph.

Returns: 

Error code.

Added in version 0.2.

Time complexity: O(|V|*k*log(|V|)), |V| is the number of vertices and k is the k parameter.

2.15. igraph_preference_game — Generates a graph with vertex types and connection preferences

int igraph_preference_game(igraph_t *graph, igraph_integer_t nodes,
			   igraph_integer_t types,	
			   const igraph_vector_t *type_dist,
			   igraph_bool_t fixed_sizes,
			   const igraph_matrix_t *pref_matrix,
			   igraph_vector_t *node_type_vec,
			   igraph_bool_t directed,
			   igraph_bool_t loops);

This is practically the nongrowing variant of igraph_establishment_game. A given number of vertices are generated. Every vertex is assigned to a vertex type according to the given type probabilities. Finally, every vertex pair is evaluated and an edge is created between them with a probability depending on the types of the vertices involved.

In other words, this function generates a graph according to a block-model. Vertices are divided into groups (or blocks), and the probability the two vertices are connected depends on their groups only.

Arguments: 

graph:

Pointer to an uninitialized graph.

nodes:

The number of vertices in the graph.

types:

The number of vertex types.

type_dist:

Vector giving the distribution of vertex types. If NULL, all vertex types will have equal probability. See also the fixed_sizes argument.

fixed_sizes:

Boolean. If true, then the number of vertices with a given vertex type is fixed and the type_dist argument gives these numbers for each vertex type. If true, and type_dist is NULL, then the function tries to make vertex groups of the same size. If this is not possible, then some groups will have an extra vertex.

pref_matrix:

Matrix giving the connection probabilities for different vertex types. This should be symmetric if the requested graph is undirected.

node_type_vec:

A vector where the individual generated vertex types will be stored. If NULL , the vertex types won't be saved.

directed:

Logical, whether to generate a directed graph. If undirected graphs are requested, only the lower left triangle of the preference matrix is considered.

loops:

Logical, whether loop edges are allowed.

Returns: 

Error code.

Added in version 0.3.

Time complexity: O(|V|+|E|), the number of vertices plus the number of edges in the graph.

See also: 

igraph_establishment_game()

Example 9.18.  File examples/simple/igraph_preference_game.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>
#include <assert.h>

int main() {
  igraph_t g;
  igraph_vector_t tdist;
  igraph_matrix_t pmat;
  igraph_bool_t conn;
  igraph_vector_bool_t bs;
  int i;
  
  /* Symmetric preference game */
  igraph_vector_bool_init(&bs, 0);

  igraph_vector_init_real(&tdist, 3, 1.0, 1.0, 1.0);

  igraph_matrix_init(&pmat, 3, 3);
  for (i=0; i<3; i++) MATRIX(pmat, i, i) = 0.2;

  /* undirected, no loops */
  IGRAPH_CHECK(igraph_preference_game(&g, 1000, 3, &tdist, /*fixed_sizes=*/ 0,
				      &pmat, 0, 0, 0));
  if (igraph_vcount(&g) != 1000) return 18;
  if (igraph_is_directed(&g)) return 2;
  igraph_is_connected(&g, &conn, IGRAPH_STRONG);
  if (conn) return 3;
  igraph_is_loop(&g, &bs, igraph_ess_all(IGRAPH_EDGEORDER_ID));
  if (igraph_vector_bool_sum(&bs)) return 4;
  igraph_is_multiple(&g, &bs, igraph_ess_all(IGRAPH_EDGEORDER_ID));
  if (igraph_vector_bool_sum(&bs)) return 5;
  igraph_destroy(&g);

  for (i=0; i<2; i++) MATRIX(pmat, i, i+1) = 0.1;

  /* directed, no loops */
  IGRAPH_CHECK(igraph_preference_game(&g, 1000, 3, &tdist, /*fixed_sizes=*/0, 
				      &pmat, 0, 1, 0));
  if (igraph_vcount(&g) != 1000) return 17;
  if (!igraph_is_directed(&g)) return 6;
  igraph_is_loop(&g, &bs, igraph_ess_all(IGRAPH_EDGEORDER_ID));
  if (igraph_vector_bool_sum(&bs)) return 7;
  igraph_is_multiple(&g, &bs, igraph_ess_all(IGRAPH_EDGEORDER_ID));
  if (igraph_vector_bool_sum(&bs)) return 8;
  igraph_destroy(&g);

  /* undirected, loops */
  for (i=0; i<3; i++) MATRIX(pmat, i, i) = 1.0;
  IGRAPH_CHECK(igraph_preference_game(&g, 100, 3, &tdist, /*fixed_sizes=*/ 0,
				      &pmat, 0, 0, 1));
  if (igraph_vcount(&g) != 100) return 16;
  if (igraph_ecount(&g) < 1395) return 20;
  if (igraph_is_directed(&g)) return 9;
  igraph_is_loop(&g, &bs, igraph_ess_all(IGRAPH_EDGEORDER_ID));
  if (igraph_vector_bool_sum(&bs) == 0) return 10;
  igraph_is_multiple(&g, &bs, igraph_ess_all(IGRAPH_EDGEORDER_ID));
  if (igraph_vector_bool_sum(&bs)) return 11;
  igraph_destroy(&g);

  /* directed, loops */
  IGRAPH_CHECK(igraph_preference_game(&g, 100, 3, &tdist, /*fixed_sizes=*/ 0,
				      &pmat, 0, 1, 1));
  if (igraph_vcount(&g) != 100) return 15;
  if (igraph_ecount(&g) < 2700) return 19;
  if (!igraph_is_directed(&g)) return 12;
  igraph_is_loop(&g, &bs, igraph_ess_all(IGRAPH_EDGEORDER_ID));
  if (igraph_vector_bool_sum(&bs) == 0) return 13;
  igraph_is_multiple(&g, &bs, igraph_ess_all(IGRAPH_EDGEORDER_ID));
  if (igraph_vector_bool_sum(&bs)) return 14;
  igraph_destroy(&g);

  /* Asymmetric preference game */

  /* directed, no loops */
  igraph_matrix_resize(&pmat, 2, 2);
  MATRIX(pmat, 0, 0) = 1; MATRIX(pmat, 0, 1) = 1;
  MATRIX(pmat, 1, 0) = 1; MATRIX(pmat, 1, 1) = 1;
  IGRAPH_CHECK(igraph_asymmetric_preference_game(&g, 100, 2, 0, &pmat, 0, 0, 0));
  if (igraph_vcount(&g) != 100) return 21;
  if (igraph_ecount(&g) != 9900) return 22;
  if (!igraph_is_directed(&g)) return 23;
  igraph_is_loop(&g, &bs, igraph_ess_all(IGRAPH_EDGEORDER_ID));
  if (igraph_vector_bool_sum(&bs)) return 24;
  igraph_is_multiple(&g, &bs, igraph_ess_all(IGRAPH_EDGEORDER_ID));
  if (igraph_vector_bool_sum(&bs)) return 25;
  igraph_destroy(&g);

  /* directed, loops */
  igraph_matrix_resize(&pmat, 2, 2);
  MATRIX(pmat, 0, 0) = 1; MATRIX(pmat, 0, 1) = 1;
  MATRIX(pmat, 1, 0) = 1; MATRIX(pmat, 1, 1) = 1;
  IGRAPH_CHECK(igraph_asymmetric_preference_game(&g, 100, 2, 0, &pmat, 0, 0, 1));
  if (igraph_vcount(&g) != 100) return 26;
  if (igraph_ecount(&g) != 10000) return 27;
  if (!igraph_is_directed(&g)) return 28;
  igraph_is_loop(&g, &bs, igraph_ess_all(IGRAPH_EDGEORDER_ID));
  if (igraph_vector_bool_sum(&bs) != 100) return 29;
  igraph_is_multiple(&g, &bs, igraph_ess_all(IGRAPH_EDGEORDER_ID));
  if (igraph_vector_bool_sum(&bs)) return 30;
  igraph_destroy(&g);

  igraph_vector_destroy(&tdist);
  igraph_matrix_destroy(&pmat);
  igraph_vector_bool_destroy(&bs);

  assert(IGRAPH_FINALLY_STACK_EMPTY);

  return 0;
}


2.16. igraph_asymmetric_preference_game — Generates a graph with asymmetric vertex types and connection preferences

int igraph_asymmetric_preference_game(igraph_t *graph, igraph_integer_t nodes,
				      igraph_integer_t types,
				      igraph_matrix_t *type_dist_matrix,
				      igraph_matrix_t *pref_matrix,
				      igraph_vector_t *node_type_in_vec,
				      igraph_vector_t *node_type_out_vec,
				      igraph_bool_t loops);

This is the asymmetric variant of igraph_preference_game() . A given number of vertices are generated. Every vertex is assigned to an "incoming" and an "outgoing" vertex type according to the given joint type probabilities. Finally, every vertex pair is evaluated and a directed edge is created between them with a probability depending on the "outgoing" type of the source vertex and the "incoming" type of the target vertex.

Arguments: 

graph:

Pointer to an uninitialized graph.

nodes:

The number of vertices in the graph.

types:

The number of vertex types.

type_dist_matrix:

Matrix giving the joint distribution of vertex types. If null, incoming and outgoing vertex types are independent and uniformly distributed.

pref_matrix:

Matrix giving the connection probabilities for different vertex types.

node_type_in_vec:

A vector where the individual generated "incoming" vertex types will be stored. If NULL, the vertex types won't be saved.

node_type_out_vec:

A vector where the individual generated "outgoing" vertex types will be stored. If NULL, the vertex types won't be saved.

loops:

Logical, whether loop edges are allowed.

Returns: 

Error code.

Added in version 0.3.

Time complexity: O(|V|+|E|), the number of vertices plus the number of edges in the graph.

See also: 

2.17. igraph_recent_degree_game — Stochastic graph generator based on the number of incident edges a node has gained recently

int igraph_recent_degree_game(igraph_t *graph, igraph_integer_t n,
			      igraph_real_t power,
			      igraph_integer_t window,
			      igraph_integer_t m,  
			      const igraph_vector_t *outseq,
			      igraph_bool_t outpref,
			      igraph_real_t zero_appeal,
			      igraph_bool_t directed);

Arguments: 

graph:

Pointer to an uninitialized graph object.

n:

The number of vertices in the graph, this is the same as the number of time steps.

power:

The exponent, the probability that a node gains a new edge is proportional to the number of edges it has gained recently (in the last window time steps) to power.

window:

Integer constant, the size of the time window to use to count the number of recent edges.

m:

Integer constant, the number of edges to add per time step if the outseq parameter is a null pointer or a zero-length vector.

outseq:

The number of edges to add in each time step. This argument is ignored if it is a null pointer or a zero length vector, is this case the constant m parameter is used.

outpref:

Logical constant, if true the edges originated by a vertex also count as recent incident edges. It is false in most cases.

zero_appeal:

Constant giving the attractiveness of the vertices which haven't gained any edge recently.

directed:

Logical constant, whether to generate a directed graph.

Returns: 

Error code.

Time complexity: O(|V|*log(|V|)+|E|), |V| is the number of vertices, |E| is the number of edges in the graph.

2.18. igraph_barabasi_aging_game — Preferential attachment with aging of vertices

int igraph_barabasi_aging_game(igraph_t *graph, 
			       igraph_integer_t nodes,
			       igraph_integer_t m,
			       const igraph_vector_t *outseq,
			       igraph_bool_t outpref,
			       igraph_real_t pa_exp,
			       igraph_real_t aging_exp,
			       igraph_integer_t aging_bin,
			       igraph_real_t zero_deg_appeal,
			       igraph_real_t zero_age_appeal,
			       igraph_real_t deg_coef,
			       igraph_real_t age_coef,
			       igraph_bool_t directed);

In this game, the probability that a node gains a new edge is given by its (in-)degree (k) and age (l). This probability has a degree dependent component multiplied by an age dependent component. The degree dependent part is: deg_coef times k to the power of pa_exp plus zero_deg_appeal; and the age dependent part is age_coef times l to the power of aging_exp plus zero_age_appeal.

The age is based on the number of vertices in the network and the aging_bin argument: vertices grew one unit older after each aging_bin vertices added to the network.

Arguments: 

graph:

Pointer to an uninitialized graph object.

nodes:

The number of vertices in the graph.

m:

The number of edges to add in each time step. If the outseq argument is not a null vector and not a zero-length vector.

outseq:

The number of edges to add in each time step. If it is a null pointer or a zero-length vector then it is ignored and the m argument is used instead.

outpref:

Logical constant, whether the edges initiated by a vertex contribute to the probability to gain a new edge.

pa_exp:

The exponent of the preferential attachment, a small positive number usually, the value 1 yields the classic linear preferential attachment.

aging_exp:

The exponent of the aging, this is a negative number usually.

aging_bin:

Integer constant, the number of vertices to add before vertices in the network grew one unit older.

zero_deg_appeal:

The degree dependent part of the attractiveness of the zero degree vertices.

zero_age_appeal:

The age dependent part of the attractiveness of the vertices of age zero. This parameter is usually zero.

deg_coef:

The coefficient for the degree.

age_coef:

The coefficient for the age.

directed:

Logical constant, whether to generate a directed graph.

Returns: 

Error code.

Time complexity: O((|V|+|V|/aging_bin)*log(|V|)+|E|). |V| is the number of vertices, |E| the number of edges.

2.19. igraph_recent_degree_aging_game — Preferential attachment based on the number of edges gained recently, with aging of vertices

int igraph_recent_degree_aging_game(igraph_t *graph,
				    igraph_integer_t nodes,
				    igraph_integer_t m, 
				    const igraph_vector_t *outseq,
				    igraph_bool_t outpref,
				    igraph_real_t pa_exp,
				    igraph_real_t aging_exp,
				    igraph_integer_t aging_bin,
				    igraph_integer_t time_window,
				    igraph_real_t zero_appeal,
				    igraph_bool_t directed);

This game is very similar to igraph_barabasi_aging_game(), except that instead of the total number of incident edges the number of edges gained in the last time_window time steps are counted.

The degree dependent part of the attractiveness is given by k to the power of pa_exp plus zero_appeal; the age dependent part is l to the power to aging_exp. k is the number of edges gained in the last time_window time steps, l is the age of the vertex.

Arguments: 

graph:

Pointer to an uninitialized graph object.

nodes:

The number of vertices in the graph.

m:

The number of edges to add in each time step. If the outseq argument is not a null vector or a zero-length vector then it is ignored.

outseq:

Vector giving the number of edges to add in each time step. If it is a null pointer or a zero-length vector then it is ignored and the m argument is used.

outpref:

Logical constant, if true the edges initiated by a vertex are also counted. Normally it is false.

pa_exp:

The exponent for the preferential attachment.

aging_exp:

The exponent for the aging, normally it is negative: old vertices gain edges with less probability.

aging_bin:

Integer constant, gives the scale of the aging. The age of the vertices is incremented by one after every aging_bin vertex added.

time_window:

The time window to use to count the number of incident edges for the vertices.

zero_appeal:

The degree dependent part of the attractiveness for zero degree vertices.

directed:

Logical constant, whether to create a directed graph.

Returns: 

Error code.

Time complexity: O((|V|+|V|/aging_bin)*log(|V|)+|E|). |V| is the number of vertices, |E| the number of edges.

2.20. igraph_cited_type_game — Simulate a citation based on vertex types.

int igraph_cited_type_game(igraph_t *graph, igraph_integer_t nodes,
			   const igraph_vector_t *types,
			   const igraph_vector_t *pref,
			   igraph_integer_t edges_per_step,
			   igraph_bool_t directed);

Function to create a network based on some vertex categories. This function creates a citation network, in each step a single vertex and edges_per_step citating edges are added, nodes with different categories (may) have different probabilities to get cited, as given by the pref vector.

Note that this function might generate networks with multiple edges if edges_per_step is greater than one. You might want to call igraph_simplify() on the result to remove multiple edges.

Arguments: 

graph:

Pointer to an uninitialized graph object.

nodes:

The number of vertices in the network.

types:

Numeric vector giving the categories of the vertices, so it should contain nodes non-negative integer numbers. Types are numbered from zero.

pref:

The attractivity of the different vertex categories in a vector. Its length should be the maximum element in types plus one (types are numbered from zero).

edges_per_step:

Integer constant, the number of edges to add in each time step.

directed:

Logical constant, whether to create a directed network.

Returns: 

Error code.

See also: 

igraph_citing_cited_type_game() for a bit more general game.

Time complexity: O((|V|+|E|)log|V|), |V| and |E| are number of vertices and edges, respectively.

2.21. igraph_citing_cited_type_game — Simulate a citation network based on vertex types.

int igraph_citing_cited_type_game(igraph_t *graph, igraph_integer_t nodes,
				  const igraph_vector_t *types,
				  const igraph_matrix_t *pref,
				  igraph_integer_t edges_per_step,
				  igraph_bool_t directed);

This game is similar to igraph_cited_type_game() but here the category of the citing vertex is also considered.

An evolving citation network is modeled here, a single vertex and its edges_per_step citation are added in each time step. The odds the a given vertex is cited by the new vertex depends on the category of both the citing and the cited vertex and is given in the pref matrix. The categories of the citing vertex correspond to the rows, the categories of the cited vertex to the columns of this matrix. Ie. the element in row i and column j gives the probability that a j vertex is cited, if the category of the citing vertex is i.

Note that this function might generate networks with multiple edges if edges_per_step is greater than one. You might want to call igraph_simplify() on the result to remove multiple edges.

Arguments: 

graph:

Pointer to an uninitialized graph object.

nodes:

The number of vertices in the network.

types:

A numeric matrix of length nodes, containing the categories of the vertices. The categories are numbered from zero.

pref:

The preference matrix, a square matrix is required, both the number of rows and columns should be the maximum element in types plus one (types are numbered from zero).

directed:

Logical constant, whether to create a directed network.

Returns: 

Error code.

Time complexity: O((|V|+|E|)log|V|), |V| and |E| are number of vertices and edges, respectively.

2.22. igraph_sbm_game — Sample from a stochastic block model

int igraph_sbm_game(igraph_t *graph, igraph_integer_t n, 
		    const igraph_matrix_t *pref_matrix,
		    const igraph_vector_int_t *block_sizes,
		    igraph_bool_t directed, igraph_bool_t loops);

This function samples graphs from a stochastic block model by (doing the equivalent of) Bernoulli trials for each potential edge with the probabilities given by the Bernoulli rate matrix, pref_matrix. See Faust, K., & Wasserman, S. (1992a). Blockmodels: Interpretation and evaluation. Social Networks, 14, 5-–61.

The order of the vertex ids in the generated graph corresponds to the block_sizes argument.

Arguments: 

graph:

The output graph.

n:

Number of vertices.

pref_matrix:

The matrix giving the Bernoulli rates. This is a KxK matrix, where K is the number of groups. The probability of creating an edge between vertices from groups i and j is given by element (i,j).

block_sizes:

An integer vector giving the number of vertices in each group.

directed:

Boolean, whether to create a directed graph. If this argument is false, then pref_matrix must be symmetric.

loops:

Boolean, whether to create self-loops.

Returns: 

Error code.

Time complexity: O(|V|+|E|+K^2), where |V| is the number of vertices, |E| is the number of edges, and K is the number of groups.

See also: 

igraph_erdos_renyi_game() for a simple Bernoulli graph.