0
# rustworkx
1

2
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.
3

4
## Package Information
5

6
- **Package Name**: rustworkx
7
- **Language**: Python with Rust implementation
8
- **Installation**: `pip install rustworkx`
9

10
## Core Imports
11

12
```python
13
import rustworkx as rx
14
```
15

16
For specific functionality:
17

18
```python
19
from rustworkx import PyGraph, PyDiGraph, PyDAG
20
```
21

22
For generators:
23

24
```python
25
import rustworkx.generators as rx_generators
26
```
27

28
For visualization:
29

30
```python
31
import rustworkx.visualization as rx_viz
32
```
33

34
## Basic Usage
35

36
```python
37
import rustworkx as rx
38

39
# Create an undirected graph
40
graph = rx.PyGraph()
41

42
# Add nodes with data
43
node_a = graph.add_node("A")
44
node_b = graph.add_node("B")
45
node_c = graph.add_node("C")
46

47
# Add edges with weights
48
graph.add_edge(node_a, node_b, 5.0)
49
graph.add_edge(node_b, node_c, 3.0)
50
graph.add_edge(node_c, node_a, 2.0)
51

52
# Find shortest paths
53
shortest_paths = rx.dijkstra_shortest_paths(graph, node_a)
54
print(shortest_paths)
55

56
# Calculate centrality measures
57
centrality = rx.betweenness_centrality(graph)
58
print(centrality)
59

60
# Generate a random graph
61
random_graph = rx.generators.erdos_renyi_gnp_random_graph(10, 0.3)
62
```
63

64
## Architecture
65

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

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

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

77
## Capabilities
78

79
### Core Graph Classes
80

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

83
```python { .api }
84
class PyGraph:
85
    """Undirected multigraph with arbitrary node and edge data."""
86
    def __init__(self, multigraph: bool = True): ...
87
    def add_node(self, node_weight): ...
88
    def add_edge(self, node_a: int, node_b: int, edge_weight) -> int: ...
89
    def remove_node(self, node_index: int): ...
90
    def nodes(self): ...
91
    
92
class PyDiGraph:
93
    """Directed multigraph with cycle checking capabilities."""  
94
    def __init__(self, check_cycle: bool = False, multigraph: bool = True): ...
95
    def add_child(self, parent_node: int, child_weight, edge_weight) -> int: ...
96
    def predecessors(self, node_index: int): ...
97
    def successors(self, node_index: int): ...
98
```
99

100
[Core Graph Classes](./core-classes.md)
101

102
### Shortest Path Algorithms
103

104
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.
105

106
```python { .api }
107
def dijkstra_shortest_paths(graph, source: int, target: int = None, weight_fn = None, default_weight: float = 1.0, as_undirected: bool = False) -> dict: ...
108
def floyd_warshall(graph, weight_fn = None, default_weight: float = 1.0, parallel_threshold: int = 300): ...
109
def bellman_ford_shortest_paths(graph, source: int, target: int = None, weight_fn = None, default_weight: float = 1.0, as_undirected: bool = False): ...
110
def astar_shortest_path(graph, node: int, goal_fn, edge_cost_fn, estimate_cost_fn): ...
111
```
112

113
[Shortest Path Algorithms](./shortest-paths.md)
114

115
### Centrality Measures
116

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

119
```python { .api }
120
def betweenness_centrality(graph, normalized: bool = True, endpoints: bool = False, parallel_threshold: int = 50) -> dict: ...
121
def closeness_centrality(graph, wf_improved: bool = True, parallel_threshold: int = 50) -> dict: ...
122
def eigenvector_centrality(graph, weight_fn = None, default_weight: float = 1.0, max_iter: int = 100, tol: float = 1e-6): ...
123
def degree_centrality(graph): ...
124
```
125

126
[Centrality Measures](./centrality.md)
127

128
### Graph Analysis
129

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

132
```python { .api }
133
def strongly_connected_components(graph) -> list: ...
134
def connected_components(graph) -> list: ...
135
def is_isomorphic(first, second, node_matcher = None, edge_matcher = None, id_order: bool = True, call_limit: int = None) -> bool: ...
136
def transitivity(graph) -> float: ...
137
def core_number(graph) -> dict: ...
138
```
139

140
[Graph Analysis](./analysis.md)
141

142
### Advanced Algorithms
143

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

146
```python { .api }
147
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): ...
148
def hits(graph, max_iter: int = 100, tol: float = 1e-8): ...
149
def max_weight_matching(graph, max_cardinality: bool = False, weight_fn = None, default_weight: float = 1.0): ...
150
def greedy_color(graph, strategy = None): ...
151
```
152

153
[Advanced Algorithms](./advanced-algorithms.md)
154

155
### Graph Generators
156

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

159
```python { .api }
160
def cycle_graph(num_nodes: int, weights = None, multigraph: bool = True): ...
161
def erdos_renyi_gnp_random_graph(num_nodes: int, probability: float, seed: int = None, multigraph: bool = True): ...
162
def barabasi_albert_graph(n: int, m: int, seed: int = None, initial_graph = None, multigraph: bool = True): ...
163
def grid_graph(rows: int, cols: int = None, weights = None, multigraph: bool = True): ...
164
```
165

166
[Graph Generators](./generators.md)
167

168
### Graph Traversal
169

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

172
```python { .api }
173
def bfs_search(graph, source, visitor): ...
174
def dfs_search(graph, source, visitor): ...
175
def dijkstra_search(graph, source, weight_fn, visitor): ...
176

177
class BFSVisitor:
178
    def discover_vertex(self, vertex): ...
179
    def tree_edge(self, edge): ...
180
    def finish_vertex(self, vertex): ...
181
```
182

183
[Graph Traversal](./traversal.md)
184

185
### Layout Algorithms
186

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

189
```python { .api }
190
def spring_layout(graph, pos = None, fixed = None, k = None, num_iter: int = 50, seed = None) -> dict: ...
191
def circular_layout(graph, scale: float = 1, center = None): ...
192
def random_layout(graph, center = None, seed = None): ...
193
def bipartite_layout(graph, first_nodes, horizontal: bool = False, scale: float = 1, center = None): ...
194
```
195

196
[Layout Algorithms](./layouts.md)
197

198
### Visualization
199

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

202
```python { .api }
203
def mpl_draw(graph, pos = None, with_labels: bool = False, node_size: int = 300, node_color = 'red', edge_color = 'black'): ...
204
def graphviz_draw(graph, node_attr_fn = None, edge_attr_fn = None, graph_attr = None, filename = None, method: str = 'dot'): ...
205
```
206

207
[Visualization](./visualization.md)
208

209
## Types
210

211
```python { .api }
212
# Core return types
213
NodeIndices = list[int]
214
EdgeList = list[tuple[int, int]]
215
WeightedEdgeList = list[tuple[int, int, Any]]
216

217
# Path and mapping types  
218
PathMapping = dict[int, list[int]]
219
PathLengthMapping = dict[int, float]
220
AllPairsPathMapping = dict[int, dict[int, list[int]]]
221
CentralityMapping = dict[int, float]
222
Pos2DMapping = dict[int, tuple[float, float]]
223

224
# Visitor classes
225
class BFSVisitor: ...
226
class DFSVisitor: ...  
227
class DijkstraVisitor: ...
228

229
# Exception classes
230
class DAGHasCycle(Exception): ...
231
class InvalidNode(Exception): ...
232
class NoPathFound(Exception): ...
233
class NegativeCycle(Exception): ...
234
class StopSearch(Exception): ...
235
class PruneSearch(Exception): ...
236
```