rustworkx

Prelude

Rustworkx 0.18.0 is a feature release that includes a number of bugfixes and new features to the library. The highlights of this release are:

Initial support for free-threaded Python builds

Performance improvements to several functions

Several new algorithm functions

An important reminder that this is the first release of rustworkx that does not include the legacy retworkx package. Historically, we have release retworkx and rustworkx at the same time, with retworkx being an alias to the same rustworkx package. The legacy name for the package was marked end of life with its final release being 0.17.0. This release uses the Python Stable ABI, and will be compatible with all versions from Python 3.10 onwards. The published binaries have been tested with Python 3.10 to 3.14, although they will likely work with future versions like 3.15. For users building Rustworkx from source that the Python build system has switched to use maturin instead of setuptools-rust . Maturin is also a PEP-517 compatible builder so if using modern standard Python packaging tooling there should be no intervention needed. Additionally, the minimum supported Rust version for building rustworkx and rustworkx-core has been raised to 1.85.

New Features

Added a new bfs_layers() (and it’s per type variants graph_bfs_layers() and digraph_bfs_layers() ) that performs a breadth-first search traversal and returns the nodes organized by their BFS layers/levels. Each layer contains all nodes at the same distance from the source nodes. This is useful for analyzing graph structure and implementing algorithms that need to process nodes level by level. For example:

import rustworkx graph = rustworkx . PyDiGraph () graph . extend_from_edge_list ([( 0 , 1 ), ( 0 , 2 ), ( 1 , 3 ), ( 2 , 3 ), ( 3 , 4 )]) # Print the layers of the graph in BFS-order relative to 0 (source) layers = rustworkx . bfs_layers ( graph , sources = [ 0 ]) print ( 'BFS layers:' , layers )

BFS layers: [[0], [2, 1], [3], [4]]

Added new functions for computing group centrality measures: group_degree_centrality() , group_closeness_centrality() , and group_betweenness_centrality() . These functions compute the centrality of a group of nodes as defined by Everett & Borgatti (1999) . Each function works with both PyGraph and PyDiGraph objects.

Added a new layout function, kamada_kawai_layout() , which positions nodes using the Kamada-Kawai path-length cost function. The function works with both PyGraph and PyDiGraph inputs. The implementation follows the original 1989 algorithm of Kamada and Kawai : an outer loop selects the node with the largest partial-gradient norm and an inner loop applies a 2D Newton step against the local Hessian until convergence.

Disconnected graphs are handled by laying out each connected component independently and packing the components in a horizontal row. This avoids the visual collapse seen with single-objective Kamada-Kawai on disconnected inputs.

Example usage:

import rustworkx from rustworkx.visualization import mpl_draw graph = rustworkx . generators . hexagonal_lattice_graph ( 2 , 2 ) layout = rustworkx . kamada_kawai_layout ( graph ) mpl_draw ( graph , pos = layout )

Added a node_list argument to adjacency_matrix() , graph_adjacency_matrix() , and digraph_adjacency_matrix() . The argument controls the output matrix row and column order and can be used to build a matrix for a subset of graph nodes.

Added feature for importing graphs from the GraphViz DOT format via the new from_dot() function. This function takes a DOT string and constructs either a PyGraph or PyDiGraph object, automatically detecting the graph type from the DOT input. Node attributes, edge attributes, and graph-level attributes are preserved. For example:

import rustworkx dot_str = ''' digraph { 0 [label="a", color=red]; 1 [label="b", color=blue]; 0 -> 1 [weight=1]; } ''' g = rustworkx . from_dot ( dot_str ) assert len ( g . nodes ()) == 2 assert len ( g . edges ()) == 1

Added two new functions to perform greedy routing algorithms. The function hyperbolic_greedy_routing() that performs the greedy routing algorithm in the hyperbolic space, and the function hyperbolic_greedy_success_rate() computes the proportion of pairs of nodes for which the greedy path reaches the destination.

Added support for reading and writing matrices in the Matrix Market (MM) format via the new read_matrix_market() , read_matrix_market_file() , and write_matrix_market() functions. These functions enable importing and exporting sparse matrices in COO (Coordinate) format, either from a file or directly from an in-memory string.

This is the first release of rustworkx with official support Python 3.14. Although previous versions of rustworkx do work with Python 3.14, this release has been tested with 3.14. Likewise, we expect future versions of Python like 3.15 to work as well.

Added Python 3.14 free-threaded wheels for Linux and macOS. See #1251 for more details.

Added a new function, random_regular_graph() for generating random undirected regular graphs. For example:

import rustworkx from rustworkx.visualization import mpl_draw graph = rustworkx . random_regular_graph ( 22 , 7 , 42 ) mpl_draw ( graph )

Added a new new function generate_random_path() to return return the path of nodes visited during a random walk on the graph.

Adds the flags multigraph and allow_self_loops to the read_edge_list methods of rustwork.PyGraph and rustworkx.PyDiGraph . When the flag multigraph is set to False , no parallel edge is created, but the edge weight is updated. The edge weight is the last one found in the edge list file. When flag allow_self_loops is set to False , the self-loops in the edge list file are ignored.

rustworkx-core Features

Added a new function bfs_laters to the rustworkx-core::traversal module that performs a a breadth-first search traversal and returns the nodes organized by their BFS layers/levels. Each layer contains all nodes at the same distance from the source nodes. This is useful for analyzing graph structure and implementing algorithms that need to process nodes level by level.

Added new functions group_degree_centrality group_closeness_centrality and group_betweenness_centrality to the rustworkx_core::centrality module. These functions compute the centrality of a group of nodes as defined by Everett & Borgatti (1999) .

Added a new rustworkx-core function longest_path_length to the module dag_algo . This function computes the length of the longest path in a directed acyclic graph without storing the actual path or returning it. This differs from the existing longest_path which internally stores the path and returns it.

Adds the new geometry module to rustworkx_core . This module mainly defines the greedy routing algorithm which is useful when each node has a position in a metric space. The greedy_routing function returns, if it exists, the greedy path between two nodes and its total length in the metric space. The greedy_routing_success_rate returns the proportion of pairs of nodes for which the greedy path reaches the destination. The greedy routing algorithm may be used with any distance. The geometry module implements many distances: angular_distance , euclidean_distance , hyperboloid_hyperbolic_distance , lp_distance , maximum_distance and polar_hyperbolic_distance .

Added a new function generate_random_path to the rustworkx-core::traversal module for returning the path of nodes visited during a random walk on a graph.

Upgrade Notes

The minimum supported rust version to build rustworkx and rustworkx-core has been raised from 1.79 to 1.85. You will need to upgrade your Rust compiler version to at least version 1.85 to continue building from source. The new MSRV has allowed rustworkx to upgrade to Rust Edition 2024.

Python library users who are installing rustworkx on a supported platform will not need to make any changes.

The minimum supported Python version for using rustworkx has been raised to Python 3.10. Python 3.9 has reached it’s end-of-life and will no longer be supported. To use rustworkx you will need to ensure you are using Python >=3.10.

As announced in the 0.17 release, the legacy retworkx name has been sunset. We encourage users to depend on ‘rustworkx’ as previously instructed.

Thanks to all users that have used the library since the early days before the name change!

Bug Fixes

Fixed a bug in rustworkx.bridges() that missed all bridges connected to the root node. The bug was introduced with the addition of the function in version 0.14.0.

Fixed a bug in PyDiGraph.find_successor_node_by_edge() where the method always returned the source node by mistake. Now, it returns any of the successors, as originally intended.

Fixed a bug in node_link_json() that caused issues when serializing graphs with deleted nodes. See #1516 for more details.

Other Notes

Avoid unnecessary hashing operations in rustworkx.all_simple_paths with multiple targets, improving performance for the use case.

Prelude

This is a new Rustworkx release with many bug fixes and new features to the library. The highlights of this release are:

Enhanced support for type checking with mypy and pyright

Support for reading GraphML files that are compressed

New dominance algorithms

This release uses the Python Stable ABI , and will be compatible with all versions from Python 3.9 onwards. The published binaries have been tested with Python 3.9 to 3.13, although they will likely work with future versions like 3.14. We’d like to thank all the users that reported issues and contributed to this release. This is the rustworkx release with the most individual contributors to date!

New Features

The following methods now support sequences and generators as inputs, in addition to the existing support for lists:

• add_nodes_from() and add_nodes_from() * add_edges_from() and add_edges_from() * add_edges_from_no_data() and add_edges_from_no_data() * extend_from_edge_list() and extend_from_edge_list() * extend_from_weighted_edge_list() and extend_from_weighted_edge_list()

Added a new function, johnson_simple_cycles , to the rustworkx-core crate. This function implements Johnson’s algorithm for finding all elementary cycles in a directed graph.

Added a new trait EdgeFindable to find an EdgeIndex from a graph given a pair of node indices.

Added a new trait EdgeRemovable to remove an edge from a graph by its EdgeIndex .

Added a new function, degree_centrality() which is used to compute the degree centrality for all nodes in a given graph. For example:

import rustworkx as rx from rustworkx.visualization import mpl_draw graph = rx . generators . hexagonal_lattice_graph ( 4 , 4 ) centrality = rx . degree_centrality ( graph ) # Generate a color list colors = [] for node in graph . node_indices (): centrality_score = centrality [ node ] graph [ node ] = centrality_score colors . append ( centrality_score ) mpl_draw ( graph , with_labels = True , node_color = colors , node_size = 650 , labels = lambda x : " {0:.2f} " . format ( x ) )

Added two new functions, in_degree_centrality() and out_degree_centrality() to calculate two special types of degree centrality for directed graphs.

Add rustworkx.immediate_dominators() function for computing immediate dominators of all nodes in a directed graph. This function mirrors the networkx.immediate_dominators function.

