igraph Reference Manual

For using the igraph C library

Chapter 1. Introduction

igraph is a library for creating and manipulating graphs. You can look at it in two ways: first, igraph contains the implementation of quite a lot of graph algorithms. These include classic graph algorithms like graph isomorphism, graph girth and connectivity and also the new wave graph algorithms like transitivity, graph motifs and community structure detection. Skim through the table of contents or the index of this book to get an impression of what is available.

Second, igraph provides a platform for developing and/or implementing graph algorithms. It has an efficient data structure for representing graphs, and a number of other data structures like flexible vectors, stacks, heaps, queues, adjacency lists that are useful for implementing graph algorithms. In fact these data structures evolved along with the implementation of the classic and non-classic graph algorithms which make up the major part of the igraph library. This way, they were fine-tuned and checked for correctness several times.

Our main goal with developing igraph was to create a graph library which is efficient on large, but not extremely large graphs. More precisely, it is assumed that the graph(s) fit into the physical memory of the computer. Nowadays this means graphs with several million vertices and/or edges. Our definition of efficient is that it runs fast, both in theory and (more importantly) in practice.

We believe that one of the big strengths of igraph is that it can be embedded into a higher-level language or environment. Three such embeddings (or interfaces if you look at them another way) are currently being developed by us: an R package, a Python extension module, and a Mathematica (Wolfram Language) package. Others are likely to come. High level languages such as R or Python make it possible to use graph routines with much greater comfort, without actually writing a single line of C code. They have some, usually very small, speed penalty compared to the C version, but add ease of use and much flexibility. This manual, however, covers only the C library. If you want to use Python, R or the Wolfram Language, please see the documentation written specifically for these interfaces and come back here only if you are interested in some detail which is not covered in those documents.

We still consider igraph as a child project. It has much room for development and we are sure that it will improve a lot in the near future. Any feedback we can get from the users is very important for us, as most of the time these questions and comments guide us in what to add and what to improve.

igraph is open source and distributed under the terms of the GNU GPL. We strongly believe that all the algorithms used in science, let that be graph theory or not, should have an efficient open-source implementation allowing use and modification for anyone.

1. igraph is free software

igraph library

Copyright (C) 2003-2012 Gábor 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA

2. Citing igraph

To cite igraph in publications, please use the following reference:

Gábor Csárdi, Tamás Nepusz: The igraph software package for complex network research. InterJournal Complex Systems, 1695, 2006.

The igraph C library is assigned the DOI 10.5281/zenodo.3630268 on Zenodo.