0
# Advanced Algorithms
1

2
Specialized algorithms for ranking, matching, coloring, and advanced graph analytics. These algorithms provide solutions for complex graph problems including node ranking, maximum matching, graph coloring, and other computationally intensive graph analysis tasks.
3

4
## Capabilities
5

6
### Ranking Algorithms
7

8
Algorithms for computing node importance and ranking based on graph structure and link analysis.
9

10
```python { .api }
11
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):
12
    """
13
    Compute PageRank centrality using power iteration method.
14
    
15
    PageRank computes node importance based on the link structure,
16
    originally developed for ranking web pages. Higher scores indicate
17
    more important nodes in the network.
18
    
19
    Parameters:
20
    - graph: Input graph (PyGraph or PyDiGraph)
21
    - alpha (float): Damping parameter, probability of following links (default: 0.85)
22
    - personalization (dict, optional): Personalization vector for personalized PageRank
23
    - max_iter (int): Maximum number of iterations (default: 100)
24
    - tol (float): Error tolerance for convergence (default: 1e-6)
25
    - weight_fn (callable, optional): Function to extract edge weights
26
    - default_weight (float): Default edge weight (default: 1.0)
27
    
28
    Returns:
29
    CentralityMapping: Dictionary mapping node indices to PageRank scores
30
    """
31

32
def hits(graph, max_iter: int = 100, tol: float = 1e-8):
33
    """
34
    Compute HITS (Hyperlink-Induced Topic Search) authority and hub scores.
35
    
36
    HITS computes two scores for each node: authority (pointed to by important hubs)
37
    and hub (points to important authorities). Useful for analyzing directed networks
38
    with hierarchical or topic-based structure.
39
    
40
    Parameters:
41
    - graph: PyDiGraph input (directed graph required)
42
    - max_iter (int): Maximum number of iterations (default: 100)  
43
    - tol (float): Error tolerance for convergence (default: 1e-8)
44
    
45
    Returns:
46
    tuple: (hubs_dict, authorities_dict) where each is a CentralityMapping
47
           mapping node indices to hub/authority scores
48
    """
49
```
50

51
### Matching Algorithms
52

53
Algorithms for finding maximum and weighted matchings in graphs.
54

55
```python { .api }
56
def max_weight_matching(graph, max_cardinality: bool = False, weight_fn = None, default_weight: float = 1.0):
57
    """
58
    Find maximum weight matching in undirected graph.
59
    
60
    A matching is a subset of edges with no common vertices.
61
    Maximum weight matching maximizes the sum of edge weights.
62
    
63
    Parameters:
64
    - graph: PyGraph input (undirected graph)
65
    - max_cardinality (bool): Prioritize cardinality over weight if True
66
    - weight_fn (callable, optional): Function to extract edge weights
67
    - default_weight (float): Default edge weight (default: 1.0)
68
    
69
    Returns:
70
    set: Set of edges forming maximum weight matching as (node1, node2) tuples
71
    """
72

73
def is_matching(graph, matching) -> bool:
74
    """
75
    Test if a set of edges forms a valid matching.
76
    
77
    A valid matching has no vertices appearing in multiple edges.
78
    
79
    Parameters:
80
    - graph: Input graph
81
    - matching: Set or list of edges to test
82
    
83
    Returns:
84
    bool: True if edges form a valid matching, False otherwise
85
    """
86

87
def is_maximal_matching(graph, matching) -> bool:
88
    """
89
    Test if a matching is maximal (cannot be extended).
90
    
91
    A maximal matching cannot have any more edges added without
92
    violating the matching property.
93
    
94
    Parameters:
95
    - graph: Input graph
96
    - matching: Set or list of edges representing a matching
97
    
98
    Returns:
99
    bool: True if matching is maximal, False otherwise
100
    """
101
```
102

103
### Graph Coloring
104

105
Algorithms for vertex and edge coloring problems.
106

