0
# Graph Algorithms
1

2
Comprehensive collection of graph algorithms covering all major areas of graph theory and network analysis. NetworkX provides over 100+ algorithms for analyzing graph structure, computing centrality measures, finding paths, detecting communities, and more.
3

4
## Capabilities
5

6
### Shortest Path Algorithms
7

8
Algorithms for finding shortest paths between nodes in graphs, supporting weighted and unweighted graphs.
9

10
```python { .api }
11
def shortest_path(G, source=None, target=None, weight=None, method='dijkstra'):
12
    """
13
    Compute shortest paths in the graph.
14
    
15
    Parameters:
16
    - G: NetworkX graph
17
    - source: Starting node (if None, compute from all nodes)
18
    - target: Ending node (if None, compute to all nodes)  
19
    - weight: Edge data key for weights
20
    - method: Algorithm ('dijkstra', 'bellman-ford', 'unweighted')
21
    
22
    Returns:
23
    Path as list of nodes, or dict of paths
24
    """
25

26
def shortest_path_length(G, source=None, target=None, weight=None, method='dijkstra'):
27
    """Compute shortest path lengths."""
28

29
def all_shortest_paths(G, source, target, weight=None, method='dijkstra'):
30
    """Compute all shortest paths between source and target."""
31

32
def dijkstra_path(G, source, target, weight='weight'):
33
    """Shortest path using Dijkstra's algorithm."""
34

35
def bellman_ford_path(G, source, target, weight='weight'):
36
    """Shortest path using Bellman-Ford algorithm."""
37

38
def floyd_warshall(G, nodelist=None, weight='weight'):
39
    """All-pairs shortest path lengths using Floyd-Warshall."""
40
```
41

42
### Centrality Measures
43

44
Algorithms to compute various centrality measures that identify important nodes in networks.
45

46
```python { .api }
47
def betweenness_centrality(G, k=None, normalized=True, weight=None, endpoints=False, seed=None):
48
    """
49
    Compute betweenness centrality for nodes.
50
    
51
    Parameters:
52
    - G: NetworkX graph
53
    - k: Number of nodes to sample (for approximation)
54
    - normalized: Whether to normalize values
55
    - weight: Edge data key for weights
56
    - endpoints: Include endpoints in path counts
57
    - seed: Random seed for sampling
58
    
59
    Returns:
60
    Dict mapping nodes to centrality values
61
    """
62

63
def closeness_centrality(G, u=None, distance=None, wf_improved=True):
64
    """Compute closeness centrality for nodes."""
65

66
def degree_centrality(G):
67
    """Compute degree centrality for nodes."""
68

69
def eigenvector_centrality(G, max_iter=100, tol=1e-06, nstart=None, weight=None):
70
    """Compute eigenvector centrality for nodes."""
71

72
def pagerank(G, alpha=0.85, personalization=None, max_iter=100, tol=1e-06, nstart=None, weight='weight', dangling=None):
73
    """Compute PageRank centrality for nodes."""
74

75
def katz_centrality(G, alpha=0.1, beta=1.0, max_iter=1000, tol=1e-06, nstart=None, normalized=True, weight=None):
76
    """Compute Katz centrality for nodes."""
77
```
78

79
### Connected Components
80

81
Algorithms for finding connected components in graphs.
82

83
```python { .api }
84
def connected_components(G):
85
    """
86
    Generate connected components of an undirected graph.
87
    
88
    Parameters:
89
    - G: NetworkX undirected graph
90
    
91
    Returns:
92
    Generator of sets of nodes, one for each component
93
    """
94

95
def strongly_connected_components(G):
96
    """Generate strongly connected components of a directed graph."""
97

98
def weakly_connected_components(G):
99
    """Generate weakly connected components of a directed graph."""
100

101
def number_connected_components(G):
102
    """Return number of connected components."""
103

104
def is_connected(G):
105
    """Return True if graph is connected."""
106

107
def node_connected_component(G, n):
108
    """Return the connected component containing node n."""
109
```
110