Add the rustworkx.dominance_frontiers() function to compute the dominance frontiers of all nodes in a directed graph. This function mirrors the networkx.dominance_frontiers function.

The PyDiGraph() and PyGraph() classes now have better support for PEP 560 . Building off of the previous releases which introduced type annotations, the following code snippet is now valid:

import rustworkx as rx graph : rx . PyGraph [ int , int ] = rx . PyGraph ()

Previously, users had to rely on post-poned evaluation of type annotations from PEP 563 for annotations to work.

Refer to issue 1345 for more information.

Added a new function, karate_club_graph() that returns Zachary’s Karate Club graph, commonly found in social network examples.

import rustworkx.generators from rustworkx.visualization import mpl_draw graph = rustworkx . generators . karate_club_graph () layout = rustworkx . circular_layout ( graph ) mpl_draw ( graph , pos = layout )

Added a new method neighbors_undirected() to obtain the neighbors of a node in a directed graph, irrespective of the edge directionality.

Added the ability to read GraphML files that are compressed using gzip, with function read_graphml() . The extensions .graphmlz and .gz are automatically recognised, but the gzip decompression can be forced with the “compression” optional argument.

Upgrade Notes

The minimum supported Python version for using rustworkx has been raised to Python 3.9. Python 3.8 has reached it’s end-of-life and will no longer be supported. To use rustworkx you will need to ensure you are using Python >=3.9.

Bug Fixes

Fixed a bug introduced in version 0.15 where the edge colors specified as a list in calls to mpl_draw() were not having their order respected. Instead, the order of the colors was being shuffled. This has been restored and now the behavior should match that of 0.14.

Fixed a bug in the type hints for find_node_by_weight() and find_node_by_weight() . Refer to issue 1243 for more information.

Fixed a bug in the type hint for layers() Refer to issue 1340 for more information.

Fixed a bug in the type hint for node_link_json() . Refer to issue 1243 for more information.

Fix typos detected by typos . Add spell checker invocations to the Nox lint session.

Fixed a bug in the discoverability of the type hints for the rustworkx.visit module. Classes declared in the module are also now properly annotated as accepting generic types. Refer to issue 1352 for more information.

Enhanced the compatibility of the type annotations with pyright in strict mode. See issue 1242 for more details.

Prelude

This release is a bugfix patch release that fixes an inadvertent breaking API change for the graphviz_draw() function in the 0.15.0 release.

Bug Fixes

Fixed an issue in the graphviz_draw() , PyGraph.to_dot() , and PyDiGraph.to_dot() which was incorrectly escaping strings when upgrading to 0.15.0. In earlier versions of rustworkx if you manually placed quotes in a string for an attr callback to get that to pass through to the output dot file, this was incorrectly being converted in rustworkx 0.15.0 to duplicate the quotes and escape them. For example, if you defined a callback like:

def color_node ( _node ): return { "color" : '"#422952"' }

to set the color attribute in the output dot file with the string "#422952" (with the quotes), this was incorrectly being converted to ""#422952"" . This no longer occurs, in rustworkx 0.16.0 there will likely be additional options exposed in graphviz_draw() , PyGraph.to_dot() , and PyDiGraph.to_dot() to expose further options around this.

Fixed two bugs in the node position calculation done by the generator functions hexagonal_lattice_graph() and directed_hexagonal_lattice_graph() when with_positions = True :

Corrected a scale factor that made all the hexagons in the lattice irregular

Corrected an indexing bug that positioned the nodes in the last column of the lattice incorrectly when periodic = False and cols is odd

Prelude

This is a new feature release of Rustworkx that adds many new features to the library. The highlights of this release are:

An expansion of functions in rustworkx-core that previously only existed in the Python API.

Expanded graph coloring algorithms

This release moves to using the Python Stable ABI , while this release officially supports Python 3.8 through 3.12, the published binaries should be compatible with future Python versions too. Although there is no guarantee provided about future versions. Additionally, the minimum supported Rust version for building rustworkx and more importantly rustworkx-core is now 1.70.0. Additionally, in this release the macOS arm64 platform has been promoted from Tier 4 to Tier 1 .

New Features

Added a method has_node() to the PyGraph and PyDiGraph classes to check if a node is in the graph.

Added a new function rustworkx_core::dag_algo::layers to rustworkx-core to get the layers of a directed acyclic graph. This is equivalent to the layers() function that existed in the Python API but now exposes it for Rust users too.

Added two new functions, from_node_link_json_file() and parse_node_link_json() , which are used to parse a node link json object and generate a rustworkx PyGraph or PyDiGraph object from it.

Added a new function ancestors() to the rustworkx_core::traversal module. That is a generic Rust implementation for the core rust library that provides the ancestors() function to Rust users.

Added a new function descendants() to the rustworkx_core::traversal module. That is a generic Rust implementation for the core rust library that provides the descendants() function to Rust users.

Added a new function bfs_predecessors() to the rustworkx_core::traversal module. That is a generic Rust implementation for the core rust library that provides the bfs_predecessors() function to Rust users.

Added a new function bfs_successors() to the rustworkx_core::traversal module. That is a generic Rust implementation for the core rust library that provides the bfs_successors() function to Rust users.

Added a new function collect_runs to rustworkx-core’s dag_algo module. Previously, the collect_runs() functionality for DAGs was only exposed via the Python interface. Now Rust users can take advantage of this functionality in rustworkx-core .

Added a function connected_subgraphs() to determine all connected subgraphs of size (k) in polynomial delay for undirected graphs. This improves upon the brute-force method by two orders of magnitude for sparse graphs such as heavy-hex, enabling addressing larger graphs and for a larger (k) . The introduced method is based on “Enumerating Connected Induced Subgraphs: Improved Delay and Experimental Comparison” by Christian Komusiewicz and Frank Sommer. In particular, the procedure Simple is implemented. Possible runtime improvement can be gained by parallelization over each recursion or by following the discussion in Lemma 4 of above work and thus implementing intermediate sets (X) and (P) more efficiently.

Rustworkx functions that return custom iterable objects, such as PyDiGraph.node_indices() , now each have an associated custom iterator and reversed-iterator object for these. This provides a speedup of approximately 40% for iterating through the custom iterables.

These types are not directly nameable or constructable from Python space, and other than the performance improvement, the behavior should largely not be noticeable from Python space.

Added rustworkx.generators.dorogovtsev_goltsev_mendes_graph() that generates deterministic scale-free graphs using the Dorogovtsev-Goltsev-Mendes iterative procedure.

import rustworkx as rx from rustworkx.visualization import mpl_draw graph = rx . generators . dorogovtsev_goltsev_mendes_graph ( 2 ) mpl_draw ( graph )

Added a new function, rustworkx_core::generators::dorogovtsev_goltsev_mendes_graph , to rustworkx-core that is used to generate deterministic scale-free graphs using the Dorogovtsev-Goltsev-Mendes iterative procedure.

Node contraction is now supported for petgraph types StableGraph and GraphMap in rustworkx-core. To use it, import one of the ContractNodes* traits from graph_ext and call the contract_nodes method on your graph.

All current petgraph data structures now support testing for parallel edges in rustworkx-core . To use this, import HasParallelEdgesDirected or HasParallelEdgesUndirected depending on your graph type, and call the has_parallel_edges method on your graph.

A new trait NodeRemovable has been added to graph_ext module in rustworkx-core which provides a consistent interface for performing node removal operations on petgraph types Graph , StableGraph , GraphMap , and MatrixGraph . To use it, import NodeRemovable from graph_ext .

Adds new random graph generator function, hyperbolic_random_graph() to sample the hyperbolic random graph model. For example:

import math import rustworkx as rx from rustworkx.visualization import mpl_draw graph = rx . hyperbolic_random_graph ( [[ math . sinh ( 0.5 ), 0 , 3.14159 ], [ - math . sinh ( 1 ), 0 , - 3.14159 ]], 2.55 , None , ) mpl_draw ( graph )

Adds new function to the rustworkx-core module rustworkx_core::generators hyperbolic_random_graph() that samples the hyperbolic random graph model.

lexicographical_topological_sort() and TopologicalSorter now both accept an initial keyword argument, which can be used to limit the returned topological orderings to be only over the nodes that are dominated by the initial set. This can provide performance improvements by removing the need for a search over all graph nodes to determine the initial set of nodes with zero in degree; this is particularly relevant to TopologicalSorter , where the user may terminate the search after only examining part of the order.

Added a new function, is_semi_connected() which will check if a :class: ~rustworkx.PyDiGraph object is semi-connected.

Added a new function lexicographical_topological_sort to the rustworkx_core::dag_algo module. That is a generic Rust implementation for the core rust library that provides the lexicographical_topological_sort() function to Rust users.

Added a new function digraph_maximum_bisimulation() to compute the maximum bisimulation or relational coarsest partition of a graph. This function is based on the algorithm described in the publication “Three partition refinement algorithms” by Paige and Tarjan. This function receives a graph and returns a RelationalCoarsestPartition .

Added a new class RelationalCoarsestPartition to output the maximum bisimulation or relational coarsest partition of a graph. This class contains instances of IndexPartitionBlock and can be iterated over.

Added a new class IndexPartitionBlock to output a block of a node partition. This class is an iterator over node indices.

Added a new function collect_bicolor_runs to rustworkx-core’s dag_algo module. Previously, the collect_bicolor_runs() functionality for DAGs was only exposed via the Python interface. Now Rust users can take advantage of this functionality in rustworkx-core .

Added a new module dag_algo to rustworkx-core which contains a new function longest_path function to rustworkx-core. Previously the longest_path() functionality for DAGs was only exposed via the Python interface. Now Rust users can take advantage of this functionality in rustworkx-core.