107
```python { .api }
108
def greedy_color(graph, strategy = None):
109
    """
110
    Color graph vertices using greedy coloring algorithm.
111
    
112
    Assigns colors to vertices such that no adjacent vertices
113
    share the same color, using a greedy approach that may not
114
    find the optimal coloring but runs efficiently.
115
    
116
    Parameters:
117
    - graph: Input graph (PyGraph or PyDiGraph)
118
    - strategy (str, optional): Vertex ordering strategy:
119
        - None: Default ordering
120
        - 'largest_first': Order by descending degree
121
        - 'smallest_last': Recursive smallest degree removal
122
        - 'saturation_largest_first': DSatur algorithm
123
    
124
    Returns:
125
    dict: Mapping of node indices to color integers (0, 1, 2, ...)
126
    """
127

128
def greedy_edge_color(graph):
129
    """
130
    Color graph edges using greedy edge coloring.
131
    
132
    Assigns colors to edges such that no incident edges
133
    share the same color.
134
    
135
    Parameters:
136
    - graph: Input graph
137
    
138
    Returns:
139
    dict: Mapping of edge indices to color integers
140
    """
141

142
def bipartite_edge_color(graph, first_nodes):
143
    """
144
    Color edges of bipartite graph optimally.
145
    
146
    For bipartite graphs, edge coloring can be solved optimally
147
    in polynomial time using König's theorem.
148
    
149
    Parameters:
150
    - graph: PyGraph input (must be bipartite)
151
    - first_nodes: Set of node indices in first partition
152
    
153
    Returns:
154
    dict: Mapping of edge indices to color integers
155
    
156
    Note: Graph must be bipartite for correct results
157
    """
158

159
def misra_gries_edge_color(graph):
160
    """
161
    Color graph edges using Misra-Gries edge coloring algorithm.
162
    
163
    Efficient edge coloring algorithm that provides good results
164
    for general graphs.
165
    
166
    Parameters:
167
    - graph: Input graph
168
    
169
    Returns:
170
    dict: Mapping of edge indices to color integers
171
    """
172
```
173

174
### Cycle Analysis
175

176
Advanced algorithms for analyzing cycles in graphs.
177

178
```python { .api }
179
def simple_cycles(graph):
180
    """
181
    Find all simple cycles in directed graph.
182
    
183
    A simple cycle is a closed path with no repeated vertices
184
    except the first and last. Uses Johnson's algorithm.
185
    
186
    Parameters:
187
    - graph: PyDiGraph input
188
    
189
    Returns:
190
    list: List of cycles, each cycle is a list of node indices
191
    
192
    Warning: Can return exponentially many cycles for some graphs
193
    """
194

195
def cycle_basis(graph):
196
    """
197
    Find fundamental cycle basis of undirected graph.
198
    
199
    A cycle basis is a minimal set of cycles that can generate
200
    all cycles in the graph through linear combination.
201
    
202
    Parameters:
203
    - graph: PyGraph input (undirected)
204
    
205
    Returns:
206
    list: List of fundamental cycles, each cycle is a list of node indices
207
    """
208
```
209

210
### Cut and Flow Algorithms
211

212
Algorithms for finding minimum cuts and analyzing graph flow properties.
213

214
```python { .api }
215
def stoer_wagner_min_cut(graph, weight_fn = None, default_weight: float = 1.0):
216
    """
217
    Find minimum cut using Stoer-Wagner algorithm.
218
    
219
    Finds the minimum cut that separates the graph into two components
220
    with minimum total edge weight crossing the cut.
221
    
222
    Parameters:
223
    - graph: PyGraph input (undirected)
224
    - weight_fn (callable, optional): Function to extract edge weights
225
    - default_weight (float): Default edge weight (default: 1.0)
226
    
227
    Returns:
228
    tuple: (cut_value, cut_nodes) where cut_value is minimum cut weight
229
           and cut_nodes is set of nodes in one partition
230
    """
231
```
232

233
### Line Graph Construction
234

235
Algorithms for constructing derived graphs.
236

