igraph Reference Manual

For using the igraph C library

Chapter 3. Tutorial

1. Lesson 1. Compiling programs using igraph.

The following short example program demonstrates the basic usage of the igraph library.

#include <igraph.h>

int main(void)
{
     igraph_integer_t diameter;
     igraph_t graph;
     igraph_rng_seed(igraph_rng_default(), 42);
     igraph_erdos_renyi_game(&graph, IGRAPH_ERDOS_RENYI_GNP, 1000, 5.0/1000,
                             IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);
     igraph_diameter(&graph, &diameter, 0, 0, 0, IGRAPH_UNDIRECTED, 1);
     printf("Diameter of a random graph with average degree 5: %d\n",
             (int) diameter);
     igraph_destroy(&graph);
     return 0;
}

This example illustrates a couple of points. First, programs using the igraph library should include the igraph.h header file. Second, igraph uses the igraph_real_t type for real numbers instead of double. Third, igraph graph objects are represented by the igraph_t data type. Fourth, the igraph_erdos_renyi_game() creates a graph and igraph_destroy() destroys it, ie. deallocates the memory associated to it.

For compiling this program you need a C compiler, if this is called gcc and the previous code is saved in file igraph_test.c, you will need a command like this:

gcc igraph_test.c -I/usr/local/igraph -L/usr/local/lib -ligraph -o igraph_test

The exact form depends on where igraph was installed on your system. The directory after the -I switch is the one containing the igraph.h file, while the one following -L should contain the library file itself, usually a file called libigraph.so, libigraph.a or igraph.dll. It your system has the pkg-config utility you are likely to get the neccessary compile options by issuing the command

pkg-config --libs --cflags igraph

The executable can be run by simply typing its name like this:

./igraph_test

on most systems. If you use dynamic linking and the igraph libraries are not at a standard place, you may need to set the LD_LIBRARY_PATH variable, the syntax depends on the shell use are using. In bash it goes like this:

export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/home/user/libs/igraph
./igraph_test

Here we assumed that the igraph library is installed in /home/user/libs/igraph. Alternatively, you can use the LD_PRELOAD variable to preload the igraph library before invoking your program:

LD_PRELOAD=/home/user/libs/igraph/libigraph.so ./igraph_test

Please note that LD_PRELOAD and LD_LIBRARY_PATH are usually available only on Un*x-like systems. On Windows using Cygwin it is usually enough to set the PATH enviroment variable to include the folder in which the igraph library is installed, look for the cygigraph-0.dll or similar file.

2. Lesson 2. Creating your first graphs.

The functions generating graph objects are called graph generators. Stochastic (=randomized) graph generators are called games.

igraph can handle directed and undirected graphs. Most graph generators are able to create both types of graphs and most other functions are usually also capable of handling both. Eg. igraph_shortest_paths() which (surprisingly) calculates shortest paths from a vertex to another vertices can calculate directed or undirected paths.

igraph has sophisticated ways for creating graphs. The simplest graphs are deterministic regular structures like star graphs (igraph_star()), ring graphs (igraph_ring()), lattices (igraph_lattice()) or trees (igraph_tree()).

The following example creates an undirected regular circular lattice, adds some random edges to it and calculates the average length of shortest paths between all pairs of vertices in the graph before and after adding the random edges. (The message is that some random edges can reduce path lengths a lot.)

#include <igraph.h>

int main(void) {
  igraph_real_t avg_path;
  igraph_t graph;
  igraph_vector_t dimvector;
  igraph_vector_t edges;
  int i;
  
  igraph_vector_init(&dimvector, 2);
  VECTOR(dimvector)[0]=30;
  VECTOR(dimvector)[1]=30;
  igraph_lattice(&graph, &dimvector, 0, IGRAPH_UNDIRECTED, 0, 1);

  igraph_rng_seed(igraph_rng_default(), 42);
  igraph_vector_init(&edges, 20);
  for (i=0; i<igraph_vector_size(&edges); i++) {
    VECTOR(edges)[i] = rand() % (int)igraph_vcount(&graph);
  }

  igraph_average_path_length(&graph, &avg_path, IGRAPH_UNDIRECTED, 1);
  printf("Average path length (lattice):            %f\n", (double) avg_path);

  igraph_add_edges(&graph, &edges, 0);
  igraph_average_path_length(&graph, &avg_path, IGRAPH_UNDIRECTED, 1);
  printf("Average path length (randomized lattice): %f\n", (double) avg_path);
  
  igraph_vector_destroy(&dimvector);
  igraph_vector_destroy(&edges);
  igraph_destroy(&graph);

  return 0;
}