111
### Clustering and Community Detection
112

113
Algorithms for analyzing clustering properties and detecting communities in networks.
114

115
```python { .api }
116
def clustering(G, nodes=None, weight=None):
117
    """
118
    Compute clustering coefficient for nodes.
119
    
120
    Parameters:
121
    - G: NetworkX graph
122
    - nodes: Compute for specific nodes (default: all)
123
    - weight: Edge data key for weights
124
    
125
    Returns:
126
    Dict mapping nodes to clustering coefficients
127
    """
128

129
def average_clustering(G, nodes=None, weight=None, count_zeros=True):
130
    """Compute average clustering coefficient."""
131

132
def transitivity(G):
133
    """Compute transitivity (global clustering coefficient)."""
134

135
def triangles(G, nodes=None):
136
    """Compute number of triangles for nodes."""
137

138
def square_clustering(G, nodes=None):
139
    """Compute square clustering coefficient."""
140
```
141

142
### Centrality Algorithms - Edge Centrality
143

144
Centrality measures for edges rather than nodes.
145

146
```python { .api }
147
def edge_betweenness_centrality(G, k=None, normalized=True, weight=None, seed=None):
148
    """Compute betweenness centrality for edges."""
149

150
def edge_closeness_centrality(G, u=None, distance=None, wf_improved=True):
151
    """Compute closeness centrality for edges."""
152

153
def edge_current_flow_betweenness_centrality(G, normalized=True, weight=None, dtype=float, solver='full'):
154
    """Compute current-flow betweenness centrality for edges."""
155
```
156

157
### Traversal Algorithms
158

159
Graph traversal algorithms for systematic exploration of graph structure.
160

161
```python { .api }
162
def dfs_edges(G, source=None, depth_limit=None):
163
    """
164
    Iterate over edges in depth-first search.
165
    
166
    Parameters:
167
    - G: NetworkX graph
168
    - source: Starting node
169
    - depth_limit: Maximum depth to search
170
    
171
    Returns:
172
    Iterator of edges
173
    """
174

175
def dfs_tree(G, source=None, depth_limit=None):
176
    """Return DFS tree from source."""
177

178
def bfs_edges(G, source, reverse=False, depth_limit=None, sort_neighbors=None):
179
    """Iterate over edges in breadth-first search."""
180

181
def bfs_tree(G, source, reverse=False, depth_limit=None, sort_neighbors=None):
182
    """Return BFS tree from source."""
183

184
def dfs_preorder_nodes(G, source=None, depth_limit=None):
185
    """Generate nodes in depth-first preorder."""
186

187
def dfs_postorder_nodes(G, source=None, depth_limit=None):
188
    """Generate nodes in depth-first postorder."""
189
```
190

191
### Flow Algorithms
192

193
Network flow algorithms for computing maximum flows, minimum cuts, and minimum cost flows.
194

195
```python { .api }
196
def maximum_flow(G, s, t, capacity='capacity', flow_func=None, **kwargs):
197
    """
198
    Find maximum flow between source and sink.
199
    
200
    Parameters:
201
    - G: NetworkX graph  
202
    - s: Source node
203
    - t: Sink node
204
    - capacity: Edge data key for capacity values
205
    - flow_func: Flow algorithm to use
206
    
207
    Returns:
208
    Tuple of (flow_value, flow_dict)
209
    """
210

211
def minimum_cut(G, s, t, capacity='capacity', flow_func=None):
212
    """Find minimum cut between source and sink."""
213

214
def max_flow_min_cost(G, s, t, capacity='capacity', weight='weight'):
215
    """Find maximum flow of minimum cost."""
216

217
def min_cost_flow(G, demand='demand', capacity='capacity', weight='weight'):
218
    """Find minimum cost flow satisfying demands."""
219

220
def network_simplex(G, demand='demand', capacity='capacity', weight='weight'):
221
    """Solve minimum cost flow using network simplex."""
222
```
223

224
### Matching Algorithms
225

226
Algorithms for finding matchings in graphs.
227

