igraph 0.5.1 Release Notes

igraph 0.5.1 is a bugfix release, but it actually contains many important new things as well. Here is a brief summary about each of them. See below for the complete list of changes.

The DrL layout generator was added

This is a sophisticated and efficient layout generator written by Shawn Martin and colleagues. See more in the manual.

Uniform sampling of random graphs with given degree sequence

A nice random graph generator that conditions on the degree of vertices was added. It can generate undirected connected graphs. The algorithm and the implementation was done by Fabien Viger and Matthieu Latapy. See more in the manual.

Conversions

igraph includes some functions to convert graphs to and from graphNEL objects as defined in the graph package (igraph.to.graphNEL, igraph.from.graphNEL) and sparse matrices using the Matrix package (get.adjacency, graph.adjacency, see the sparse argument).

New graph constructors

A new function was added to create graphs from adjacency lists (graph.adjlist), and graph.data.frame has an argument call vertices, this allows easy construction of graphs with vertex and edge meta data.

Weighted shortest path algorithms

Both the Dijkstra and the Belmann-Ford algorithms were added. See more in the documentation.

Function to test edge reciprocity

Mutuality can be tested for each edge now. See more in the documentation.

Vertex shapes

The R interface now supports different vertex shapes when plotting. See more in the R documentation.

New in the R interface

• A new layout generator called DrL.
• Uniform sampling of random connected undirected graphs with a given degree sequence.
• Edge labels are plotted at 1/3 of the edge, this is better if the graph has mutual edges.
• Initial and experimental vertex shape support in plot.
• New function, graph.adjlist creates igraph graphs from adjacency lists.
• Conversion to/from graphNEL graphs, from the graph R package.
• Fastgreedy community detection can utilize edge weights now, this was missing from the R interface.
• The arrow.width graphical parameter was added.
• graph.data.frame has a new argument vertices.
• graph.adjacency and get.adjacency support sparse matrices, the Matrix package is required to use this functionality.
• graph.adjacency adds column/row names as name attribute.
• Weighted shortest paths using Dijkstra’s or the Belmann-Ford algorithm.
• Shortest path functions return Inf for unreachable vertices.
• New function is.mutual to find mutual edges in a directed graph.
• Added inverse log-weighted similarity measure (a.k.a. Adamic/Adar similarity).
• preference.game and asymmetric.preference.game were rewritten, they are O(|V|+|E|) now, instead of O(|V|^2).
• Edge weight support in function get.shortest.paths, it uses Dijkstra’s algorithm.

Bugs corrected in the R interface

• A bug was corrected in write.pajek.bgraph.
• Several bugs were corrected in graph.adjacency.
• Pajek reader bug corrected, used to segfault if *Vertices was missing.
• Directedness is handled correctly when writing GML files. (But note that ‘correct’ conflicts the standard here.)
• Corrected a bug when calculating weighted, directed PageRank on an undirected graph. (Which does not make sense anyway.)
• Several bugs were fixed in the Reingold-Tilford layout to avoid edge crossings.
• A bug was fixed in the GraphML reader, when the value of a graph attribute was not specified.
• Fixed a bug in the graph isomorphism routine for small (3-4 vertices) graphs.
• Corrected the random sampling implementation (igraph_random_sample), now it always generates unique numbers. This affects the G(n,m) Erdos-Renyi generator, it always generates simple graphs now.
• The basic igraph constructor (igraph_empty_attrs, all functions are expected to call this internally) now checks whether the number of vertices is finite.
• The LGL, NCOL and Pajek graph readers handle errors properly now.
• The non-symmetric ARPACK solver returns results in a consistent form now.
• The fast greedy community detection routine now checks that the graph is simple.
• The LGL and NCOL parsers were corrected to work with all kinds of end-of-line encodings.
• Hub & authority score calculations initialize ARPACK parameters now.
• Fixed a bug in the Walktrap community detection routine, when applied to unconnected graphs.
• Several small memory leaks were removed, and a big one from the Spinglass community structure detection function