igraph 0.10.12

Added

• igraph_transitive_closure() computes the transitive closure of a graph (experimental function).
• igraph_reachability() determines which vertices are reachable from each other in a graph (experimental function).
• igraph_count_reachable() counts how many vertices are reachable from each vertex (experimental function).
• Added a bitset data structure, igraph_bitset_t, and a set of corresponding functions (experimental functionality).

Fixed

• igraph_community_label_propagation() is now interruptible.
• igraph_is_bipartite() would on rare occasions return invalid results when the cache was employed.
• igraph_weighted_adjacency() correctly passes through NaN values with IGRAPH_ADJ_MAX, and correctly recognizes symmetric adjacency matrices containing NaN values with IGRAPH_ADJ_UNDIRECTED.
• igraph_read_graph_gml() can now read GML files that use ids larger than what is representable on 32 bits, provided that igraph was configured with a 64-bit igraph_integer_t size.
• Fixed a performance issue in igraph_read_graph_graphml() with files containing a very large number of entities, such as >.
• igraph_read_graph_pajek() has improved vertex ID validation that better matches that of Pajek's own behavior.

Changed

• igraph_eigenvector_centrality() no longer issues a warning when the input is directed and weighted. When using this function, keep in mind that eigenvector centrality is well-defined only for (strongly) connected graphs, and edges with a zero weights are effectively treated as absent.

Deprecated

• igraph_transitive_closure_dag() is deprecated in favour of igraph_transitive_closure()

Other