Added two new keyword arguments, periodic an with_positions , to the generator functions hexagonal_lattice_graph() and directed_hexagonal_lattice_graph() . If periodic is set to True the boundaries of the lattice will be joined to form a periodic grid. If the with_positions argument is set to True than the data payload of all the nodes will be set to a tuple of the form (x, y) where x and y represent the node’s position in the lattice. For example:

import rustworkx as rx from rustworkx.visualization import mpl_draw graph = rx . generators . hexagonal_lattice_graph ( 4 , 4 , periodic = True , with_positions = True ) mpl_draw ( graph , with_labels = True , labels = str )

Added a new rustworkx-core function rustworkx_core::generators::hexagonal_lattice_graph_weighted() which is used to generate a hexagonal lattice graph where a callback is used to generate the node weights for each node from a tuple of the form (usize, usize) .

Added the PyDiGraph.remove_node_retain_edges_by_id() and remove_node_retain_edges_by_key() methods, which provide a node-removal that is linear in the degree of the node, as opposed to quadratic like remove_node_retain_edges() . These methods require, respectively, that the edge weights are referentially identical if they should be retained ( a is b , in Python), or that you can supply a key function that produces a Python-hashable result that is used to do the equality matching between input and output edges.

Added a new class ColoringStrategy used to specify the strategy used by the greedy node and edge coloring algorithms. The Degree strategy colors the nodes with higher degree first. The Saturation strategy dynamically chooses the vertex that has the largest number of different colors already assigned to its neighbors, and, in case of a tie, the vertex that has the largest number of uncolored neighbors. The IndependentSet strategy finds independent subsets of the graph, and assigns a different color to each of these subsets.

The rustworkx-core coloring module has 2 new functions, greedy_node_color_with_coloring_strategy and greedy_edge_color_with_coloring_strategy . These functions color respectively the nodes or the edges of the graph using the specified coloring strategy and handling the preset colors when provided.

Added a new keyword argument, strategy , to graph_greedy_color() and to graph_greedy_edge_color() to specify the greedy coloring strategy.

For example:

import rustworkx as rx from rustworkx.visualization import mpl_draw graph = rx . generators . generalized_petersen_graph ( 5 , 2 ) coloring = rx . graph_greedy_color ( graph , strategy = rx . ColoringStrategy . Saturation ) colors = [ coloring [ node ] for node in graph . node_indices ()] layout = rx . shell_layout ( graph , nlist = [[ 0 , 1 , 2 , 3 , 4 ],[ 6 , 7 , 8 , 9 , 5 ]]) mpl_draw ( graph , node_color = colors , pos = layout )

Added a new keyword argument, preset_color_fn , to graph_greedy_edge_color() which is used to provide preset colors for specific edges when computing the graph coloring. You can optionally pass a callable to that argument which will be passed edge index from the graph and is either expected to return an integer color to use for that edge, or None to indicate there is no preset color for that edge. For example:

import rustworkx as rx from rustworkx.visualization import mpl_draw graph = rx . generators . generalized_petersen_graph ( 5 , 2 ) def preset_colors ( edge_index ): if edge_index == 0 : return 3 coloring = rx . graph_greedy_edge_color ( graph , preset_color_fn = preset_colors ) colors = [ coloring [ edge ] for edge in graph . edge_indices ()] layout = rx . shell_layout ( graph , nlist = [[ 0 , 1 , 2 , 3 , 4 ], [ 6 , 7 , 8 , 9 , 5 ]]) mpl_draw ( graph , edge_color = colors , pos = layout )

Adds new random graph generator in rustworkx for the stochastic block model. There is a generator for directed directed_sbm_random_graph() and undirected graphs undirected_sbm_random_graph() .

import numpy as np import rustworkx as rx from rustworkx.visualization import mpl_draw graph = rx . undirected_sbm_random_graph ( [ 2 , 1 ], np . array ([[ 1 , 1 ], [ 1 , 0 ]], dtype = float ), False , ) mpl_draw ( graph )

Adds new function sbm_random_graph to the rustworkx-core module rustworkx_core::generators that samples a graph from the stochastic block model.

rustworkx wheels are now built against Python’s stable Application Binary Interface (ABI). For rustworkx users, this means that wheels distributed by us via PyPI will continue to work with newer versions of Python without having to recompile the code. This change will also simplify the release process for the developers and reduce the storage size required to mirror rustworkx wheels.

TopologicalSorter now has a check_args keyword argument, which can be set to False to disable the runtime detection of invalid arguments to done() . This provides a memory and runtime improvement to the online sorter, at the cost that the results will be undefined and likely meaningless if invalid values are given.

TopologicalSorter.done() now accepts single integers, in addition to lists of integers. This can be a sizeable performance improvement for algorithms that iterate through nodes, and only conditionally mark them as done ; there is no longer a need to allocate a temporary Python array.

lexicographical_topological_sort() and TopologicalSorter now accept a reverse keyword argument, which can be set to True to find a “reversed” topological ordering. This is a topological ordering that would be found if all the edges in the graph had their directions reversed.

PyGraph and PyDiGraph now each take keyword arguments node_count_hint and edge_count_hint in their constructors, which can be used to pre-allocate space for the given number of nodes and edges.

Upgrade Notes

The minimum supported rust version to build rustworkx and rustworkx-core has been raised from 1.64 to 1.70. You will need to upgrade your rust compiler version to at least version 1.70 to continue building from source. Python library users who are installing rustworkx on a supported platform will not need to make any changes.

The rustworkx-core function rustworkx_core::connectivity::find_cycle now requires the petgraph::visit::Visitable trait for its input argument graph . This was required to fix the behavior when source is None to ensure we always find a cycle if one exists.

The interface of the rustworkx_core::generators::hexagonal_lattice_graph() function has been changed, there is a new required boolean argument periodic which is used to indicate whether the output graph should join the bondaries of the lattice to form a periodic grid or not. This argument didn’t exist in prior releases of rustworkx-core and it will need to be added when upgrading to this new release.

Bug Fixes

Fixed the behavior of digraph_find_cycle() when no source node was provided. Previously, the function would start looking for a cycle at an arbitrary node which was not guaranteed to return a cycle. Now, the function will smartly choose a source node to start the search from such that if a cycle exists, it will be found.

Fixed an issue with the graphviz_draw() where it would not correctly escape special characters in all scenarios. This has been corrected so you can now use special characters with the function, for example:

import rustworkx as rx from rustworkx.visualization import graphviz_draw graphviz_draw ( rx . generators . path_graph ( 2 ), node_attr_fn = lambda x : { "label" : "the \n label" , "tooltip" : "the \n tooltip" }, )

Fixed: #750

Fixed the plots of multigraphs using mpl_draw() . Previously, parallel edges of multigraphs were plotted on top of each other, with overlapping arrows and labels. The radius of parallel edges of the multigraph was fixed to be 0.25 for connectionstyle supporting this argument in draw_edges() . The edge labels were offset to 0.25 in draw_edge_labels() to align with their respective edges. This fix can be tested using the following code:

import rustworkx from rustworkx.visualization import mpl_draw graph = rustworkx . PyDiGraph () graph . add_node ( 'A' ) graph . add_node ( 'B' ) graph . add_node ( 'C' ) graph . add_edge ( 1 , 0 , 2 ) graph . add_edge ( 0 , 1 , 3 ) graph . add_edge ( 1 , 2 , 4 ) mpl_draw ( graph , with_labels = True , labels = str , edge_labels = str , alpha = 0.5 )

Fixed #774

Fixed a bug in the type hint for the mpl_draw() . Previously, the type hint indicated that all kwargs were required when calling the method. The type annotation has been updated to indicate that kwargs with partial arguments is allowed.

Fixed an issue with the Dijkstra path functions:

rustworkx.dijkstra_shortest_paths()

rustworkx.dijkstra_shortest_path_lengths()

rustworkx.bellman_ford_shortest_path_lengths()

rustworkx.bellman_ford_shortest_paths()

rustworkx.astar_shortest_path()

where a PanicException was raised without much detail when an invalid node index was passed in to the source argument. This has been corrected so an IndexError is raised instead. Fixed #1117

Fixed the bug type hint for the bfs_search() , dfs_search() and dijkstra_search() . Refer to #1130 for more information.

Fixed support for handling Long type attributes from input GraphML in the read_graphml() function. Fixed #1140 .

Other Notes

Support for the arm64 macOS platform has been promoted from Tier 4 to Tier 1 . Previously the platform was at Tier 4 because there was no available CI environment for testing rustworkx on the platform. Now that Github has made an arm64 macOS environment available to open source projects [ 1 ] we’re testing the platform along with the other Tier 1 supported platforms. [ 1 ] https://github.blog/changelog/2024-01-30-github-actions-introducing-the-new-m1-macos-runner-available-to-open-source/

For development of rustworkx the automated testing environment tooling used has switched from Tox to instead Nox . This is has no impact for end users and is only relevant if you contribute code to rustworkx.

Release notes: https://www.rustworkx.org/release_notes.html#relnotes-0-14-0

What's Changed