237
```python { .api }
238
def line_graph(graph):
239
    """
240
    Construct line graph of input graph.
241
    
242
    In the line graph, each edge of the original graph becomes a vertex,
243
    and two vertices in the line graph are connected if the corresponding
244
    edges in the original graph share a common vertex.
245
    
246
    Parameters:
247
    - graph: Input graph
248
    
249
    Returns:
250
    Same type as input: Line graph where edges become vertices
251
    """
252
```
253

254
## Usage Examples
255

256
### PageRank Analysis
257

258
```python
259
import rustworkx as rx
260

261
# Create web-like directed graph
262
web_graph = rx.PyDiGraph()
263
pages = web_graph.add_nodes_from(['Home', 'About', 'Products', 'Contact', 'Blog'])
264

265
# Add links between pages (edges represent hyperlinks)
266
web_graph.add_edges_from([
267
    (pages[0], pages[1], None),  # Home -> About
268
    (pages[0], pages[2], None),  # Home -> Products  
269
    (pages[1], pages[0], None),  # About -> Home
270
    (pages[2], pages[4], None),  # Products -> Blog
271
    (pages[4], pages[0], None),  # Blog -> Home
272
    (pages[4], pages[2], None),  # Blog -> Products
273
])
274

275
# Compute PageRank scores
276
pagerank_scores = rx.pagerank(web_graph, alpha=0.85)
277
print("PageRank scores:")
278
for node_idx, score in pagerank_scores.items():
279
    page_name = web_graph[node_idx]
280
    print(f"  {page_name}: {score:.3f}")
281

282
# Find most important page
283
most_important = max(pagerank_scores, key=pagerank_scores.get)
284
print(f"Most important page: {web_graph[most_important]}")
285
```
286

287
### HITS Algorithm
288

289
```python
290
# HITS works best on directed graphs with authority/hub structure
291
citation_graph = rx.PyDiGraph()
292
papers = citation_graph.add_nodes_from([
293
    'Survey_Paper_A', 'Research_Paper_B', 'Research_Paper_C', 
294
    'Survey_Paper_D', 'Research_Paper_E'
295
])
296

297
# Add citation relationships  
298
citation_graph.add_edges_from([
299
    (papers[0], papers[1], None),  # Survey A cites Research B
300
    (papers[0], papers[2], None),  # Survey A cites Research C
301
    (papers[3], papers[1], None),  # Survey D cites Research B
302
    (papers[3], papers[4], None),  # Survey D cites Research E
303
    (papers[1], papers[2], None),  # Research B cites Research C
304
])
305

306
# Compute HITS scores
307
hubs, authorities = rx.hits(citation_graph)
308

309
print("Hub scores (good at citing others):")
310
for node_idx, score in hubs.items():
311
    print(f"  {citation_graph[node_idx]}: {score:.3f}")
312

313
print("Authority scores (well-cited):")  
314
for node_idx, score in authorities.items():
315
    print(f"  {citation_graph[node_idx]}: {score:.3f}")
316
```
317

318
### Maximum Weight Matching
319

320
```python
321
# Create weighted graph representing job assignments
322
job_graph = rx.PyGraph()
323
workers = job_graph.add_nodes_from(['Alice', 'Bob', 'Carol'])
324
jobs = job_graph.add_nodes_from(['Job1', 'Job2', 'Job3'])
325

326
# Add edges with weights representing worker-job compatibility scores
327
job_graph.add_edges_from([
328
    (workers[0], jobs[0], 8),   # Alice-Job1: score 8
329
    (workers[0], jobs[1], 6),   # Alice-Job2: score 6
330
    (workers[1], jobs[0], 5),   # Bob-Job1: score 5  
331
    (workers[1], jobs[2], 9),   # Bob-Job3: score 9
332
    (workers[2], jobs[1], 7),   # Carol-Job2: score 7
333
    (workers[2], jobs[2], 4),   # Carol-Job3: score 4
334
])
335

336
# Find maximum weight matching
337
matching = rx.max_weight_matching(job_graph, weight_fn=lambda x: x)
338
print("Optimal job assignments:")
339
for worker_idx, job_idx in matching:
340
    worker_name = job_graph[worker_idx]  
341
    job_name = job_graph[job_idx]
342
    edge_weight = job_graph.get_edge_data(worker_idx, job_idx)
343
    print(f"  {worker_name} -> {job_name} (score: {edge_weight})")
344
```
345

