TopolearnReachability and components answer 'what is linked to what', and they're the first step in most analyses.
Breadth-first search (BFS) visits nodes in order of distance from a start; depth-first search (DFS) goes as deep as possible before backtracking. NetworkX exposes both as iterators, so they stay cheap on large graphs:
nx.bfs_edges(G, s),nx.bfs_tree(G, s),nx.bfs_layers(G, s)(nodes grouped by distance)nx.dfs_preorder_nodes(G, s),nx.dfs_postorder_nodes,nx.dfs_edgesnx.descendants(G, s)andnx.node_connected_component(G, s)for everything reachable
Connected components split an undirected graph into islands: nx.connected_components(G) yields one set of nodes per component, and nx.number_connected_components(G) counts them. The largest is max(nx.connected_components(G), key=len), and G.subgraph(that).copy() extracts it.
Directed graphs have two notions:
- Strongly connected: every node can reach every other following edge directions (
nx.strongly_connected_components). Cycles of mutual reachability, such as link loops. - Weakly connected: connected if you ignore direction (
nx.weakly_connected_components).
nx.condensation(G) collapses each strongly connected component into one node, producing a DAG of components. That's useful for dependency analysis.
Calling connected_components on a DiGraph raises an error; use the weak or strong version.
Example
import networkx as nx
G = nx.Graph([(1, 2), (2, 3), (3, 4), (2, 5), (10, 11)])
print(list(nx.bfs_layers(G, 1))) # [[1], [2], [3, 5], [4]]
print(list(nx.dfs_preorder_nodes(G, 1))) # [1, 2, 3, 4, 5]
comps = sorted(nx.connected_components(G), key=len, reverse=True)
print(comps) # [{1, 2, 3, 4, 5}, {10, 11}]
giant = G.subgraph(comps[0]).copy()
print(giant.number_of_nodes()) # 5
D = nx.DiGraph([("a", "b"), ("b", "c"), ("c", "a"), ("c", "d"), ("e", "d")])
print(sorted(map(sorted, nx.strongly_connected_components(D))))
# [['a', 'b', 'c'], ['d'], ['e']]
print(nx.number_weakly_connected_components(D)) # 1
print(nx.condensation(D).number_of_nodes()) # 3 (a DAG of components)Remember
- BFS and DFS are lazy iterators;
bfs_layersgroups by distance - Undirected: connected components; directed: strong or weak
condensationturns strongly connected components into a DAG
Watch out for
- Calling
nx.connected_componentson a DiGraph, which raises NetworkXNotImplemented.