• Documentation improvements.
• igraph_strength() and igraph_degree(loops=false) are now faster when calculating values for all vertices (contributed by @gendelpiekel in #2602)

igraph 0.10.11

Added

• igraph_is_complete() checks whether there is a connection between all pairs of vertices (experimental function, contributed by Aymeric Agon-Rambosson @aagon in #2510).
• igraph_join() creates the join of two graphs (experimental function, contributed by Quinn Buratynski @GanzuraTheConsumer in #2508).

Fixed

• Fixed a corruption of the "finally" stack in igraph_write_graph_gml() for certain invalid GML files.
• Fixed a memory leak in igraph_write_graph_lgl() when vertex names were present but edge weights were not.
• Fixed the handling of duplicate edge IDs in igraph_subgraph_from_edges().
• Fixed conversion of sparse matrices to dense with igraph_sparsemat_as_matrix() when sparse matrix object did not make use of its full allocated capacity.
• igraph_write_graph_ncol() and igraph_write_graph_lgl() now refuse to write vertex names which would result in an invalid file that cannot be read back in.
• igraph_write_graph_gml() now ignores graph attributes called edge or node with a warning. Writing these would create an invalid GML file that igraph couldn't read back.
• igraph_disjoint_union() and igraph_disjoint_union_many() now check for overflow.
• igraph_read_graph_graphml() now correctly compares attribute values with certain expected values, meaning that prefixes of valid values of attr.type are not accepted anymore.
• Empty IDs are not allowed any more in <key> tags of GraphML files as this is a violation of the GraphML specification.
• igraph_is_separator() and igraph_is_minimal_separator() now work correctly with disconnected graphs.
• igraph_linegraph() now considers self-loops to be self-adjacent in undirected graphs, bringing consistency with how directed graphs were already handled in previous versions.
• igraph_all_st_mincuts() now correctly returns all minimum cuts. This also fixes a problem with igraph_minimum_size_separators().
• Corrected minor error in igraph_community_label_propagation() when adding labels to isolated nodes with some fixed labels present.
• igraph_community_spinglass() no longer crashes when passing an edgeless graph and an empty weight vector.
• igraph_rewire() no longer crashes on graphs with more than three vertices but fewer than two edges.

Changed

• igraph_rewire() on longer throws an error on graphs with fewer than four vertices. These graphs are now returned unchanged, just like other graphs which are the unique realization of their degree sequence.

Other

• Performance: igraph_is_simple() now makes more granular use of the cache.
• Performance: igraph_degree() now makes use of the cache when checking for self-loops.
• The performance of igraph_is_minimal_separator() was improved.
• igraph_is_graphical() now performs graphicality checks for degree sequences of simple directed graphs in linear time, an improvement from the previously used quadratic algorithm (contributed by Arnar Bjarni Arnarson @Tagl in #2537).
• Documentation improvements.

igraph 0.10.10

Fixed

• When igraph_is_forest() determined that a graph is not a directed forest, and the roots output parameter was set to NULL, it would incorrectly cache that the graph is also not an undirected forest.
• igraph_spanner() now correctly ignores edge directions, and no longer crashes on directed graphs.

Deprecated

• igraph_are_connected() is renamed to igraph_are_adjacent(); the old name is kept available until at least igraph 1.0.

Other

• Documentation improvements.

igraph 0.10.9

Added

• igraph_is_biconnected() checks if a graph is biconnected.
• igraph_realize_bipartite_degree_sequence() constructs a bipartite graph that has the given bidegree sequence, optionally ensuring that it is connected (PR #2425 by Lára Margrét Hólmfríðardóttir @larah19).

Fixed

• More robust error handling in HRG code.
• Fixed infinite loop in igraph_hrg_sample_many().
• igraph_community_fastgreedy() no longer crashes when providing a modularity vector only, but not a merges matrix of membership vector.
• The graph property cache was not initialized correctly on systems where the size of bool was not 1 byte (#2477).
• Compatibility with libxml2 version 2.12 (#2442).

Deprecated

• The macro STR() is deprecated; use the function igraph_strvector_get() instead.

Other

• Performance: Reduced memory usage and improved initialization performance for igraph_strvector_t.
• Performance: Improved cache use by igraph_is_bipartite().
• The documentation is now also generated in Texinfo format.
• Documentation improvements

igraph 0.10.8

Added

• igraph_joint_degree_matrix() computes the joint degree matrix, i.e. counts connections between vertices of different degrees. (PR #2407 by Lára Margrét Hólmfríðardóttir @larah19)
• igraph_joint_degree_distribution() computes the joint distribution of degrees at either end of edges.
• igraph_joint_type_distribution() computes the joint distribution of vertex categories at either end of edges, i.e. the mixing matrix.
• igraph_degree_correlation_vector() computes the degree correlation function and its various directed generalizations.

Changed

• The behaviour of the Pajek format reader and writer is now more closely aligned with the Pajek software and the reader is more tolerant of input it cannot interpret. Only those vertex and edge parameters are treated as valid which Pajek itself understands, therefore support for size is now dropped, and support for the font edge parameter is added. See http://mrvar.fdv.uni-lj.si/pajek/DrawEPS.htm for more information. Invalid/unrecognized parameters are now converted to igraph attributes by the reader, but just as before, they are not output by the writer.
• The Pajek format writer now encodes newline and quotation mark characters in a Pajek-compatible manner (\n and ", respectively).
• igraph_avg_nearest_neighbor_degree() now supports non-simple graphs.

Fixed

• Resolved "ignoring duplicate libraries" warning when building tests with Xcode 15 on macOS.
• Fixed the handling of duplicate vertex IDs in igraph_induced_subgraph().
• igraph_vector_which_min() and igraph_vector_which_max() no longer allow zero-length input, which makes them consistent with other similar functions, and was the originally intended behaviour. Passing zero-length input is invalid use and currently triggers an assertion failure.
• igraph_erdos_renyi_game_gnm() and igraph_erdos_renyi_game_gnp() are now interruptible.
• igraph_de_bruijn() and igraph_kautz() are now interruptible.
• igraph_full(), igraph_full_citation(), igraph_full_multipartite() and igraph_turan() are now interruptible.
• igraph_avg_nearest_neighbor_degree() did not compute knnk correctly in the weighted case.
• Fixed variadic arguments of invalid types, which could cause incorrect behaviour with igraph_matrix_print(), as well as test suite failures, on some platforms. 32-bit x86 was affected when setting IGRAPH_INTEGER_SIZE to 64.
• igraph_subisomorphic_lad() now returns a single null map when the pattern is the null graph.
• igraph_community_spinglass() now checks its parameters more carefully.
• igraph_similarity_dice_pairs() and igraph_similarity_jaccard_pairs() now validate vertex IDs.
• igraph_maxflow() now returns an error code if the source and target vertices are the same. It used to get stuck in an infinite loop in earlier versions when the flow argument was non-NULL.

igraph 0.10.7

Added

• igraph_radius_dijkstra() computes the graph radius with weighted edges (experimental function).
• igraph_graph_center_dijkstra() computes the graph center, i.e. the set of minimum eccentricity vertices, with weighted edges (experimental function).

Fixed

• igraph_full_bipartite() now checks for overflow.
• igraph_bipartite_game_gnm() and igraph_bipartite_game_gnp() are now more robust to overflow.
• Bipartite graph creation functions now check input arguments.
• igraph_write_graph_dot() now quotes real numbers written in exponential notation as necessary.
• Independent vertex set finding functions could trigger the fatal error "Finally stack too large" when called on large graphs.

Deprecated

• igraph_bipartite_game() is now deprecated; use igraph_bipartite_game_gnm() and igraph_bipartite_game_gnp() instead.

Other

• Documentation improvements.

igraph 0.10.6

Fixed

• Compatibility with libxml2 2.11.
• Fixed some converge failures in igraph_community_voronoi().
• IGRAPH_CALLOC() and IGRAPH_REALLOC() now check for overflow.
• CMake packages created with the install target of the CMake build system are now relocatable, i.e. the generated igraph-targets.cmake file does not contain absolute paths any more.

igraph 0.10.5

Added

• igraph_graph_power() computes the kth power of a graph (experimental function).
• igraph_community_voronoi() for detecting communities using Voronoi partitioning (experimental function).

Changes

• igraph_community_walktrap() no longer requires modularity and merges to be non-NULL when membership is non-NULL.
• igraph_isomorphic() now supports multigraphs.
• Shortest path related functions now consistently ignore edges with positive infinite weights.

Fixed

• igraph_hub_and_authority_scores(), igraph_hub_score() and igraph_authority_score() considered self-loops only once on the diagonal of the adjacency matrix of undirected graphs, thus the result was not identical to that obtained by igraph_eigenvector_centrality() on loopy undirected graphs. This is now corrected.
• igraph_community_infomap() now checks edge and vertex weights for validity.
• igraph_minimum_spanning_tree() and igraph_minimum_spanning_tree_prim() now check that edge weights are not NaN.
• Fixed an initialization error in the string attribute combiner of the C attribute handler.
• Fixed an issue with the weighted clique number calculation when all the weights were the same.
• HRG functions now require a graph with at least 3 vertices; previous versions crashed with smaller graphs.
• igraph_arpack_rssolve() and igraph_arpack_rnsolve(), i.e. the ARPACK interface in igraph, are now interruptible. As a result, several other functions that rely on ARPACK (eigenvector centrality, hub and authority scores, etc.) also became interruptible.
• igraph_get_shortest_paths_dijkstra(), igraph_get_all_shortest_paths_dijkstra() and igraph_get_shortest_paths_bellman_ford() now validate the from vertex.
• Fixed bugs in igraph_local_scan_1_ecount() for weighted undirected graphs which would miscount loops and multi-edges.

Deprecated

• igraph_automorphisms() is now deprecated; its new name is igraph_count_automorphisms(). The old name is kept available until at least igraph 0.11.
• igraph_hub_score() and igraph_authority_score() are now deprecated. Use igraph_hub_and_authority_scores() instead.
• igraph_get_incidence() is now deprecated; its new name is igraph_get_biadjacency() to reflect that the returned matrix is an adjacency matrix between pairs of vertices and not an incidence matrix between vertices and edges. The new name is kept available until at least igraph 0.11. We plan to re-use the name in later versions to provide a proper incidence matrix where the rows are vertices and the columns are edges.
• igraph_hrg_dendrogram() is deprecated because it requires an attribute handler and it goes against the convention of returning attributes in vectors where possible. Use igraph_from_hrg_dendrogram() instead, which constructs the dendrogram as an igraph graph and returns the associated probabilities in a vector.

Other

• Improved performance for igraph_vertex_connectivity().
• igraph_simplify() makes use of the cache, and avoids simplification when the graph is already known to be simple.
• Documentation improvements.

igraph 0.10.4

Added

• igraph_get_shortest_path_astar() finds a shortest path with the A* algorithm.
• igraph_vertex_coloring_greedy() now supports the DSatur heuristics (#2284, thanks to @professorcode1).

Changed

• The test build target now only runs the unit tests, but it does not build them. In order to both build and run tests, use the check target, which continues to behave as before (PR #2291).
• The experimental function igraph_distances_floyd_warshall() now has from and to parameters for choosing source and target vertices.
• The experimental function igraph_distances_floyd_warshall() now has an additional method parameter to select a specific algorithm. A faster "Tree" variant of the Floyd-Warshall algorithm is now available (#2267, thanks to @rfulekjames).

Fixed

• The Bellman-Ford shortest path finder is now interruptible.
• The Floyd-Warshall shortest path finder is now interruptible.
• Running CTest no longer builds the tests automatically, as this interfered with VSCode, which would invoke the ctest executable after configuring a project in order to determine test executables. Use the build_tests target to build the tests first, or use the check target to both build and run all unit tests (PR #2291).

Other

• Improved the performance and memory usage of igraph_widest_path_widths_floyd_warshall().
• Documentation improvements.

igraph 0.10.3

Added

• igraph_matrix_init_array() to initialize an igraph matrix by copying an existing C array in column-major or row-major order.
• igraph_layout_umap_compute_weights() computes weights for the UMAP layout algorithm from distances. This used to be part of igraph_layout_umap(), but it is now in a separate function to allow the user to experiment with different weighting schemes.
• igraph_triangular_lattice() to generate triangular lattices of various kinds (#2235, thanks to @rfulekjames).
• igraph_hexagonal_lattice() to generate hexagonal lattices of various kinds (#2262, thanks to @rfulekjames).
• igraph_tree_from_parent_vector() to create a tree or a forest from a parent vector (i.e. a vector that encodes the parent vertex of each vertex).
• igraph_induced_subgraph_edges() produces the IDs of edges contained within a subgraph induced by the given vertices.

Changed

• The signature of the experimental igraph_layout_umap() function changed; the last argument is now a Boolean that specifies whether distances should already be treated as weights, and the sampling probability argument was removed.

Fixed

• igraph_transitivity_barrat(), igraph_community_fluid_communities(), igraph_sir(), igraph_trussness() and graphlet functions did not correctly detect when a directed input graph had effective multi-edges due to ignoring edge directions. Such graphs are now rejected by these functions.
• Fixed a bug in igraph_2dgrid_move() that sometimes crashed the Large Graph Layout function when a grid cell became empty.
• igraph_pagerank() and igraph_personalized_pagerank() would fail to converge when the ARPACK implementation was used and a vertex had more than one outgoing edge but all these edges had zero weights.
• igraph_pagerank() and igraph_personalized_pagerank() no longer allow negative weights. Previously, edges with negative weights were silently ignored when using the PRPACK implementation. The ARPACK implementation would issue a warning saying that they are ignored, but in fact it computed an incorrect result.
• igraph_all_st_cuts() and igraph_all_st_mincuts() no longer trigger the "Finally stack too large" fatal error when called on certain large graphs. This was a regression in igraph 0.10.
• igraph_community_label_propagation() no longer rounds weights to integers. This was a regression in igraph 0.10.
• igraph_read_graph_graphdb() does more thorough checks on the input file.
• igraph_calloc() did not zero-initialize the allocated memory. This is now corrected. Note that the macro IGRAPH_CALLOC() was not affected.
• Fixed new warnings issued by the Xcode 14.1 toolchain.

Deprecated

• igraph_subgraph_edges() is now deprecated to avoid confusion with igraph_induced_subgraph_edges(); its new name is igraph_subgraph_from_edges(). The old name is kept available until at least igraph 0.11.

Other

• Significantly improved performance for igraph_matrix_transpose().
• Documentation improvements.