NetworkX + NumPy: Optional dependency impact on dense graph performance

Performance Impact of NumPy Optionality

NetworkX should not enforce NumPy as a mandatory dependency. Doing so would break the library's core value proposition of being a lightweight, pure-Python implementation suitable for minimal environments and small-scale prototyping. However, for dense-graph workloads, the absence of NumPy creates a significant performance cliff because NetworkX falls back to Python lists and dictionary-based iterations, which lack the vectorization capabilities of NumPy arrays.

Analysis of Divergent Runtime Paths

The performance divergence occurs primarily during the transition from graph traversal to matrix operations. While NetworkX's internal data structure remains a dictionary of dictionaries regardless of NumPy's presence, functions like to_numpy_array() or specific centrality algorithms rely on NumPy for acceleration. In a CI environment without NumPy, these operations either fail or execute via suboptimal Python loops, masking regressions that only appear in production environments where NumPy is installed.

Detection and Documentation Mechanisms

To detect divergent paths without forcing a hard dependency, the following mechanisms are recommended:

• Dependency Auditing: Implement a runtime check at the start of performance-critical pipelines to log the presence of accelerators.
• Environment-Aware Testing: Configure CI matrices to run a subset of dense-graph benchmarks both with and without NumPy to quantify the "performance gap."
• Explicit Casting: Instead of relying on implicit fallbacks, developers should explicitly call nx.to_numpy_array(). If NumPy is missing, this will raise an ImportError, making the missing dependency visible immediately rather than silently degrading performance.

Version Constraints and Fallback Strategies

To avoid subtle bugs and ensure reproducibility, adopt these strategies:

1. Pin Minimum Versions: Specify numpy>=1.20 (or the version corresponding to the NetworkX release) in requirements.txt to ensure compatibility with modern array API behaviors.
2. Type Validation: When using fallback strategies, verify the return type of adjacency functions. If the result is a Python list instead of a numpy.ndarray, trigger a warning that vectorized operations are unavailable.
3. Scoped Conversion: Only convert to NumPy arrays for the specific duration of the dense computation to avoid the $O(V^2)$ memory overhead associated with dense matrices in large graphs.

Diagnostic Detail Needed: Are your CI environments currently failing silently (returning slower results) or raising ImportError when NumPy-dependent functions are called?