• Bump version strings post release by Matthew Treinish (@mtreinish) in #892
• Bump serde from 1.0.163 to 1.0.164 by Dependabot (@dependabot) in #895
• Add todo_nodes sort to maintain deterministic output in token_swapper by Edwin Navarro (@enavarro51) in #897
• Node and Edge Filtering by danielleodigie in #886
• Bump quick-xml from 0.28.2 to 0.29.0 by Dependabot (@dependabot) in #900
• Bump serde_json from 1.0.96 to 1.0.97 by Dependabot (@dependabot) in #903
• Apply wheel job fixes from 0.13.0 release by Matthew Treinish (@mtreinish) in #896
• Pin Python version in CI by Matthew Treinish (@mtreinish) in #905
• Implement substitute_node_with_subgraph to Pygraph by Raynel Sanchez (@raynelfss) in #894
• Adding Option to change parallel edge behavior in adjacency_matrix functions by danielleodigie in #899
• Drop support for python 3.7 for 0.14.0 by Raynel Sanchez (@raynelfss) in #907
• Bump MSRV to 1.64 for 0.14.0 by Matthew Treinish (@mtreinish) in #910
• Bump serde_json from 1.0.97 to 1.0.99 by Dependabot (@dependabot) in #913
• Bump rayon-cond from 0.2.0 to 0.3.0 by Dependabot (@dependabot) in #915
• Pin pillow<10 in CI by Matthew Treinish (@mtreinish) in #922
• Bump serde from 1.0.164 to 1.0.166 by Dependabot (@dependabot) in #919
• Bump pyo3 from 0.19.0 to 0.19.1 by Dependabot (@dependabot) in #920
• Bump serde_json from 1.0.99 to 1.0.100 by Dependabot (@dependabot) in #921
• adding line_graph and greedy_edge_color for undirected graphs by Alexander Ivrii (@alexanderivrii) in #870
• Bump serde from 1.0.166 to 1.0.167 by Dependabot (@dependabot) in #924
• Bump serde from 1.0.167 to 1.0.171 by Dependabot (@dependabot) in #925
• Bump serde_json from 1.0.100 to 1.0.102 by Dependabot (@dependabot) in #928
• Adding Clippy Fix by danielleodigie in #930
• Bump serde_json from 1.0.102 to 1.0.103 by Dependabot (@dependabot) in #932
• Bump serde from 1.0.171 to 1.0.173 by Dependabot (@dependabot) in #935
• Bump num-traits from 0.2.15 to 0.2.16 by Dependabot (@dependabot) in #936
• Bump serde from 1.0.173 to 1.0.174 by Dependabot (@dependabot) in #937
• Bump quick-xml from 0.29.0 to 0.30.0 by Dependabot (@dependabot) in #938
• Reorganize API docs into subpages by Eric Arellano (@Eric-Arellano) in #927
• Bump serde from 1.0.174 to 1.0.175 by Dependabot (@dependabot) in #939
• Switch to Qiskit Ecosystem theme by Eric Arellano (@Eric-Arellano) in #926
• Add a section to Python docs about page for rustworkx-core by Matthew Treinish (@mtreinish) in #944
• Bump serde_json from 1.0.103 to 1.0.104 by Dependabot (@dependabot) in #946
• Bump serde from 1.0.175 to 1.0.177 by Dependabot (@dependabot) in #948
• Bump serde from 1.0.177 to 1.0.179 by Dependabot (@dependabot) in #951
• Bump serde from 1.0.179 to 1.0.180 by Dependabot (@dependabot) in #958
• Bump pyo3 from 0.19.1 to 0.19.2 by Dependabot (@dependabot) in #957
• Has path by Eliot Heinrich (@eliotheinrich) in #952
• Bump serde from 1.0.180 to 1.0.181 by Dependabot (@dependabot) in #961
• Bump serde from 1.0.181 to 1.0.183 by Dependabot (@dependabot) in #962
• Use workspace versioning and relax hashbrown/indexmap deps by Jake Lishman (@jakelishman) in #956
• Adding Transitive Reduction Function by danielleodigie in #923
• remove deploy documentation to /documentation by Luciano Bello (@1ucian0) in #964
• add .so files to gitignore by Luciano Bello (@1ucian0) in #965
• Bump num-complex from 0.4.3 to 0.4.4 by Dependabot (@dependabot) in #966
• Bump serde_json from 1.0.104 to 1.0.105 by Dependabot (@dependabot) in #968
• Bump petgraph from 0.6.3 to 0.6.4 by Dependabot (@dependabot) in #970
• Bump serde from 1.0.183 to 1.0.185 by Dependabot (@dependabot) in #969
• Handle token_swapper impossible swap mapping with Error by Matthew Treinish (@mtreinish) in #971
• Bump num-bigint from 0.4.3 to 0.4.4 by Dependabot (@dependabot) in #972
• Bump serde from 1.0.185 to 1.0.186 by Dependabot (@dependabot) in #973
• Bump serde from 1.0.186 to 1.0.188 by Dependabot (@dependabot) in #974
• Shortern boilerplate for singledispatch by Ivan Carvalho (@IvanIsCoding) in #882
• Update README.md - Fix Typo by @bricekams in #977
• Bump serde_json from 1.0.105 to 1.0.106 by Dependabot (@dependabot) in #979
• Rename old RETWORKX environment variables by Ivan Carvalho (@IvanIsCoding) in #976
• Bump serde_json from 1.0.106 to 1.0.107 by Dependabot (@dependabot) in #981
• Make stestr >= 4.1 by Ivan Carvalho (@IvanIsCoding) in #983
• Bump rayon from 1.7.0 to 1.8.0 by Dependabot (@dependabot) in #985
• Bump indexmap to 2.0.2, hashbrown to 0.14.1 & more by Ivan Carvalho (@IvanIsCoding) in #989
• Fix build errors with Rust 1.73.0 by Matthew Treinish (@mtreinish) in #996
• Added clear, clear_edges functions to PyGraph and PyDiGraph objects by Arjun Bhamra (@abhamra) in #993
• mapping is not possible when a node has no neighbors by Alexander Ivrii (@alexanderivrii) in #995
• Bump num-traits from 0.2.16 to 0.2.17 by Dependabot (@dependabot) in #999
• Add support for Python 3.12 and musllinux to main by Matthew Treinish (@mtreinish) in #997
• Add isolates() function to rustworkx by Matthew Treinish (@mtreinish) in #998
• Bump serde from 1.0.188 to 1.0.189 by Dependabot (@dependabot) in #1003
• Ramp up deprecation of retworkx package and remove tests by Matthew Treinish (@mtreinish) in #1004
• Update pyo3 and numpy to 0.20.0 by Matthew Treinish (@mtreinish) in #1005
• Add two_color and is_bipartite by Matthew Treinish (@mtreinish) in #1002
• Pivot to from flake8 to ruff for Python linting by Matthew Treinish (@mtreinish) in #1006
• Pivot PyPI publishing to use trusted publishers by Matthew Treinish (@mtreinish) in #1001
• Add barabasi_albert_graph random graph functions by Matthew Treinish (@mtreinish) in #1007
• Pin Numpy < 2 in requirements by Matthew Treinish (@mtreinish) in #1012
• Bump hashbrown from 0.14.1 to 0.14.2 by Dependabot (@dependabot) in #1013
• Bump ahash from 0.8.3 to 0.8.5 by Dependabot (@dependabot) in #1020
• Bump quick-xml from 0.30.0 to 0.31.0 by Dependabot (@dependabot) in #1019
• Bump ahash from 0.8.5 to 0.8.6 by Dependabot (@dependabot) in #1021
• Bump serde from 1.0.189 to 1.0.190 by Dependabot (@dependabot) in #1022
• fix all_simple_paths by Prakhar Bhatnagar (@prakharb10) in #1015
• Bump serde_json from 1.0.107 to 1.0.108 by Dependabot (@dependabot) in #1023
• Bump indexmap from 2.0.2 to 2.1.0 by Dependabot (@dependabot) in #1024
• Add musl aarch64 support at tier 4 by Ivan Carvalho (@IvanIsCoding) in #1008
• Bump serde from 1.0.190 to 1.0.192 by Dependabot (@dependabot) in #1027
• Fix clippy findings for Rust 1.74 by Ivan Carvalho (@IvanIsCoding) in #1030
• Bump serde from 1.0.192 to 1.0.193 by Dependabot (@dependabot) in #1031
• Add annotations for type-specific rustworkx functions by Ivan Carvalho (@IvanIsCoding) in #963
• Fix directed gnp_random_graph by Edwin Navarro (@enavarro51) in #954
• Bump hashbrown from 0.14.2 to 0.14.3 by Dependabot (@dependabot) in #1032
• Fix docs-clean tox job by Jake Lishman (@jakelishman) in #1034
• Bump zerocopy from 0.7.21 to 0.7.31 by Dependabot (@dependabot) in #1038
• Bump pyo3 from 0.20.0 to 0.20.1 by Dependabot (@dependabot) in #1044
• Bump serde_json from 1.0.108 to 1.0.109 by Dependabot (@dependabot) in #1043
• Bump ahash from 0.8.6 to 0.8.7 by Dependabot (@dependabot) in #1042
• all_shortest_paths function by lucasvanmol in #1017
• Bump serde from 1.0.193 to 1.0.194 by Dependabot (@dependabot) in #1046
• Bump serde_json from 1.0.109 to 1.0.110 by Dependabot (@dependabot) in #1045
• Bump serde_json from 1.0.110 to 1.0.111 by Dependabot (@dependabot) in #1047
• Bump pyo3 from 0.20.1 to 0.20.2 by Dependabot (@dependabot) in #1048
• Save next nodes in Floyd-Warshall numpy variants for path reconstruction by maleicacid (@kazuki0824) in #1040
• Add release notes and universal functions for floyd_warshall_successor_and_distance by Ivan Carvalho (@IvanIsCoding) in #1049
• Deploy documentation to Github Pages by Ivan Carvalho (@IvanIsCoding) in #1037
• Bump serde from 1.0.194 to 1.0.195 by Dependabot (@dependabot) in #1050
• Fix URL in comment around origin of matplotlib drawer by Matthew Treinish (@mtreinish) in #1051
• Add Misra-Gries edge coloring method by Alexander Ivrii (@alexanderivrii) in #902
• Add missing methods in PyGraph and PyDiGraph stubs by Ivan Carvalho (@IvanIsCoding) in #967
• Add the function to get topological generations by Yiming Zhang (@inmzhang) in #1053
• Replace call to deprecated np.alltrue with np.all by Pieter Eendebak (@eendebakpt) in #1054
• run clippy CI job on all targets by danieleades in #1057
• simplify ruff exclude list by danieleades in #1056
• Bump rayon from 1.8.0 to 1.8.1 by Dependabot (@dependabot) in #1059
• Add typing stubs for universal functions by Ivan Carvalho (@IvanIsCoding) in #1010
• Add method to return edge indices from endpoints by Pieter Eendebak (@eendebakpt) in #1055
• Add function to return the bridges of the graph by Yiming Zhang (@inmzhang) in #1058
• Finalize type signatures and enforce for all future functions by Matthew Treinish (@mtreinish) in #1061
• Unnest rustworkx tests folder by Ivan Carvalho (@IvanIsCoding) in #1062
• Update contribution guidelines around type annotations by Matthew Treinish (@mtreinish) in #1063
• Add option to specify preset colors to graph_greedy_color by Matthew Treinish (@mtreinish) in #1060
• Adding edge coloring algorithm for bipartite graphs by Alexander Ivrii (@alexanderivrii) in #1026
• Prepare 0.14.0 release by Matthew Treinish (@mtreinish) in #1065

