networkx

Creates graph objects from diverse input formats including adjacency matrices, edge lists, GML, GraphML, JSON, and edge-weighted dictionaries. NetworkX uses a flexible node-edge abstraction where nodes can be any hashable Python object and edges store arbitrary attribute dictionaries, enabling heterogeneous graph representations without schema enforcement. The library automatically infers graph directionality and handles self-loops and multi-edges through specialized graph classes (DiGraph, MultiGraph, MultiDiGraph).

Implements breadth-first search (BFS), depth-first search (DFS), and shortest path algorithms (Dijkstra, Bellman-Ford, A*) using iterator-based traversal patterns that yield nodes/edges on-the-fly rather than materializing full paths. The library uses deque-based queue management for BFS and recursive/stack-based DFS, with optional weight-aware variants for weighted graphs. Path algorithms return both the shortest distance and the actual path as a list of nodes.

Analyzes bipartite graphs (graphs with two disjoint node sets where edges only connect nodes from different sets) using specialized algorithms for bipartite matching, projection, and property checking. Includes maximum bipartite matching (Hopcroft-Karp algorithm), bipartite projection (creating unipartite graphs from bipartite structure), and bipartiteness checking (2-coloring via BFS). Returns matching as edge set, projections as new Graph objects, or boolean for bipartiteness.

Exports graphs to multiple file formats including GML (Graph Modelling Language), GraphML (XML-based), JSON, edge lists (CSV/TSV), and adjacency matrices (NumPy/SciPy). Export functions serialize node/edge attributes as format-specific metadata; GML and GraphML preserve full graph structure and attributes, while edge lists and matrices lose attribute information. Supports both text-based (GML, GraphML, JSON) and binary (pickle) serialization.

Computes node importance scores using multiple centrality algorithms: degree centrality (node degree normalized by graph size), betweenness centrality (fraction of shortest paths passing through a node), closeness centrality (inverse average distance to all other nodes), eigenvector centrality (importance based on connections to important nodes), PageRank (iterative importance propagation), and harmonic centrality. Each algorithm returns a dictionary mapping nodes to numeric scores; algorithms use matrix operations (NumPy/SciPy) or iterative approximation for scalability.

Detects communities (densely-connected subgraphs) using modularity optimization algorithms (Louvain, greedy modularity), spectral clustering, and label propagation. The Louvain algorithm uses hierarchical agglomeration with local modularity optimization to find high-quality partitions; label propagation assigns community labels through iterative neighbor voting. Returns a partition as a dictionary or set of sets mapping nodes to community IDs. Modularity score quantifies partition quality (higher = better separation).

Detects graph isomorphism (structural equivalence) and finds maximum matchings (sets of non-adjacent edges) using backtracking-based isomorphism checking and augmenting path algorithms. Graph isomorphism uses VF2 algorithm with pruning heuristics to compare node/edge structure; maximum matching uses augmenting paths (Hopcroft-Karp for bipartite graphs, general matching for arbitrary graphs). Returns boolean for isomorphism or matching as a set of edge tuples.

Analyzes graph connectivity by computing connected components (maximal connected subgraphs), strongly connected components (SCCs) in directed graphs, and bridge/articulation point detection. Uses union-find (disjoint set) for component identification and Tarjan's algorithm for SCC computation. Returns components as generators of node sets or dictionaries mapping nodes to component IDs. Bridge detection identifies edges whose removal disconnects the graph; articulation points identify nodes with the same property.

Computes node positions for graph visualization using force-directed layout algorithms (spring layout using Fruchterman-Reingold), spectral layout (using graph Laplacian eigenvectors), and circular/shell layouts. Spring layout iteratively adjusts node positions to minimize edge length and node overlap using physics-inspired forces; spectral layout uses eigenvectors of the graph Laplacian for dimensionality reduction. Returns dictionary mapping nodes to (x, y) coordinate tuples suitable for matplotlib or other visualization libraries.

Computes structural properties of graphs including density (ratio of actual edges to possible edges), diameter (longest shortest path), average clustering coefficient (local triangle density), transitivity (global clustering), and assortativity (correlation of node degrees). These metrics use direct mathematical formulas or graph traversal: density is E / (V * (V-1) / 2), diameter uses all-pairs shortest paths, clustering uses triangle counting. Returns numeric scores characterizing overall graph structure.

Generates synthetic graphs from parametric models including random graphs (Erdős-Rényi), scale-free networks (Barabási-Albert preferential attachment), small-world networks (Watts-Strogatz), and regular lattices. Each model uses specific generation algorithms: Erdős-Rényi adds edges with fixed probability, Barabási-Albert iteratively adds nodes with preferential attachment to high-degree nodes, Watts-Strogatz starts with a ring lattice and rewires edges with probability. Returns a Graph object with specified number of nodes and edges.

Solves graph coloring (assigning colors to nodes such that adjacent nodes have different colors) and maximum independent set (finding largest set of non-adjacent nodes) using greedy approximation algorithms. Graph coloring uses greedy node ordering with various heuristics (largest-degree-first, smallest-degree-last); maximum independent set uses greedy selection and complement graph analysis. Returns color assignment as dictionary or independent set as list of nodes.