0
# Core Graph Classes
1
2
The foundational graph data structures in rustworkx, providing comprehensive node and edge management with support for arbitrary Python objects as node and edge weights. These classes form the basis for all graph operations and algorithms in the library.
3
4
## Capabilities
5
6
### PyGraph - Undirected Graph
7
8
Generic undirected multigraph supporting parallel edges and arbitrary node/edge data payloads. Provides comprehensive methods for graph construction, manipulation, and querying.
9
10
```python { .api }
11
class PyGraph:
12
"""
13
Undirected multigraph with arbitrary node and edge data.
14
15
Parameters:
16
- multigraph (bool): Allow parallel edges between nodes (default: True)
17
"""
18
19
def __init__(self, multigraph: bool = True): ...
20
21
# Node operations
22
def add_node(self, node_weight) -> int:
23
"""Add node with data payload, returns node index."""
24
25
def add_nodes_from(self, node_list) -> list[int]:
26
"""Add multiple nodes, returns list of node indices."""
27
28
def remove_node(self, node_index: int):
29
"""Remove node and all incident edges."""
30
31
def nodes(self):
32
"""Get all node data payloads."""
33
34
def node_indices(self) -> list[int]:
35
"""Get all node indices."""
36
37
# Edge operations
38
def add_edge(self, node_a: int, node_b: int, edge_weight) -> int:
39
"""Add edge between nodes, returns edge index."""
40
41
def add_edges_from(self, edge_list):
42
"""Add multiple edges from list of (node_a, node_b, weight) tuples."""
43
44
def add_edges_from_no_data(self, edge_list):
45
"""Add edges without data from list of (node_a, node_b) tuples."""
46
47
def remove_edge(self, source: int, target: int):
48
"""Remove edge between nodes."""
49
50
def remove_edges_from(self, edge_list):
51
"""Remove multiple edges."""
52
53
def edges(self):
54
"""Get all edge data payloads."""
55
56
def edge_list(self) -> list[tuple[int, int]]:
57
"""Get edge list as (source, target) tuples."""
58
59
def weighted_edge_list(self) -> list[tuple[int, int, Any]]:
60
"""Get weighted edge list as (source, target, weight) tuples."""
61
62
# Graph properties and queries
63
def num_nodes(self) -> int:
64
"""Number of nodes in graph."""
65
66
def num_edges(self) -> int:
67
"""Number of edges in graph."""
68
69
def degree(self, node_index: int) -> int:
70
"""Get degree of specified node."""
71
72
def neighbors(self, node_index: int):
73
"""Get neighboring nodes."""
74
75
def find_node_by_weight(self, weight) -> int:
76
"""Find first node with matching weight."""
77
78
# Graph operations
79
def copy(self):
80
"""Create deep copy of graph."""
81
82
def clear(self):
83
"""Remove all nodes and edges."""
84
85
def subgraph(self, node_list: list[int]):
86
"""Create subgraph from specified nodes."""
87
88
def to_directed(self):
89
"""Convert to directed graph."""
90
91
def compose(self, other_graph, node_map: dict):
92
"""Compose with another graph using node mapping."""
93
94
def contract_nodes(self, node_list: list[int], new_weight):
95
"""Contract specified nodes into single node."""
96
97
# Attributes
98
attrs: Any # Graph-level attributes
99
multigraph: bool # Whether parallel edges are allowed
100
```
101
102
### PyDiGraph - Directed Graph
103
104
Generic directed multigraph with additional directed-specific functionality including cycle checking, predecessor/successor queries, and directed graph operations.
105
106
```python { .api }
107
class PyDiGraph:
108
"""
109
Directed multigraph with cycle checking capabilities.
110
111
Parameters:
112
- check_cycle (bool): Enable runtime cycle detection (default: False)
113
- multigraph (bool): Allow parallel edges between nodes (default: True)
114
"""
115
116
def __init__(self, check_cycle: bool = False, multigraph: bool = True): ...
117
118
# Inherits all PyGraph methods plus:
119
120
# Directed node operations
121
def add_child(self, parent_node: int, child_weight, edge_weight) -> int:
122
"""Add child node connected to parent, returns child index."""
123
124
def add_parent(self, child_node: int, parent_weight, edge_weight) -> int:
125
"""Add parent node connected to child, returns parent index."""
126
127
# Directed edge queries
128
def in_edges(self, node_index: int):
129
"""Get incoming edges for node."""
130
131
def out_edges(self, node_index: int):
132
"""Get outgoing edges for node."""
133
134
def in_degree(self, node_index: int) -> int:
135
"""Get in-degree of node."""
136
137
def out_degree(self, node_index: int) -> int:
138
"""Get out-degree of node."""
139
140
# Directed neighbors
141
def predecessors(self, node_index: int):
142
"""Get predecessor nodes."""
143
144
def successors(self, node_index: int):
145
"""Get successor nodes."""
146
147
# Directed operations
148
def reverse(self):
149
"""Reverse direction of all edges."""
150
151
def to_undirected(self):
152
"""Convert to undirected graph."""
153
154
def is_symmetric(self) -> bool:
155
"""Check if graph is symmetric (bidirectional edges)."""
156
157
def make_symmetric(self):
158
"""Make graph symmetric by adding reverse edges."""
159
160
def find_successor_node_by_edge(self, source: int, edge_weight) -> int:
161
"""Find successor node by edge weight."""
162
163
# Attributes
164
check_cycle: bool # Runtime cycle detection flag
165
attrs: Any # Graph-level attributes
166
multigraph: bool # Whether parallel edges are allowed
167
```
168
169
### PyDAG - Directed Acyclic Graph
170
171
Specialized directed graph class with enhanced cycle prevention. Functionally identical to PyDiGraph but conceptually represents a DAG.
172
173
```python { .api }
174
class PyDAG(PyDiGraph):
175
"""
176
Directed Acyclic Graph - alias for PyDiGraph with cycle checking.
177
178
Identical functionality to PyDiGraph, exists for semantic clarity
179
and backward compatibility. Supports runtime cycle detection.
180
"""
181
pass
182
```
183
184
## Graph Construction Patterns
185
186
### Basic Graph Creation
187
188
```python
189
import rustworkx as rx
190
191
# Create undirected graph
192
graph = rx.PyGraph()
193
nodes = graph.add_nodes_from(['A', 'B', 'C', 'D'])
194
graph.add_edges_from([
195
(nodes[0], nodes[1], 1.0),
196
(nodes[1], nodes[2], 2.0),
197
(nodes[2], nodes[3], 3.0)
198
])
199
200
# Create directed graph with cycle checking
201
digraph = rx.PyDiGraph(check_cycle=True)
202
try:
203
n1 = digraph.add_node("Node 1")
204
n2 = digraph.add_child(n1, "Node 2", "edge_1_to_2")
205
n3 = digraph.add_child(n2, "Node 3", "edge_2_to_3")
206
# This would raise DAGWouldCycle if cycle checking is enabled
207
# digraph.add_edge(n3, n1, "would_create_cycle")
208
except rx.DAGWouldCycle:
209
print("Cycle detected!")
210
```
211
212
### Multigraph vs Simple Graph
213
214
```python
215
# Multigraph allows parallel edges
216
multigraph = rx.PyGraph(multigraph=True)
217
n1 = multigraph.add_node("A")
218
n2 = multigraph.add_node("B")
219
multigraph.add_edge(n1, n2, "edge1")
220
multigraph.add_edge(n1, n2, "edge2") # Parallel edge allowed
221
222
# Simple graph updates existing edge
223
simple_graph = rx.PyGraph(multigraph=False)
224
n1 = simple_graph.add_node("A")
225
n2 = simple_graph.add_node("B")
226
simple_graph.add_edge(n1, n2, "edge1")
227
simple_graph.add_edge(n1, n2, "edge2") # Updates existing edge
228
```
229
230
### Graph Manipulation
231
232
```python
233
# Node and edge removal
234
graph.remove_node(node_index) # Removes node and incident edges
235
graph.remove_edge(source, target) # Removes specific edge
236
graph.remove_edges_from([(0, 1), (1, 2)]) # Batch removal
237
238
# Graph querying
239
neighbors = graph.neighbors(node_index)
240
degree = graph.degree(node_index)
241
node_data = graph.nodes()[node_index]
242
edge_data = graph.edges()[edge_index]
243
244
# Graph transformation
245
directed = graph.to_directed() # Convert undirected to directed
246
undirected = digraph.to_undirected() # Convert directed to undirected
247
subgraph = graph.subgraph([0, 1, 2]) # Extract subgraph
248
copy = graph.copy() # Deep copy
249
```