228
```python { .api }
229
def max_weight_matching(G, maxcardinality=False, weight='weight'):
230
    """
231
    Compute maximum-weight matching of G.
232
    
233
    Parameters:
234
    - G: NetworkX undirected graph
235
    - maxcardinality: If True, compute maximum-cardinality matching
236
    - weight: Edge data key for weights
237
    
238
    Returns:
239
    Set of edges in the matching
240
    """
241

242
def is_matching(G, matching):
243
    """Return True if matching is a valid matching."""
244

245
def is_maximal_matching(G, matching):
246
    """Return True if matching is maximal."""
247

248
def is_perfect_matching(G, matching):
249
    """Return True if matching is perfect."""
250
```
251

252
### Tree Algorithms
253

254
Algorithms for working with trees and computing spanning trees.
255

256
```python { .api }
257
def minimum_spanning_tree(G, weight='weight', algorithm='kruskal', ignore_nan=False):
258
    """
259
    Compute minimum spanning tree of graph.
260
    
261
    Parameters:
262
    - G: NetworkX undirected graph
263
    - weight: Edge data key for weights
264
    - algorithm: Algorithm to use ('kruskal', 'prim', 'boruvka')
265
    - ignore_nan: Ignore NaN weights
266
    
267
    Returns:
268
    NetworkX Graph containing the MST
269
    """
270

271
def maximum_spanning_tree(G, weight='weight', algorithm='kruskal', ignore_nan=False):
272
    """Compute maximum spanning tree of graph."""
273

274
def minimum_spanning_edges(G, weight='weight', algorithm='kruskal', data=True, ignore_nan=False):
275
    """Generate edges of minimum spanning tree."""
276

277
def is_tree(G):
278
    """Return True if G is a tree."""
279

280
def is_forest(G):
281
    """Return True if G is a forest."""
282
```
283

284
### Isomorphism
285

286
Graph isomorphism algorithms for comparing graph structure.
287

288
```python { .api }
289
def is_isomorphic(G1, G2, node_match=None, edge_match=None):
290
    """
291
    Return True if graphs G1 and G2 are isomorphic.
292
    
293
    Parameters:
294
    - G1, G2: NetworkX graphs
295
    - node_match: Function for comparing node attributes
296
    - edge_match: Function for comparing edge attributes
297
    
298
    Returns:
299
    Boolean indicating if graphs are isomorphic
300
    """
301

302
def could_be_isomorphic(G1, G2):
303
    """Return False if graphs are definitely not isomorphic."""
304

305
def fast_could_be_isomorphic(G1, G2):
306
    """Return False if graphs are definitely not isomorphic (fast)."""
307

308
def faster_could_be_isomorphic(G1, G2):
309
    """Return False if graphs are definitely not isomorphic (faster)."""
310
```
311

312
### Community Detection
313

314
Algorithms for finding communities and modules in networks.
315

316
```python { .api }
317
def louvain_communities(G, weight='weight', resolution=1, threshold=1e-07, seed=None):
318
    """
319
    Find communities using Louvain algorithm.
320
    
321
    Parameters:
322
    - G: NetworkX graph
323
    - weight: Edge data key for weights
324
    - resolution: Resolution parameter
325
    - threshold: Modularity gain threshold
326
    - seed: Random seed
327
    
328
    Returns:
329
    Generator of sets of nodes, one for each community
330
    """
331

332
def greedy_modularity_communities(G, weight=None, resolution=1, cutoff=1, best_n=None):
333
    """Find communities using greedy modularity maximization."""
334

335
def label_propagation_communities(G, weight=None, seed=None):
336
    """Find communities using label propagation algorithm."""
337

338
def asyn_fluidc(G, k, max_iter=100, seed=None):
339
    """Find communities using asynchronous fluid communities algorithm."""
340
```
341

342
### Graph Coloring
343

344
Algorithms for graph vertex coloring and related problems.
345

