Traversal, Components, and Reachability
Traversal systematically visits nodes reachable through edges. In a directed graph, following outgoing edges answers a different question from ignoring direction or following incoming edges. Reachability is directional.
Prerequisites
Complete random graphs and null models. Return to the original MultiDiGraph; do not reuse the simplified null-model representation silently.
Learning goals
- Explain breadth-first search (BFS) and depth-first search (DFS) as traversal strategies.
- Make neighbor ordering explicit when a reproducible visit order matters.
- Distinguish weakly connected and strongly connected components in a directed graph.
- Separate reachability and component membership from distance, influence, and causation.
Traversal and components
BFS explores one edge-depth layer at a time; DFS follows a branch before backtracking. Both can find the set reachable from a source. Their visit order can differ, and without a declared neighbor order it should not be interpreted as a ranking.
For a directed graph:
- a weakly connected component is connected after replacing directed edges with undirected ones;
- a strongly connected component lets every node reach every other node by following direction;
- an isolate is a one-node weak and strong component when it has no edges.
Parallel edges do not make a new node reachable, although they may matter for later weighted or reliability questions. The self-loop does not connect Eli to a new node.
Worked example
import csv
from pathlib import Path
import networkx as nx
fixture = Path("tests/fixtures/graph-data-science")
graph = nx.MultiDiGraph()
with (fixture / "interaction-nodes.csv").open(encoding="utf-8") as handle:
graph.add_nodes_from(row["node_id"] for row in csv.DictReader(handle))
with (fixture / "interaction-relationships.csv").open(encoding="utf-8") as handle:
for row in csv.DictReader(handle):
if row["record_status"] == "valid":
graph.add_edge(row["source"], row["target"], key=row["relationship_id"])
bfs_from_ada = list(nx.bfs_tree(graph, "ada", sort_neighbors=sorted))
weak = sorted(
(sorted(component) for component in nx.weakly_connected_components(graph)),
key=lambda nodes: (-len(nodes), nodes),
)
strong = sorted(
(sorted(component) for component in nx.strongly_connected_components(graph)),
key=lambda nodes: (-len(nodes), nodes),
)
print(f"bfs_from_ada={bfs_from_ada}")
print(f"weak={weak}")
print(f"strong={strong}")
Expected output:
bfs_from_ada=['ada', 'ben', 'cy', 'fox', 'dia', 'eli']
weak=[['ada', 'ben', 'cy', 'dia', 'eli', 'fox'], ['gia']]
strong=[['ada', 'ben', 'cy', 'fox'], ['dia', 'eli'], ['gia']]
Ada can reach Dia and Eli, but neither can return to Ada under the recorded direction. Therefore all six non-isolates form one weak component but split into two strong components.
Limitations
- Reachability shows that a directed path exists in the modeled graph; it does not prove information traveled, influence occurred, or an outcome was caused.
- BFS depth counts hops, not weighted distance. Ticket 53 introduces distance semantics separately.
- A missing or filtered bridge can split components dramatically, while one erroneous bridge can merge them.
- Traversing a large graph can be expensive in memory and time; this in-memory example is intentionally small.
Practice
Predict the BFS visit set from Eli and the effect of reversing every edge. Then verify both while keeping neighbor sorting fixed. Explain why a different visit order can still produce the same reachable set.
Next steps
This foundation batch is complete. Continue directly with shortest paths and distance, where edge weights become distance or cost only under an explicit contract.
Primary sources
Checked 2026-10-18: NetworkX, traversal reference; NetworkX, components reference; NetworkX, bfs_tree; NetworkX, strongly_connected_components.