0
# Graph Traversal
1
2
Event-driven traversal algorithms using the visitor pattern for breadth-first search, depth-first search, and Dijkstra's algorithm. rustworkx provides customizable traversal with event handling for implementing complex graph algorithms.
3
4
## Capabilities
5
6
### Breadth-First Search
7
8
BFS traversal with visitor pattern for event-driven algorithm implementation.
9
10
```python { .api }
11
def bfs_search(graph, source, visitor):
12
"""
13
Breadth-first search traversal with visitor callbacks.
14
15
Explores graph level by level from source nodes, calling visitor
16
methods at key algorithm events for custom processing.
17
18
Parameters:
19
- graph: Input graph (PyGraph or PyDiGraph)
20
- source: List of source node indices or single node index
21
- visitor: BFSVisitor instance with event callback methods
22
23
Returns:
24
None (results communicated through visitor methods)
25
26
Raises:
27
StopSearch: When visitor raises this to terminate early
28
PruneSearch: When visitor raises this to skip subtrees
29
"""
30
31
def dfs_edges(graph, source = None):
32
"""
33
Get depth-first search tree edges.
34
35
Returns edges discovered during DFS traversal, forming
36
a spanning forest of the graph.
37
38
Parameters:
39
- graph: Input graph (PyGraph or PyDiGraph)
40
- source (int, optional): Starting node, if None searches all components
41
42
Returns:
43
EdgeList: List of tree edges as (source, target) tuples
44
"""
45
```
46
47
### Depth-First Search
48
49
DFS traversal with visitor pattern and timing information.
50
51
```python { .api }
52
def dfs_search(graph, source, visitor):
53
"""
54
Depth-first search traversal with visitor callbacks.
55
56
Explores graph by going as deep as possible before backtracking,
57
providing discovery and finish times for each node.
58
59
Parameters:
60
- graph: Input graph (PyGraph or PyDiGraph)
61
- source: List of source node indices or single node index
62
- visitor: DFSVisitor instance with event callback methods
63
64
Returns:
65
None (results communicated through visitor methods)
66
67
Raises:
68
StopSearch: When visitor raises this to terminate early
69
PruneSearch: When visitor raises this to skip subtrees
70
"""
71
```
72
73
### Dijkstra Search
74
75
Dijkstra's algorithm with visitor pattern for shortest path exploration.
76
77
```python { .api }
78
def dijkstra_search(graph, source, weight_fn, visitor):
79
"""
80
Dijkstra shortest path search with visitor callbacks.
81
82
Explores graph in order of increasing distance from source,
83
calling visitor methods for path relaxation events.
84
85
Parameters:
86
- graph: Input graph (PyGraph or PyDiGraph)
87
- source: List of source node indices or single node index
88
- weight_fn (callable): Function to extract edge weights, or None for unit weights
89
- visitor: DijkstraVisitor instance with event callback methods
90
91
Returns:
92
None (results communicated through visitor methods)
93
94
Raises:
95
StopSearch: When visitor raises this to terminate early
96
PruneSearch: When visitor raises this to skip subtrees
97
"""
98
```
99
100
## Visitor Classes
101
102
### BFSVisitor
103
104
Base class for breadth-first search event handling.
105
106
```python { .api }
107
class BFSVisitor:
108
"""
109
Visitor base class for BFS algorithm events.
110
111
Override methods to implement custom BFS-based algorithms.
112
All methods are optional with default no-op implementations.
113
"""
114
115
def discover_vertex(self, vertex: int):
116
"""
117
Called when vertex is first discovered (colored gray).
118
119
Parameters:
120
- vertex (int): Node index being discovered
121
"""
122
pass
123
124
def examine_edge(self, edge: tuple):
125
"""
126
Called on every out-edge of each vertex after discovery.
127
128
Parameters:
129
- edge (tuple): Edge as (source, target, weight) tuple
130
"""
131
pass
132
133
def tree_edge(self, edge: tuple):
134
"""
135
Called on each edge in the BFS tree.
136
137
These are edges to previously undiscovered vertices.
138
139
Parameters:
140
- edge (tuple): Tree edge as (source, target, weight) tuple
141
"""
142
pass
143
144
def non_tree_edge(self, edge: tuple):
145
"""
146
Called on back or cross edges (non-tree edges).
147
148
Parameters:
149
- edge (tuple): Non-tree edge as (source, target, weight) tuple
150
"""
151
pass
152
153
def gray_target_edge(self, edge: tuple):
154
"""
155
Called on edges to gray (discovered but unfinished) vertices.
156
157
Parameters:
158
- edge (tuple): Edge to gray vertex as (source, target, weight) tuple
159
"""
160
pass
161
162
def black_target_edge(self, edge: tuple):
163
"""
164
Called on edges to black (finished) vertices.
165
166
Parameters:
167
- edge (tuple): Edge to black vertex as (source, target, weight) tuple
168
"""
169
pass
170
171
def finish_vertex(self, vertex: int):
172
"""
173
Called when vertex processing is complete (colored black).
174
175
Parameters:
176
- vertex (int): Node index being finished
177
"""
178
pass
179
```
180
181
### DFSVisitor
182
183
Base class for depth-first search event handling with timing information.
184
185
```python { .api }
186
class DFSVisitor:
187
"""
188
Visitor base class for DFS algorithm events.
189
190
Override methods to implement custom DFS-based algorithms.
191
Provides discovery and finish timing information.
192
"""
193
194
def discover_vertex(self, vertex: int, timestamp: int):
195
"""
196
Called when vertex is first discovered.
197
198
Parameters:
199
- vertex (int): Node index being discovered
200
- timestamp (int): Discovery time
201
"""
202
pass
203
204
def tree_edge(self, edge: tuple):
205
"""
206
Called on tree edges (to undiscovered vertices).
207
208
Parameters:
209
- edge (tuple): Tree edge as (source, target, weight) tuple
210
"""
211
pass
212
213
def back_edge(self, edge: tuple):
214
"""
215
Called on back edges (to ancestors in DFS tree).
216
217
In undirected graphs, these may indicate cycles.
218
219
Parameters:
220
- edge (tuple): Back edge as (source, target, weight) tuple
221
"""
222
pass
223
224
def forward_or_cross_edge(self, edge: tuple):
225
"""
226
Called on forward edges (to descendants) or cross edges.
227
228
Parameters:
229
- edge (tuple): Forward/cross edge as (source, target, weight) tuple
230
"""
231
pass
232
233
def finish_vertex(self, vertex: int, timestamp: int):
234
"""
235
Called when vertex processing is complete.
236
237
Parameters:
238
- vertex (int): Node index being finished
239
- timestamp (int): Finish time
240
"""
241
pass
242
```
243
244
### DijkstraVisitor
245
246
Base class for Dijkstra algorithm event handling with distance information.
247
248
```python { .api }
249
class DijkstraVisitor:
250
"""
251
Visitor base class for Dijkstra algorithm events.
252
253
Override methods to implement custom shortest path algorithms.
254
Provides distance information for path relaxation.
255
"""
256
257
def discover_vertex(self, vertex: int, cost: float):
258
"""
259
Called when vertex is first discovered with its distance.
260
261
Parameters:
262
- vertex (int): Node index being discovered
263
- cost (float): Shortest distance found to this vertex
264
"""
265
pass
266
267
def examine_edge(self, edge: tuple):
268
"""
269
Called on every out-edge of each vertex.
270
271
Parameters:
272
- edge (tuple): Edge being examined as (source, target, weight) tuple
273
"""
274
pass
275
276
def edge_relaxed(self, edge: tuple):
277
"""
278
Called when edge relaxation improves shortest path.
279
280
Parameters:
281
- edge (tuple): Relaxed edge as (source, target, weight) tuple
282
"""
283
pass
284
285
def edge_not_relaxed(self, edge: tuple):
286
"""
287
Called when edge relaxation does not improve path.
288
289
Parameters:
290
- edge (tuple): Non-relaxed edge as (source, target, weight) tuple
291
"""
292
pass
293
294
def finish_vertex(self, vertex: int):
295
"""
296
Called when vertex is finished (optimal distance found).
297
298
Parameters:
299
- vertex (int): Node index being finished
300
"""
301
pass
302
```
303
304
## Exception Classes
305
306
### StopSearch
307
308
Exception for early termination of graph traversal.
309
310
```python { .api }
311
class StopSearch(Exception):
312
"""
313
Raise this exception in visitor methods to stop traversal early.
314
315
The search function will return normally without re-raising
316
this exception, allowing clean early termination.
317
"""
318
pass
319
```
320
321
### PruneSearch
322
323
Exception for pruning search subtrees.
324
325
```python { .api }
326
class PruneSearch(Exception):
327
"""
328
Raise this exception in visitor methods to prune search subtree.
329
330
Prevents further exploration of the current branch while
331
continuing search in other areas of the graph.
332
333
Note: Raising in finish_vertex events causes an error.
334
"""
335
pass
336
```
337
338
## Usage Examples
339
340
### Basic BFS Implementation
341
342
```python
343
import rustworkx as rx
344
from rustworkx.visit import BFSVisitor, StopSearch, PruneSearch
345
346
class PathFinder(BFSVisitor):
347
def __init__(self, target):
348
self.target = target
349
self.parent = {}
350
self.found = False
351
352
def tree_edge(self, edge):
353
source, target, _ = edge
354
self.parent[target] = source
355
if target == self.target:
356
self.found = True
357
raise rx.visit.StopSearch()
358
359
def get_path(self, start):
360
if not self.found:
361
return None
362
path = []
363
current = self.target
364
while current != start:
365
path.append(current)
366
current = self.parent[current]
367
path.append(start)
368
return list(reversed(path))
369
370
# Find path using BFS
371
graph = rx.generators.grid_graph(5, 5)
372
finder = PathFinder(target=24) # Bottom-right corner
373
rx.bfs_search(graph, [0], finder) # Start from top-left
374
375
if finder.found:
376
path = finder.get_path(0)
377
print(f"Path found: {path}")
378
else:
379
print("No path found")
380
```
381
382
### DFS-Based Cycle Detection
383
384
```python
385
from rustworkx.visit import DFSVisitor
386
387
class CycleDetector(DFSVisitor):
388
def __init__(self):
389
self.has_cycle = False
390
self.cycle_edge = None
391
392
def back_edge(self, edge):
393
self.has_cycle = True
394
self.cycle_edge = edge
395
raise rx.visit.StopSearch()
396
397
# Detect cycles in directed graph
398
digraph = rx.PyDiGraph()
399
nodes = digraph.add_nodes_from(['A', 'B', 'C'])
400
digraph.add_edges_from([
401
(nodes[0], nodes[1], None),
402
(nodes[1], nodes[2], None),
403
(nodes[2], nodes[0], None) # Creates cycle
404
])
405
406
detector = CycleDetector()
407
rx.dfs_search(digraph, [nodes[0]], detector)
408
409
if detector.has_cycle:
410
print(f"Cycle detected on edge: {detector.cycle_edge}")
411
else:
412
print("No cycles found")
413
```
414
415
### Dijkstra-Based Shortest Path Tree
416
417
```python
418
from rustworkx.visit import DijkstraVisitor
419
420
class ShortestPathTree(DijkstraVisitor):
421
def __init__(self, start):
422
self.start = start
423
self.distances = {}
424
self.predecessors = {}
425
426
def discover_vertex(self, vertex, cost):
427
self.distances[vertex] = cost
428
429
def edge_relaxed(self, edge):
430
source, target, _ = edge
431
self.predecessors[target] = source
432
433
def get_path_to(self, target):
434
if target not in self.predecessors and target != self.start:
435
return None
436
437
path = []
438
current = target
439
while current != self.start:
440
path.append(current)
441
current = self.predecessors[current]
442
path.append(self.start)
443
return list(reversed(path))
444
445
# Build shortest path tree
446
weighted_graph = rx.PyGraph()
447
nodes = weighted_graph.add_nodes_from(['S', 'A', 'B', 'T'])
448
weighted_graph.add_edges_from([
449
(nodes[0], nodes[1], 2.0),
450
(nodes[0], nodes[2], 4.0),
451
(nodes[1], nodes[3], 3.0),
452
(nodes[2], nodes[3], 1.0)
453
])
454
455
spt = ShortestPathTree(nodes[0])
456
rx.dijkstra_search(
457
weighted_graph,
458
[nodes[0]],
459
weight_fn=lambda x: x,
460
visitor=spt
461
)
462
463
# Get paths to all reachable nodes
464
for node in nodes[1:]:
465
path = spt.get_path_to(node)
466
distance = spt.distances.get(node, float('inf'))
467
print(f"Path to {node}: {path}, distance: {distance}")
468
```
469
470
### Connected Components Using BFS
471
472
```python
473
class ComponentFinder(BFSVisitor):
474
def __init__(self):
475
self.current_component = []
476
self.components = []
477
478
def discover_vertex(self, vertex):
479
self.current_component.append(vertex)
480
481
def finish_component(self):
482
if self.current_component:
483
self.components.append(self.current_component.copy())
484
self.current_component.clear()
485
486
def find_components(graph):
487
finder = ComponentFinder()
488
visited = set()
489
490
for node in graph.node_indices():
491
if node not in visited:
492
# Start new component
493
rx.bfs_search(graph, [node], finder)
494
visited.update(finder.current_component)
495
finder.finish_component()
496
497
return finder.components
498
499
# Find connected components
500
disconnected_graph = rx.PyGraph()
501
# Component 1
502
comp1 = disconnected_graph.add_nodes_from(['A', 'B', 'C'])
503
disconnected_graph.add_edges_from([
504
(comp1[0], comp1[1], None),
505
(comp1[1], comp1[2], None)
506
])
507
# Component 2
508
comp2 = disconnected_graph.add_nodes_from(['X', 'Y'])
509
disconnected_graph.add_edges_from([
510
(comp2[0], comp2[1], None)
511
])
512
513
components = find_components(disconnected_graph)
514
print(f"Components found: {components}")
515
```
516
517
### Advanced: Bipartite Testing with BFS
518
519
```python
520
class BipartiteTester(BFSVisitor):
521
def __init__(self):
522
self.colors = {}
523
self.is_bipartite = True
524
self.conflict_edge = None
525
526
def discover_vertex(self, vertex):
527
if vertex not in self.colors:
528
self.colors[vertex] = 0 # Start with color 0
529
530
def tree_edge(self, edge):
531
source, target, _ = edge
532
# Color target with opposite color of source
533
self.colors[target] = 1 - self.colors[source]
534
535
def non_tree_edge(self, edge):
536
source, target, _ = edge
537
# Check if both endpoints have same color
538
if self.colors[source] == self.colors[target]:
539
self.is_bipartite = False
540
self.conflict_edge = edge
541
raise rx.visit.StopSearch()
542
543
def test_bipartite(graph):
544
tester = BipartiteTester()
545
try:
546
rx.bfs_search(graph, [0], tester)
547
except rx.visit.StopSearch:
548
pass
549
550
return tester.is_bipartite, tester.colors if tester.is_bipartite else None
551
552
# Test bipartite property
553
test_graph = rx.generators.cycle_graph(6) # Even cycle is bipartite
554
is_bip, coloring = test_bipartite(test_graph)
555
print(f"Is bipartite: {is_bip}")
556
if is_bip:
557
print(f"Coloring: {coloring}")
558
```
559
560
### Search Pruning Example
561
562
```python
563
class RestrictedBFS(BFSVisitor):
564
def __init__(self, forbidden_nodes):
565
self.forbidden = set(forbidden_nodes)
566
self.visited = set()
567
568
def discover_vertex(self, vertex):
569
self.visited.add(vertex)
570
571
def examine_edge(self, edge):
572
source, target, _ = edge
573
if target in self.forbidden:
574
raise rx.visit.PruneSearch() # Don't explore this branch
575
576
# BFS avoiding certain nodes
577
graph = rx.generators.grid_graph(4, 4)
578
forbidden = [5, 6, 9, 10] # Block some central nodes
579
580
restricted_bfs = RestrictedBFS(forbidden)
581
rx.bfs_search(graph, [0], restricted_bfs)
582
583
print(f"Visited nodes: {sorted(restricted_bfs.visited)}")
584
print(f"Avoided nodes: {forbidden}")
585
```