Keywords
Python, NetworkX, Graph Algorithms

Technologies
Python, Rust

Introduction Graph algorithms are fundamental to applications such as networking, social analysis, and optimization. NetworkX is a widely used Python library due to its flexibility and ease of use, but Python’s dynamic typing and interpreted nature can limit performance on large graphs.

Rust offers memory safety without garbage collection and performance comparable to C/C++. This project investigates whether re-implementing key NetworkX algorithms in Rust can improve efficiency while maintaining correctness.

Objectives Analyse NetworkX implementations Re-implement algorithms in Rust Benchmark performance Evaluate trade-offs

NetworkX supports directed, undirected, and weighted graphs using nested dictionaries (G._adj[node][neighbor]). While flexible, this introduces overhead from hashing, object allocation, and dynamic typing.

Algorithms The project focuses on BFS, DFS, and Dijkstra’s algorithm due to their fundamental importance.

Findings NetworkX relies on dict, set, and deque, using iterative designs. However, performance is impacted by hashing, object overhead, interpreter cost, and poor data locality, suggesting advantages for lower-level implementations.