Skip to main content

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.