Networkx

# NetworkX Graph Algorithms

## Shortest Paths

### Single Source Shortest Paths
```python
# Dijkstra's algorithm (weighted graphs)
path = nx.shortest_path(G, source=1, target=5, weight='weight')
length = nx.shortest_path_length(G, source=1, target=5, weight='weight')

# All shortest paths from source
paths = nx.single_source_shortest_path(G, source=1)
lengths = nx.single_source_shortest_path_length(G, source=1)

# Bellman-Ford (handles negative weights)
path = nx.bellman_ford_path(G, source=1, target=5, weight='weight')
```

### All Pairs Shortest Paths
```python
# All pairs (returns iterator)
for source, paths in nx.all_pairs_shortest_path(G):
    print(f"From {source}: {paths}")

# Floyd-Warshall algorithm
lengths = dict(nx.all_pairs_shortest_path_length(G))
```

### Specialized Shortest Path Algorithms
```python
# A* algorithm (with heuristic)
def heuristic(u, v):
    # Custom heuristic function
    return abs(u - v)

path = nx.astar_path(G, source=1, target=5, heuristic=heuristic, weight='weight')

# Average shortest path length
avg_length = nx.average_shortest_path_length(G)
```

## Connectivity

### Connected Components (Undirected)
```python
# Check if connected
is_connected = nx.is_connected(G)

# Number of components
num_components = nx.number_connected_components(G)

# Get all components (returns iterator of sets)
components = list(nx.connected_components(G))
largest_component = max(components, key=len)

# Get component containing specific node
component = nx.node_connected_component(G, node=1)
```

### Strong/Weak Connectivity (Directed)
```python
# Strong connectivity (mutually reachable)
is_strongly_connected = nx.is_strongly_connected(G)
strong_components = list(nx.strongly_connected_components(G))
largest_scc = max(strong_components, key=len)

# Weak connectivity (ignoring direction)
is_weakly_connected = nx.is_weakly_connected(G)
weak_components = list(nx.weakly_connected_components(G))

# Condensation (DAG of strongly connected components)
condensed = nx.condensation(G)
```

### Cuts and Connectivity
```python
# Minimum node/edge cut
min_node_cut = nx.minimum_node_cut(G, s=1, t=5)
min_edge_cut = nx.minimum_edge_cut(G, s=1, t=5)

# Node/edge connectivity
node_connectivity = nx.node_connectivity(G)
edge_connectivity = nx.edge_connectivity(G)
```

## Centrality Measures

### Degree Centrality
```python
# Fraction of nodes each node is connected to
degree_cent = nx.degree_centrality(G)

# For directed graphs
in_degree_cent = nx.in_degree_centrality(G)
out_degree_cent = nx.out_degree_centrality(G)
```

### Betweenness Centrality
```python
# Fraction of shortest paths passing through node
betweenness = nx.betweenness_centrality(G, weight='weight')

# Edge betweenness
edge_betweenness = nx.edge_betweenness_centrality(G, weight='weight')

# Approximate for large graphs
approx_betweenness = nx.betweenness_centrality(G, k=100)  # Sample 100 nodes
```

### Closeness Centrality
```python
# Reciprocal of average shortest path length
closeness = nx.closeness_centrality(G)

# For disconnected graphs
closeness = nx.closeness_centrality(G, wf_improved=True)
```

### Eigenvector Centrality
```python
# Centrality based on connections to high-centrality nodes
eigenvector = nx.eigenvector_centrality(G, max_iter=1000)

# Katz centrality (variant with attenuation factor)
katz = nx.katz_centrality(G, alpha=0.1, beta=1.0)
```

### PageRank
```python
# Google's PageRank algorithm
pagerank = nx.pagerank(G, alpha=0.85)

# Personalized PageRank
personalization = {node: 1.0 if node in [1, 2] else 0.0 for node in G}
ppr = nx.pagerank(G, personalization=personalization)
```

## Clustering

### Clustering Coefficients
```python
# Clustering coefficient for each node
clustering = nx.clustering(G)

# Average clustering coefficient
avg_clustering = nx.average_clustering(G)

# Weighted clustering
weighted_clustering = nx.clustering(G, weight='weight')
```

### Transitivity
```python
# Overall clustering (ratio of triangles to triads)
transitivit