repository·main·Indexed 23 days ago
https://github.com/qiskit/rustworkxA high-performance, general-purpose graph library for Python implemented in Rust. It provides efficient data structures and algorithms for directed and undirected graphs, including centrality measures, graph coloring, connectivity analysis, and DAG-specific algorithms. The project also includes rustworkx-core, a pure Rust graph algorithm library built on top of petgraph.
rustworkx-core is a pure Rust graph algorithm library built on top of petgraph. While the main rustworkx project is a Python library, rustworkx-core provides a stable Rust API for downstream Rust crates. It offers additional algorithms and functionality that are not available in the base petgraph library.rustworkx is a high-performance Python package for working with graphs and complex networks, written in Rust. It is designed for creating, interacting with, and studying graphs.
Key features include:
rustworkx provides several functions to generate random graphs based on different mathematical models. These generators allow you to create complex graph structures (directed or undirected) for testing, simulation, or algorithmic analysis.
Available generator types include:
directed_gnp_random_graph, undirected_gnp_random_graphdirected_gnm_random_graph, undirected_gnm_random_graphdirected_sbm_random_graph, undirected_sbm_random_graphrandom_geometric_graph, hyperbolic_random_graphbarabasi_albert_graph, directed_barabasi_albert_graphdirected_random_bipartite_graph, undirected_random_bipartite_graphrandom_regular_graphThe rustworkx library provides a suite of functions to analyze graph connectivity and identify cycles. These functions are categorized by the type of graph (undirected vs. directed) and the specific property being queried (e.g., strong vs. weak connectivity in directed graphs).
is_connected: Checks if the graph is connected.connected_components: Returns a list of sets of node indices representing connected components.number_connected_components: Returns the count of connected components.node_connected_component: Returns the set of nodes in the same component as a specific node.is_strongly_connected, strongly_connected_components, and number_strongly_connected_components (where every node is reachable from every other node in the component).is_weakly_connected, weakly_connected_components, and number_weakly_connected_components (where connectivity is considered by ignoring edge direction).simple_cycles: Finds all simple cycles in a directed graph.cycle_basis: Finds a basis for the cycle space.digraph_find_cycle: Finds a cycle in a directed graph.all_simple_paths: Finds all simple paths between two nodes.all_pairs_all_simple_paths: Finds all simple paths between all pairs of nodes.longest_simple_path: Finds the longest simple path.articulation_points: Finds nodes whose removal increases the number of connected components.bridges: Finds edges whose removal increases the number of connected components.biconnected_components: Finds biconnected components of the graph.is_bipartite: Checks if the graph is bipartite.isolates: Returns a list of nodes with no edges.has_path: Checks if a path exists between two nodes.stoer_wagner_min_cut: Computes the minimum cut of an undirected graph.rustworkx provides three primary graph types for different structural requirements:
PyGraph: An undirected graph where edges have no direction.PyDiGraph: A directed graph where edges have a specific direction.PyDAG: A Directed Acyclic Graph, which is a directed graph with no cycles.You can use these classes to model various network structures depending on whether your relationships are directed or undirected, and whether cycles are permitted.
A Directed Acyclic Graph (DAG) is a directed graph with no cycles. In rustworkx, you can ensure a PyDiGraph remains acyclic by enabling the check_cycle property. When check_cycle=True, any method that would introduce a cycle (such as add_edge) will raise an error.
Note on Performance: Enabling cycle checking introduces a noticeable runtime overhead. To avoid this overhead while still building DAGs, use add_parent or add_child, as these methods add a new node and edge simultaneously in a way that cannot introduce a cycle.
Rustworkx provides two types of algorithm functions for directed graphs:
digraph_ (e.g., rustworkx.digraph_bfs_search) that are explicitly designed for rustworkx.PyDiGraph or rustworkx.PyDAG objects.digraph_ variants) to perform the operation.When working with directed graphs, you can use either the universal functions or the specific digraph_ prefixed functions directly.
rustworkx includes rustworkx-core, a standalone Rust library. This core library provides a generic interface for Rust users, allowing them to use the same high-performance graph algorithm implementations that are exposed in the Python library. You can use rustworkx-core in any Rust application requiring these graph functionalities.By default, all graphs in rustworkx are multigraphs, meaning they allow parallel edges between the same two nodes.
To prevent parallel edges, set the multigraph argument to False in the PyGraph or PyDiGraph constructors. When multigraph=False, any attempt to add a parallel edge will instead update the existing edge's weight or data payload rather than creating a new edge.
import rustworkx as rx
graph = rx.PyGraph(multigraph=False)
graph.add_nodes_from(range(3))
graph.add_edges_from([(0, 1, 'A'), (0, 1, 'B'), (1, 2, 'C')])
# The edge between 0 and 1 will have the payload 'B', not both 'A' and 'B'.Since rustworkx allows any Python object as a payload, a common pattern is to store the graph index back onto the object itself. This allows you to easily find the graph index of an object you are holding.
To ensure all objects have their index attribute populated, you can iterate through the graph indices after creation:
# For nodes
for index in graph.node_indices():
graph[index].index = index
# For edges
for index, data in graph.edge_index_map().items():
# data is (node_index1, node_index2, payload)
data[2].index = indexclass GraphNode:
def __init__(self, value):
self.index = None
self.value = value
graph = rx.PyGraph()
graph.add_nodes_from([GraphNode(i) for i in range(5)])
# Populate index attribute in GraphNode objects
for index in graph.node_indices():
graph[index].index = indexWhen migrating from NetworkX to rustworkx, the most significant change is how nodes and edges are identified and accessed.
rustworkx assigns a unique integer index to every node and edge. You must use these integer indices to interact with the graph.rustworkx uses a single payload object attached to the node index. You can store any Python object (hashable or not) as this payload.rustworkx functions are explicitly typed. Functions prefixed with graph_* are designed for PyGraph (undirected), while digraph_* functions are designed for PyDiGraph (directed). Passing the wrong graph type to these functions will result in errors, unlike the dynamic typing in NetworkX.rustworkx uses callback functions (e.g., weight_fn) to extract values from node or edge payloads, rather than looking up named attributes in a dictionary.Rustworkx categorizes platform support into tiers, which determines the level of testing and ease of installation:
Numpy from source (requires a C/C++ compiler).