Skip to main content Crate fnx_algorithms Copy item path Source pub use network_simplex_int::CAP_INF as NETWORK_SIMPLEX_INT_CAP_INF;pub use network_simplex_int::NetworkSimplexIntSolution ;pub use network_simplex_int::NetworkSimplexStatus ;pub use network_simplex_int::network_simplex_int ;network_simplex_int Exact-integer primal network-simplex kernel, exposed as a first-class Rust
API so sibling crates can use the exact-integer min-cost-flow path without
depending on the PyO3 binding crate. The PyO3 network_simplex_int binding
in fnx-python delegates here, keeping a single source of truth.
Exact-integer primal network-simplex kernel (first-class Rust API). AllSimplePathsResult ArborescenceIteratorState ArticulationPointsResult AverageNeighborDegreeResult AverageShortestPathLengthResult BetweennessCentralityResult BipartiteSetsResult BranchingEdge BranchingResult BridgesResult CentralityScore CgseWitnessArtifact ClosenessCentralityResult ClosenessVitalityResult ClusteringCoefficientResult CommonGraphEditDistance ComplexityWitness ComponentsResult CoreNumberResult CycleBasisResult DegreeAssortativityResult DegreeCentralityResult DensityResult DistanceMeasuresResult EccentricityEntry EdgeBetweennessCentralityResult EdgeCentralityScore EdgeConnectivityResult EdgeCutResult EigenvectorCentralityResult EulerianCircuitResult EulerianPathResult FindCliquesResult FlowEdgeValue GlobalEdgeCutResult GlobalEfficiencyResult GraphCliqueNumberResult GraphMLWriterConfig Configuration for GraphML writer, matching NX GraphMLWriter parameters. GreedyColorResult HarmonicCentralityResult HasEulerianPathResult HasPathResult HitsCentralityResult IndexedDijkstraFull Index-space single-source Dijkstra output for PyO3 path emission. IsBipartiteResult IsConnectedResult IsEulerianResult IsForestResult IsSemiEulerianResult IsTreeResult KCoreResult Result for k-core decomposition functions (k_core, k_shell, k_crust, k_corona). KTrussResult KatzCentralityResult KatzNotConverged Returned by katz_centrality_checkedKATZ_DEFAULT_MAX_ITERATIONS]. Mirrors
nx’s PowerIterationFailedConvergence contract — the Rust
scaffolding previously discarded the convergence flag, so callers
got a normalized-but-un-converged vector instead of an error
(br-r37-c1-ua4i8). LoadCentralityResult LocalEfficiencyResult MaxFlowResult MaximalMatchingResult MinCostFlowResult Result of min-cost flow computation. MinEdgeCoverResult MinimumCutResult MinimumCycleBasisCoreResult MinimumNodeCutResult MinimumSpanningTreeResult MstEdge NodeAvgNeighborDegree NodeColor NodeConnectivityResult NodeCoreNumber NodeOnionLayer NodeTriangleCount NumberConnectedComponentsResult OnionLayersResult PageRankNegativeWeight Error returned by pagerank_with_weight_checked PageRankResult PlanarEmbeddingData Per-node planar rotation data captured from a successful Boyer-Myrvold
run: (node name, neighbours in nx's PlanarEmbedding clockwise order). PruferResult ShortestPathLengthResult ShortestPathResult SpanningTreeIteratorState SquareClusteringResult StoerWagnerResult Result of stoer_wagner minimum cut. TopologicalGenerationsResult Result of topological generations. TopologicalSortResult Result of topological sort. TrianglesResult VoterankResult WeightedDistanceEntry WeightedMatchingResult WeightedPredecessorEntry WeightedShortestPathsResult BidirectionalDijkstraOutcome Outcome of bidirectional_dijkstra_undirected ChordalGraphTreewidthError ConnectedComponentsQueueArm Queue implementation selector retained for same-binary performance proofs. DfsEdgeLabel DFS edge classification. FlowError MaximalIndependentSetError MinimumCycleBasisError ModularityError PartitionSpanningTreeError RandomSpanningTreeError SpannerError CGSE_WITNESS_ARTIFACT_SCHEMA_VERSION_V1 CGSE_WITNESS_LEDGER_PATH CGSE_WITNESS_POLICY_SPEC_PATH GraphView adamic_adar_index Compute the Adamic-Adar index for pairs of nodes. all_neighbors_directed Return all neighbors of a node (for undirected: same as neighbors;
for directed: union of predecessors and successors). all_pairs_all_shortest_paths All shortest paths between all pairs of nodes. all_pairs_bellman_ford_path All-pairs Bellman-Ford returning paths only.
Returns None if a negative cycle is detected.
Matches networkx.all_pairs_bellman_ford_path(G, weight=weight). all_pairs_bellman_ford_path_length All-pairs Bellman-Ford returning distances only.
Returns None if a negative cycle is detected.
Matches networkx.all_pairs_bellman_ford_path_length(G, weight=weight). all_pairs_dijkstra All-pairs Dijkstra returning (distances, paths).
Matches networkx.all_pairs_dijkstra(G, weight=weight). all_pairs_dijkstra_directed All-pairs Dijkstra returning (distances, paths) for directed graphs. all_pairs_dijkstra_path All-pairs Dijkstra returning paths only.
Matches networkx.all_pairs_dijkstra_path(G, weight=weight). all_pairs_dijkstra_path_length All-pairs Dijkstra returning distances only.
Matches networkx.all_pairs_dijkstra_path_length(G, weight=weight). all_pairs_dijkstra_path_length_directed All-pairs Dijkstra returning distances only for directed graphs. all_pairs_dijkstra_path_length_indexed_with_pred Index-space all-pairs Dijkstra rows. Sources are implicit by row index;
targets and predecessors stay as graph indices so bindings can avoid two
temporary String allocations for every reachable pair. all_pairs_dijkstra_path_length_indexed_with_pred_directed Directed twin of all_pairs_dijkstra_path_length_indexed_with_pred all_pairs_dijkstra_path_length_with_pred All-pairs Dijkstra returning distance rows plus predecessor metadata. all_pairs_dijkstra_path_length_with_pred_directed Directed all-pairs Dijkstra returning distance rows plus predecessor metadata. all_pairs_lowest_common_ancestor Find lowest common ancestors for all pairs in a DAG. all_pairs_node_connectivity All-pairs node connectivity via node-disjoint paths. all_pairs_node_connectivity_subset Approximate node connectivity for only the requested node pairs. all_pairs_shortest_path Return all shortest paths between all pairs of nodes (unweighted BFS). all_pairs_shortest_path_directed Return all shortest paths between all pairs of nodes in a directed graph. all_pairs_shortest_path_length Return shortest path lengths between all pairs of nodes (unweighted BFS). all_pairs_shortest_path_length_directed Return shortest path lengths between all pairs of nodes in a directed graph. all_pairs_shortest_path_length_directed_indexed Directed counterpart of all_pairs_shortest_path_length_indexed all_pairs_shortest_path_length_indexed All-pairs unweighted distances indexed by graph insertion order. all_shortest_paths Return all shortest paths between source and target in an unweighted graph. all_shortest_paths_directed Return all shortest paths between source and target in a directed graph. all_shortest_paths_weighted Return all shortest paths from source to target in a weighted graph. all_shortest_paths_weighted_bellman_ford Return all shortest paths from source to target using Bellman-Ford
(undirected). Returns Err(()) if a negative cycle is reachable. all_shortest_paths_weighted_directed Return all shortest directed paths from source to target in a weighted graph. all_shortest_paths_weighted_directed_bellman_ford Return all shortest directed paths from source to target using
Bellman-Ford. Returns Err(()) if a negative cycle is reachable from
source. all_simple_paths Enumerate all simple (loopless) paths from source to target. all_simple_paths_directed Find all simple paths between source and target in a directed graph. all_topological_sorts Enumerate all topological orderings of a directed acyclic graph. all_triads Enumerate all triads in a directed graph. all_triangles Return all triangles in the graph as sorted 3-tuples. ancestors Ancestors of node in a directed graph (all nodes with a path to node). antichains Return all antichains of a DAG.
An antichain is a set of nodes where no two are connected by a directed path. approx_average_clustering Byte-exact native reimplementation of
networkx.approximation.average_clustering(G, trials, seed) for an integer
seed (br-r37-c1-approxacc). nx samples trials random nodes, picks two
random neighbours of each, and counts how many are adjacent — all over a
CPython random.Random(seed). The node indices are drawn FIRST (the list
comprehension), then sample(nbrs, 2) interleaves with the loop exactly as
nx does, so the ApproxRandom draw order is identical. Runs over
neighbors_indices (== nx’s list(G[node]) order). Caller gates n >= 1
and trials >= 1. approximate_local_node_connectivity White-Newman greedy local node connectivity approximation for an
undirected simple graph. arborescence_iterator Enumerate spanning arborescences of a directed graph in weight-sorted order. arborescence_iterator_ordered arborescence_iterator_ordered_with_partition articulation_points astar_path A* shortest path algorithm. astar_path_length A* shortest path length. attracting_components Return the attracting components of a directed graph.
An attracting component is an SCC with no outgoing edges.
Matches networkx.attracting_components(G). attribute_assortativity Attribute assortativity coefficient. attribute_assortativity_coefficient Attribute assortativity coefficient for categorical attributes. attribute_mixing_dict Attribute mixing dictionary: count edges by (source_attr, target_attr). average_degree_connectivity Compute the average degree connectivity of a graph. average_neighbor_degree Computes the average neighbor degree for each node. average_node_connectivity Return the average node connectivity of a graph.
Average of local node connectivity over all distinct pairs of nodes. average_node_connectivity_directed Compute average node connectivity over all ordered pairs in a directed graph. average_shortest_path_length Computes the average shortest path length of an undirected graph. average_shortest_path_length_directed Average shortest path length for directed graphs. balanced_tree Return a balanced tree of branching factor r and height h. barbell_graph Return the barbell graph: two complete graphs K_n1 connected by a path P_n2. barycenter Find the barycenter of a connected graph. bellman_ford_path_length Return the shortest path length from source to target using Bellman-Ford.
Matches networkx.bellman_ford_path_length(G, source, target, weight).
Returns Err(true) if a negative cycle is detected, Err(false) if no path, Ok(length) otherwise. bellman_ford_shortest_paths bellman_ford_shortest_paths_directed betweenness_centrality betweenness_centrality_directed betweenness_centrality_directed_with_params betweenness_centrality_sampled_directed_with_params betweenness_centrality_sampled_with_params betweenness_centrality_subset betweenness_centrality_subset_directed betweenness_centrality_subset_weighted Weighted subset betweenness for an undirected Graph. betweenness_centrality_subset_weighted_directed Weighted subset betweenness for a directed DiGraph (out-edges). betweenness_centrality_weighted Weighted Brandes betweenness for an undirected Graph. betweenness_centrality_weighted_directed Weighted Brandes betweenness for a directed DiGraph (out-edge projection). betweenness_centrality_with_params bfs_beam_edges BFS with beam width: at each level, keep only the top width nodes
(by some heuristic — here we use degree as proxy). bfs_edges Edges in BFS order from source on an undirected graph. bfs_edges_directed Edges in BFS order from source on a directed graph. bfs_edges_directed_reverse Edges in BFS order from source on a directed graph, following predecessors. bfs_labeled_edges BFS with edge labeling: tree edges, non-tree edges, and reverse edges. bfs_layers BFS layers from source on an undirected graph. bfs_layers_directed BFS layers from source on a directed graph. bfs_layers_directed_multi BFS layers from multiple sources on a directed graph. bfs_layers_directed_multi_with_parents br-r37-c1-6hpa9: directed sibling of bfs_layers_multi_with_parents. bfs_layers_multi BFS layers from multiple sources on an undirected graph.
Layer 0 = all sources, Layer 1 = neighbors of any source not already visited, etc.
Matches networkx.bfs_layers with an iterable of sources. bfs_layers_multi_with_parents br-r37-c1-6hpa9: multi-source BFS layers WITH the discovering parent
(None for sources) — lets bindings reproduce nx’s discovery-object
semantics without a second walk. bfs_predecessors BFS predecessors map on an undirected graph. bfs_predecessors_directed BFS predecessors map on a directed graph. bfs_successors BFS successors map on an undirected graph. bfs_successors_directed BFS successors map on a directed graph. biconnected_component_edges Return the biconnected component edges.
Each component is a list of (u, v) edges.
Matches networkx.biconnected_component_edges(G). biconnected_components Return the biconnected components of the graph.
Each component is a set of edges. Uses edge-stack based DFS.
Matches networkx.biconnected_components(G). bidirectional_dijkstra_directed Directed counterpart of bidirectional_dijkstra_undirected bidirectional_dijkstra_undirected networkx’s EXACT bidirectional Dijkstra for an undirected simple graph with a
string weight key and non-negative, finite, numeric (or absent => 1.0) edge
weights — precisely the cases the Python dispatcher routes here (multigraph,
directed, callable / non-string / negative / non-finite / non-numeric / None
weights are all delegated to nx before this is reached). bidirectional_shortest_path bidirectional_shortest_path_directed_index_meta Directed index-space sibling of bidirectional_shortest_path_directed_meta bidirectional_shortest_path_directed_meta br-r37-c1-k4wsy: directed sibling — forward over succ rows, reverse
over pred rows. The old single-pair path used a UNIDIRECTIONAL BFS,
which picks a different (equal-length) path than nx on tie-breaks
(probe: diamond s->{a,b}->t gave fnx [s,a,t] vs nx [s,b,t]). bidirectional_shortest_path_index_meta Index-space sibling of bidirectional_shortest_path_meta bidirectional_shortest_path_meta Bidirectional shortest path (unweighted BFS from both ends).
Matches networkx.bidirectional_shortest_path(G, source, target).
br-r37-c1-k4wsy: nx-faithful bidirectional BFS with discovery
metadata. Mirrors networkx _bidirectional_pred_succ LINE BY LINE:
per-round expansion of the smaller fringe (forward over succ/adj
rows, reverse over pred/adj rows, row order), pred/succ
membership checks in nx’s exact sequence (the meet check runs for
EVERY scanned w, even already-visited ones), early return mid-level.
Returns the nx path as (node, parent_used_for_display, from_reverse)
triples: endpoints have parent None; the meet node records the
RETURNING iteration’s v (which can differ from its stored parent). binomial_tree Return the binomial tree of order n (2^n nodes). bipartite_hopcroft_karp Byte-exact index-space Hopcroft-Karp maximum bipartite matching matching
networkx.bipartite.hopcroft_karp_matching (br-r37-c1-bngez). bipartite_sets Computes the two sets of a bipartite graph via BFS 2-coloring. boundary_expansion Return the boundary expansion of a set S in graph G.
boundary_expansion(G, S) = |edge_boundary(S)| / |S| bridges bull_graph Return the bull graph (5 nodes, 5 edges). cartesian_product Return the Cartesian product of G and H. cartesian_product_directed Return the Cartesian product of two directed graphs. cgse_witness_schema_version chain_decomposition Return the chain decomposition of a graph. chordal_cycle_graph Return the chordal cycle graph C_n with chords.
This creates a cycle of n nodes where node i is also connected to node (i+2) mod n. chordal_graph_cliques Return maximal cliques of a chordal graph.
A graph is chordal if every cycle of length > 3 has a chord.
Uses perfect elimination ordering to find maximal cliques efficiently. chordal_graph_treewidth Return the treewidth of a chordal graph. chromatic_polynomial Evaluate chromatic polynomial P(G, x). chvatal_graph Return the Chvátal graph (12 nodes, 24 edges). circulant_graph Return the circulant graph C_n(offsets). circular_ladder_graph Return the circular ladder graph (Möbius ladder, 2n nodes). clique_removal Ramsey-based clique removal: repeatedly extracts maximal cliques
to find a large independent set. closeness_centrality closeness_centrality_directed closeness_vitality Compute the closeness vitality for all nodes in a graph. closeness_vitality_single Compute the closeness vitality for a single node. clustering_coefficient clustering_coefficient_directed Directed clustering coefficient (Fagiolo 2007). cn_soundarajan_hopcroft Common-Neighbors Soundarajan-Hopcroft link prediction index. common_graph_edit_distance_mappings common_neighbor_centrality Common Neighbor Centrality (CCPA) link prediction index. common_neighbors Return the common neighbors of two nodes in an undirected graph. communicability_betweenness_centrality Communicability betweenness centrality. community_partition_is_valid Compute modularity of a partition. complement Return the complement of a graph. complement_digraph Return the complement of a directed graph. complement_directed Return the complement of a directed graph. complement_edges Like complementGraph. Lets the PyO3 binding skip a duplicate insertion
pass: previously the binding called this fn, walked the result
graph’s edges, and re-inserted each into a PyGraph — twice the
per-edge runtime_policy.record overhead, which dominates for
dense complements (BA500: 130 ms in nx, ~860 ms in fnx). complement_edges_directed DiGraph counterpart to complement_edgescomplement_graph Return the complement of the graph. complete_bipartite_graph Return the complete bipartite graph K_{n1, n2}. complete_multipartite_graph Return the complete multipartite graph K_{n1, n2, …}. condensation Condense a directed graph by contracting each SCC into a single node. conductance Return the conductance of a set S.
conductance(G, S) = |edge_boundary(S)| / min(vol(S), vol(V-S)) connected_components connected_components_arm connected_components_borrowed BFS that returns components as Vec<&str> borrowed from the
input graph — skips the final String::to_owned pass that the
public connected_components API performs to wrap the result in
owned Strings. Useful when the consumer only needs to read the
names (e.g., emit them across the PyO3 boundary) and would
otherwise pay an unnecessary ~|V| allocation pass per call. connected_dominating_set Return a greedy connected dominating set. connected_double_edge_swap_seeded Degree-preserving double edge swaps maintaining connectivity. constraint Burt’s constraint measure for each node. constraint_directed br-r37-c1-qbj9u (constraint): Burt’s constraint for a DIRECTED graph, unweighted. convert_node_labels_to_integers Convert node labels to integers (0, 1, 2, …). core_number Computes the core number for every node using the iterative peeling algorithm. could_be_isomorphic Fast check whether two graphs could possibly be isomorphic. cubical_graph Return the cubical graph (Q3) — 8 nodes, 12 edges. current_flow_betweenness_centrality Current-flow betweenness centrality (also known as random-walk betweenness). current_flow_betweenness_centrality_nx_ordered NetworkX-compatible current-flow betweenness for an already-RCM-ordered
simple graph and the default full-solver path. current_flow_closeness_centrality_ordered Current-flow closeness centrality for an already-RCM-ordered simple graph. current_flow_pseudo_peripheral_node NetworkX-compatible pseudo-peripheral start node for current-flow RCM. cut_size Return the size of the cut between two node sets in an undirected graph. cut_size_directed Return the size of the cut between two node sets in a directed graph. cycle_basis cycle_basis_index_cycles Compute a cycle basis for an undirected graph using Paton’s algorithm. dag_longest_path Return the longest path in a DAG. dag_longest_path_length Return the length of the longest path in a DAG. dag_longest_path_length_weighted Return the (weighted) length of the longest path in a DAG. dag_longest_path_weighted Return the longest path in a DAG using weighted edges. dedensify Dedensify a graph by compressing high-degree neighborhoods. degree_assortativity_coefficient Computes the degree assortativity coefficient of the graph. degree_assortativity_coefficient_directed br-r37-c1-d7etr: directed degree assortativity for the default (x="out", y="in") contract. nx pairs (out_degree(src), in_degree(tgt)) per DIRECTED
edge (a single pair per edge, NOT both orientations) and runs the same
Pearson over those pairs. Integer successor-CSR walk + precomputed out/in
degree vecs; the five running sums are exact f64 for any realistic graph, so
the result is byte-stable regardless of edge order and matches nx’s
mixing-matrix numeric_ac to f64 tolerance (nx normalises the matrix first,
so the two paths differ only at ULP — same situation as the undirected
kernel). Degenerate inputs (no variance in either column) yield NaN via the
zero denominator, matching nx’s invalid value divide. degree_centrality degree_centrality_directed degree_histogram Return the degree histogram of a graph. degree_mixing_dict Degree mixing dictionary: count edges by (source_degree, target_degree). degree_mixing_dict_directed Degree mixing dictionary for directed graphs. density Computes the density of an undirected graph: 2 * |E| / (|V| * (|V| - 1)). desargues_graph Return the Desargues graph (20 nodes, 30 edges). descendants Descendants of node in a directed graph (all nodes reachable from node). descendants_at_distance Nodes at exactly distance hops from source on an undirected graph. descendants_at_distance_directed Nodes at exactly distance hops from source on a directed graph. dfs_edges Edges in DFS order from source on an undirected graph. dfs_edges_directed Edges in DFS order from source on a directed graph. dfs_labeled_edges Return DFS-labeled edges from source . dfs_postorder_nodes DFS postorder nodes from source on an undirected graph. dfs_postorder_nodes_directed DFS postorder nodes from source on a directed graph. dfs_predecessors DFS predecessors map on an undirected graph. dfs_predecessors_directed DFS predecessors map on a directed graph. dfs_preorder_nodes DFS preorder nodes from source on an undirected graph. dfs_preorder_nodes_directed DFS preorder nodes from source on a directed graph. dfs_successors DFS successors map on an undirected graph. dfs_successors_directed DFS successors map on a directed graph. diamond_graph Return the diamond graph (4 nodes, 5 edges). digraph_edge_weights_all_int DiGraph counterpart to graph_edge_weights_all_intdigraph_has_negative_edge_weight Like graph_has_negative_edge_weightDiGraph. digraph_has_nonfinite_edge_weight DiGraph counterpart to graph_has_nonfinite_edge_weightdigraph_has_nonnumeric_edge_weight digraph_info Text description of a directed graph. dijkstra_path_length Return the shortest path length from source to target using Dijkstra’s
algorithm. Matches networkx.dijkstra_path_length(G, source, target, weight). dijkstra_path_length_directed Return the shortest path length from source to target using Dijkstra’s
on a directed graph. dijkstra_path_length_typed Target-only Dijkstra length with NetworkX-observable distance type metadata. dijkstra_path_length_typed_directed Directed target-only Dijkstra length with distance type metadata. dijkstra_path_to_target br-r37-c1-lc2qy (cc): single-pair weighted shortest PATH with target early-exit. dijkstra_path_to_target_directed Directed counterpart of dijkstra_path_to_targetsingle_source_dijkstra_full_directed dijkstra_predecessor_and_distance Dijkstra predecessor/distance for an undirected simple graph. dijkstra_predecessor_and_distance_directed Directed twin of dijkstra_predecessor_and_distance directed_edge_swap_seeded Directed edge swap preserving in/out degree sequences. dispersion_full Native bitset dispersion kernel for the full dict form. dispersion_node br-r37-c1-dispego: single-node (ego) Backstrom-Kleinberg dispersion. dispersion_pair Dispersion between node u and node v. distance_measures dodecahedral_graph Return the dodecahedral graph (20 nodes, 30 edges). dominance_frontiers Compute dominance frontiers for all nodes reachable from start.
Returns a map from node -> set of nodes in its dominance frontier. dominating_set Return a greedy dominating set of an undirected graph. dorogovtsev_goltsev_mendes_graph Return the Dorogovtsev-Goltsev-Mendes graph. double_edge_swap_seeded Perform nswap degree-preserving double edge swaps. edge_betweenness_centrality edge_betweenness_centrality_directed edge_betweenness_centrality_subset edge_betweenness_centrality_subset_directed edge_betweenness_centrality_subset_weighted Weighted subset edge betweenness for an undirected Graph. edge_betweenness_centrality_subset_weighted_directed Weighted subset edge betweenness for a directed DiGraph (out-edges). edge_betweenness_centrality_weighted Weighted edge betweenness for an undirected Graph (normalized). edge_betweenness_centrality_weighted_directed Weighted edge betweenness for a directed DiGraph (normalized, out-edges). edge_bfs BFS traversal yielding edges. Similar to bfs_edges but explicitly returns
edges as (u, v) tuples in BFS order. edge_bfs_directed BFS traversal yielding edges on a directed graph. edge_boundary Return the set of edges with one endpoint in nbunch1 and the other in
nbunch2. edge_boundary_directed Return the set of edges on the boundary in a directed graph. edge_connectivity_edmonds_karp edge_connectivity_edmonds_karp_directed edge_current_flow_betweenness_centrality Edge current-flow betweenness centrality. edge_current_flow_betweenness_centrality_nx_ordered NetworkX-compatible edge current-flow betweenness for an already-RCM-ordered
simple graph and the default full-solver path. edge_dfs DFS traversal yielding edges. edge_dfs_directed DFS traversal yielding edges on a directed graph. edge_disjoint_paths Find edge-disjoint paths between source and target. edge_disjoint_paths_directed Find edge-disjoint paths in a directed graph. edge_expansion Return the edge expansion of a set S.
edge_expansion(G, S) = |edge_boundary(S)| / min(|S|, |V-S|) effective_size Burt’s effective size for each node. effective_size_directed Burt’s effective size for unweighted simple directed graphs. efficiency Compute the efficiency of a pair of distinct nodes. ego_graph Return the ego graph of center within radius radius . ego_graph_directed Ego graph for a directed graph. eigenvector_centrality eigenvector_centrality_directed eigenvector_centrality_directed_with_params eigenvector_centrality_with_params enumerate_all_cliques enumerate_all_cliques_index Enumerate all cliques (not just maximal) in a graph.
Returns all cliques starting from size 1 up.
Index-space core of enumerate_all_cliquesString per clique-node (every node appears in
many cliques, so the binding resolves each Python object once and reuses it). eulerian_circuit Finds an Eulerian circuit in the graph using Hierholzer’s algorithm. eulerian_path Finds an Eulerian path in the graph using Hierholzer’s algorithm. eulerian_path_directed Finds an Eulerian path in a simple directed graph. fast_could_be_isomorphic Fast check: compares order, size, and degree sequence only (no triangles). faster_could_be_isomorphic Fastest NetworkX pre-check: compares order, size, and degree sequence. faster_could_be_isomorphic_directed Directed counterpart to faster_could_be_isomorphic. fiedler_vector_unweighted_lanczos Approximate the Fiedler vector of an unweighted simple graph with a native
safe-Rust Lanczos/Ritz solve on the subspace orthogonal to the all-ones
vector. Returns None when residual checks do not prove a valid Fiedler
vector, letting the Python wrapper fall back to its exact dense path. find_asteroidal_triple Find an asteroidal triple in the graph, if one exists. find_cliques Enumerate all maximal cliques using the Bron-Kerbosch algorithm with pivoting. find_cliques_recursive Find all maximal cliques using a recursive Bron-Kerbosch algorithm.
Returns the same result as find_cliques but uses explicit recursion. find_cycle_directed Find a cycle in the directed graph. Returns Some(cycle) where cycle is a
list of nodes forming the cycle, or None if the graph is acyclic.
Uses DFS-based cycle detection. find_cycle_undirected Find a cycle in an undirected graph. Returns Some(cycle) or None. find_negative_cycle Find a negative cycle in a weighted graph using Bellman-Ford.
Returns Some(cycle) if a negative-weight cycle exists, None otherwise.
Matches networkx.find_negative_cycle(G, source, weight). flow_hierarchy_directed Flow hierarchy of a directed graph. floyd_warshall Floyd-Warshall all-pairs shortest paths (dense, O(V^3)).
Returns a nested map: source -> target -> distance.
Matches networkx.floyd_warshall(G, weight=weight). floyd_warshall_predecessor_and_distance Floyd-Warshall with predecessors.
Returns (distances, predecessors) where predecessors[u][v] = next-to-last node on path u->v.
Matches networkx.floyd_warshall_predecessor_and_distance(G, weight=weight). from_prufer_sequence Reconstruct a labeled tree from a Prüfer sequence. frucht_graph Return the Frucht graph (12 nodes, 18 edges) — smallest cubic graph with no automorphism. full_join Return the full join of two graphs. full_rary_tree Return the full r-ary tree of height h. generalized_degree Generalized degree: for each node, returns a map from triangle count
to the number of neighbors with that many shared triangles. generalized_degree_for br-r37-c1-gdsub (cc): generalized-degree triangle-multiplicity distribution for a
SUBSET of nodes. generalized_degree(G, nodes=<list>) previously ran the Python
_triangles_and_degree_iter_local neighbor-intersection loop (0.76-0.81x vs nx); the
per-node kernel here is lazy (graph.neighbors per node, no whole-graph setup), so
restricting it to targets is O(|S|*deg^2). Byte-identical to the all-node path (same
per-node body) — the caller gates on number_of_selfloops(G) == 0 because this kernel
counts a self-loop as a neighbour (nx excludes them), matching the nodes=None gate. generalized_petersen_graph Return the generalized Petersen graph GP(n, k). generate_edgelist Generate edgelist string representation. generate_random_paths Generate random paths from source by random walking. generic_bfs_edges BFS edges with depth limit. geometric_edges Return edges for a random geometric graph: connect nodes within radius. get_edge_attributes Get a specific attribute from all edges. get_node_attributes Get a specific attribute from all nodes. girth Return the girth (length of the shortest cycle) of an undirected graph.
Returns None if the graph is acyclic (a forest).
Matches networkx.girth(G). global_edge_connectivity_edmonds_karp global_edge_connectivity_edmonds_karp_directed global_efficiency Compute the average global efficiency of the graph. global_minimum_edge_cut_edmonds_karp global_minimum_node_cut Compute global minimum node cut: the smallest set of nodes whose removal disconnects the graph. global_minimum_node_cut_directed Compute global minimum node cut on a directed graph using NetworkX semantics. global_node_connectivity Compute global node connectivity: minimum s-t node connectivity over all pairs. global_node_connectivity_directed Compute global node connectivity for a directed graph by checking all ordered pairs. global_parameters Return the global parameters of a distance-regular graph. global_reaching_centrality Global reaching centrality for undirected graphs. global_reaching_centrality_directed Global reaching centrality.
C_G = sum(C_max - C_L(v)) / (n - 1) where C_max = max(C_L(v)).
Matches networkx.global_reaching_centrality(G). gomory_hu_tree Build Gomory-Hu tree using iterative max-flow. google_matrix Compute the Google PageRank matrix: alpha * S + (1-alpha) * v * e^T google_matrix_directed Google matrix for directed graphs. graph_clique_number Return the size of the largest maximal clique (the graph’s clique number). graph_compose Return the composition of two graphs. graph_difference Return the difference of two graphs. graph_edge_weights_all_int True iff every present value at weight_attr is an integer variant (missing
keys default to int 1, so they do not break the all-int property). Mirrors
the Python _sp_edge_weights_all_int gate, replacing its O(E) EdgeView scan. graph_has_negative_edge_weight Return true if any edge in graph carries a finite negative
value at weight_attr. Missing or non-finite values are skipped
(treated as the unweighted default). graph_has_nonfinite_edge_weight Return true if any edge in graph carries a value at
weight_attr that is non-numeric (can’t be converted to f64) or
non-finite (NaN / ±∞). Used by the Python pagerank dispatcher
(br-r37-c1-s0tno) to decide whether to delegate to nx — pagerank
power iteration over signed/non-finite transition matrices is
numerically unstable, so the dispatcher needs a fast O(|E|) Rust
scan instead of the previous Python edge iteration. graph_has_nonnumeric_edge_weight graph_info Text description of an undirected graph. graph_intersection Return the intersection of two graphs. graph_symmetric_difference Return the symmetric difference of two graphs. graph_union Return the union of two graphs. greedy_color Greedy graph coloring in canonical (sorted) node order. greedy_color_directed_largest_first br-r37-c1-vevfq: largest_first greedy colouring for a DIRECTED graph. greedy_color_with_strategy Greedy graph coloring with a specified node ordering strategy. greedy_modularity_communities Greedy modularity communities (Clauset-Newman-Moore algorithm). grid_2d_graph Return the 2D grid graph (m x n nodes). grid_graph Return the n-dimensional grid graph. group_betweenness_centrality Group betweenness centrality: fraction of shortest paths passing through
at least one node in the group. group_closeness_centrality Group closeness centrality: closeness of a SET of nodes. group_degree_centrality Group degree centrality.
C_g(S) = |N(S) \ S| / (n - |S|) where N(S) is the set of neighbors of S.
Matches networkx.group_degree_centrality(G, S). group_in_degree_centrality Group in-degree centrality for directed graphs.
C_gin(S) = |{v : v->s for some s in S, v not in S}| / (n - |S|) group_out_degree_centrality Group out-degree centrality for directed graphs.
C_gout(S) = |{v : s->v for some s in S, v not in S}| / (n - |S|) gutman_index Gutman index: sum of deg(u)*deg(v)*d(u,v) for all pairs. harmonic_centrality harmonic_centrality_directed harmonic_centrality_directed_source_ordered Directed counterpart of harmonic_centrality_source_ordered harmonic_centrality_source_ordered Compute harmonic centrality while replaying sources in an explicit order. harmonic_diameter Harmonic diameter: reciprocal of the harmonic mean of all pairwise distances. has_eulerian_path Checks whether an undirected graph has an Eulerian path. has_path Returns whether there is a path between source and target in the graph. has_path_directed heawood_graph Return the Heawood graph (14 nodes, 21 edges). hits_centrality hits_centrality_directed hoffman_singleton_graph Return the Hoffman-Singleton graph (50 nodes, 175 edges). house_graph Return the house graph (5 nodes, 6 edges). house_x_graph Return the house-with-X graph (5 nodes, 8 edges). hyper_wiener_index Hyper-Wiener index over unordered node pairs. hyper_wiener_index_weighted Weighted Hyper-Wiener index over unordered node pairs. hypercube_graph Return the hypercube graph Q_n (2^n nodes). icosahedral_graph Return the icosahedral graph (12 nodes, 30 edges). identified_nodes Contract two nodes into one, merging their edges. immediate_dominators Compute immediate dominators for all nodes reachable from start.
Uses the Cooper-Harvey-Kennedy algorithm (iterative).
Returns a map from node -> its immediate dominator. in_degree_centrality In-degree centrality for directed graphs.
c_in(v) = in_degree(v) / (n - 1) for n > 1, else 1.0 if isolated.
Matches networkx.in_degree_centrality(G). info Alias: NX uses info(G), Rust uses graph_info. intersection_all Intersection of multiple undirected graphs. is_aperiodic Check if a directed graph is aperiodic.
A strongly connected digraph is aperiodic if the GCD of all cycle lengths is 1.
A general digraph is aperiodic if every strongly connected component is aperiodic. is_aperiodic_digraph Check if a directed graph is aperiodic using a DiGraph. is_arborescence Return True if the directed graph is an arborescence (a directed rooted tree
where every node except the root has in-degree 1, and the root has in-degree 0). is_at_free Check if graph is asteroidal-triple-free (AT-free). is_attracting_component Return True if the given component is an attracting component.
Matches networkx.is_attracting_component(G, component). is_biconnected Return True if the graph is biconnected (connected and no articulation points).
Matches networkx.is_biconnected(G). is_bipartite Checks whether the graph is bipartite. is_branching Return True if the directed graph is a branching (a directed forest where
every node has in-degree 0 or 1). is_chordal Check whether a graph is chordal (every cycle of length 4+ has a chord). is_connected Returns whether the graph is connected (all nodes reachable from each other). is_connected_dominating_set Check if a set of nodes forms a connected dominating set. is_d_separator Test whether x and y are d-separated by z in a DAG. is_digraphical Check if a directed degree sequence is digraphical (Fulkerson’s conditions).
Each element is (out_degree, in_degree). is_directed_acyclic_graph Check whether a directed graph is acyclic (a DAG). is_distance_regular Check if a graph is distance-regular.
A connected graph is distance-regular if for any two vertices u, v at distance d,
the numbers of neighbors of v at distances d-1, d, d+1 from u depend only on d. is_dominating_set Return whether the given set of nodes is a dominating set. is_edge_cover Check if a set of edges is an edge cover (every node is incident to at least one edge). is_empty Return whether the graph has no nodes.
Matches networkx.is_empty(G) — note: NetworkX considers a graph “empty”
if it has no edges, but we follow the function signature which checks edges. is_empty_directed Return whether the graph is empty (directed). is_eulerian Checks whether an undirected graph has an Eulerian circuit. is_forest Checks whether the graph is a forest (acyclic graph, possibly disconnected). is_graphical Check if a degree sequence is graphical (Erdős–Gallai theorem).
A sequence is graphical if it can be the degree sequence of a simple graph. is_isolate Return true if node is an isolate (degree 0). is_isolate_directed Return true if node is an isolate in a directed graph. is_isomorphic Check if two graphs are isomorphic using the VF2 algorithm. is_isomorphic_directed Check if two directed graphs are isomorphic. is_k_edge_connected Return True if the graph is k-edge-connected. is_k_regular Check if an undirected graph is k-regular (all nodes have degree k). is_kl_connected Check if graph is (k,l)-connected. is_matching is_maximal_matching is_multigraphical Check if a sequence is multigraphical (can be degree sequence of a multigraph).
A sequence is multigraphical iff its sum is even and max degree <= sum of remaining. is_negatively_weighted Check if an undirected graph has negatively weighted edges. is_path_graph Check if a graph is a path graph (connected, every node has degree <= 2,
exactly 2 nodes have degree 1 unless single node). is_perfect_matching is_planar Check whether a graph is planar using Kuratowski’s theorem approximation. is_planar_lr Exact planarity test via the Left-Right algorithm (boolean result only). is_pseudographical Check if a sequence is pseudographical (can be degree sequence of a pseudograph).
A pseudograph allows self-loops. A sequence is pseudographical iff its sum is even. is_regular Check if an undirected graph is regular (all nodes have the same degree). is_semiconnected Return True if the directed graph is semiconnected.
A digraph is semiconnected if for every pair u,v there is a path u->v or v->u.
Matches networkx.is_semiconnected(G). is_semieulerian Checks whether an undirected graph is semi-Eulerian. is_simple_path Return True if path is a simple path in the graph (no repeated nodes,
all consecutive nodes connected by edges). is_simple_path_directed Return True if path is a simple path in the directed graph. is_strongly_connected Return whether the directed graph is strongly connected. is_strongly_regular Check if graph is strongly regular. is_tournament Check if a directed graph is a tournament (complete oriented graph).
Every pair of distinct vertices has exactly one directed edge. is_tree Checks whether the graph is a tree (connected acyclic graph). is_weakly_connected Return whether the directed graph is weakly connected. is_weighted Check if an undirected graph has weighted edges. isolates Return a sorted list of isolate nodes (nodes with degree 0). isolates_directed Return a sorted list of isolate nodes in a directed graph. jaccard_coefficient Compute the Jaccard coefficient for pairs of nodes. johnson_path_directed Johnson all-pairs shortest paths for directed graphs. k_clique_communities Find k-clique communities using the clique percolation method. k_core Returns the k-core of the graph. k_corona Returns the k-corona of the graph. k_crust Returns the k-crust of the graph. k_shell Returns the k-shell of the graph. k_truss Return the k-truss subgraph of a graph. katz_centrality katz_centrality_checked Like katz_centralityErr(KatzNotConverged) if
the power iteration runs out of budget without satisfying the
convergence tolerance. katz_centrality_directed katz_centrality_directed_checked DiGraph counterpart to katz_centrality_checkedkneser_graph Return the Kneser graph KG(n, k).
Nodes are all k-element subsets of {0,…,n-1}; edges connect disjoint subsets. kosaraju_strongly_connected_components Kosaraju’s algorithm for strongly connected components.
Matches networkx.kosaraju_strongly_connected_components(G). krackhardt_kite_graph Return the Krackhardt kite graph (10 nodes, 18 edges). kuratowski_subgraph Kuratowski subgraph certificate for non-planar graphs. label_propagation_communities Label propagation community detection. ladder_graph Return the ladder graph (2n nodes: two paths connected by rungs). lexicographic_topological_sort Return a topological ordering of nodes, breaking ties lexicographically. lexicographical_topological_sort Alias: NX uses lexicographical_topological_sort, Rust uses lexicographic_topological_sort. line_graph Return the line graph of G. line_graph_directed Return the line graph of a directed graph. load_centrality Compute load centrality for all nodes in an undirected graph. load_centrality_directed Compute load centrality for all nodes in a directed graph. load_centrality_directed_normalized Compute directed load centrality with optional normalization. load_centrality_normalized Compute load centrality with optional normalization. load_centrality_weighted Weighted Newman load centrality for an undirected Graph. load_centrality_weighted_directed Weighted Newman load centrality for a directed DiGraph (out-edges). local_bridges_list Local bridges: edges whose endpoints share no common neighbor. local_constraint Local constraint of node u with respect to neighbor v. local_efficiency Compute the average local efficiency of the graph. local_reaching_centrality Local reaching centrality for undirected graph. local_reaching_centrality_directed Local reaching centrality for a given node.
C_L(v) = (|R(v)| / (n - 1)) where R(v) is the set of nodes reachable from v.
Matches networkx.local_reaching_centrality(G, v). lollipop_graph Return the lollipop graph (K_m connected to P_n). louvain_communities Matches the NetworkX multi-level Louvain routine for undirected graphs. make_clique_bipartite Convert a graph of cliques to a bipartite graph. make_max_clique_graph Build the max clique graph: one node per maximal clique, edge between
cliques that share at least one node. max_clique_approx Greedy approximation for maximum clique. max_flow_edmonds_karp max_flow_edmonds_karp_directed max_weight_clique Find the maximum weight clique.
Uses a branch-and-bound approach. Each node’s weight comes from the given attribute
(default 1.0 if not present).
Returns (clique_nodes, total_weight). max_weight_matching maximal_independent_set Return a maximal independent set, optionally seeded for reproducible choices. maximal_matching maximum_branching Return a maximum branching of a directed graph. maximum_independent_set Greedy approximation for maximum independent set. maximum_spanning_arborescence Return a maximum spanning arborescence of a directed graph, if one exists. maximum_spanning_arborescence_with_edge_partition maximum_spanning_tree Return a maximum spanning tree using Kruskal’s algorithm (negate weights). min_cost_flow Compute minimum cost flow using successive shortest paths. min_edge_cover Compute a minimum edge cover of the graph. min_weight_matching min_weighted_vertex_cover 2-approximation for minimum weighted vertex cover. minimum_branching Return a minimum branching of a directed graph. minimum_cut_edmonds_karp minimum_cut_edmonds_karp_directed minimum_cycle_basis Compute a minimum weight cycle basis for a FrankenNetworkX undirected graph. minimum_cycle_basis_core Compute a minimum weight cycle basis for an undirected indexed graph. minimum_cycle_basis_core_with_chord_order Compute a minimum weight cycle basis with an explicit initial chord order. minimum_cycle_basis_with_chord_order Compute a minimum weight cycle basis with an explicit NetworkX-compatible
initial chord order. minimum_node_cut Compute minimum s-t node cut: the smallest set of nodes whose removal disconnects s from t. minimum_node_cut_directed Compute minimum s-t node cut on a directed graph. minimum_spanning_arborescence Return a minimum spanning arborescence of a directed graph, if one exists. minimum_spanning_arborescence_with_edge_partition minimum_spanning_tree Computes the minimum spanning tree using Kruskal’s algorithm. minimum_spanning_tree_prim Computes the minimum spanning forest using Prim’s algorithm. minimum_st_edge_cut_edmonds_karp mixing_expansion Return the mixing expansion of a set S.
mixing_expansion(G, S) = |edge_boundary(S)| / (|S| * |V-S|) modularity moebius_kantor_graph Return the Möbius-Kantor graph (16 nodes, 24 edges). moral_graph Return the moral graph of a DAG. multi_source_dijkstra multi_source_dijkstra_directed multi_source_dijkstra_nearest_source br-r37-c1-2z0mw (cc): multi-source Dijkstra returning, for each reachable node, the
SOURCE (center) on its shortest path — i.e. path[0] of multi_source_dijkstravoronoi_cells only needs this mapping; propagating the
source label (source[v] = source[u] on each relaxation, exactly where the path
kernel does path[v] = path[u] + [v]) and skipping the all-paths String construction
is the fix. Emitted in finalize (distance, push-seq) order — identical to the path
kernel’s key order — so {node: source} is byte-identical to {v: paths[v][0]}. multidigraph_has_negative_edge_weight MultiDiGraph counterpart to multigraph_has_negative_edge_weightmultidigraph_has_nonfinite_edge_weight MultiDiGraph counterpart to multigraph_has_nonfinite_edge_weightmultigraph_has_negative_edge_weight br-r37-c1-mgnegscan-8l53h: MultiGraph counterpart to
graph_has_negative_edge_weight multigraph_has_nonfinite_edge_weight br-r37-c1-mgnegscan-8l53h: MultiGraph counterpart to
graph_has_nonfinite_edge_weight navigable_small_world_graph Generate a navigable small-world graph using the Kleinberg model. negative_edge_cycle Detect whether a graph contains a negative weight cycle.
Matches networkx.negative_edge_cycle(G, weight=weight). node_attribute_xy Return (source_attr, target_attr) pairs for each edge. node_boundary Return the set of nodes on the boundary of nbunch.
The node boundary is the set of nodes outside nbunch that have
a neighbor in nbunch. If nbunch2 is given, only nodes in nbunch2
are considered for the boundary. node_boundary_directed Return the node boundary of nbunch in a directed graph. node_clique_number Return the clique number of each node (size of the largest clique containing that node). node_connected_component Return the connected component containing the given node.
Matches networkx.node_connected_component(G, n). node_connectivity Compute node connectivity between two specific nodes s and t. node_connectivity_directed Compute node connectivity between two specific nodes in a directed graph. node_connectivity_directed_global Compute directed node connectivity with NetworkX global semantics. node_degree_xy Yield (source_degree, target_degree) for each edge. node_degree_xy_directed Directed variant: use out-degree for source, in-degree for target. node_disjoint_paths Find node-disjoint paths between source and target. node_disjoint_paths_directed Find node-disjoint paths between source and target in a directed graph. node_expansion Return the node expansion of a set S.
node_expansion(G, S) = |union(N(v) for v in S)| / |S| nodes_with_selfloops Nodes with self-loops. non_edges Return all non-edges of the graph (pairs of nodes not connected by an edge). non_neighbors Return the non-neighbors of a node in an undirected graph. normalized_cut_size Return the normalized cut size between two node sets in an undirected graph. normalized_cut_size_directed Return the normalized cut size between two node sets in a directed graph. null_graph Return the null graph (0 nodes). number_attracting_components Return the number of attracting components.
Matches networkx.number_attracting_components(G). number_connected_components number_of_cliques Return the number of maximal cliques containing each node. number_of_isolates Return the number of isolate nodes. number_of_isolates_directed Return the number of isolate nodes in a directed graph. number_of_selfloops Count of self-loop edges. number_of_spanning_arborescences Return the number of spanning arborescences rooted at root. number_of_spanning_trees Return the number of spanning trees of an undirected graph. number_strongly_connected_components Return the number of strongly connected components. number_weakly_connected_components Return the number of weakly connected components. numeric_assortativity_coefficient Numeric assortativity coefficient for a scalar node attribute. octahedral_graph Return the octahedral graph (6 nodes, 12 edges). onion_layers Onion layer decomposition (generalized k-core peeling). out_degree_centrality Out-degree centrality for directed graphs.
c_out(v) = out_degree(v) / (n - 1) for n > 1, else 1.0 if isolated.
Matches networkx.out_degree_centrality(G). overall_reciprocity Compute the overall reciprocity of a directed graph. pagerank pagerank_directed pagerank_with_params PageRank with explicit parameters. pagerank_with_weight pagerank_with_weight_checked Like pagerank_with_weight paley_graph Return the Paley graph of order q (q must be a prime power ≡ 1 mod 4).
For simplicity, this only supports prime q. pappus_graph Return the Pappus graph (18 nodes, 27 edges). partial_duplication_graph Partial duplication graph. partition_spanning_tree Return a spanning tree or forest that respects EdgePartition constraints. path_weight Compute the weight of a path given edge weights.
Matches networkx.path_weight(G, path, weight). path_weight_directed Compute the weight of a path in a directed graph. percolation_centrality_weighted Weighted percolation centrality for an undirected Graph. percolation_centrality_weighted_directed Weighted percolation centrality for a directed DiGraph (out-edges). petersen_graph Return the Petersen graph (10 nodes, 15 edges). planar_embedding_data Build the planar embedding (per-node clockwise neighbour orders) for a
planar graph, mirroring networkx/algorithms/planarity.py’s embedding
phases exactly: sign(e) resolves each edge’s absolute side through the
ref/side chains, the oriented adjacency lists are re-sorted by the
signed nesting depth, the initial ccw chain is laid down per node, and
dfs_embedding then places tree half-edges first and back edges per the
resolved side (rc-planar-embedding-kernel-07rh8, milestone 1). Returns
None for non-planar graphs. power Return the k-th power of graph G. predecessor Return the predecessor dictionary from BFS.
Matches networkx.predecessor(G, source, target=None, cutoff=None).
Each node maps to the list of predecessors on shortest paths from source. preferential_attachment Compute the preferential attachment score for pairs of nodes. prim_spanning_edges_indexed Byte-exact Prim MST edge enumeration matching networkx’s
prim_mst_edges yield order + (parent, child) orientation, returning node
INDEX pairs. nx selects each component’s start node with set(G).pop() — a
CPython set iteration order that cannot be reproduced in safe Rust — so the
caller passes the full pop sequence in start_order (indices); the kernel
starts each unvisited node in that order. Neighbours are pushed in
neighbors_indices (adjacency-insertion) order, identical to nx’s
G.adj[u], so the global seq tie-break reproduces nx exactly. Returns
None when a NaN weight is hit with ignore_nan = false (the caller then
delegates so nx raises its exact ValueError). quotient_graph Build a quotient graph from a partition. ra_index_soundarajan_hopcroft RA-index Soundarajan-Hopcroft link prediction. random_spanning_tree Generate a uniformly random spanning tree using Wilson’s algorithm. random_spanning_tree_directed Generate a random spanning tree for a directed graph. random_spanning_tree_from_samples Sample a random spanning tree using precomputed edge order and random draws. random_tree Generate a uniformly random labeled tree on n nodes via Prüfer sequence. real_general_eigvals Eigenvalues of a real general dense row-major matrix via safe-Rust
Hessenberg reduction plus implicit double-shift QR. This is a private
no-BLAS/no-LAPACK prototype for adjacency_spectrum; callers must still
prove the raw public solver order before routing public APIs to it. reciprocity Compute the reciprocity for each node in a directed graph. reconstruct_path Reconstruct a path from a predecessor dictionary.
Matches networkx.reconstruct_path(source, target, predecessors). relabel_nodes Relabel graph nodes according to a mapping. relabel_nodes_directed Relabel directed graph nodes. relaxed_caveman_graph Relaxed caveman graph. remove_node_attributes Remove a specific attribute from all nodes. resource_allocation_index Compute the resource allocation index for pairs of nodes. reverse_digraph Return the reverse of a directed graph (all edges reversed). rich_club_coefficient Compute the rich-club coefficient for each degree k. ring_of_cliques Generate a ring of cliques graph.
Creates num_cliques complete graphs of size clique_size, connected in a ring. s_metric Compute the s-metric of a graph. schultz_index Schultz index: sum of (deg(u) + deg(v)) * d(u,v) for all pairs. second_order_centrality Compute second-order centrality: std dev of mean first passage times. sedgewick_maze_graph Return the Sedgewick maze graph (8 nodes, 10 edges). selfloop_edges Return all self-loop edges in the graph. shortest_path_length Returns the length of the shortest path between source and target. shortest_path_length_matrix_directed_indexed Directed counterpart of shortest_path_length_matrix_indexed shortest_path_length_matrix_indexed Dense multi-source unweighted distances indexed by graph insertion order. shortest_path_unweighted Returns the shortest path between source and target using BFS. shortest_path_unweighted_directed Returns the shortest path between source and target in a directed graph using BFS. shortest_path_weighted shortest_path_weighted_directed shortest_simple_paths Generate simple paths from source to target in order of increasing length/weight. simple_cycles Find all elementary cycles (simple cycles) in a directed graph using
Johnson’s algorithm. Returns cycles as lists of node labels. simrank_similarity Compute SimRank similarity between all pairs of nodes. simrank_similarity_directed SimRank similarity for directed graphs (uses predecessors). simrank_similarity_pair SimRank for a specific pair of nodes. single_source_bellman_ford Single-source Bellman-Ford returning (distances, paths).
Returns None if a negative cycle is detected.
Matches networkx.single_source_bellman_ford(G, source, weight=weight). single_source_bellman_ford_path Single-source Bellman-Ford returning paths only.
Returns None if a negative cycle is detected.
Matches networkx.single_source_bellman_ford_path(G, source, weight=weight). single_source_bellman_ford_path_directed Single-source Bellman-Ford returning paths only for directed graph.
Returns None if a negative cycle is detected. single_source_bellman_ford_path_length Single-source Bellman-Ford returning distances only.
Returns None if a negative cycle is detected.
Matches networkx.single_source_bellman_ford_path_length(G, source, weight=weight). single_source_bellman_ford_path_length_directed Single-source Bellman-Ford returning distances only for directed graph.
Returns None if a negative cycle is detected. single_source_dijkstra_directed Single-source Dijkstra returning distances only (directed graph).
Returns (node, distance) pairs in networkx finalize order. single_source_dijkstra_full Single-source Dijkstra returning (distances, paths) for undirected graph.
Matches networkx.single_source_dijkstra(G, source, weight=weight). single_source_dijkstra_full_directed Single-source Dijkstra returning (distances, paths) for directed graph. single_source_dijkstra_indexed_full Single-source Dijkstra metadata in index space for direct Python emission. single_source_dijkstra_indexed_full_directed Directed twin of single_source_dijkstra_indexed_full single_source_dijkstra_path Single-source Dijkstra returning paths only.
Matches networkx.single_source_dijkstra_path(G, source, weight=weight). single_source_dijkstra_path_directed Single-source Dijkstra returning paths only for directed graph. single_source_dijkstra_path_length Single-source Dijkstra returning distances only.
Matches networkx.single_source_dijkstra_path_length(G, source, weight=weight). single_source_dijkstra_path_length_directed Single-source Dijkstra returning distances only for directed graph. single_source_dijkstra_path_length_typed_with_pred Length-only Dijkstra with NetworkX-observable distance type metadata. single_source_dijkstra_path_length_typed_with_pred_directed Directed twin of single_source_dijkstra_path_length_typed_with_pred single_source_dijkstra_path_length_with_pred weighted sp batch: distances WITH the finalizing predecessor — lets
the binding map nx’s discovery objects (a node displays as its
predecessor’s row object) without a second dijkstra. single_source_dijkstra_path_length_with_pred_directed Directed twin of single_source_dijkstra_path_length_with_pred. single_source_shortest_path Return all shortest paths from a single source (unweighted, BFS). single_source_shortest_path_directed Return all shortest paths from a single source for a directed graph (unweighted, BFS). single_source_shortest_path_directed_index Index-space core of single_source_shortest_path_directedsingle_source_shortest_path_indexsuccessors_indices,
each discovered node recording the POSITION of its discovering parent in the discovery
vector, so paths are reconstructed by index arithmetic over a vector sized to the reach
rather than to the graph (br-r37-c1-dkwy7). Returns (target_idx, path_indices) pairs in
BFS discovery order. single_source_shortest_path_index Index-space core of single_source_shortest_path(target_idx, path_indices) pairs in BFS discovery order; the binding
maps the indices to Python node objects, skipping the per-path-node String
materialization (O(|V|·depth) allocations) the String wrapper does for Rust
callers. single_source_shortest_path_length Return shortest path lengths from a single source (unweighted, BFS). single_source_shortest_path_length_borrowed Borrowed-string version that avoids String allocations during BFS.
Returns Vec of (node_name, distance) pairs in BFS discovery order. single_source_shortest_path_length_directed Return shortest path lengths from a single source for a directed graph (unweighted, BFS). single_source_shortest_path_length_directed_with_parents br-r37-c1-6hpa9: directed BFS lengths WITH the discovering parent —
see single_source_shortest_path_length_with_parents_borrowed. single_source_shortest_path_length_with_parents_borrowed br-r37-c1-6hpa9: BFS lengths WITH the discovering parent — lets the
Python bindings reproduce nx’s discovery-object semantics (each
node’s display object is its parent’s adjacency-row object) without
a second walk. Parent is None for the source. single_target_dijkstra_path_length_typed_with_pred_directed Directed target-only Dijkstra, equivalent to NetworkX’s
single_source_dijkstra_path_length(G.reverse(copy=False), target, weight). single_target_shortest_path Single-target shortest path (unweighted BFS, reversed).
Matches networkx.single_target_shortest_path(G, target, cutoff=None). single_target_shortest_path_directed Single-target shortest path for a directed graph (unweighted reverse BFS).
Matches networkx.single_target_shortest_path(G, target, cutoff=None). single_target_shortest_path_length Single-target shortest path lengths (unweighted BFS, reversed).
Matches networkx.single_target_shortest_path_length(G, target, cutoff=None). single_target_shortest_path_length_directed Single-target shortest path lengths for a directed graph (unweighted reverse BFS).
Matches networkx.single_target_shortest_path_length(G, target, cutoff=None). snap_aggregation SNAP (Summarization by grouping Nodes on Attributes and Pairs) aggregation. spanner Return a spanner of an undirected simple graph. spanning_tree_iterator Enumerate spanning trees in weight-sorted order using the Janssens-Sörensen
partition scheme. spanning_tree_iterator_ordered spectral_bisection Spectral bisection: split graph into two halves using Fiedler vector. square_clustering Computes the square clustering coefficient for each node. square_clustering_map Square clustering coefficient for each node. square_clustering_pairs br-r37-c1-sqclfast: integer-CSR realization of NetworkX’s optimized
(Lind/Zhang two-hop) square-clustering algorithm. square_clustering_pairs_for br-r37-c1-sqclsub (cc): square-clustering (squares, potential) pairs for a
SUBSET of node indices, aligned to targets. square_clustering(G, nodes)
with an explicit node list previously ran the Python neighbor-set port
(per-node _raw_neighbors -> set() materialization, 0.5-0.66x vs nx and
growing with N). This shares the exact stamp-array kernel below: the full
adjacency + stamp arrays are built once (O(V+E) + O(V), microseconds in Rust),
then ONLY the targets nodes are computed — the compute term (O(sum deg^2))
dominates whole-node runtime, so restricting it to the subset is the win.
Byte-identical to the all-node path (same arithmetic, same order). stochastic_block_model Stochastic block model graph. stoer_wagner stoer_wagner_nx Compute a minimum cut using the Stoer-Wagner algorithm. strongly_connected_components Return the strongly connected components of a directed graph using
Tarjan’s algorithm. subgraph_centrality_expdiag Subgraph centrality for a simple undirected graph. sudoku_graph Return the n-Sudoku graph. symmetric_eigvals Ascending eigenvalues of a real symmetric n×n row-major matrix via a
100% safe-Rust Householder→implicit-shift-QL pipeline (no C BLAS/LAPACK).
The behavioural analogue of numpy.linalg.eigvalsh for symmetric input.
Returns None on a dimension mismatch or non-convergence so callers can
fall back to the reference path. tadpole_graph Return the tadpole graph (C_m connected to P_n). tensor_product Return the tensor (categorical) product of G and H. tensor_product_directed Return the tensor product of two directed graphs. tetrahedral_graph Return the tetrahedral graph (K4, 4 nodes, 6 edges). to_dict_of_dicts Convert graph to adjacency dict-of-dicts representation. to_dict_of_lists Convert graph to dict-of-lists adjacency representation. to_edgelist Convert graph to edge list representation. to_prufer_sequence Extract the Prüfer sequence from a labeled tree. topological_generations Topological generations of a DAG (Kahn’s algorithm). topological_sort Topological sort of a directed acyclic graph. transitive_closure Return the transitive closure of a directed graph. transitive_reduction Return the transitive reduction of a directed acyclic graph. transitivity Return the transitivity (global clustering coefficient) of an undirected graph. tree_all_pairs_lowest_common_ancestor Find lowest common ancestors for a rooted directed tree. tree_broadcast_center Compute the broadcast center of a tree. tree_broadcast_time Compute the tree broadcast time for either the tree or a specific node. tree_data Tree adjacency representation from a root. triad_type Classify the triad type of three nodes in a directed graph. triadic_census Triadic census for a directed graph. triangles Counts the number of triangles each node participates in. trivial_graph Return the trivial graph (1 node, 0 edges). trophic_differences Trophic difference for each edge: difference in trophic levels. truncated_cube_graph Return the truncated cube graph (24 nodes, 36 edges). truncated_tetrahedron_graph Return the truncated tetrahedron graph (12 nodes, 18 edges). try_double_edge_swap Perform a single degree-preserving double edge swap on graph . turan_graph Return the Turán graph T(n, r). tutte_graph Return the Tutte graph (46 nodes, 69 edges). tutte_polynomial Tutte polynomial via deletion-contraction. Exponential time. union_all Union of multiple undirected graphs. unweighted_laplacian_spectrum Ascending eigenvalues of the unweighted undirected Laplacian D - A. volume Return the volume of a set of nodes (sum of degrees of nodes in the set). voronoi_cells Partition nodes into Voronoi cells based on nearest center. voterank Computes VoteRank centrality — iterative voting to find influential spreaders. voterank_directed weakly_connected_components Return the weakly connected components of a directed graph. wheel_graph Return the wheel graph W_n using NetworkX semantics. wiener_index Compute the Wiener index of a connected graph. wiener_index_directed Wiener index for directed graphs: sum of shortest-path distances between all ordered pairs. wiener_index_weighted Weighted Wiener index for undirected graphs: sum of shortest-path
distances over all unordered pairs, summed via Dijkstra. wiener_index_weighted_directed Weighted Wiener index for directed graphs: sum of shortest-path
distances over all ordered pairs (u, v) with u != v, summed
via Dijkstra. Returns f64::INFINITY if the digraph is not
strongly connected (some pair is unreachable). windmill_graph Return the windmill graph Wd(k, n): n copies of K_k sharing a universal vertex. write_graphml_string Generate GraphML XML string for an undirected graph with full NX compatibility. write_graphml_string_config Generate GraphML with configuration options. write_graphml_string_config_with_graph_attrs Generate GraphML with configuration options and graph-level attributes. write_graphml_string_directed Generate GraphML for a directed graph. write_graphml_string_directed_config Generate GraphML for a directed graph with configuration. write_graphml_string_directed_config_with_graph_attrs Generate GraphML for a directed graph with configuration and graph-level attributes. write_weighted_edgelist Generate weighted edgelist lines: “u v weight”. IndexedTypedPredDistances Index-space form of [OrderedTypedPredDistances]. A predecessor of
u32::MAX denotes the source row’s root. StoerWagnerNxTrace