This example illustrates some new points. igraph uses igraph_vector_t instead of plain C arrays. igraph_vector_t is superior to regular arrays in almost every sense. Vectors are created by the igraph_vector_init() function and like graphs they should be destroyed if not needed any more by calling igraph_vector_destroy() on them. A vector can be indexed by the VECTOR() function (right now it is a macro). Vectors can be resized, eg. most igraph functions returning the result in a vector resize it to the size of the result.

igraph_lattice() takes a vector argument specifying the dimensions of the lattice, in this example we generate a 30x30 two dimensional lattice. See the documentation of igraph_lattice() in the reference manual for the other arguments.

The vertices in a graph are identified by an integer number between 0 and N-1, N is the number of vertices in the graph (this can be obtained by igraph_vcount(), as in the example).

The igraph_add_edges() function simply takes a graph and a vector of vertex ids defining the new edges. The first edge is between the first two vertex ids in the vector, the second edge is between the second two, etc. This way we add ten random edges to the lattice.

Note that in the example it is possible to add loop edges, edges pointing to the same vertex and multiple edges, more than one edge between the same pair of vertices. igraph_t can of course represent loops and multiple edges, although some routines expect simple graphs, ie. graphs without loop and multiple edges, because for example some structural properties are ill-defined for non-simple graphs. Loop edges can be removed by calling igraph_simplify().

3. Lesson 3. Calculating various properties of graphs.

In our next example we will calculate various centrality measures in a friendship graph. The friendship graph is from the famous Zachary karate club study. (Web search on 'Zachary karate' if you want to know more about this.) Centrality measures quantify how central is the position of individual vertices in the graph.

#include <igraph.h>

int main(void) {
     igraph_t graph;
     igraph_vector_t v;
     igraph_vector_t result;
     igraph_real_t edges[] = { 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8,
                               0,10, 0,11, 0,12, 0,13, 0,17, 0,19, 0,21, 0,31,
                               1, 2, 1, 3, 1, 7, 1,13, 1,17, 1,19, 1,21, 1,30,
                               2, 3, 2, 7, 2,27, 2,28, 2,32, 2, 9, 2, 8, 2,13,
                               3, 7, 3,12, 3,13, 4, 6, 4,10, 5, 6, 5,10, 5,16,
                               6,16, 8,30, 8,32, 8,33, 9,33,13,33,14,32,14,33,
                              15,32,15,33,18,32,18,33,19,33,20,32,20,33,
                              22,32,22,33,23,25,23,27,23,32,23,33,23,29,
                              24,25,24,27,24,31,25,31,26,29,26,33,27,33,
                              28,31,28,33,29,32,29,33,30,32,30,33,31,32,31,33,
                              32,33
     };

     igraph_vector_view(&v, edges, sizeof(edges)/sizeof(double));
     igraph_create(&graph, &v, 0, IGRAPH_UNDIRECTED);

     igraph_vector_init(&result, 0);

     igraph_degree(&graph, &result, igraph_vss_all(), IGRAPH_ALL,
                   IGRAPH_LOOPS);
     printf("Maximum degree is      %10i, vertex %2i.\n",
            (int)igraph_vector_max(&result), (int)igraph_vector_which_max(&result));

     igraph_closeness(&graph, &result, igraph_vss_all(), IGRAPH_ALL,
                      /*weights=*/ 0);
     printf("Maximum closeness is   %10f, vertex %2i.\n",
             (double)igraph_vector_max(&result), (int)igraph_vector_which_max(&result));

     igraph_betweenness(&graph, &result, igraph_vss_all(),
                        IGRAPH_UNDIRECTED, /*weights=*/ 0, /*nobigint=*/ 1);
     printf("Maximum betweenness is %10f, vertex %2i.\n",
             (double)igraph_vector_max(&result), (int)igraph_vector_which_max(&result));

     igraph_vector_destroy(&result);
     igraph_destroy(&graph);

     return 0;
}

This example reflects some new features. First of all, it shows a way to define a graph simply as defining a C array with its edges. Function igraph_vector_view() creates a view of a C array. It does not copy any data, this also means that you should not call igraph_vector_destroy() on a vector created this way. This vector is then used to create the undirected graph.

Then the degree, closeness and betweenness centrality of the vertices is calculated and the highest values are printed. Note that the vector (result) which returns the result from these functions has to be initialized first, and also that the functions resize it to be able to hold the result.

The igraph_vss_all() argument tells the functions to calculate the property for every vertex in the graph, it is shorthand for a vertex selector (igraph_vs_t). Vertex selectors help performing operations on a subset of vertices, you can read more about them in one of the following chapters.