0
# Graph Analysis
1

2
Comprehensive tools for analyzing graph structure, connectivity, and properties. These functions provide insights into graph topology, component structure, isomorphism relationships, and various graph-theoretic measures.
3

4
## Capabilities
5

6
### Connectivity Analysis
7

8
Functions for analyzing how nodes and components are connected within graphs.
9

10
```python { .api }
11
def strongly_connected_components(graph) -> list:
12
    """
13
    Find strongly connected components in directed graph.
14
    
15
    A strongly connected component is a maximal set of vertices
16
    where every vertex is reachable from every other vertex.
17
    
18
    Parameters:
19
    - graph: PyDiGraph input
20
    
21
    Returns:
22
    list: List of components, each component is list of node indices
23
    """
24

25
def connected_components(graph) -> list:
26
    """
27
    Find connected components in undirected graph.
28
    
29
    Parameters:
30
    - graph: PyGraph input
31
    
32
    Returns:
33
    list: List of components, each component is list of node indices
34
    """
35

36
def is_strongly_connected(graph) -> bool:
37
    """
38
    Test if directed graph is strongly connected.
39
    
40
    Parameters:
41
    - graph: PyDiGraph input
42
    
43
    Returns:
44
    bool: True if strongly connected, False otherwise
45
    """
46

47
def is_connected(graph) -> bool:
48
    """
49
    Test if undirected graph is connected.
50
    
51
    Parameters:
52
    - graph: PyGraph input
53
    
54
    Returns:
55
    bool: True if connected, False otherwise
56
    """
57

58
def is_weakly_connected(graph) -> bool:
59
    """
60
    Test if directed graph is weakly connected.
61
    
62
    A directed graph is weakly connected if replacing all edges
63
    with undirected edges produces a connected graph.
64
    
65
    Parameters:
66
    - graph: PyDiGraph input
67
    
68
    Returns:
69
    bool: True if weakly connected, False otherwise
70
    """
71
```
72

73
### Cut Points and Bridges
74

75
Functions for identifying critical vertices and edges whose removal would disconnect the graph.
76

77
```python { .api }
78
def articulation_points(graph):
79
    """
80
    Find articulation points (cut vertices) in undirected graph.
81
    
82
    An articulation point is a vertex whose removal increases
83
    the number of connected components.
84
    
85
    Parameters:
86
    - graph: PyGraph input
87
    
88
    Returns:
89
    NodeIndices: List of articulation point node indices
90
    """
91

92
def bridges(graph):
93
    """
94
    Find bridges (cut edges) in undirected graph.
95
    
96
    A bridge is an edge whose removal increases the number
97
    of connected components.
98
    
99
    Parameters:
100
    - graph: PyGraph input
101
    
102
    Returns:
103
    EdgeList: List of bridge edges as (source, target) tuples
104
    """
105

106
def biconnected_components(graph) -> list:
107
    """
108
    Find biconnected components in undirected graph.
109
    
110
    A biconnected component is a maximal subgraph with no
111
    articulation points (cannot be disconnected by removing
112
    a single vertex).
113
    
114
    Parameters:
115
    - graph: PyGraph input
116
    
117
    Returns:
118
    list: List of biconnected components, each is list of node indices
119
    """
120
```
121

122
### Topological Analysis
123

124
Functions for analyzing directed acyclic graphs and topological properties.
125

