or run

npx @tessl/cli init
Log in

Version

Tile

Overview

Evals

Files

docs

advanced-algorithms.mdanalysis.mdcentrality.mdcore-classes.mdgenerators.mdindex.mdlayouts.mdshortest-paths.mdtraversal.mdvisualization.md
tile.json

tessl/pypi-rustworkx

A high-performance graph library for Python implemented in Rust, providing fast graph algorithms and data structures for computational tasks

Workspace
tessl
Visibility
Public
Created
Last updated
Describes
pypipkg:pypi/rustworkx@0.17.x

To install, run

npx @tessl/cli install tessl/pypi-rustworkx@0.17.0

index.mddocs/

rustworkx

A high-performance graph library for Python implemented in Rust, designed to provide fast graph algorithms and data structures for computational tasks. rustworkx offers comprehensive graph functionality including directed and undirected graphs, shortest path algorithms, traversal methods, centrality measures, and advanced graph analysis tools. The library leverages Rust's performance characteristics to deliver significant speed improvements over pure Python implementations while maintaining a Pythonic API that integrates seamlessly with the scientific Python ecosystem including NumPy compatibility.

Package Information

  • Package Name: rustworkx
  • Language: Python with Rust implementation
  • Installation: pip install rustworkx

Core Imports

import rustworkx as rx

For specific functionality:

from rustworkx import PyGraph, PyDiGraph, PyDAG

For generators:

import rustworkx.generators as rx_generators

For visualization:

import rustworkx.visualization as rx_viz

Basic Usage

import rustworkx as rx

# Create an undirected graph
graph = rx.PyGraph()

# Add nodes with data
node_a = graph.add_node("A")
node_b = graph.add_node("B")
node_c = graph.add_node("C")

# Add edges with weights
graph.add_edge(node_a, node_b, 5.0)
graph.add_edge(node_b, node_c, 3.0)
graph.add_edge(node_c, node_a, 2.0)

# Find shortest paths
shortest_paths = rx.dijkstra_shortest_paths(graph, node_a)
print(shortest_paths)

# Calculate centrality measures
centrality = rx.betweenness_centrality(graph)
print(centrality)

# Generate a random graph
random_graph = rx.generators.erdos_renyi_gnp_random_graph(10, 0.3)

Architecture

rustworkx uses a hybrid architecture that combines Python's ease of use with Rust's performance:

  • Core Graph Classes: PyGraph (undirected), PyDiGraph (directed), and PyDAG (directed acyclic)
  • Universal Functions: Work with both directed and undirected graphs using single dispatch
  • Specialized Functions: Type-specific algorithms optimized for directed or undirected graphs
  • Generator Module: Comprehensive collection of graph generation algorithms
  • Visualization Module: Integration with matplotlib and graphviz for graph visualization
  • Visitor Pattern: Event-driven traversal system for custom algorithms

The library supports multigraphs, provides NumPy integration for matrix operations, and offers extensive parallelization for computationally intensive algorithms.

Capabilities

Core Graph Classes

The foundational graph data structures providing node and edge management, with support for arbitrary Python objects as node and edge weights.

class PyGraph:
    """Undirected multigraph with arbitrary node and edge data."""
    def __init__(self, multigraph: bool = True): ...
    def add_node(self, node_weight): ...
    def add_edge(self, node_a: int, node_b: int, edge_weight) -> int: ...
    def remove_node(self, node_index: int): ...
    def nodes(self): ...
    
class PyDiGraph:
    """Directed multigraph with cycle checking capabilities."""  
    def __init__(self, check_cycle: bool = False, multigraph: bool = True): ...
    def add_child(self, parent_node: int, child_weight, edge_weight) -> int: ...
    def predecessors(self, node_index: int): ...
    def successors(self, node_index: int): ...

Core Graph Classes

Shortest Path Algorithms

Comprehensive shortest path algorithms including Dijkstra, Bellman-Ford, Floyd-Warshall, and A* for finding optimal paths between nodes with support for weighted and unweighted graphs.

def dijkstra_shortest_paths(graph, source: int, target: int = None, weight_fn = None, default_weight: float = 1.0, as_undirected: bool = False) -> dict: ...
def floyd_warshall(graph, weight_fn = None, default_weight: float = 1.0, parallel_threshold: int = 300): ...
def bellman_ford_shortest_paths(graph, source: int, target: int = None, weight_fn = None, default_weight: float = 1.0, as_undirected: bool = False): ...
def astar_shortest_path(graph, node: int, goal_fn, edge_cost_fn, estimate_cost_fn): ...

Shortest Path Algorithms

