C/igraph 0.10.13

Announcements
1

C/igraph 0.10.13 is released now, with several new additions, bug fixes and performance improvements. As usual, the source can be obtained from the GitHub releases page.

A summary of changes is below.

Added

  • igraph_bitset_fill() sets all elements of a bitset to the same value (experimental function).
  • igraph_bitset_null() clears all elements of a bitset (experimental function).
  • igraph_bitset_is_all_zero(), igraph_bitset_is_all_one(), igraph_bitset_is_any_zero(), igraph_bitset_is_any_one() check if any/all elements of a bitset are zeros/ones (experimental functions).
  • igraph_chung_lu_game() implements the classic Chung-Lu model, as well as a number of its variants (experimental function).
  • igraph_mean_degree() computes the average of vertex degrees (experimental function).
  • igraph_count_loops() counts self-loops in the graph (experimental function).
  • igraph_is_clique() checks if all pairs within a set of vertices are connected (experimental function).
  • igraph_is_independent_vertex_set() checks if no pairs within a set of vertices are connected (experimental function).
  • igraph_hypercube() creates a hypercube graph (experimental function).
  • igraph_vector_intersection_size_sorted() counts elements common to two sorted vectors (experimental function).
  • igraph_stack_capacity() returns the allocated capacity of a stack.
  • igraph_vector_is_all_finite() checks if all elements in a vector are finite (i.e. neither NaN nor Inf).

Fixed

  • Fixed a bug that incorrectly cached that a graph has no multiple edges when igraph_init_adjlist() was called with IGRAPH_NO_LOOPS and IGRAPH_NO_MULTIPLE and all the multi-edges were loop edges.
  • igraph_is_forest() would fail to set the result variable when testing for a directed forest, and it was already cached that the graph was not an undirected forest.
  • igraph_hub_and_authority_scores() no longer clips negative results to zeros when negative weights are present.
  • Fixed an assertion failure in igraph_realize_bipartite_degree_sequence() with some non-graphical degree sequences when requesting simple bipartite graphs.
  • igraph_static_fitness_game() checks the input more carefully, and avoids an infinite loop in rare edge cases, such as when (almost) all fitness scores are zero.
  • igraph_arpack_rnsolve() used the incorrect error message text for some errors. This is now corrected.
  • Corrected the detection of some MSVC-specific bitset intrinsics during configuration.
  • Corrected a bug in the fallback implementation of igraph_bitset_countl_zero() when IGRAPH_INTEGER_SIZE was set to 32. This fallback implementation was not used with GCC, Clang, or MSVC.

Changed

  • igraph_is_graphical() and igraph_is_bigraphical() are now linear-time in all cases, and generally several times faster than before (thanks to @gendelpiekel, contributed in #2605).
  • igraph_erdos_renyi_game_gnp() can now generate graphs with more than a hundred million vertices.
  • igraph_hub_and_authority_scores() now warns when negative edge weights are present.
  • igraph_layout_lgl() now uses a BFS tree rooted in the vertex specified as proot to guide the layout. Previously it used an unspecified (arbitrary) spanning tree.
  • Updated the internal heuristics used by igraph’s ARPACK interface, igraph_arpack_rssolve() and igraph_arpack_rnsolve(), to improve the robustness of calculations.
  • Updated the initial vector construction in igraph_hub_and_authority_scores(), igraph_eigenvector_centrality() and igraph_(personalized_)pagerank() with IGRAPH_PAGERANK_ALGO_ARPACK. This improves the robustness and convergence of calculations.

Other

  • Documentation improvements.
  • Reduced the memory usage of several functions by using bitsets instead of Boolean vectors.
  • igraph_vector_intersect_sorted() has better performance when the input vector sizes are similar.
1 Like