126
```python { .api }
127
def topological_sort(graph):
128
    """
129
    Compute topological ordering of directed acyclic graph.
130
    
131
    Returns nodes in topological order where for every directed
132
    edge (u,v), u appears before v in the ordering.
133
    
134
    Parameters:
135
    - graph: PyDiGraph input (must be acyclic)
136
    
137
    Returns:
138
    NodeIndices: List of node indices in topological order
139
    
140
    Raises:
141
    DAGHasCycle: If graph contains cycles
142
    """
143

144
def is_directed_acyclic_graph(graph) -> bool:
145
    """
146
    Test if directed graph is acyclic (is a DAG).
147
    
148
    Parameters:
149
    - graph: PyDiGraph input
150
    
151
    Returns:
152
    bool: True if graph is a DAG, False if it contains cycles
153
    """
154

155
def dag_longest_path(graph, weight_fn = None, default_weight: float = 1.0):
156
    """
157
    Find longest path in directed acyclic graph.
158
    
159
    Parameters:
160
    - graph: PyDiGraph input (must be acyclic)
161
    - weight_fn (callable, optional): Function to extract edge weight
162
    - default_weight (float): Default edge weight
163
    
164
    Returns:
165
    NodeIndices: List of node indices forming longest path
166
    
167
    Raises:
168
    DAGHasCycle: If graph contains cycles
169
    """
170

171
def condensation(graph, sccs = None):
172
    """
173
    Return condensation of directed graph.
174
    
175
    The condensation is a DAG where each node represents a
176
    strongly connected component of the original graph.
177
    
178
    Parameters:
179
    - graph: PyDiGraph input
180
    - sccs (list, optional): Pre-computed strongly connected components
181
    
182
    Returns:
183
    PyDiGraph: Condensation graph with SCC nodes
184
    """
185
```
186

187
### Reachability Analysis
188

189
Functions for analyzing which nodes can reach which other nodes in directed graphs.
190

191
```python { .api }
192
def ancestors(graph, node: int) -> set:
193
    """
194
    Find all ancestors of a node in directed graph.
195
    
196
    Ancestors are all nodes from which the given node is reachable.
197
    
198
    Parameters:
199
    - graph: PyDiGraph input
200
    - node (int): Target node index
201
    
202
    Returns:
203
    set: Set of ancestor node indices
204
    """
205

206
def descendants(graph, node: int) -> set:
207
    """
208
    Find all descendants of a node in directed graph.
209
    
210
    Descendants are all nodes reachable from the given node.
211
    
212
    Parameters:
213
    - graph: PyDiGraph input  
214
    - node (int): Source node index
215
    
216
    Returns:
217
    set: Set of descendant node indices
218
    """
219
```
220

221
### Isomorphism Testing
222

223
Functions for testing structural equivalence between graphs.
224

225
```python { .api }
226
def is_isomorphic(first, second, node_matcher = None, edge_matcher = None, id_order: bool = True, call_limit: int = None) -> bool:
227
    """
228
    Test if two graphs are isomorphic using VF2 algorithm.
229
    
230
    Parameters:
231
    - first: First graph (PyGraph or PyDiGraph)
232
    - second: Second graph (same type as first)
233
    - node_matcher (callable, optional): Function to compare node data
234
    - edge_matcher (callable, optional): Function to compare edge data
235
    - id_order (bool): Use ID-based ordering for better performance on large graphs
236
    - call_limit (int, optional): Limit on VF2 algorithm iterations
237
    
238
    Returns:
239
    bool: True if graphs are isomorphic, False otherwise
240
    """
241

242
def is_isomorphic_node_match(first, second, matcher, id_order: bool = True) -> bool:
243
    """
244
    Test isomorphism with node data matching only.
245
    
246
    Parameters:
247
    - first: First graph
248
    - second: Second graph  
249
    - matcher (callable): Function to compare node data
250
    - id_order (bool): Use ID-based ordering
251
    
252
    Returns:
253
    bool: True if graphs are isomorphic with matching nodes
254
    """
255

256
def is_subgraph_isomorphic(first, second, node_matcher = None, edge_matcher = None, id_order: bool = False, induced: bool = True, call_limit: int = None) -> bool:
257
    """
258
    Test if second graph is isomorphic to subgraph of first.
259
    
260
    Parameters:
261
    - first: Host graph
262
    - second: Pattern graph
263
    - node_matcher (callable, optional): Function to compare node data
264
    - edge_matcher (callable, optional): Function to compare edge data
265
    - id_order (bool): Use ID-based ordering
266
    - induced (bool): Check for induced subgraph if True
267
    - call_limit (int, optional): Limit on VF2 algorithm iterations
268
    
269
    Returns:
270
    bool: True if subgraph isomorphism exists
271
    """
272

273
def vf2_mapping(first, second, node_matcher = None, edge_matcher = None, id_order: bool = True, subgraph: bool = False, induced: bool = True, call_limit: int = None):
274
    """
275
    Generate all VF2 mappings between graphs.
276
    
277
    Returns iterator over all possible isomorphic mappings.
278
    
279
    Parameters:
280
    - first: First graph
281
    - second: Second graph
282
    - node_matcher (callable, optional): Function to compare node data
283
    - edge_matcher (callable, optional): Function to compare edge data
284
    - id_order (bool): Use ID-based ordering
285
    - subgraph (bool): Find subgraph isomorphisms if True
286
    - induced (bool): Check induced subgraphs if True
287
    - call_limit (int, optional): Limit on VF2 algorithm iterations
288
    
289
    Returns:
290
    Iterable[NodeMap]: Iterator over node index mappings
291
    """
292
```
293

