C/igraph 0.9.0

Announcements
1

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 open-source project run by volunteers. As always, your contributions are very welcome!

Most people use igraph through its high-level 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 self-loops.
    • igraph_is_bigraphical() checks if two degree sequences have a realization as a bipartite graph.
    • igraph_realize_degree_sequence() now supports constructing non-simple 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 functions igraph_fatal() and igraph_fatalf() raise a fatal error. These are for internal use.
    • IGRAPH_ASSERT() is a replacement for the assert() macro. It is for internal use.
    • igraph_fatal_handler_abort() is the default fatal error handler.
  • The new IGRAPH_WARNINGF, IGRAPH_ERRORF and IGRAPH_FATALF macros provide warning/error reporting with printf-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 Bellman-Ford 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 for igraph_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 range-limited harmonic centrality.
  • Range-limited 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 an igraph_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 breadth-first search functionality.

Changed

  • igraph now uses a CMake-based build sysyem.
  • GMP support can no longer be disabled. When GMP is not present on the system, igraph will use an embedded copy of Mini-GMP (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() and igraph_lazy_adjlist_init() now require the caller to specify what to do with loop and multiple edges.
    • igraph_inclist_init() and igraph_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() and igraph_modularity_matrix(): added resolution parameter.
    • igraph_modularity() and igraph_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 well-defined for such graphs.
  • Centralities:
    • cutoff=0 is no longer interpreted as infinity (i.e. no cutoff) in betweenness, edge_betweenness and closeness. If no cutoff is desired, use a negative value such as cutoff=-1.
    • The nobigint argument has been removed from igraph_betweenness(), igraph_betweenness_estimate() and igraph_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 per-component in the undirected case) (PR #1630).
    • igraph_closeness() gained two additional output parameters, reachable_count and all_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() and igraph_personalized_pagerank_vs() no longer support the IGRAPH_PAGERANK_ALGO_POWER method. Their options argument now has type igraph_arpack_options_t * instead of void *.
  • Shortest paths (PR #1344):
    • igraph_average_path_length() now returns the number of disconnected vertex pairs in the new unconn_pairs output argument.
    • igraph_diameter() now return the result as an igraph_real_t instead of an igraph_integer_t.
    • igraph_average_path_length() and igraph_diameter() now return IGRAPH_INFINITY when unconn=FALSE and the graph is not connected. Previously they returned the number of vertices.
  • Trait-based random graph generators:
    • igraph_callaway_traits_game() and igraph_establishment_game() now have an optional output argument to retrieve the generated vertex types.
    • igraph_callaway_traits_game() and igraph_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 in-types and out-types.
  • igraph_subisomorphic_lad() now supports graphs with self-loops.
  • igraph_is_chordal() and igraph_maximum_cardinality_search() now support non-simple graphs and directed graphs.
  • igraph_realize_degree_sequence() has an additional argument controlling whether multi-edges or self-loops 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 to igraph_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_)(min|max|minmax)() now handles NaN elements.
  • igraph_i_set_attribute_table() is renamed to igraph_set_attribute_table().
  • igraph_i_sparsemat_view() is renamed to igraph_sparsemat_view().

Deprecated

  • igraph_is_degree_sequence() and igraph_is_graphical_degree_sequence() are deprecated in favour of the newly added igraph_is_graphical().
  • igraph_closeness_estimate() is deprecated in favour of the newly added igraph_closeness_cutoff().
  • igraph_betweenness_estimate() and igraph_edge_betweenness_estimate() are deprecated in favour of the newly added igraph_betweenness_cutoff() and igraph_edge_betweenness_cutoff().
  • igraph_adjlist_remove_duplicate() and igraph_inclist_remove_duplicate() are now deprecated in favour of the new constructor arguments in igraph_adjlist_init() and igraph_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 and igraph_matrix_bool functions that relied on inequality-comparing igraph_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() and igraph_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 the IGRAPH_SPINCOMM_IMP_NEG implementation.
  • igraph_incident() now returns edges in the same order as igraph_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 passing NULL for its ipiv argument (thanks for the fix to Daniel Noom).
  • Some igraph_matrix functions would fail to report errors on out-of-memory 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 its reset parameter.
    • igraph_(personalized_)pagerank(_vs): the IGRAPH_PAGERANK_ALGO_ARPACK method now handles self-loops correctly.
    • igraph_personalized_pagerank(_vs)(): the result retuned for edgeless or all-zero-weight graphs with the IGRAPH_PAGERANK_ALGO_ARPACK ignored the personalization vector. This is now corrected.
    • igraph_personalized_pagerank(_vs)() with a non-uniform personalization vector, a disconnected graph and the IGRAPH_PAGERANK_ALGO_PRPACK method would return results that were inconsistent with IGRAPH_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 user-specified 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 zero-length 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 re-organized 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!
1 Like