New Contributors

Note truncated.

Prelude

This is a new feature release of Rustworkx that adds many new features to the library. The highlights of this release are:

Fully type annotated for support with mypy and other tooling

Improvements to the graph coloring functions

This release supports running with Python 3.8 through 3.12. The minimum supported Rust version for building rustworkx and rustworkx-core from source is now 1.64.0. The minimum supported version of macOS for this release has been increased from 10.9 to 10.12. Also, the Linux ppc64le and s390x platform support has been downgraded from Tier 3 to Tier 4 .

New Features

Added two new random graph generator functions, directed_barabasi_albert_graph() and barabasi_albert_graph() , to generate a random graph using Barabási–Albert preferential attachment to extend an input graph. For example:

import rustworkx from rustworkx.visualization import mpl_draw starting_graph = rustworkx . generators . path_graph ( 10 ) random_graph = rustworkx . barabasi_albert_graph ( 20 , 10 , initial_graph = starting_graph ) mpl_draw ( random_graph )

Added a new function to the rustworkx-core module rustworkx_core::generators barabasi_albert_graph() which is used to generate a random graph using Barabási–Albert preferential attachment to extend an input graph.

Added a new function all_shortest_paths() (and the graph type specific variants: graph_all_shortest_paths() and digraph_all_shortest_paths() ) that finds every simple shortest path two nodes in a graph.

Added a new function to the rustworkx-core module rustworkx_core::shortest_path module all_shortest_path() which is used to find every simple shortest path in a graph.

Added a new function two_color to the rustworkx-core rustworkx_core::coloring module. This function is used to compute a two coloring of a graph and can also be used to determine if a graph is bipartite as it returns None when a two coloring is not possible.

Added a new function, two_color() , which is used to compute a two coloring for a graph. For example:

import rustworkx as rx from rustworkx.visualization import mpl_draw graph = rx . generators . heavy_square_graph ( 5 ) colors = rx . two_color ( graph ) mpl_draw ( graph , node_color = [ colors [ i ] for i in range ( len ( graph ))])

Added a new function, is_bipartite() to determine whether a given graph object is bipartite or not.

Added a new function, bridges() that finds the bridges of an undirected PyGraph . Bridges are edges that, if removed, would increase the number of connected components of a graph. For example:

import rustworkx from rustworkx.visualization import mpl_draw graph = rustworkx . PyGraph () graph . extend_from_edge_list ([ ( 0 , 1 ), ( 1 , 2 ), ( 0 , 2 ), ( 1 , 3 ) ]) bridges = rustworkx . bridges ( graph ) bridges_set = [ set ( edge ) for edge in bridges ] colors = [] for edge in graph . edge_list (): color = "red" if set ( edge ) in bridges_set else "black" colors . append ( color ) mpl_draw ( graph , edge_color = colors )

Added a new function bridges to the rustworkx_core:connectivity:biconnected module that finds the bridges of an undirected graph. Bridges are edges that, if removed, would increase the number of connected components of a graph. For example:

Added a new function, clear() that clears all nodes and edges from a PyGraph or PyDiGraph .

Added a new function, clear_edges() that clears all edges for PyGraph or rustworkx.PyDiGraph without modifying nodes.

Added method edge_indices_from_endpoints() which returns the indices of all edges between the specified endpoints. For PyDiGraph there is a corresponding method that returns the directed edges.

The PyGraph and the PyDiGraph classes have a new method filter_nodes() (or filter_nodes() ). This method returns a NodeIndices object with the resulting nodes that fit some abstract criteria indicated by a filter function. For example:

from rustworkx import PyGraph graph = PyGraph () graph . add_nodes_from ( list ( range ( 5 ))) # Adds nodes from 0 to 5 def my_filter_function ( node ): return node > 2 indices = graph . filter_nodes ( my_filter_function ) print ( indices )

NodeIndices[3, 4]

The PyGraph and the PyDiGraph classes have a new method filter_edges() (or filter_edges() ). This method returns a EdgeIndices object with the resulting edges that fit some abstract criteria indicated by a filter function. For example:

from rustworkx import PyGraph from rustworkx.generators import complete_graph graph = PyGraph () graph . add_nodes_from ( range ( 3 )) graph . add_edges_from ([( 0 , 1 , 'A' ), ( 0 , 1 , 'B' ), ( 1 , 2 , 'C' )]) def my_filter_function ( edge ): if edge : return edge == 'B' return False indices = graph . filter_edges ( my_filter_function ) print ( indices )

EdgeIndices[1]

Added a new algorithm function, rustworkx.floyd_warshall_successor_and_distance() , that calculates the shortest path distance and the successor nodes for all node pairs in PyGraph and PyDiGraph graphs.

Added a new function, graph_line_graph() to construct a line graph of a PyGraph object.

The line graph (L(G)) of a graph (G) represents the adjacencies between edges of G. (L(G)) contains a vertex for every edge in (G) , and (L(G)) contains an edge between two vertices if the corresponding edges in (G) have a vertex in common.

import rustworkx as rx from rustworkx.visualization import mpl_draw graph = rx . PyGraph () node_a = graph . add_node ( "a" ) node_b = graph . add_node ( "b" ) node_c = graph . add_node ( "c" ) node_d = graph . add_node ( "d" ) edge_ab = graph . add_edge ( node_a , node_b , 1 ) edge_ac = graph . add_edge ( node_a , node_c , 1 ) edge_bc = graph . add_edge ( node_b , node_c , 1 ) edge_ad = graph . add_edge ( node_a , node_d , 1 ) out_graph , out_edge_map = rx . graph_line_graph ( graph ) assert out_graph . node_indices () == [ 0 , 1 , 2 , 3 ] assert out_graph . edge_list () == [( 3 , 1 ), ( 3 , 0 ), ( 1 , 0 ), ( 2 , 0 ), ( 2 , 1 )] assert out_edge_map == { edge_ab : 0 , edge_ac : 1 , edge_bc : 2 , edge_ad : 3 } mpl_draw ( out_graph , with_labels = True )

Added a new function, graph_greedy_edge_color() to color edges of a PyGraph object using a greedy approach.

This function works by greedily coloring the line graph of the given graph.

import rustworkx as rx from rustworkx.visualization import mpl_draw graph = rx . generators . cycle_graph ( 7 ) edge_colors = rx . graph_greedy_edge_color ( graph ) assert edge_colors == { 0 : 0 , 1 : 1 , 2 : 0 , 3 : 1 , 4 : 0 , 5 : 1 , 6 : 2 } mpl_draw ( graph , edge_color = [ edge_colors [ i ] for i in range ( graph . num_edges ())])

Added a new function, graph_misra_gries_edge_color() to color edges of a PyGraph object using the Misra-Gries edge coloring algorithm.

The above algorithm is described in the paper paper: “A constructive proof of Vizing’s theorem” by Misra and Gries, 1992.

The coloring produces at most (d + 1) colors where (d) is the maximum degree of the graph.

import rustworkx as rx from rustworkx.visualization import mpl_draw graph = rx . generators . cycle_graph ( 7 ) edge_colors = rx . graph_misra_gries_edge_color ( graph ) assert edge_colors == { 0 : 0 , 1 : 1 , 2 : 2 , 3 : 0 , 4 : 1 , 5 : 0 , 6 : 2 } mpl_draw ( graph , edge_color = [ edge_colors [ i ] for i in range ( graph . num_edges ())])

Added a new function, isolates() , which is used to find the isolates (nodes with a degree of 0) in a PyDiGraph or PyGraph .

Added a new function, isolates() to the rustworkx-core rustworkx_core::connectivity module which is used to find the isolates (nodes with a degree of 0).

Added method substitute_node_with_subgraph to the PyGraph class.

import rustworkx from rustworkx.visualization import * # Needs matplotlib/ graph = rustworkx . generators . complete_graph ( 5 ) sub_graph = rustworkx . generators . path_graph ( 3 ) # Replace node 4 in this graph with sub_graph # Make sure to connect the graphs at node 2 of the sub_graph # This is done by passing a function that returns 2 graph . substitute_node_with_subgraph ( 4 , sub_graph , lambda _ , __ , ___ : 2 ) # Draw the updated graph mpl_draw ( graph , with_labels = True )

Added a new function topological_generations() which stratifies a PyDiGraph into topological generations.

Added a new exception class GraphNotBipartite which is raised when a graph is not bipartite. The sole user of this exception is the graph_bipartite_edge_color() which will raise it when the user provided graph is not bipartite.

Added a new function, graph_bipartite_edge_color() to color edges of a PyGraph object. The function first checks whether a graph is bipartite, raising exception of type GraphNotBipartite if this is not the case. Otherwise, the function calls the algorithm for edge-coloring bipartite graphs, and returns a dictionary with key being the edge index and value being the assigned color.