294
### Graph Properties
295

296
Functions for computing various graph-theoretic properties and measures.
297

298
```python { .api }
299
def transitivity(graph) -> float:
300
    """
301
    Compute transitivity (global clustering coefficient) of graph.
302
    
303
    Transitivity is the fraction of triangles to connected triples,
304
    measuring the tendency of nodes to cluster together.
305
    
306
    Parameters:
307
    - graph: Input graph (PyGraph or PyDiGraph)
308
    
309
    Returns:
310
    float: Transitivity coefficient (0.0 to 1.0)
311
    
312
    Note: Assumes no parallel edges or self-loops for accurate results.
313
    """
314

315
def core_number(graph) -> dict:
316
    """
317
    Compute k-core decomposition of graph.
318
    
319
    The k-core is the maximal subgraph where each vertex has
320
    degree at least k. Core number is the highest k for which
321
    a vertex belongs to the k-core.
322
    
323
    Parameters:
324
    - graph: Input graph (PyGraph or PyDiGraph)
325
    
326
    Returns:
327
    dict: Mapping of node indices to core numbers
328
    
329
    Note: Assumes no parallel edges or self-loops.
330
    """
331

332
def complement(graph):
333
    """
334
    Compute complement of graph.
335
    
336
    The complement has the same vertices but complementary edges:
337
    edges present in original are absent in complement and vice versa.
338
    
339
    Parameters:
340
    - graph: Input graph (PyGraph or PyDiGraph)
341
    
342
    Returns:
343
    Same type as input: Complement graph
344
    
345
    Note: Never creates parallel edges or self-loops.
346
    """
347

348
def isolates(graph):
349
    """
350
    Find isolated nodes (degree 0) in graph.
351
    
352
    Parameters:
353
    - graph: Input graph
354
    
355
    Returns:
356
    NodeIndices: List of isolated node indices
357
    """
358
```
359

360
### Bipartite Analysis
361

362
Functions for analyzing and testing bipartite graph properties.
363

364
```python { .api }
365
def is_bipartite(graph) -> bool:
366
    """
367
    Test if graph is bipartite.
368
    
369
    A graph is bipartite if its vertices can be colored with
370
    two colors such that no adjacent vertices have the same color.
371
    
372
    Parameters:
373
    - graph: Input graph
374
    
375
    Returns:
376
    bool: True if graph is bipartite, False otherwise
377
    """
378

379
def two_color(graph) -> dict:
380
    """
381
    Compute two-coloring of bipartite graph.
382
    
383
    Parameters:
384
    - graph: Input graph
385
    
386
    Returns:
387
    dict or None: Mapping of node indices to colors (0 or 1),
388
                  or None if graph is not bipartite
389
    """
390
```
391

