gh-k-dense-ai-claude-scientific-skills-scientific-skills/skills/networkx/references/algorithms.md

NetworkX Graph Algorithms

Shortest Paths

Single Source Shortest Paths

# 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

# 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

# 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)

# 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)

# 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

# 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

# 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

# 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

# Reciprocal of average shortest path length
closeness = nx.closeness_centrality(G)

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

Eigenvector Centrality

# 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

# 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

# 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

# Overall clustering (ratio of triangles to triads)
transitivity = nx.transitivity(G)

Triangles

# Count triangles per node
triangles = nx.triangles(G)

# Total number of triangles
total_triangles = sum(triangles.values()) // 3

Community Detection

Modularity-Based

from networkx.algorithms import community

# Greedy modularity maximization
communities = community.greedy_modularity_communities(G)

# Compute modularity
modularity = community.modularity(G, communities)

Label Propagation

# Fast community detection
communities = community.label_propagation_communities(G)

Girvan-Newman

# Hierarchical community detection via edge betweenness
comp = community.girvan_newman(G)
limited = itertools.takewhile(lambda c: len(c) <= 10, comp)
for communities in limited:
    print(tuple(sorted(c) for c in communities))

Matching and Covering

Maximum Matching

# Maximum cardinality matching
matching = nx.max_weight_matching(G)

# Check if matching is valid
is_matching = nx.is_matching(G, matching)
is_perfect = nx.is_perfect_matching(G, matching)

Minimum Vertex/Edge Cover

# Minimum set of nodes covering all edges
min_vertex_cover = nx.approximation.min_weighted_vertex_cover(G)

# Minimum edge dominating set
min_edge_dom = nx.approximation.min_edge_dominating_set(G)

Tree Algorithms

Minimum Spanning Tree

# Kruskal's or Prim's algorithm
mst = nx.minimum_spanning_tree(G, weight='weight')

# Maximum spanning tree
mst_max = nx.maximum_spanning_tree(G, weight='weight')

# Enumerate all spanning trees
all_spanning = nx.all_spanning_trees(G)

Tree Properties

# Check if graph is tree
is_tree = nx.is_tree(G)
is_forest = nx.is_forest(G)

# For directed graphs
is_arborescence = nx.is_arborescence(G)

Flow and Capacity

Maximum Flow

# Maximum flow value
flow_value = nx.maximum_flow_value(G, s=1, t=5, capacity='capacity')

# Maximum flow with flow dict
flow_value, flow_dict = nx.maximum_flow(G, s=1, t=5, capacity='capacity')

# Minimum cut
cut_value, partition = nx.minimum_cut(G, s=1, t=5, capacity='capacity')

Cost Flow

# Minimum cost flow
flow_dict = nx.min_cost_flow(G, demand='demand', capacity='capacity', weight='weight')
cost = nx.cost_of_flow(G, flow_dict, weight='weight')

Cycles

Finding Cycles

# Simple cycles (for directed graphs)
cycles = list(nx.simple_cycles(G))

# Cycle basis (for undirected graphs)
basis = nx.cycle_basis(G)

# Check if acyclic
is_dag = nx.is_directed_acyclic_graph(G)

Topological Sorting

# Only for DAGs
try:
    topo_order = list(nx.topological_sort(G))
except nx.NetworkXError:
    print("Graph has cycles")

# All topological sorts
all_topo = nx.all_topological_sorts(G)

Cliques

Finding Cliques

# All maximal cliques
cliques = list(nx.find_cliques(G))

# Maximum clique (NP-complete, approximate)
max_clique = nx.approximation.max_clique(G)

# Clique number
clique_number = nx.graph_clique_number(G)

# Number of maximal cliques containing each node
clique_counts = nx.node_clique_number(G)

Graph Coloring

Node Coloring

# Greedy coloring
coloring = nx.greedy_color(G, strategy='largest_first')

# Different strategies: 'largest_first', 'smallest_last', 'random_sequential'
coloring = nx.greedy_color(G, strategy='smallest_last')

Isomorphism

Graph Isomorphism

# Check if graphs are isomorphic
is_isomorphic = nx.is_isomorphic(G1, G2)

# Get isomorphism mapping
from networkx.algorithms import isomorphism
GM = isomorphism.GraphMatcher(G1, G2)
if GM.is_isomorphic():
    mapping = GM.mapping

Subgraph Isomorphism

# Check if G1 is subgraph isomorphic to G2
is_subgraph_iso = nx.is_isomorphic(G1, G2.subgraph(nodes))

Traversal Algorithms

Depth-First Search (DFS)

# DFS edges
dfs_edges = list(nx.dfs_edges(G, source=1))

# DFS tree
dfs_tree = nx.dfs_tree(G, source=1)

# DFS predecessors
dfs_pred = nx.dfs_predecessors(G, source=1)

# Preorder and postorder
preorder = list(nx.dfs_preorder_nodes(G, source=1))
postorder = list(nx.dfs_postorder_nodes(G, source=1))

Breadth-First Search (BFS)

# BFS edges
bfs_edges = list(nx.bfs_edges(G, source=1))

# BFS tree
bfs_tree = nx.bfs_tree(G, source=1)

# BFS predecessors and successors
bfs_pred = nx.bfs_predecessors(G, source=1)
bfs_succ = nx.bfs_successors(G, source=1)

Efficiency Considerations

Algorithm Complexity

• Many algorithms have parameters to control computation time
• For large graphs, consider approximate algorithms
• Use k parameter to sample nodes in centrality calculations
• Set max_iter for iterative algorithms

Memory Usage

• Iterator-based functions (e.g., nx.simple_cycles()) save memory
• Convert to list only when necessary
• Use generators for large result sets

Numerical Precision

When using weighted algorithms with floating-point numbers, results are approximate. Consider:

• Using integer weights when possible
• Setting appropriate tolerance parameters
• Being aware of accumulated rounding errors in iterative algorithms