# How to Perform Graph Traversal (BFS) in Semantica: A Complete Guide

> Learn how to perform graph traversal BFS in Semantica with our complete guide. Discover the PathFinder class and its bfs_shortest_path method for efficient shortest path computation on NetworkX graphs.

- Repository: [Semantica /semantica](https://github.com/semantica-agi/semantica)
- Tags: how-to-guide
- Published: 2026-09-04

---

**Semantica implements Breadth-First Search (BFS) through the `PathFinder` class in [`semantica/kg/path_finder.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/kg/path_finder.py), providing a FIFO queue-based `bfs_shortest_path` method that computes shortest unweighted paths on any NetworkX-compatible graph.**

Semantica is an open-source knowledge graph framework that treats graph traversal as a first-class operation. The repository centralizes BFS logic in the `PathFinder` engine, allowing developers to execute shortest-path queries across directed and undirected graphs without depending on specific storage backends. Whether you are exploring entity relationships or tracing decision provenance, understanding how to leverage BFS in Semantica unlocks efficient multi-hop retrieval capabilities.

## Core BFS Implementation in PathFinder

### The bfs_shortest_path Method

The primary entry point for BFS graph traversal in Semantica is `PathFinder.bfs_shortest_path()` located at lines 386-443 of [`semantica/kg/path_finder.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/kg/path_finder.py). This method accepts a graph object, source node, and target node, then executes a classic breadth-first search using a FIFO queue to guarantee the shortest unweighted path.

The implementation first validates node existence through `_node_exists()` and determines traversal directionality via `_make_undirected_view()` when necessary. It then iterates through neighbors—retrieved via `_get_neighbors()`—until either the target is discovered or the queue exhausts. Upon success, it returns a list of node IDs representing the path; otherwise, it returns an empty list.

### Design Rationale and Abstractions

Semantica decouples traversal algorithms from storage implementations by exposing helper methods that abstract graph-specific details. The `_get_neighbors()` protocol allows `PathFinder` to work uniformly across **NetworkX** graphs, **Amazon Neptune** backends, and **Neo4j** stores. This architecture ensures that `bfs_shortest_path` remains reusable for provenance tracing, knowledge graph queries, and contextual reasoning without modification.

## BFS Integration Points Across Semantica

### ContextGraph Multi-Hop Discovery

The `ContextGraph` module utilizes BFS for neighbor discovery within bounded depths. Located in [`semantica/context/context_graph.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/context/context_graph.py) at line 3904, the `get_neighbors()` method accepts a `hops` parameter that internally translates to a BFS depth limit. This enables retrieval of all entities within *n* hops of a query node for contextual expansion.

### DecisionQuery Dependency Traversal

Decision provenance relies on BFS to explore dependency chains. The `DecisionQuery` class in [`semantica/context/decision_query.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/context/decision_query.py) (line 656) leverages `max_hops` to constrain traversal depth when resolving related decisions. This prevents unbounded graph exploration while maintaining completeness within the specified horizon.

### Graph Store Adapters

Backend implementations including `AmazonNeptune` and Neo4j adapters expose BFS-compatible traversal interfaces that comply with Semantica's generic `PathFinder` contracts. These adapters translate high-level BFS calls into storage-specific queries while returning results in the standard format expected by the path-finding engine.

## Practical BFS Examples

### Example 1: Simple BFS on a NetworkX Graph

```python
import networkx as nx
from semantica.kg.path_finder import PathFinder

G = nx.DiGraph()
G.add_edges_from([
    ("A", "B"), ("A", "C"),
    ("B", "D"), ("C", "D"),
    ("D", "E")
])

finder = PathFinder()
shortest_path = finder.bfs_shortest_path(G, source="A", target="E")
print(shortest_path)  # → ['A', 'B', 'D', 'E']

```

### Example 2: BFS in an Undirected Context Graph

```python
from semantica.context.context_graph import ContextGraph

# Assume `cg` is a ContextGraph instance already populated

paths = cg.get_neighbors(start_entity="Entity42", hops=2)
print(paths)  # Dictionary of entities within two BFS hops

```

### Example 3: Decision Query with BFS Depth Limit

```python
from semantica.context.decision_query import DecisionQuery

dq = DecisionQuery()
related_decisions = dq.get_related_decisions(
    decision_id="DEC-123",
    max_hops=3  # BFS depth limit

)
print(related_decisions)  # List of decision IDs reachable within 3 hops

```

## Summary

- **Centralized BFS engine**: The `PathFinder` class in [`semantica/kg/path_finder.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/kg/path_finder.py) provides the canonical BFS implementation via `bfs_shortest_path()`.
- **Storage agnostic**: Helper methods abstract neighbor lookup, enabling BFS across NetworkX, Neptune, Neo4j, and custom backends.
- **Bounded traversal**: Both `ContextGraph` and `DecisionQuery` leverage BFS with depth limits (`hops` and `max_hops`) to control query scope.
- **Shortest path guarantee**: The FIFO queue implementation returns optimal unweighted paths or empty lists when no path exists.

## Frequently Asked Questions

### What is the difference between BFS and DFS in Semantica?

Semantica's `PathFinder` currently emphasizes BFS for **shortest-path calculations**, while DFS implementations may be used for exhaustive traversal or cycle detection in other modules. BFS guarantees the shortest unweighted path between nodes, whereas DFS explores as far as possible along each branch before backtracking.

### Does Semantica support weighted BFS or Dijkstra's algorithm?

The `bfs_shortest_path` method specifically handles unweighted graphs. For weighted shortest paths, Semantica provides separate implementations (likely using Dijkstra or A* variants) in the same `PathFinder` module, though BFS remains optimal for unit-cost edge scenarios according to the source architecture.

### How does Semantica handle cyclic graphs during BFS traversal?

The `bfs_shortest_path` implementation automatically handles cycles by maintaining a visited set during queue processing. Each node is processed at most once, preventing infinite loops in cyclic directed graphs or undirected graphs with back-edges.

### Can I use BFS with custom graph backends that are not NetworkX?

Yes. By implementing the neighbor lookup protocol (specifically the `_get_neighbors()` interface expected by `PathFinder`), any custom graph store can support BFS traversal. The Amazon Neptune and Neo4j adapters demonstrate this pattern by translating neighbor requests into Cypher or Gremlin queries while presenting a unified interface to the BFS engine.