# How to Perform BFS Traversal on a Semantica Graph: Complete Guide

> Learn how to perform BFS traversal on a Semantica graph using get_neighbors for exploration or bfs_shortest_path for shortest paths. Optimize your graph analysis today.

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

---

**To perform BFS traversal on a Semantica graph, use `ContextGraph.get_neighbors()` for multi-hop neighborhood exploration or `PathFinder.bfs_shortest_path()` for unweighted shortest-path discovery, both of which leverage `deque`-based FIFO queues with O(1) adjacency lookups.**

Performing BFS traversal on a Semantica graph enables efficient exploration of knowledge structures and relationship networks. The semantica-agi/semantica repository provides two specialized utilities—`ContextGraph.get_neighbors` and `PathFinder.bfs_shortest_path`—that share a common queue-based implementation while serving distinct traversal use cases. This guide examines the underlying BFS architecture, thread-safe implementation details, and practical code examples for both neighbor discovery and shortest-path routing.

## Core BFS Architecture and Implementation

Semantica's BFS implementation rests on a high-performance adjacency index and a standardized queue-based expansion pattern. According to the source code in [`semantica/context/context_graph.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/context/context_graph.py), the graph maintains `self._adjacency: Dict[str, List[ContextEdge]]` as its primary navigational structure, enabling constant-time neighbor lookups during traversal.

The BFS queue uses Python's `collections.deque` to store traversal state as tuples of `(current_node, hop_count, path_so_far, cumulative_weight)`. The algorithm calls `deque.popleft()` to guarantee strict FIFO order, ensuring true breadth-first expansion. A `visited = {node_id}` set prevents cycles and redundant node processing, while an internal `RLock` protects all mutable operations to ensure thread safety in concurrent environments.

Edge filtering occurs during expansion through optional parameters: `rel_filter` validates `edge.edge_type` against allowed relationship types, while `min_weight` thresholds filter edges based on confidence scores. When `include_distance_metadata=True`, the engine enriches results with `classify_path_distance`, `confidence_decay`, and `path_to_anchor` attributes for analytical context.

## Multi-Hop Neighborhood Discovery with `get_neighbors`

The `get_neighbors` method in [`semantica/context/context_graph.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/context/context_graph.py) (lines 983-1010) provides the primary API for BFS-based neighborhood exploration. This method supports **k-hop** queries—limiting traversal depth via the `hops` parameter—while offering granular control over relationship types, weight thresholds, and result pagination.

```python
from semantica.context import ContextGraph

# Initialize and populate the graph

graph = ContextGraph()
graph.add_nodes([
    {"id": "A", "type": "entity", "content": "Alpha"},
    {"id": "B", "type": "entity", "content": "Beta"},
    {"id": "C", "type": "entity", "content": "Gamma"},
    {"id": "D", "type": "entity", "content": "Delta"},
])
graph.add_edges([
    {"source": "A", "target": "B", "type": "related_to", "weight": 0.9},
    {"source": "B", "target": "C", "type": "related_to", "weight": 0.8},
    {"source": "C", "target": "D", "type": "related_to", "weight": 0.7},
])

# Perform 2-hop BFS traversal from node A

neighbors = graph.get_neighbors(
    node_id="A",
    hops=2,
    relationship_types=["related_to"],
    min_weight=0.0,
    include_distance_metadata=True
)

for n in neighbors:
    print(f"{n['id']} at hop {n['hop']}")

```

The method returns a list of dictionaries containing node identifiers, hop distances from the source, and optional distance metadata. The `skip` and `limit` parameters enable pagination for large result sets, processing the full BFS traversal internally before returning the requested window.

## Finding Shortest Paths with `PathFinder`

For unweighted shortest-path discovery, the `PathFinder.bfs_shortest_path` method in [`semantica/kg/path_finder.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/kg/path_finder.py) (lines 386-420) implements a classic BFS that terminates upon reaching the target node. Unlike `get_neighbors`, which explores the full neighborhood, this utility returns the exact sequence of node identifiers forming the shortest route from source to target.

