Release 0.9.0 of igraph’s C core has arrived, almost exactly one year after version 0.8.0. This release brings several new features and improvements, and also a complete switch from the old autotools
based build system to a new one based on CMake. This results in faster build times and the opportunity to use alternative build tools instead of make
; in particular, igraph now supports ninja
and can also make use of a locally installed ccache
compiler cache for even faster builds. Installation instructions are on the website and included in the documentation, which is now bundled with the release.
We gratefully acknowledge support from the Chan Zuckerberg Initiative for the development of igraph. In addition, we would like to thank everyone who reported issues, contributed features or fixes, or edited the documentation. igraph is an opensource project run by volunteers. As always, your contributions are very welcome!
Most people use igraph through its highlevel interfaces for R, Python or Mathematica. A new release of the Python interface, based on 0.9.0, is expected to be released in a few days. The Mathematica interfaces already includes some of the improvements, and along with the R interface it will continue to integrate more. The sources can be obtained from the GitHub releases page.
The summary of changes is below.
Added
 Eulerian paths/cycles (PR #1346):

igraph_is_eulerian()
finds out whether an Eulerian path/cycle exists. 
igraph_eulerian_path()
returns an Eulerian path. 
igraph_eulerian_cycle()
returns an Eulerian cycle.

 Efficiency (PR #1344):

igraph_global_efficiency()
computes the global efficiency of a network. 
igraph_local_efficiency()
computes the local efficiency around each vertex. 
igraph_average_local_efficiency()
computes the mean local efficiency.

 Degree sequences (PR #1445):

igraph_is_graphical()
checks if a degree sequence has a realization as a simple or multigraph, with or without selfloops. 
igraph_is_bigraphical()
checks if two degree sequences have a realization as a bipartite graph. 
igraph_realize_degree_sequence()
now supports constructing nonsimple graphs as well.

 There is a new fatal error handling mechanism (PR #1548):

igraph_set_fatal_handler()
sets the fatal error handler. It is the only function in this functionality group that is relevant to end users.  The macro
IGRAPH_FATAL()
and the functionsigraph_fatal()
andigraph_fatalf()
raise a fatal error. These are for internal use. 
IGRAPH_ASSERT()
is a replacement for theassert()
macro. It is for internal use. 
igraph_fatal_handler_abort()
is the default fatal error handler.

 The new
IGRAPH_WARNINGF
,IGRAPH_ERRORF
andIGRAPH_FATALF
macros provide warning/error reporting withprintf
like syntax. (PR #1627, thanks to Daniel Noom!) 
igraph_average_path_length_dijkstra()
computes the mean shortest path length in weighted graphs (PR #1344). 
igraph_get_shortest_paths_bellman_ford()
computes the shortest paths (including the vertex and edge IDs along the paths) using the BellmanFord algorithm (PR #1642, thanks to Guy Rozenberg). This makes it possible to calculate the shortest paths on graphs with negative edge weights, which was not possible before with Dijkstra’s algorithm. 
igraph_get_shortest_path_bellman_ford()
is a wrapper forigraph_get_shortest_paths_bellman_ford()
for the single path case. 
igraph_is_same_graph()
cheks that two labelled graphs are the same (PR #1604).  Harmonic centrality (PR #1583):

igraph_harmonic_centrality()
computes the harmonic centrality of vertices. 
igraph_harmonic_centrality_cutoff()
computes the rangelimited harmonic centrality.

 Rangelimited centralities, currently equivalent to the old functions with names ending in
_estimate
(PR #1583):
igraph_closeness_cutoff()
. 
igraph_betweenness_cutoff()
. 
igraph_edge_betweenness_cutoff()
.


igraph_vector_is_any_nan()
checks if any elements of anigraph_vector_t
is NaN. 
igraph_inclist_size()
returns the number of vertices in an incidence list. 
igraph_lazy_adjlist_size()
returns the number of vertices in a lazy adjacency list. 
igraph_lazy_inclist_size()
returns the number of vertices in a lazy incidence list. 
igraph_bfs_simple()
now provides a simpler interface to the breadthfirst search functionality.
Changed
 igraph now uses a CMakebased build sysyem.
 GMP support can no longer be disabled. When GMP is not present on the system, igraph will use an embedded copy of MiniGMP (PR #1549).
 Bliss has been updated to version 0.75. Bliss functions are now interruptible. Thanks to Tommi Junttila for making this possible!
 Adjacency and incidence lists:

igraph_adjlist_init()
andigraph_lazy_adjlist_init()
now require the caller to specify what to do with loop and multiple edges. 
igraph_inclist_init()
andigraph_lazy_inclist_init()
now require the caller to specify what to do with loop edges.  Adjacency and incidence lists now use
igraph_vector_int_t
consistently.

 Community detection:

igraph_community_multilevel()
: added resolution parameter. 
igraph_community_fluid_communities()
: graphs with no vertices or with one vertex only are now supported; they return a trivial partition.

 Modularity:

igraph_modularity()
andigraph_modularity_matrix()
: added resolution parameter. 
igraph_modularity()
andigraph_modularity_matrix()
now support the directed version of modularity. 
igraph_modularity()
returns NaN for graphs with no edges to indicate that the modularity is not welldefined for such graphs.

 Centralities:

cutoff=0
is no longer interpreted as infinity (i.e. no cutoff) inbetweenness
,edge_betweenness
andcloseness
. If no cutoff is desired, use a negative value such ascutoff=1
.  The
nobigint
argument has been removed fromigraph_betweenness()
,igraph_betweenness_estimate()
andigraph_centralization_betweenness()
, as it is not longer needed. The current implementation is more accurate than the old one using big integers. 
igraph_closeness()
now considers only reachable vertices during the calculation (i.e. the closeness is calculated percomponent in the undirected case) (PR #1630). 
igraph_closeness()
gained two additional output parameters,reachable_count
andall_reachable
, returning the number of reached vertices from each vertex, as well as whether all vertices were reachable. This allows for computing various generalizations of closeness for disconnected graphs (PR #1630). 
igraph_pagerank()
,igraph_personalized_pagerank()
andigraph_personalized_pagerank_vs()
no longer support theIGRAPH_PAGERANK_ALGO_POWER
method. Theiroptions
argument now has typeigraph_arpack_options_t *
instead ofvoid *
.

 Shortest paths (PR #1344):

igraph_average_path_length()
now returns the number of disconnected vertex pairs in the newunconn_pairs
output argument. 
igraph_diameter()
now return the result as anigraph_real_t
instead of anigraph_integer_t
. 
igraph_average_path_length()
andigraph_diameter()
now returnIGRAPH_INFINITY
whenunconn=FALSE
and the graph is not connected. Previously they returned the number of vertices.

 Traitbased random graph generators:

igraph_callaway_traits_game()
andigraph_establishment_game()
now have an optional output argument to retrieve the generated vertex types. 
igraph_callaway_traits_game()
andigraph_establishment_game()
now allow omitting the type distribution vector, in which case they assume a uniform distribution. 
igraph_asymmetric_preference_game()
now accept a different number of intypes and outtypes.


igraph_subisomorphic_lad()
now supports graphs with selfloops. 
igraph_is_chordal()
andigraph_maximum_cardinality_search()
now support nonsimple graphs and directed graphs. 
igraph_realize_degree_sequence()
has an additional argument controlling whether multiedges or selfloops are allowed. 
igraph_is_connected()
now returns false for the null graph; see igraph_diameter() mishandles null graph · Issue #1538 · igraph/igraph · GitHub for the reasoning behind this decision. 
igraph_lapack_ddot()
is renamed toigraph_blas_ddot()
. 
igraph_to_directed()
: added RANDOM and ACYCLIC modes (PR #1511). 
igraph_topological_sorting()
now issues an error if the input graph is not acyclic. Previously it issued a warning. 
igraph_vector_(which_)(minmaxminmax)()
now handles NaN elements. 
igraph_i_set_attribute_table()
is renamed toigraph_set_attribute_table()
. 
igraph_i_sparsemat_view()
is renamed toigraph_sparsemat_view()
.
Deprecated

igraph_is_degree_sequence()
andigraph_is_graphical_degree_sequence()
are deprecated in favour of the newly addedigraph_is_graphical()
. 
igraph_closeness_estimate()
is deprecated in favour of the newly addedigraph_closeness_cutoff()
. 
igraph_betweenness_estimate()
andigraph_edge_betweenness_estimate()
are deprecated in favour of the newly addedigraph_betweenness_cutoff()
andigraph_edge_betweenness_cutoff()
. 
igraph_adjlist_remove_duplicate()
andigraph_inclist_remove_duplicate()
are now deprecated in favour of the new constructor arguments inigraph_adjlist_init()
andigraph_inclist_init()
.
Removed
 The following functions, all deprecated in igraph 0.6, have been removed (PR #1562):

igraph_adjedgelist_init()
,igraph_adjedgelist_destroy()
,igraph_adjedgelist_get()
,igraph_adjedgelist_print()
,igraph_adjedgelist_remove_duplicate()
. 
igraph_lazy_adjedgelist_init()
,igraph_lazy_adjedgelist_destroy()
,igraph_lazy_adjedgelist_get()
,igraph_lazy_adjedgelist_get_real()
. 
igraph_adjacent()
. 
igraph_es_adj()
. 
igraph_subgraph()
.


igraph_pagerank_old()
, deprecated in 0.7, has been removed. 
igraph_vector_bool
andigraph_matrix_bool
functions that relied on inequalitycomparingigraph_bool_t
values are removed.
Fixed
 Betweenness calculations are no longer at risk from integer overflow.
 The actual cutoff distance used in closeness calculation was one smaller than the
cutoff
parameter. This is corrected (PR #1630). 
igraph_layout_gem()
was not interruptible; now it is. 
igraph_barabasi_aging_game()
now checks its parameters more carefully. 
igraph_callaway_traits_game()
andigraph_establishment_game()
now check their parameters. 
igraph_lastcit_game()
checks its parameters more carefully, and no longer crashes with zero vertices (PR #1625). 
igraph_cited_type_game()
incorrectly rounded the attractivity vector entries to integers. 
igraph_residual_graph()
now returns the correct residual capacities; previously it wrongly returned the original capacities (PR #1598). 
igraph_psumtree_update()
now checks for negative values and NaN. 
igraph_communities_spinglass()
: fixed several memory leaks in theIGRAPH_SPINCOMM_IMP_NEG
implementation. 
igraph_incident()
now returns edges in the same order asigraph_neighbors()
. 
igraph_modularity_matrix()
returned incorrect results for weighted graphs. This is now fixed. (PR #1649, thanks to Daniel Noom!) 
igraph_lapack_dgetrf()
would crash when passingNULL
for itsipiv
argument (thanks for the fix to Daniel Noom).  Some
igraph_matrix
functions would fail to report errors on outofmemory conditions. 
igraph_maxdegree()
now returns 0 for the null graph or empty vector set. Previously, it did not handle this case. 
igraph_vector_bool_all_e()
now considers all nonzero (i.e. “true”) values to be the same.  PageRank (PR #1640):

igraph_(personalized_)pagerank(_vs)()
now check their parameters more carefully. 
igraph_personalized_pagerank()
no longer modifies itsreset
parameter. 
igraph_(personalized_)pagerank(_vs)
: theIGRAPH_PAGERANK_ALGO_ARPACK
method now handles selfloops correctly. 
igraph_personalized_pagerank(_vs)()
: the result retuned for edgeless or allzeroweight graphs with theIGRAPH_PAGERANK_ALGO_ARPACK
ignored the personalization vector. This is now corrected. 
igraph_personalized_pagerank(_vs)()
with a nonuniform personalization vector, a disconnected graph and theIGRAPH_PAGERANK_ALGO_PRPACK
method would return results that were inconsistent withIGRAPH_PAGERANK_ALGO_ARPACK
. This happened because PRPACK always used a uniform reset distribution when the random walk got stuck in a sink vertex. Now it uses the userspecified reset distribution for this case as well.

 Fixed crashes in several functions when passing a weighted graph with zero edges (due to
vector_min
being called on the zerolength weight vector).  Fixed problems in several functions when passing in a graph with zero vertices.
 Weighted betweenness, closeness, PageRank, shortest path calculations and random walk functions now check if any weights are NaN.
 Many functions now reject input arguments containing NaN values.
 Compatibility with the PGI compiler.
Other
 Documentation improvements.
 Improved error and warning messages.
 More robust error handling.
 General code cleanup to reduce the number of compiler warnings.
 igraph’s source files have been reorganized for better maintainability.
 Debugging aid: When igraph is build with AddressSanitizer, the default error handler prints a stack trace before exiting.
 igraph can now be built with an external CXSparse library.
 The references to igraph source files in error and warning messages are now always relative to igraph’s base directory.
 When igraph is built as a shared library, only public symbols are exported even on Linux and macOS.
Acknowledgments
 Thanks to Daniel Noom for significantly expanding igraph’s test coverage and exposing several issues in the process!