The implemented algorithm is based on the paper “A simple algorithm for edge-coloring bipartite multigraphs” by Noga Alon, 2003.

The coloring produces at most (d) colors where (d) is the maximum degree of a node in the graph. The algorithm runs in time (\mathcal{O}(n + m\log{}m)) , where (n) is the number of vertices and (m) is the number of edges in the graph.

import rustworkx as rx from rustworkx.visualization import mpl_draw graph = rx . generators . cycle_graph ( 8 ) edge_colors = rx . graph_bipartite_edge_color ( graph ) assert edge_colors == { 0 : 0 , 1 : 1 , 2 : 0 , 3 : 1 , 4 : 0 , 5 : 1 , 6 : 0 , 7 : 1 } mpl_draw ( graph , edge_color = [ edge_colors [ i ] for i in range ( graph . num_edges ())])

Added two new random graph generator functions, directed_random_bipartite_graph() and undirected_random_bipartite_graph() , to generate a random bipartite graph. For example:

import rustworkx as rx from rustworkx.visualization import mpl_draw random_graph = rx . undirected_random_bipartite_graph ( 10 , 5 , 0.5 , seed = 20 ) layout = rx . bipartite_layout ( random_graph , set ( range ( 10 ))) mpl_draw ( random_graph , pos = layout )

The functions graph_adjacency_matrix() and digraph_adjacency_matrix() now have the option to adjust parallel edge behavior. Instead of just the default sum behavior, the value in the output matrix can be the minimum (“min”), maximum (“max”), or average (“avg”) of the weights of the parallel edges. For example:

import rustworkx as rx graph = rx . PyGraph () a = graph . add_node ( "A" ) b = graph . add_node ( "B" ) c = graph . add_node ( "C" ) graph . add_edges_from ([ ( a , b , 3.0 ), ( a , b , 1.0 ), ( a , c , 2.0 ), ( b , c , 7.0 ), ( c , a , 1.0 ), ( b , c , 2.0 ), ( a , b , 4.0 ) ]) print ( "Adjacency Matrix with Summed Parallel Edges" ) print ( rx . graph_adjacency_matrix ( graph , weight_fn = lambda x : float ( x ))) print ( "Adjacency Matrix with Averaged Parallel Edges" ) print ( rx . graph_adjacency_matrix ( graph , weight_fn = lambda x : float ( x ), parallel_edge = "avg" ))

Adjacency Matrix with Summed Parallel Edges [[0. 8. 3.] [8. 0. 9.] [3. 9. 0.]] Adjacency Matrix with Averaged Parallel Edges [[0. 2.66666667 1.5 ] [2.66666667 0. 4.5 ] [1.5 4.5 0. ]]

The rustworkx Python package is now fully typed with mypy . Building off of the previous 0.13.0 release which introduced partial type annotations to the library, rustworkx now includes type annotations for the entire public API.

Added a new exception class InvalidMapping which is raised when a function receives an invalid mapping. The sole user of this exception is the graph_token_swapper() which will raise it when the user provided mapping is not feasible on the provided graph.

Added has_path() which accepts as arguments a PyGraph or PyDiGraph and checks if there is a path from source to destination

from rustworkx import PyDiGraph , has_path graph = PyDiGraph () a = graph . add_node ( "A" ) b = graph . add_node ( "B" ) c = graph . add_node ( "C" ) edge_list = [( a , b , 1 ), ( b , c , 1 )] graph . add_edges_from ( edge_list ) path_exists = has_path ( graph , a , c ) assert ( path_exists == True ) path_exists = has_path ( graph , c , a ) assert ( path_exists == False )

Added support for musl Linux platforms on x86_64 at Tier 3 and aarch64 at Tier 4 .

Added a new keyword argument, preset_color_fn , to graph_greedy_color() which is used to provide preset colors for specific nodes when computing the graph coloring. You can optionally pass a callable to that argument which will be passed node index from the graph and is either expected to return an integer color to use for that node, or None to indicate there is no preset color for that node. For example:

import rustworkx as rx from rustworkx.visualization import mpl_draw graph = rx . generators . generalized_petersen_graph ( 5 , 2 ) def preset_colors ( node_index ): if node_index == 0 : return 3 coloring = rx . graph_greedy_color ( graph , preset_color_fn = preset_colors ) colors = [ coloring [ node ] for node in graph . node_indices ()] layout = rx . shell_layout ( graph , nlist = [[ 0 , 1 , 2 , 3 , 4 ],[ 6 , 7 , 8 , 9 , 5 ]]) mpl_draw ( graph , node_color = colors , pos = layout )

Added a new function greedy_node_color_with_preset_colors to the rustworkx-core module coloring . This new function is identical to the rustworkx_core::coloring::greedy_node_color except it has a second preset parameter which is passed a callable which is used to provide preset colors for particular node ids.

Added a new function, transitive_reduction() which returns the transitive reduction of a given PyDiGraph and a dictionary with the mapping of indices from the given graph to the returned graph. The given graph must be a Directed Acyclic Graph (DAG). For example:

from rustworkx import PyDiGraph from rustworkx import transitive_reduction graph = PyDiGraph () a = graph . add_node ( "a" ) b = graph . add_node ( "b" ) c = graph . add_node ( "c" ) d = graph . add_node ( "d" ) e = graph . add_node ( "e" ) graph . add_edges_from ([ ( a , b , 1 ), ( a , d , 1 ), ( a , c , 1 ), ( a , e , 1 ), ( b , d , 1 ), ( c , d , 1 ), ( c , e , 1 ), ( d , e , 1 ) ]) tr , _ = transitive_reduction ( graph ) list ( tr . edge_list ())