```python
from semantica.kg import PathFinder
from semantica.context import ContextGraph

# Build the graph structure

g = ContextGraph()
g.add_node("A", "entity", "Alpha")
g.add_node("B", "entity", "Beta")
g.add_node("C", "entity", "Gamma")
g.add_edge("A", "B", "related_to")
g.add_edge("B", "C", "related_to")

# Find shortest path using the adjacency index

pf = PathFinder()
path = pf.bfs_shortest_path(g._adjacency, source="A", target="C")

print(" → ".join(path))  # Output: A → B → C

```

Note that `bfs_shortest_path` requires the raw `graph._adjacency` dictionary rather than the `ContextGraph` instance itself. This design allows the pathfinder to operate on any compatible adjacency structure while maintaining separation between the graph data model and traversal algorithms.

## Advanced BFS Configuration and Filtering

### Filtering by Edge Type and Weight

Both BFS implementations support selective traversal through relationship filtering. The `relationship_types` parameter accepts a whitelist of edge types, while `min_weight` establishes a confidence threshold for traversal:

```python

# Traverse only high-confidence "part_of" or "related_to" edges

results = graph.get_neighbors(
    node_id="A",
    hops=3,
    relationship_types=["related_to", "part_of"],
    min_weight=0.7,
    include_distance_metadata=True
)

for n in results:
    print(f"{n['id']} (hop {n['hop']}, weight {n['weight']})")

```

The engine evaluates filters during edge expansion—checking `if edge.edge_type not in rel_filter` and `if edge.weight < min_weight`—ensuring that excluded edges never enter the traversal queue.

### Distance Metadata and Pagination

For analytical workflows, enabling `include_distance_metadata=True` enriches results with traversal context including `distance_band` classifications and decayed confidence scores. Combined with pagination controls, this supports efficient processing of large neighborhood graphs:

```python

# Skip first 5 results, return next 10, with full metadata

batch = graph.get_neighbors(
    node_id="A",
    hops=3,
    min_weight=0.5,
    skip=5,
    limit=10,
    include_distance_metadata=True
)

```

## Summary

- **Two primary BFS utilities** serve distinct purposes: `ContextGraph.get_neighbors` for multi-hop neighborhood exploration and `PathFinder.bfs_shortest_path` for unweighted shortest-path discovery.
- **Queue-based implementation** uses `deque` with FIFO ordering, storing traversal state as `(node, hop_count, path, weight)` tuples to ensure proper breadth-first expansion.
- **O(1) adjacency lookups** rely on the `self._adjacency` dictionary structure maintained in [`semantica/context/context_graph.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/context/context_graph.py).
- **Thread-safe execution** is guaranteed by an internal `RLock` protecting all graph mutations during traversal.
- **Flexible filtering** supports relationship type whitelists, minimum weight thresholds, and optional distance metadata for analytical contexts.
- **Source locations**: Core BFS logic resides in [`semantica/context/context_graph.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/context/context_graph.py) (lines 983-1010), while shortest-path functionality lives in [`semantica/kg/path_finder.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/kg/path_finder.py) (lines 386-420).

## Frequently Asked Questions

### What is the difference between `get_neighbors` and `bfs_shortest_path`?

`get_neighbors` performs a complete multi-hop BFS exploration from a source node, returning all reachable nodes within a specified depth along with optional metadata, making it suitable for neighborhood analysis. `bfs_shortest_path` terminates as soon as it reaches a specific target node, returning only the minimal path sequence, which optimizes for routing and connectivity queries.

### How does Semantica handle cycles during BFS traversal?

The implementation maintains a `visited` set containing processed node identifiers. Before enqueueing any neighbor, the algorithm checks membership in this set, preventing cycles and redundant processing while ensuring each node expands at most once per traversal.

### Is BFS traversal in Semantica thread-safe?

Yes. All BFS operations execute within the protection of `self._lock`, an `RLock` instance that guards the `_adjacency` index and other mutable graph state. This ensures consistent traversal results even when multiple threads concurrently modify or query the graph structure.

### Can I perform BFS traversal with custom relationship filters?

Absolutely. The `relationship_types` parameter accepts a list of allowed edge types, and the `min_weight` parameter sets a confidence threshold. The engine applies these filters during edge expansion in [`semantica/context/context_graph.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/context/context_graph.py), ensuring only edges matching your criteria participate in the BFS queue.