igraph Reference Manual

For using the igraph C library

Chapter 1. Introduction

This is another library for creating and manipulating graphs. You can look at it two ways: first, igraph contains the implementation of quite a lot 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.

Second, igraph provides a platform for the developing and/or implementing graph algorithms. It has a quite efficient data structure for representing graphs and a number of other data structures like flexible vectors, stacks, heaps, queues, adjacency lists to accomplish this. In fact these data structures evolved along 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. Two such embeddings (or interfaces if you look at them the other way) are currently being developed by us: igraph as a GNU R package and igraph as a Python extension module. A third embedding, being developed by another developer is a Ruby extension. Other are likely to come. The high level languages as R or Python make it possible to do use graph routines with mush 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 and much flexibility. This manual however covers only the C library. If you want to use Python or GNU R, please see the documentation written specifically for these interfaces and come back here only if you're 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 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., 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.