tessl/pypi-networkx
Python package for creating and manipulating graphs and networks
—
Pending
algorithms.mddocs/
Graph Algorithms
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.
Capabilities
Shortest Path Algorithms
Algorithms for finding shortest paths between nodes in graphs, supporting weighted and unweighted graphs.
def shortest_path(G, source=None, target=None, weight=None, method='dijkstra'):
"""
Compute shortest paths in the graph.
Parameters:
- G: NetworkX graph
- source: Starting node (if None, compute from all nodes)
- target: Ending node (if None, compute to all nodes)
- weight: Edge data key for weights
- method: Algorithm ('dijkstra', 'bellman-ford', 'unweighted')
Returns:
Path as list of nodes, or dict of paths
"""
def shortest_path_length(G, source=None, target=None, weight=None, method='dijkstra'):
"""Compute shortest path lengths."""
def all_shortest_paths(G, source, target, weight=None, method='dijkstra'):
"""Compute all shortest paths between source and target."""
def dijkstra_path(G, source, target, weight='weight'):
"""Shortest path using Dijkstra's algorithm."""
def bellman_ford_path(G, source, target, weight='weight'):
"""Shortest path using Bellman-Ford algorithm."""
def floyd_warshall(G, nodelist=None, weight='weight'):
"""All-pairs shortest path lengths using Floyd-Warshall."""Centrality Measures
Algorithms to compute various centrality measures that identify important nodes in networks.
def betweenness_centrality(G, k=None, normalized=True, weight=None, endpoints=False, seed=None):
"""
Compute betweenness centrality for nodes.
Parameters:
- G: NetworkX graph
- k: Number of nodes to sample (for approximation)
- normalized: Whether to normalize values
- weight: Edge data key for weights
- endpoints: Include endpoints in path counts
- seed: Random seed for sampling
Returns:
Dict mapping nodes to centrality values
"""
def closeness_centrality(G, u=None, distance=None, wf_improved=True):
"""Compute closeness centrality for nodes."""
def degree_centrality(G):
"""Compute degree centrality for nodes."""
def eigenvector_centrality(G, max_iter=100, tol=1e-06, nstart=None, weight=None):
"""Compute eigenvector centrality for nodes."""
def pagerank(G, alpha=0.85, personalization=None, max_iter=100, tol=1e-06, nstart=None, weight='weight', dangling=None):
"""Compute PageRank centrality for nodes."""
def katz_centrality(G, alpha=0.1, beta=1.0, max_iter=1000, tol=1e-06, nstart=None, normalized=True, weight=None):
"""Compute Katz centrality for nodes."""Connected Components
Algorithms for finding connected components in graphs.
def connected_components(G):
"""
Generate connected components of an undirected graph.
Parameters:
- G: NetworkX undirected graph
Returns:
Generator of sets of nodes, one for each component
"""
def strongly_connected_components(G):
"""Generate strongly connected components of a directed graph."""
def weakly_connected_components(G):
"""Generate weakly connected components of a directed graph."""
def number_connected_components(G):
"""Return number of connected components."""
def is_connected(G):
"""Return True if graph is connected."""
def node_connected_component(G, n):
"""Return the connected component containing node n."""Clustering and Community Detection
Algorithms for analyzing clustering properties and detecting communities in networks.
def clustering(G, nodes=None, weight=None):
"""
Compute clustering coefficient for nodes.
Parameters:
- G: NetworkX graph
- nodes: Compute for specific nodes (default: all)
- weight: Edge data key for weights
Returns:
Dict mapping nodes to clustering coefficients
"""
def average_clustering(G, nodes=None, weight=None, count_zeros=True):
"""Compute average clustering coefficient."""
def transitivity(G):
"""Compute transitivity (global clustering coefficient)."""
def triangles(G, nodes=None):
"""Compute number of triangles for nodes."""
def square_clustering(G, nodes=None):
"""Compute square clustering coefficient."""Centrality Algorithms - Edge Centrality
Centrality measures for edges rather than nodes.
def edge_betweenness_centrality(G, k=None, normalized=True, weight=None, seed=None):
"""Compute betweenness centrality for edges."""
def edge_closeness_centrality(G, u=None, distance=None, wf_improved=True):
"""Compute closeness centrality for edges."""
def edge_current_flow_betweenness_centrality(G, normalized=True, weight=None, dtype=float, solver='full'):
"""Compute current-flow betweenness centrality for edges."""Traversal Algorithms
Graph traversal algorithms for systematic exploration of graph structure.
def dfs_edges(G, source=None, depth_limit=None):
"""
Iterate over edges in depth-first search.
Parameters:
- G: NetworkX graph
- source: Starting node
- depth_limit: Maximum depth to search
Returns:
Iterator of edges
"""
def dfs_tree(G, source=None, depth_limit=None):
"""Return DFS tree from source."""
def bfs_edges(G, source, reverse=False, depth_limit=None, sort_neighbors=None):
"""Iterate over edges in breadth-first search."""
def bfs_tree(G, source, reverse=False, depth_limit=None, sort_neighbors=None):
"""Return BFS tree from source."""
def dfs_preorder_nodes(G, source=None, depth_limit=None):
"""Generate nodes in depth-first preorder."""
def dfs_postorder_nodes(G, source=None, depth_limit=None):
"""Generate nodes in depth-first postorder."""Flow Algorithms
Network flow algorithms for computing maximum flows, minimum cuts, and minimum cost flows.
def maximum_flow(G, s, t, capacity='capacity', flow_func=None, **kwargs):
"""
Find maximum flow between source and sink.
Parameters:
- G: NetworkX graph
- s: Source node
- t: Sink node
- capacity: Edge data key for capacity values
- flow_func: Flow algorithm to use
Returns:
Tuple of (flow_value, flow_dict)
"""
def minimum_cut(G, s, t, capacity='capacity', flow_func=None):
"""Find minimum cut between source and sink."""
def max_flow_min_cost(G, s, t, capacity='capacity', weight='weight'):
"""Find maximum flow of minimum cost."""
def min_cost_flow(G, demand='demand', capacity='capacity', weight='weight'):
"""Find minimum cost flow satisfying demands."""
def network_simplex(G, demand='demand', capacity='capacity', weight='weight'):
"""Solve minimum cost flow using network simplex."""Matching Algorithms
Algorithms for finding matchings in graphs.
def max_weight_matching(G, maxcardinality=False, weight='weight'):
"""
Compute maximum-weight matching of G.
Parameters:
- G: NetworkX undirected graph
- maxcardinality: If True, compute maximum-cardinality matching
- weight: Edge data key for weights
Returns:
Set of edges in the matching
"""
def is_matching(G, matching):
"""Return True if matching is a valid matching."""
def is_maximal_matching(G, matching):
"""Return True if matching is maximal."""
def is_perfect_matching(G, matching):
"""Return True if matching is perfect."""Tree Algorithms
Algorithms for working with trees and computing spanning trees.
def minimum_spanning_tree(G, weight='weight', algorithm='kruskal', ignore_nan=False):
"""
Compute minimum spanning tree of graph.
Parameters:
- G: NetworkX undirected graph
- weight: Edge data key for weights
- algorithm: Algorithm to use ('kruskal', 'prim', 'boruvka')
- ignore_nan: Ignore NaN weights
Returns:
NetworkX Graph containing the MST
"""
def maximum_spanning_tree(G, weight='weight', algorithm='kruskal', ignore_nan=False):
"""Compute maximum spanning tree of graph."""
def minimum_spanning_edges(G, weight='weight', algorithm='kruskal', data=True, ignore_nan=False):
"""Generate edges of minimum spanning tree."""
def is_tree(G):
"""Return True if G is a tree."""
def is_forest(G):
"""Return True if G is a forest."""Isomorphism
Graph isomorphism algorithms for comparing graph structure.
def is_isomorphic(G1, G2, node_match=None, edge_match=None):
"""
Return True if graphs G1 and G2 are isomorphic.
Parameters:
- G1, G2: NetworkX graphs
- node_match: Function for comparing node attributes
- edge_match: Function for comparing edge attributes
Returns:
Boolean indicating if graphs are isomorphic
"""
def could_be_isomorphic(G1, G2):
"""Return False if graphs are definitely not isomorphic."""
def fast_could_be_isomorphic(G1, G2):
"""Return False if graphs are definitely not isomorphic (fast)."""
def faster_could_be_isomorphic(G1, G2):
"""Return False if graphs are definitely not isomorphic (faster)."""Community Detection
Algorithms for finding communities and modules in networks.
def louvain_communities(G, weight='weight', resolution=1, threshold=1e-07, seed=None):
"""
Find communities using Louvain algorithm.
Parameters:
- G: NetworkX graph
- weight: Edge data key for weights
- resolution: Resolution parameter
- threshold: Modularity gain threshold
- seed: Random seed
Returns:
Generator of sets of nodes, one for each community
"""
def greedy_modularity_communities(G, weight=None, resolution=1, cutoff=1, best_n=None):
"""Find communities using greedy modularity maximization."""
def label_propagation_communities(G, weight=None, seed=None):
"""Find communities using label propagation algorithm."""
def asyn_fluidc(G, k, max_iter=100, seed=None):
"""Find communities using asynchronous fluid communities algorithm."""Graph Coloring
Algorithms for graph vertex coloring and related problems.
def greedy_color(G, strategy='largest_first', interchange=False):
"""
Color graph using greedy algorithm.
Parameters:
- G: NetworkX graph
- strategy: Node ordering strategy
- interchange: Whether to use interchange improvement
Returns:
Dict mapping nodes to colors (integers)
"""
def equitable_color(G, num_colors):
"""Color graph with balanced color class sizes."""
def strategy_connected_sequential(G, colors, nodes):
"""Connected sequential coloring strategy."""Connectivity Analysis
Algorithms for analyzing graph connectivity and finding cuts.
def node_connectivity(G, s=None, t=None):
"""
Return node connectivity of graph.
Parameters:
- G: NetworkX graph
- s: Source node (for local connectivity)
- t: Target node (for local connectivity)
Returns:
Integer node connectivity
"""
def edge_connectivity(G, s=None, t=None):
"""Return edge connectivity of graph."""
def minimum_node_cut(G, s=None, t=None):
"""Return minimum node cut."""
def minimum_edge_cut(G, s=None, t=None):
"""Return minimum edge cut."""
def stoer_wagner(G, weight='weight', heap=None):
"""Find minimum cut using Stoer-Wagner algorithm."""Cliques and Independent Sets
Algorithms for finding cliques and independent sets.
def find_cliques(G):
"""
Find all maximal cliques in graph.
Parameters:
- G: NetworkX undirected graph
Returns:
Generator of cliques (lists of nodes)
"""
def enumerate_all_cliques(G):
"""Enumerate all cliques in graph."""
def max_clique(G):
"""Find maximum clique in graph."""
def clique_number(G):
"""Return clique number of graph."""
def maximal_independent_set(G, nodes=None, seed=None):
"""Find maximal independent set."""Usage Examples
Shortest Paths
import networkx as nx
G = nx.Graph()
G.add_weighted_edges_from([(1, 2, 0.5), (2, 3, 1.0), (1, 3, 2.0)])
# Single shortest path
path = nx.shortest_path(G, source=1, target=3, weight='weight')
print(path) # [1, 2, 3]
# All shortest paths
paths = nx.shortest_path(G, source=1, weight='weight')
print(paths) # {1: [1], 2: [1, 2], 3: [1, 2, 3]}
# Path length
length = nx.shortest_path_length(G, source=1, target=3, weight='weight')
print(length) # 1.5Centrality Analysis
G = nx.karate_club_graph()
# Compute various centrality measures
betweenness = nx.betweenness_centrality(G)
closeness = nx.closeness_centrality(G)
degree = nx.degree_centrality(G)
pagerank = nx.pagerank(G)
# Find most central nodes
most_between = max(betweenness, key=betweenness.get)
most_close = max(closeness, key=closeness.get)
print(f"Highest betweenness: node {most_between}")
print(f"Highest closeness: node {most_close}")Connected Components
G = nx.Graph()
G.add_edges_from([(1, 2), (2, 3), (4, 5), (6, 7), (7, 8)])
# Find connected components
components = list(nx.connected_components(G))
print(components) # [{1, 2, 3}, {4, 5}, {6, 7, 8}]
# Check connectivity
print(nx.is_connected(G)) # False
print(nx.number_connected_components(G)) # 3Install with Tessl CLI
npx tessl i tessl/pypi-networkx