[(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]

Ref: https://en.wikipedia.org/wiki/Transitive_reduction

Upgrade Notes

The minimum supported rust version (MSRV) for rustworkx and rustworkx-core has been raised to 1.64.0. Previously you could build rustworkx or rustworkx-core using an MSRV of 1.56.1. This change was necessary as the upstream dependencies of rustworkx have adopted newer MSRVs.

The minimum required Python version was raised to Python 3.8. To use rustworkx, please ensure you are using Python >= 3.8.

The rustworkx function graph_token_swapper() now will raise an InvalidMapping exception instead of a PanicException when an invalid mapping is requested. This was done because a PanicException is difficult to catch by design as it is used to indicate an unhandled error. Using

The return type of the rustworkx-core function token_swapper() has been changed from Vec<(NodeIndex, NodeIndex)> to be Result<Vec<(NodeIndex, NodeIndex)>, MapNotPossible> . This change was necessary to return an expected error condition if a mapping is requested for a graph that is not possible. For example is if you have a disjoint graph and you’re trying to map nodes without any connectivity:

use rustworkx_core :: token_swapper ; use rustworkx_core :: petgraph ; let g = petgraph :: graph :: UnGraph :: < (), () > :: from_edges ( & [( 0 , 1 ), ( 2 , 3 ) ]); let mapping = HashMap :: from ([ ( NodeIndex :: new ( 2 ), NodeIndex :: new ( 0 )), ( NodeIndex :: new ( 1 ), NodeIndex :: new ( 1 )), ( NodeIndex :: new ( 0 ), NodeIndex :: new ( 2 )), ( NodeIndex :: new ( 3 ), NodeIndex :: new ( 3 )), ]); token_swapper ( & g , mapping , Some ( 10 ), Some ( 4 ), Some ( 50 ));

will now return Err(MapNotPossible) instead of panicking. If you were using this function before you’ll need to handle the result type.

Support for the Linux ppc64le pllatform has changed from tier 3 to tier 4 (as documented in Platform Support ). This is a result of no longer being able to run tests during the pre-compiled wheel publishing jobs due to constraints in the available CI infrastructure. There hopefully shouldn’t be any meaningful impact resulting from this change, but as there are no longer tests being run to validate the binaries prior to publishing them there are no longer guarantees that the wheels for ppc64le are fully functional (although the likelihood they are is still high as it works on other platforms). If any issues are encountered with ppc64le Linux please open an issue.

For macOS the minimum version of macOS is now 10.12. Previously, the precompiled binary wheel packages for macOS x86_64 were published with support for >=10.9. However, because of changes in the support policy for the Rust programming language the minimum version needed to raised to macOS 10.12. If you’re using Qiskit on macOS 10.9 you can probably build Qiskit from source while the rustworkx MSRV (minimum supported Rust version) is < 1.74, but the precompiled binaries published to PyPI will only be compatible with macOS >= 10.12.

Support for the Linux s390x platform has changed from tier 3 to tier 4 (as documented in Platform Support ). This is a result of no longer being able to run tests during the pre-compiled wheel publishing jobs due to constraints in the available CI infrastructure. There hopefully shouldn’t be any meaningful impact resulting from this change, but as there are no longer tests being run to validate the binaries prior to publishing them there are no longer guarantees that the wheels for s390x are fully functional (although the likelihood they are is still high as it works on other platforms). If any issues are encountered with s390x Linux please open an issue.

Deprecation Notes

The legacy retworkx package that operates as a backwards compatibility alias for rustworkx has been marked as deprecated. If you’re using the retworkx package it will now emit a DeprecationWarning on import.

Bug Fixes

Fixed the behavior of graph_all_simple_paths() and digraph_all_simple_paths() when min_depth is set to 0 . Refer to #955 for more information.

Fixed an issue where the directed_gnp_random_graph() and the gnp_random_graph() for directed graphs produced a graph where lower node numbers had only a small number of edges compared to what was expected.

Other Notes

This version of rustworkx is explicitly pinned to the Numpy 1.x series, because it includes compiled extensions that are not yet compiled against the as-yet-unreleased Numpy 2.x series. We will release a new version of rustworkx with Numpy 2.x support as soon as feasible.

We cannot prevent your package manager from resolving to older versions of rustworkx (which do not have the same pin but are still likely to be incompatible) if you forcibly try to install rustworkx alongside Numpy 2, before we have released a compatible version.

Prelude

This release is major feature release of Rustworkx that adds some new features to the library. The highlights of this release are:

An expansion of the functions exposed by rustworkx-core to including a new graph generator module.

New link analysis functions such as page rank

Expanded centrality measure functions

Added partial type annotations to the library including for the PyDiGraph and PyGraph classes. This enables type checking with mypy

This is also the final rustworkx release that supports running with Python 3.7. Starting in the 0.14.0 release Python >= 3.8 will be required to use rustworkx. This release also increased the minimum supported Rust version for compiling rustworkx and rustworkx-core from source to 1.56.1.

New Features

Added a new method, make_symmetric() , to the PyDiGraph class. This method is used to make all the edges in the graph symmetric (there is a reverse edge in the graph for each edge). For example:

import rustworkx as rx from rustworkx.visualization import graphviz_draw graph = rx . generators . directed_path_graph ( 5 , bidirectional = False ) graph . make_symmetric () graphviz_draw ( graph )

Added a new function, edge_betweenness_centrality() to compute edge betweenness centrality of all edges in a PyGraph or PyDiGraph object. The algorithm used in this function is based on: Ulrik Brandes, On Variants of Shortest-Path Betweenness Centrality and their Generic Computation. Social Networks 30(2):136-145, 2008. Edge betweenness centrality of an edge (e) is the sum of the fraction of all-pairs shortest paths that pass through (e)

[c_B(e) =\sum_{s,t \in V} \frac{\sigma(s, t|e)}{\sigma(s, t)}]

where (V) is the set of nodes, (\sigma(s, t)) is the number of shortest ((s, t)) -paths, and (\sigma(s, t|e)) is the number of those paths passing through edge (e) . For example, the following computes the edge betweenness centrality for all edges in a 5x5 grid graph and uses the result to color the edges in a graph visualization:

import rustworkx from rustworkx.visualization import mpl_draw graph = rustworkx . generators . grid_graph ( 5 , 5 ) btw = rustworkx . edge_betweenness_centrality ( graph ) # Color edges in graph visualization with edge betweenness centrality colors = [] for i in graph . edge_indices (): colors . append ( btw [ i ]) mpl_draw ( graph , edge_color = colors )

Added a new function to rustworkx-core edge_betweenness_centrality to the rustworkx_core:centrality module which computes the edge betweenness centrality of all edges in a given graph.

Two new functions, find_cycle and cycle_basis , have been added to the rustworkx-core crate in the connectivity module. These functions can be used to find a cycle in a petgraph graph or to find the cycle basis of a graph.

Added a new function, hits() which is used to compute the hubs and authorities for all nodes in a given directed graph. For example:

import rustworkx as rx from rustworkx.visualization import mpl_draw graph = rx . generators . directed_hexagonal_lattice_graph ( 2 , 2 ) hubs , _ = rx . hits ( graph ) # Generate a color list colors = [] for node in graph . node_indices (): hub_score = hubs [ node ] graph [ node ] = hub_score colors . append ( hub_score ) mpl_draw ( graph , with_labels = True , node_color = colors , node_size = 650 , labels = lambda x : " {0:.2f} " . format ( x ) )

Added a new function, katz_centrality() which is used to compute the Katz centrality for all nodes in a given graph. For example:

import rustworkx as rx from rustworkx.visualization import mpl_draw graph = rx . generators . hexagonal_lattice_graph ( 4 , 4 ) centrality = rx . katz_centrality ( graph ) # Generate a color list colors = [] for node in graph . node_indices (): centrality_score = centrality [ node ] graph [ node ] = centrality_score colors . append ( centrality_score ) mpl_draw ( graph , with_labels = True , node_color = colors , node_size = 650 , labels = lambda x : " {0:.2f} " . format ( x ) )

Added a new function to rustworkx-core katz_centrality to the rustworkx_core::centrality modules which is used to compute the Katz centrality for all nodes in a given graph.

Added a new function, longest_simple_path() which is used to search all the simple paths between all pairs of nodes in a graph and return the longest path found. For example:

import rustworkx as rx graph = rx . generators . binomial_tree_graph ( 5 ) longest_path = rx . longest_simple_path ( graph ) print ( longest_path )

NodeIndices[31, 30, 28, 24, 16, 0, 8, 12, 14, 15]

Then visualizing the nodes in the longest path found:

from rustworkx.visualization import mpl_draw path_set = set ( longest_path ) colors = [] for index in range ( len ( graph )): if index in path_set : colors . append ( 'r' ) else : colors . append ( '#1f78b4' ) mpl_draw ( graph , node_color = colors )

Added a new function longest_simple_path_multiple_targets() to rustworkx-core. This function will return the longest simple path from a source node to a HashSet of target nodes.

Added a new function, pagerank() which is used to compute the PageRank score for all nodes in a given directed graph. For example:

import rustworkx as rx from rustworkx.visualization import mpl_draw graph = rx . generators . directed_hexagonal_lattice_graph ( 2 , 2 ) ranks = rx . pagerank ( graph ) # Generate a color list colors = [] for node in graph . node_indices (): pagerank_score = ranks [ node ] graph [ node ] = pagerank_score colors . append ( pagerank_score ) mpl_draw ( graph , with_labels = True , node_color = colors , node_size = 650 , labels = lambda x : " {0:.2f} " . format ( x ) )

Three new random graph generators, gnp_random_graph , gnm_random_graph and random_geometric_graph , have been added to the rustworkx-core crate in the generators module. The gnp_random_graph takes inputs of the number of nodes and a probability for adding edges. The gnp_random_graph takes inputs of the number of nodes and number of edges. The random_geometric_graph creates a random graph within an n-dimensional cube.

Added a new function, bfs_predecessors() , which is used to return a list of predecessors in a reversed bread-first traversal from a specified node. This is analogous to the existing bfs_successors() method.

Add a method find_predecessor_node_by_edge() to get the immediate predecessor of a node which is connected by the specified edge.

Added a new function, graph_token_swapper() , which performs an approximately optimal token swapping algorithm based on:

Approximation and Hardness for Token Swapping by Miltzow et al. (2016) https://arxiv.org/abs/1602.05150

that supports partial mappings (i.e. not-permutations) for graphs with missing tokens.

Added a new function token_swapper() to the new rustworkx-core module rustworkx_core::token_swapper . This function performs an approximately optimal token swapping algorithm based on:

Approximation and Hardness for Token Swapping by Miltzow et al. (2016) https://arxiv.org/abs/1602.05150

that supports partial mappings (i.e. not-permutations) for graphs with missing tokens.

Added a new function, closeness_centrality() to compute the closeness centrality of all nodes in a PyGraph or PyDiGraph object.

The closeness centrality of a node (u) is defined as the the reciprocal of the average shortest path distance to (u) over all (n-1) reachable nodes. In it’s general form this can be expressed as:

[C(u) = \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)},]

where (d(v, u)) is the shortest-path distance between (v) and (u) , and (n) is the number of nodes that can reach (u) . For example, to visualize the closeness centrality of a graph:

import matplotlib.pyplot as plt import rustworkx as rx from rustworkx.visualization import mpl_draw graph = rx . generators . hexagonal_lattice_graph ( 4 , 4 ) centrality = rx . closeness_centrality ( graph ) # Generate a color list colors = [] for node in graph . node_indices (): colors . append ( centrality [ node ]) # Generate a visualization with a colorbar plt . rcParams [ 'figure.figsize' ] = [ 15 , 10 ] ax = plt . gca () sm = plt . cm . ScalarMappable ( norm = plt . Normalize ( vmin = min ( centrality . values ()), vmax = max ( centrality . values ()) )) plt . colorbar ( sm , ax = ax ) plt . title ( "Closeness Centrality of a 4 x 4 Hexagonal Lattice Graph" ) mpl_draw ( graph , node_color = colors , ax = ax )

Added new generator functions, empty_graph() , and directed_empty_graph() to the rustworkx.generators module that will generate an empty graph. For example:

import rustworkx.generators from rustworkx.visualization import mpl_draw graph = rustworkx . generators . empty_graph ( 4 ) mpl_draw ( graph )

Added new generator functions, complete_graph() , and directed_complete_graph() to the rustworkx.generators module that will generate a complete graph. These functions are equivalent to calling the mesh_graph() and directed_mesh_graph() functions. For example:

import rustworkx.generators from rustworkx.visualization import mpl_draw graph = rustworkx . generators . complete_graph ( 4 ) mpl_draw ( graph )

Added a new generators module to the rustworkx-core crate. This module contains functions for generating graphs. These functions are generic on the output graph type and can be used to create graph objects for any type that implement the required petgraph traits.

Added partial type annotations to the library, including for the PyDiGraph and PyGraph classes. This enables statically type checking with mypy .

Added a new function, greedy_node_color , to rustworkx-core in a new coloring module. It colors a graph using a greedy graph coloring algorithm.

The function core_number has been added to the rustworkx-core crate in the connectivity module. It computes the k-core number for the nodes in a graph.

Upgrade Notes

Passing a negative value to the probability argument to the gnp_directed_random_graph() or the gnp_undirected_random_graph() function will now cause an OverflowError to be raised. Previously, a ValueError would be raised in this situation. This was changed to be consistent with other similar error conditions in other functions in the library.

The minimum supported Rust version has been increased from 1.48 to 1.56.1. This applies to both building the rustworkx package from source as well as the rustworkx-core crate. This change was made to facilitate using newer versions of our upstream dependencies as well as leveraging newer Rust language features.

Bug Fixes

Fixed the check_cycle attribute not being preserved when copying PyDiGraph with copy.copy() and copy.deepcopy() . Fixed #836