392
### Spanning Trees
393

394
Functions for finding spanning trees in undirected graphs.
395

396
```python { .api }
397
def minimum_spanning_tree(graph, weight_fn = None, default_weight: float = 1.0):
398
    """
399
    Find minimum spanning tree using Prim's algorithm.
400
    
401
    Parameters:
402
    - graph: PyGraph input
403
    - weight_fn (callable, optional): Function to extract edge weight
404
    - default_weight (float): Default edge weight
405
    
406
    Returns:
407
    EdgeList: List of edges forming minimum spanning tree
408
    """
409
```
410

411
## Usage Examples
412

413
### Connectivity Analysis
414

415
```python
416
import rustworkx as rx
417

418
# Create directed graph with multiple components
419
digraph = rx.PyDiGraph()
420
nodes = digraph.add_nodes_from(['A', 'B', 'C', 'D', 'E'])
421
digraph.add_edges_from([
422
    (nodes[0], nodes[1], None),  # A -> B
423
    (nodes[1], nodes[2], None),  # B -> C
424
    (nodes[2], nodes[0], None),  # C -> A (creates SCC)
425
    (nodes[3], nodes[4], None),  # D -> E (separate component)
426
])
427

428
# Analyze connectivity
429
sccs = rx.strongly_connected_components(digraph)
430
print(f"Strongly connected components: {sccs}")
431

432
is_strong = rx.is_strongly_connected(digraph)
433
is_weak = rx.is_weakly_connected(digraph)
434
print(f"Strongly connected: {is_strong}")
435
print(f"Weakly connected: {is_weak}")
436
```
437

438
### Cut Points and Bridges Analysis
439

440
```python
441
# Create graph with articulation points
442
graph = rx.PyGraph()
443
nodes = graph.add_nodes_from(['A', 'B', 'C', 'D', 'E'])
444
graph.add_edges_from([
445
    (nodes[0], nodes[1], None),  # A-B
446
    (nodes[1], nodes[2], None),  # B-C (B is articulation point)
447
    (nodes[2], nodes[3], None),  # C-D
448
    (nodes[3], nodes[4], None),  # D-E
449
])
450

451
# Find critical vertices and edges
452
articulation_pts = rx.articulation_points(graph)
453
bridge_edges = rx.bridges(graph)
454
biconnected = rx.biconnected_components(graph)
455

456
print(f"Articulation points: {articulation_pts}")
457
print(f"Bridges: {bridge_edges}")
458
print(f"Biconnected components: {biconnected}")
459
```
460

461
### Topological Analysis
462

463
```python
464
# Create DAG for topological analysis
465
dag = rx.PyDiGraph()
466
tasks = dag.add_nodes_from(['Start', 'Task1', 'Task2', 'Task3', 'End'])
467
dag.add_edges_from([
468
    (tasks[0], tasks[1], None),  # Start -> Task1
469
    (tasks[0], tasks[2], None),  # Start -> Task2
470
    (tasks[1], tasks[3], None),  # Task1 -> Task3
471
    (tasks[2], tasks[3], None),  # Task2 -> Task3
472
    (tasks[3], tasks[4], None),  # Task3 -> End
473
])
474

475
# Check if DAG and get topological order
476
is_dag = rx.is_directed_acyclic_graph(dag)
477
if is_dag:
478
    topo_order = rx.topological_sort(dag)
479
    longest_path = rx.dag_longest_path(dag)
480
    print(f"Topological order: {topo_order}")
481
    print(f"Longest path: {longest_path}")
482
else:
483
    print("Graph contains cycles!")
484
```
485

486
### Isomorphism Testing
487