346
```python { .api }
347
def greedy_color(G, strategy='largest_first', interchange=False):
348
    """
349
    Color graph using greedy algorithm.
350
    
351
    Parameters:
352
    - G: NetworkX graph
353
    - strategy: Node ordering strategy
354
    - interchange: Whether to use interchange improvement
355
    
356
    Returns:
357
    Dict mapping nodes to colors (integers)
358
    """
359

360
def equitable_color(G, num_colors):
361
    """Color graph with balanced color class sizes."""
362

363
def strategy_connected_sequential(G, colors, nodes):
364
    """Connected sequential coloring strategy."""
365
```
366

367
### Connectivity Analysis
368

369
Algorithms for analyzing graph connectivity and finding cuts.
370

371
```python { .api }
372
def node_connectivity(G, s=None, t=None):
373
    """
374
    Return node connectivity of graph.
375
    
376
    Parameters:
377
    - G: NetworkX graph
378
    - s: Source node (for local connectivity)
379
    - t: Target node (for local connectivity)
380
    
381
    Returns:
382
    Integer node connectivity
383
    """
384

385
def edge_connectivity(G, s=None, t=None):
386
    """Return edge connectivity of graph."""
387

388
def minimum_node_cut(G, s=None, t=None):
389
    """Return minimum node cut."""
390

391
def minimum_edge_cut(G, s=None, t=None):
392
    """Return minimum edge cut."""
393

394
def stoer_wagner(G, weight='weight', heap=None):
395
    """Find minimum cut using Stoer-Wagner algorithm."""
396
```
397

398
### Cliques and Independent Sets
399

400
Algorithms for finding cliques and independent sets.
401

402
```python { .api }
403
def find_cliques(G):
404
    """
405
    Find all maximal cliques in graph.
406
    
407
    Parameters:
408
    - G: NetworkX undirected graph
409
    
410
    Returns:
411
    Generator of cliques (lists of nodes)
412
    """
413

414
def enumerate_all_cliques(G):
415
    """Enumerate all cliques in graph."""
416

417
def max_clique(G):
418
    """Find maximum clique in graph."""
419

420
def clique_number(G):
421
    """Return clique number of graph."""
422

423
def maximal_independent_set(G, nodes=None, seed=None):
424
    """Find maximal independent set."""
425
```
426

427
## Usage Examples
428

429
### Shortest Paths
430

431
```python
432
import networkx as nx
433

434
G = nx.Graph()
435
G.add_weighted_edges_from([(1, 2, 0.5), (2, 3, 1.0), (1, 3, 2.0)])
436

437
# Single shortest path
438
path = nx.shortest_path(G, source=1, target=3, weight='weight')
439
print(path)  # [1, 2, 3]
440

441
# All shortest paths
442
paths = nx.shortest_path(G, source=1, weight='weight')
443
print(paths)  # {1: [1], 2: [1, 2], 3: [1, 2, 3]}
444

445
# Path length
446
length = nx.shortest_path_length(G, source=1, target=3, weight='weight')
447
print(length)  # 1.5
448
```
449

450
### Centrality Analysis
451

452
```python
453
G = nx.karate_club_graph()
454

455
# Compute various centrality measures
456
betweenness = nx.betweenness_centrality(G)
457
closeness = nx.closeness_centrality(G)
458
degree = nx.degree_centrality(G)
459
pagerank = nx.pagerank(G)
460

461
# Find most central nodes
462
most_between = max(betweenness, key=betweenness.get)
463
most_close = max(closeness, key=closeness.get)
464
print(f"Highest betweenness: node {most_between}")
465
print(f"Highest closeness: node {most_close}")
466
```
467

468
### Connected Components
469

470
```python
471
G = nx.Graph()
472
G.add_edges_from([(1, 2), (2, 3), (4, 5), (6, 7), (7, 8)])
473

474
# Find connected components
475
components = list(nx.connected_components(G))
476
print(components)  # [{1, 2, 3}, {4, 5}, {6, 7, 8}]
477

478
# Check connectivity
479
print(nx.is_connected(G))  # False
480
print(nx.number_connected_components(G))  # 3
481
```