Skip to content

igraph 0.9.0

Choose a tag to compare

View all tags
@ntamas ntamas released this 16 Feb 15:31
0.9.0
6bb4e76
This commit was signed with the committer’s verified signature.
ntamas Tamás Nepusz
GPG key ID: F290BD5B08A71E84
Verified
Learn about vigilant mode.

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 #1538 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!
Assets 3
Loading