346
### Graph Coloring
347

348
```python
349
# Create conflict graph for scheduling
350
conflict_graph = rx.PyGraph()
351
meetings = conflict_graph.add_nodes_from([
352
    'Team_A_Meeting', 'Team_B_Meeting', 'All_Hands', 
353
    'Project_Review', 'Training_Session'
354
])
355

356
# Add edges representing scheduling conflicts
357
conflict_graph.add_edges_from([
358
    (meetings[0], meetings[2], None),  # Team A conflicts with All Hands
359
    (meetings[1], meetings[2], None),  # Team B conflicts with All Hands
360
    (meetings[0], meetings[3], None),  # Team A conflicts with Project Review
361
    (meetings[3], meetings[4], None),  # Project Review conflicts with Training
362
])
363

364
# Find coloring (each color represents a time slot)
365
coloring = rx.greedy_color(conflict_graph, strategy='largest_first')
366
print("Meeting schedule (by time slot):")
367
time_slots = {}
368
for meeting_idx, color in coloring.items():
369
    meeting_name = conflict_graph[meeting_idx]
370
    slot_name = f"Time_Slot_{color + 1}"
371
    if slot_name not in time_slots:
372
        time_slots[slot_name] = []
373
    time_slots[slot_name].append(meeting_name)
374

375
for slot, meetings_list in time_slots.items():
376
    print(f"  {slot}: {', '.join(meetings_list)}")
377
```
378

379
### Cycle Analysis
380

381
```python
382
# Create directed graph with cycles
383
process_graph = rx.PyDiGraph() 
384
steps = process_graph.add_nodes_from(['Start', 'Process', 'Check', 'Finish', 'Retry'])
385

386
process_graph.add_edges_from([
387
    (steps[0], steps[1], None),  # Start -> Process
388
    (steps[1], steps[2], None),  # Process -> Check  
389
    (steps[2], steps[3], None),  # Check -> Finish
390
    (steps[2], steps[4], None),  # Check -> Retry
391
    (steps[4], steps[1], None),  # Retry -> Process (creates cycle)
392
])
393

394
# Find all simple cycles
395
cycles = rx.simple_cycles(process_graph)
396
print("Process cycles found:")
397
for i, cycle in enumerate(cycles):
398
    cycle_names = [process_graph[node] for node in cycle]
399
    print(f"  Cycle {i+1}: {' -> '.join(cycle_names)} -> {cycle_names[0]}")
400
```
401

402
### Minimum Cut Analysis
403

404
```python
405
# Create network flow graph
406
network = rx.PyGraph()
407
nodes = network.add_nodes_from(['Source', 'Router1', 'Router2', 'Router3', 'Sink'])
408

409
# Add edges with capacities
410
network.add_edges_from([
411
    (nodes[0], nodes[1], 10),  # Source-Router1: capacity 10
412
    (nodes[0], nodes[2], 8),   # Source-Router2: capacity 8
413
    (nodes[1], nodes[3], 5),   # Router1-Router3: capacity 5
414
    (nodes[2], nodes[3], 7),   # Router2-Router3: capacity 7
415
    (nodes[1], nodes[4], 6),   # Router1-Sink: capacity 6
416
    (nodes[3], nodes[4], 12),  # Router3-Sink: capacity 12
417
])
418

419
# Find minimum cut
420
cut_value, cut_partition = rx.stoer_wagner_min_cut(network, weight_fn=lambda x: x)
421
print(f"Minimum cut value: {cut_value}")
422
print("Cut partition:")
423
partition_names = [network[node] for node in cut_partition]
424
print(f"  Side 1: {partition_names}")
425
remaining = set(network.node_indices()) - cut_partition  
426
remaining_names = [network[node] for node in remaining]
427
print(f"  Side 2: {remaining_names}")
428
```