Fixed an issue when using copy.deepcopy() on PyDiGraph and PyGraph objects when there were removed edges from the graph object. Previously, if there were any holes in the edge indices caused by the removal the output copy of the graph object would incorrectly have flatten the indices. This has been corrected so that the edge indices are recreated exactly after a deepcopy() . Fixed #585

Fixed a compatibility issue when building rustworkx-core with priority-queue 1.3.0. Fixed #744

Fixed an issue with several PyDiGraph and PyGraph methods that removed nodes where previously when calling these methods the PyDiGraph.node_removed attribute would not be updated to reflect that nodes were removed.

Fixed an issue with the custom sequence return types, BFSSuccessors , NodeIndices , EdgeList , WeightedEdgeList , EdgeIndices , and Chains where they previously were missing certain attributes that prevented them being used as a sequence for certain built-in functions such as reversed() . Fixed #696 .

rustworkx.PyGraph.add_edge() and rustworkx.PyDiGraph.add_edge() and now raises an IndexError when one of the nodes does not exist in the graph. Previously, it caused the Python interpreter to exit with a PanicException

Prelude

This release introduces some major changes to the Rustworkx (formerly retworkx) project. The first change is the library has been renamed from retworkx to rustworkx, and the retworkx-core rust crate has been renamed rustworkx-core. This was done out of respect for a request from the maintainers of the NetworkX library. For the current release the retworkx library will still continue to work as it has without any notification, but starting in the 0.13.0 release a DeprecationWarning will be emitted when importing from retworkx and in the 1.0.0 release we will drop support for the legacy name. For the retworkx-core crate, there will no longer be any releases under that name on crates.io and all future versions of the library will be released as rustworkx-core.

Additionally this release adds support for Python 3.11 and also moves to manylinux2014 for all precompiled Linux binaries we publish to PyPI. The minimum supported Rust version for building rustworkx from source has increased to Rust 1.48.

This release also includes several new features, some highlights are:

Support for graph attributes under the attrs attribute

New serialization format support (a graphml parser, read_graphml() , and a node link JSON generator, node_link_json() )

• New algorithms functions including:

Eigenvector Centrality

Stoer–Wagner Min-Cut algorithm

Bellman-Ford shortest path algorithm

New Features

Added a new function, eigenvector_centrality() which is used to compute the eigenvector centrality for all nodes in a given graph. For example:

import rustworkx as rx from rustworkx.visualization import mpl_draw graph = rx . generators . hexagonal_lattice_graph ( 4 , 4 ) centrality = rx . eigenvector_centrality ( graph ) # Generate a color list colors = [] for node in graph . node_indices (): centrality_score = centrality [ node ] graph [ node ] = centrality_score colors . append ( centrality_score ) mpl_draw ( graph , with_labels = True , node_color = colors , node_size = 650 , labels = lambda x : " {0:.2f} " . format ( x ) )

Added a new function to rustworkx-core eigenvector_centrality to the rustworkx_core::centrality modules which is used to compute the eigenvector centrality for all nodes in a given graph.

Added a new keyword arguments, index_output , to the layers() function. When set to True the output of the function is a list of layers as node indices. The default output is still a list of layers of node data payloads as before.

Added a new function, node_link_json() , which is used to generate JSON node-link data representation of an input PyGraph or PyDiGraph object. For example, running:

import rustworkx graph = rustworkx . generators . path_graph ( weights = [ 'a' , 'b' , 'c' ]) print ( rustworkx . node_link_json ( graph , node_attrs = lambda n : { 'label' : n }))

will output a JSON payload equivalent (identical except for whitespace) to:

{ "directed" : false , "multigraph" : true , "attrs" : null , "nodes" : [ { "id" : 0 , "data" : { "label" : "a" } }, { "id" : 1 , "data" : { "label" : "b" } }, { "id" : 2 , "data" : { "label" : "c" } } ], "links" : [ { "source" : 0 , "target" : 1 , "id" : 0 , "data" : null }, { "source" : 1 , "target" : 2 , "id" : 1 , "data" : null } ] }

Added a new algorithm function, rustworkx.stoer_wagner_min_cut() that uses the Stoer Wagner algorithm for computing a weighted minimum cut in an undirected PyGraph . For example:

import rustworkx from rustworkx.visualization import mpl_draw graph = rustworkx . generators . grid_graph ( 2 , 2 ) cut_val , partition = rustworkx . stoer_wagner_min_cut ( graph ) colors = [ 'orange' if node in partition else 'blue' for node in graph . node_indexes () ] mpl_draw ( graph , node_color = colors )

Add two new functions which calculates the tensor product of two graphs graph_tensor_product() for undirected graphs and digraph_tensor_product() for directed graphs. For example:

import rustworkx from rustworkx.visualization import mpl_draw graph_1 = rustworkx . generators . path_graph ( 2 ) graph_2 = rustworkx . generators . path_graph ( 3 ) graph_product , _ = rustworkx . graph_tensor_product ( graph_1 , graph_2 ) mpl_draw ( graph_product )

Added new functions to compute the all-pairs shortest path in graphs with negative edge weights using the Bellman-Ford algorithm with the SPFA heuristic:

rustworkx.all_pairs_bellman_ford_path_lengths()

rustworkx.all_pairs_bellman_ford_shortest_paths()

Added a new function all_pairs_all_simple_paths() which is used to return all simple paths between all pairs of nodes in a graph. It can also be used with a optional min_depth and cutoff parameters to filter the results based on path lengths. For example:

from rustworkx.generators import grid_graph from rustworkx import all_pairs_all_simple_paths g = grid_graph ( 2 , 3 ) paths = all_pairs_all_simple_paths ( g , min_depth = 3 , cutoff = 3 )

will return a dictionary of dictionaries where the 2 dictionary keys are the node indices and the inner value is the list of all simple paths of length 3 between those 2 nodes.

The rustworkx-core rustworkx_core::connectivity module has a new function all_simple_paths_multiple_targets this is similar to the all_simple_paths() method in petgraph’s algo module but instead of returning an iterator that will yield the all the simple path from a source to the target node it instead will build a DictMap of all the simple paths from a source node to all targets in a provided HashSet of target node indices.

Added new functions to compute negative cycles and the shortest path in graphs with negative edge weights using the Bellman-Ford algorithm with the SPFA heuristic:

rustworkx.find_negative_cycle()

rustworkx.bellman_ford_shortest_path_lengths()

rustworkx.bellman_ford_shortest_paths()

rustworkx.negative_edge_cycle()

Added a concept of graph attributes to the PyDiGraph and PyGraph classes. The attributes are accessible via the attrs attribute of the graph objects and can be modified in place. Additionally, they can be set initially when creating the object via the constructor. For example:

import rustworkx as rx graph = rx . PyGraph ( attrs = dict ( day = "Friday" )) graph . attrs [ 'day' ] = "Monday"

The attributes can contain any Python object, not just a dictionary. For example:

class Day : def init ( self , day ): self . day = day graph = rx . PyGraph ( attrs = Day ( "Friday" )) graph . attrs = Day ( "Monday" )

If attrs is not set it will default to None .

The PyGraph.subgraph() and PyDiGraph.subgraph() methods have a new keyword argument preserve_attributes which can be set to True to copy by reference the contents of the attrs attribute from the graph to the subgraph’s attrs attribute.

Implements a new function is_planar() that checks whether an undirected PyGraph is planar.

import rustworkx as rx graph = rx . generators . mesh_graph ( 5 ) print ( 'Is K_5 graph planar?' , rx . is_planar ( graph ))

Is K_5 graph planar? False

The rustworkx-core connectivity module has 3 new functions, connected_components , number_connected_components , and bfs_undirected . These functions are based on the existing connected_components() , number_connected_components() , and bfs_undirected() in rustworkx.

Added a new function read_graphml() that generates a rustworkx graph object (a PyGraph or a PyDiGraph ) from a file written in GraphML format. GraphML is an xml serialization format for representing graph files.

Added a new function, simple_cycles() , which is an implementation of Johnson’s algorithm for finding all elementary cycles in a directed graph.

Upgrade Notes

The return type for the PyGraph method add_edges_from() and add_edges_from_no_data() has changed from a list of integer edge indices to an EdgeIndices object. The EdgeIndices class is a read-only sequence type of integer edge indices. For the most part this should be fully compatible except if you were mutating the output list or were explicitly type checking the return. In these cases you can simply cast the EdgeIndices object with list() .

This release no longer provides binaries that support the manylinux2010 packaging specification. All the precompiled binaries for Linux platforms are built against manylinux2014 . This change is required due to changes in the GLIBC versions supported by the latest versions of the Rust compiler in addition to the manylinux2010 platform no longer being supported. If you need to run Rustworkx on a platform only compatible with manylinux2010 starting with this release you will need to build and install from source (which includes the sdist published to PyPI, so pip install rustworkx will continue to work assuming you have a Rust compiler installed) and also use a Rust compiler with a version < 1.64.0.

The minimum supported Rust version for building rustworkx has been raised from 1.41 to 1.48. To compile rustworkx from source you will need to ensure you have at Rustc >=1.48 installed.

The minimum supported Python version for using rustworkx has been raised to Python 3.7. To use rustworkx you will need to ensure you are using Python >=3.7.

The retworkx package has been renamed to rustworkx . This was done out of respect for a request from the maintainers of the NetworkX library. For the time being the retworkx name will continue to work, however any package requirements or imports using retworkx should be renamed to rustworkx .

Bug Fixes

The custom sequence return classes:

BFSSSuccessors

NodeIndices

EdgeList

WeightedEdgeList

EdgeIndices

Chains

now correctly handle slice inputs to getitem . Previously if you tried to access a slice from one of these objects it would raise a TypeError . For example, if you had a NodeIndices object named nodes containing [0, 1, 3, 4, 5] if you did something like:

nodes [ 0 : 3 ]

it would return a new NodeIndices object containing [0, 1, 3] Fixed #590