Algorithms

The backend implements 111 NetworkX algorithms plus constructors and generators for rustworkx-backed graphs. Anything outside this list stays on NetworkX when the input is still an ordinary NetworkX graph.

Automatic-dispatch policy

Explicit backend="rustworkx" calls can reach every implementation above. Automatic backend priority declines 24 functions for which conversion or result remapping is usually slower than NetworkX:

• Early exit favors NetworkX: has_path, bidirectional_shortest_path, descendants_at_distance, is_bipartite, find_cycle, find_negative_cycle, is_maximal_matching.
• Python result construction dominates: complement, all_pairs_shortest_path, all_shortest_paths, dijkstra_path, bellman_ford_path, the single_source_* and single_target_* path variants — the paths kernels materialize a path for every visited node, which is quadratic on high-diameter graphs.
• The kernel is cheaper than remapping: degree centrality variants, cycle_basis, weak connectivity, and single_source_dijkstra.

Single source-target forms of shortest_path are declined automatically whether weighted or not: NetworkX answers a pair with a bidirectional search that visits a fraction of the graph. The goal-stopped length kernels have no such handicap, so weighted single-pair shortest_path_length, dijkstra_path_length, and bellman_ford_path_length keep dispatching — measured 1.2–9× faster across path, dense, and road-network shapes (benches/bench_single_pair.py).

Generators have no size cutoff: there is no conversion cost to amortize, and the dispatcher never consults should_run for them. Random generators with an explicit seed fall back to NetworkX's sampler by default; see seeded random generators.

The eccentricity family computes rustworkx's all-pairs distance matrix, which is quadratic in memory. Automatic dispatch declines it past ~4096 nodes (a ~134 MB matrix); backend="rustworkx" runs anyway, accepting the memory cost. A single-node eccentricity request computes per-source lengths instead and has no such gate.

Compatibility limits

The backend rejects argument shapes it cannot honor:

• MultiGraph and MultiDiGraph inputs follow NetworkX's parallel-edge semantics: shortest paths take the lightest parallel edge, PageRank and HITS sum parallel weights, betweenness, bridges and articulation points collapse bundles, and spanning trees, find_cycle and line_graph report edge keys. The functions NetworkX itself refuses on multigraphs (core_number, cycle_basis, chain_decomposition, stoer_wagner, max_weight_matching, is_maximal_matching, eigenvector_centrality, katz_centrality, katz_centrality_numpy, transitivity) fall through, as do complement, cartesian_product, tensor_product and vf2pp_all_isomorphisms, whose multigraph results NetworkX keys by edge identity the rustworkx kernels drop.
• No callable weight functions.
• No cutoff on shortest-path functions.
• Betweenness is unweighted and has no k= sampling; closeness accepts a string distance, callables fall through.
• Isomorphism is structural; node_match and edge_match fall through.
• greedy_color implements largest_first, saturation_largest_first/DSATUR, and independent_set; other strategies fall through.
• max_weight_matching requires integer edge weights.
• A* requires a consistent heuristic. Disable the check with nx.config.backends.rustworkx.astar_heuristic_check = False only when you already know it is consistent.
• The native generators (path_graph, cycle_graph, …) fall through for a multigraph create_using; empty_graph and from_edgelist build a rustworkx-backed multigraph for one.
• Random generators take no create_using; random_geometric_graph samples its own positions (explicit pos falls through); barabasi_albert_graph takes no initial_graph; grid_2d_graph handles undirected, non-periodic grids; bipartite.random_graph is undirected with p < 1.

Valid differences

When an answer is not unique, rustworkx may return a different valid ordering or structure. This applies to topological order, longest DAG paths, cycle bases, chain decompositions, greedy colorings, isomorphism mappings, the order inside a BFS layer, some predecessor maps, negative-cycle starting nodes, and minimum spanning forests with tied weights. PageRank, HITS, Katz, and eigenvector centrality may differ slightly through floating-point ordering.

Random generators sample with rustworkx's RNG when nx.config.backends.rustworkx.native_seeded_generators is enabled, so a seeded call draws a different — equally valid — graph than NetworkX's for the same seed. The same seed then reproduces the same graph for a pinned rustworkx version. Deterministic generators always match NetworkX exactly.

Graph-returning algorithms return real NetworkX graphs; generators return rustworkx-backed graphs. Backend metadata publishes per-function caveats, so help(nx.function_name) shows the relevant constraints after installation.