488
```python
489
# Create two structurally identical graphs
490
graph1 = rx.PyGraph()
491
nodes1 = graph1.add_nodes_from(['X', 'Y', 'Z'])
492
graph1.add_edges_from([(nodes1[0], nodes1[1], 1), (nodes1[1], nodes1[2], 2)])
493

494
graph2 = rx.PyGraph()  
495
nodes2 = graph2.add_nodes_from(['A', 'B', 'C'])
496
graph2.add_edges_from([(nodes2[0], nodes2[1], 1), (nodes2[1], nodes2[2], 2)])
497

498
# Test structural isomorphism
499
is_iso = rx.is_isomorphic(graph1, graph2)
500
print(f"Structurally isomorphic: {is_iso}")
501

502
# Test with node data matching
503
is_iso_nodes = rx.is_isomorphic_node_match(
504
    graph1, graph2, 
505
    matcher=lambda x, y: True  # Ignore node data differences
506
)
507
print(f"Isomorphic ignoring node data: {is_iso_nodes}")
508

509
# Generate all mappings
510
mappings = list(rx.vf2_mapping(graph1, graph2))
511
print(f"All isomorphic mappings: {mappings}")
512
```
513

514
### Graph Property Analysis
515

516
```python
517
# Compute various graph properties
518
properties_graph = rx.generators.erdos_renyi_gnp_random_graph(20, 0.3)
519

520
# Structural properties
521
transitivity = rx.transitivity(properties_graph)
522
core_nums = rx.core_number(properties_graph)
523
isolated_nodes = rx.isolates(properties_graph)
524
is_bip = rx.is_bipartite(properties_graph)
525

526
print(f"Transitivity: {transitivity:.3f}")
527
print(f"Max core number: {max(core_nums.values()) if core_nums else 0}")
528
print(f"Isolated nodes: {len(isolated_nodes)}")
529
print(f"Is bipartite: {is_bip}")
530

531
# Two-coloring if bipartite
532
if is_bip:
533
    coloring = rx.two_color(properties_graph)
534
    print(f"Two-coloring: {coloring}")
535
```
536

537
### Reachability Analysis
538

539
```python
540
# Analyze reachability in directed graph
541
hierarchy = rx.PyDiGraph()
542
levels = hierarchy.add_nodes_from(['Root', 'Level1A', 'Level1B', 'Level2A', 'Level2B'])
543
hierarchy.add_edges_from([
544
    (levels[0], levels[1], None),  # Root -> Level1A
545
    (levels[0], levels[2], None),  # Root -> Level1B
546
    (levels[1], levels[3], None),  # Level1A -> Level2A
547
    (levels[2], levels[4], None),  # Level1B -> Level2B
548
])
549

550
# Find ancestors and descendants
551
root_descendants = rx.descendants(hierarchy, levels[0])
552
leaf_ancestors = rx.ancestors(hierarchy, levels[3])
553

554
print(f"Descendants of root: {root_descendants}")
555
print(f"Ancestors of Level2A: {leaf_ancestors}")
556
```
557

558
### Minimum Spanning Tree
559

560
```python
561
# Find MST in weighted graph
562
weighted_graph = rx.PyGraph()
563
cities = weighted_graph.add_nodes_from(['A', 'B', 'C', 'D'])
564
weighted_graph.add_edges_from([
565
    (cities[0], cities[1], 5),   # A-B: distance 5
566
    (cities[0], cities[2], 3),   # A-C: distance 3  
567
    (cities[1], cities[2], 2),   # B-C: distance 2
568
    (cities[1], cities[3], 4),   # B-D: distance 4
569
    (cities[2], cities[3], 6),   # C-D: distance 6
570
])
571

572
mst_edges = rx.minimum_spanning_tree(
573
    weighted_graph,
574
    weight_fn=lambda x: x
575
)
576

577
print(f"MST edges: {mst_edges}")
578
total_weight = sum(weighted_graph.edges()[i] for _, _, i in mst_edges)
579
print(f"Total MST weight: {total_weight}")
580
```