Connected components and strongly connected components.
| is_connected(G) | Return True if G is connected. |
| number_connected_components(G) | Return the number of connected components in G. |
| connected_components(G) | Return a list of lists of nodes in each connected component of G. |
| connected_component_subgraphs(G) | Return a list of graphs of each connected component of G. |
| node_connected_component(G, n) | Return a list of nodes of the connected component containing node n. |
| is_strongly_connected(G) | Return True if G is strongly connected. |
| number_strongly_connected_components(G) | Return the number of strongly connected components in G. |
| strongly_connected_components(G) | Returns a list of strongly connected components in G. |
| strongly_connected_component_subgraphs(G) | Return a list of graphs of each strongly connected component of G. |
| strongly_connected_components_recursive(G) | Returns list of strongly connected components in G. |
| kosaraju_strongly_connected_components(G[, ...]) | Returns list of strongly connected components in G. |
Algorithms for directed acyclic graphs (DAGs).
| topological_sort(G[, nbunch]) | Return a list of nodes in topological sort order. |
| topological_sort_recursive(G[, nbunch]) | Return a list of nodes in topological sort order. |
| is_directed_acyclic_graph(G) | Return True if the graph G is a directed acyclic graph (DAG) |
Shortest paths, diameter, radius, eccentricity, and related methods.
| eccentricity(G[, v, sp, with_labels]) | Return the eccentricity of node v in G (or all nodes if v is None). |
| diameter(G[, e]) | Return the diameter of the graph G. |
| radius(G[, e]) | Return the radius of the graph G. |
| periphery(G[, e]) | Return the periphery of the graph G. |
| center(G[, e]) | Return the center of graph G. |
Shortest path algorithms.
| average_shortest_path_length(G[, weighted]) | Return the average shortest path length. |
| shortest_path(G, source, target) | Return a list of nodes in a shortest path between source and target. |
| shortest_path_length(G, source, target) | Return the shortest path length between the source and target. |
| single_source_shortest_path(G, source[, cutoff]) | Return list of nodes in a shortest path between source and all other nodes reachable from source. |
| single_source_shortest_path_length(G, source) | Return the shortest path length from source to all reachable nodes. |
| all_pairs_shortest_path(G[, cutoff]) | Return shortest paths between all nodes. |
| all_pairs_shortest_path_length(G[, cutoff]) | Return dictionary of shortest path lengths between all nodes in G. |
| dijkstra_path(G, source, target) | Returns the shortest path from source to target in a weighted |
| dijkstra_path_length(G, source, target) | Returns the shortest path length from source to target in a weighted |
| single_source_dijkstra_path(G, source) | Return list of nodes in a shortest path between source and all other nodes reachable from source for a weighted graph. |
| single_source_dijkstra_path_length(G, source) | Returns the shortest path lengths from source to all other |
| single_source_dijkstra(G, source[, target, ...]) | Returns shortest paths and lengths in a weighted graph G. |
| bidirectional_dijkstra(G, source, target) | Dijkstra’s algorithm for shortest paths using bidirectional search. |
| bidirectional_shortest_path(G, source, target) | Return a list of nodes in a shortest path between source and target. |
| dijkstra_predecessor_and_distance(G, source) | Returns two dictionaries representing a list of predecessors of a node and the distance to each node respectively. |
| predecessor(G, source[, target, cutoff, ...]) | Returns dictionary of predecessors for the path from source to all |
| floyd_warshall(G[, huge]) | The Floyd-Warshall algorithm for all pairs shortest paths. |
Shortest paths using A* (“A star”) algorithm.
| astar_path(G, source, target[, heuristic]) | Return a list of nodes in a shortest path between source and target |
| astar_path_length(G, source, target[, heuristic]) | Return a list of nodes in a shortest path between source and target |
Search algorithms.
See also networkx.path.
| dfs_preorder(G[, source, reverse_graph]) | Return list of nodes connected to source in depth-first-search preorder. |
| dfs_postorder(G[, source, reverse_graph]) | Return list of nodes connected to source in depth-first-search postorder. |
| dfs_predecessor(G[, source, reverse_graph]) | Return predecessors of depth-first-search with root at source. |
| dfs_successor(G[, source, reverse_graph]) | Return succesors of depth-first-search with root at source. |
| dfs_tree(G[, source, reverse_graph]) | Return directed graph (tree) of depth-first-search with root at source. |