Centrality Measures

Node and edge centrality algorithms for identifying important vertices and edges in networks, including betweenness, closeness, degree, eigenvector, and Katz centrality measures.

def betweenness_centrality(graph, normalized: bool = True, endpoints: bool = False, parallel_threshold: int = 50) -> dict: ...
def closeness_centrality(graph, wf_improved: bool = True, parallel_threshold: int = 50) -> dict: ...
def eigenvector_centrality(graph, weight_fn = None, default_weight: float = 1.0, max_iter: int = 100, tol: float = 1e-6): ...
def degree_centrality(graph): ...

Centrality Measures

Graph Analysis

Structural analysis tools for understanding graph properties including connectivity, components, isomorphism testing, and graph-theoretic measures like transitivity and core decomposition.

def strongly_connected_components(graph) -> list: ...
def connected_components(graph) -> list: ...
def is_isomorphic(first, second, node_matcher = None, edge_matcher = None, id_order: bool = True, call_limit: int = None) -> bool: ...
def transitivity(graph) -> float: ...
def core_number(graph) -> dict: ...

Graph Analysis

Advanced Algorithms

Specialized algorithms for ranking, matching, coloring, and advanced graph analytics including PageRank, HITS, maximum matching, and graph coloring algorithms.

def pagerank(graph, alpha: float = 0.85, personalization = None, max_iter: int = 100, tol: float = 1e-6, weight_fn = None, default_weight: float = 1.0): ...
def hits(graph, max_iter: int = 100, tol: float = 1e-8): ...
def max_weight_matching(graph, max_cardinality: bool = False, weight_fn = None, default_weight: float = 1.0): ...
def greedy_color(graph, strategy = None): ...

Advanced Algorithms

Graph Generators

Extensive collection of graph generation algorithms for creating various graph types including classic graphs, random graphs, lattice structures, and special topologies.

def cycle_graph(num_nodes: int, weights = None, multigraph: bool = True): ...
def erdos_renyi_gnp_random_graph(num_nodes: int, probability: float, seed: int = None, multigraph: bool = True): ...
def barabasi_albert_graph(n: int, m: int, seed: int = None, initial_graph = None, multigraph: bool = True): ...
def grid_graph(rows: int, cols: int = None, weights = None, multigraph: bool = True): ...

Graph Generators

Graph Traversal

Event-driven traversal algorithms using the visitor pattern for breadth-first search, depth-first search, and Dijkstra's algorithm with customizable event handling.

def bfs_search(graph, source, visitor): ...
def dfs_search(graph, source, visitor): ...
def dijkstra_search(graph, source, weight_fn, visitor): ...

class BFSVisitor:
    def discover_vertex(self, vertex): ...
    def tree_edge(self, edge): ...
    def finish_vertex(self, vertex): ...

Graph Traversal

Layout Algorithms

Graph layout algorithms for positioning nodes in 2D space for visualization, including force-directed, circular, grid-based, and specialized layouts for different graph types.

def spring_layout(graph, pos = None, fixed = None, k = None, num_iter: int = 50, seed = None) -> dict: ...
def circular_layout(graph, scale: float = 1, center = None): ...
def random_layout(graph, center = None, seed = None): ...
def bipartite_layout(graph, first_nodes, horizontal: bool = False, scale: float = 1, center = None): ...

Layout Algorithms

Visualization

Integration with matplotlib and graphviz for creating publication-quality graph visualizations with extensive customization options for nodes, edges, and graph appearance.

def mpl_draw(graph, pos = None, with_labels: bool = False, node_size: int = 300, node_color = 'red', edge_color = 'black'): ...
def graphviz_draw(graph, node_attr_fn = None, edge_attr_fn = None, graph_attr = None, filename = None, method: str = 'dot'): ...

Visualization

Types

# Core return types
NodeIndices = list[int]
EdgeList = list[tuple[int, int]]
WeightedEdgeList = list[tuple[int, int, Any]]

# Path and mapping types  
PathMapping = dict[int, list[int]]
PathLengthMapping = dict[int, float]
AllPairsPathMapping = dict[int, dict[int, list[int]]]
CentralityMapping = dict[int, float]
Pos2DMapping = dict[int, tuple[float, float]]

# Visitor classes
class BFSVisitor: ...
class DFSVisitor: ...  
class DijkstraVisitor: ...

# Exception classes
class DAGHasCycle(Exception): ...
class InvalidNode(Exception): ...
class NoPathFound(Exception): ...
class NegativeCycle(Exception): ...
class StopSearch(Exception): ...
class PruneSearch(Exception): ...