# How Room Traversal and BFS Navigation Work in MemPalace’s palace_graph Module

> Explore the MemPalace palace_graph module. Learn how it builds a graph from ChromaDB metadata and uses BFS for room traversal, finding connected rooms sorted by proximity and relevance.

- Repository: [MemPalace/mempalace](https://github.com/MemPalace/mempalace)
- Tags: internals
- Published: 2026-06-06

---

**The `palace_graph` module builds an in-memory undirected graph from ChromaDB metadata and executes a Breadth-First Search (BFS) to find connected rooms via shared wings, returning results sorted by proximity and relevance.**

The **MemPalace** repository implements a semantic memory palace using vector storage, where the [`mempalace/palace_graph.py`](https://github.com/MemPalace/mempalace/blob/main/mempalace/palace_graph.py) module provides the navigation backbone. This module constructs a graph representation of rooms and their connecting tunnels (wings) to enable intelligent discovery. Understanding how it implements **room traversal and BFS navigation** reveals how the system answers "what is connected to this idea?" queries with minimal latency.

## Constructing the In-Memory Graph

Before traversal begins, the module must translate ChromaDB collections into traversable graph structures.

### Loading the ChromaDB Collection

The `_get_collection()` function (lines 78-87) retrieves the underlying ChromaDB collection that stores the palace data. If the collection cannot be opened, it returns `None` harmlessly, allowing the module to fail gracefully while maintaining operational independence from the database layer.

### Building Nodes and Edges

The `build_graph()` function (lines 90-108) performs the heavy lifting of graph construction. It iterates over every drawer in the collection, extracting metadata fields including `room`, `wing`, `hall`, and optional `date` timestamps. 

For each unique room, the function aggregates:
- The set of **wings** the room appears in
- The **halls** (tunnels) traversing those wings
- A count of drawers belonging to the room
- Up to five recent dates

When a room spans **two or more wings**, the function creates an **undirected edge** for every unordered pair of those wings, tied to each participating hall. The resulting graph structure is cached with a **60-second TTL** to ensure cheap reuse across subsequent queries without rebuilding from scratch.

## BFS Navigation Implementation

With the graph cached in memory, the `traverse()` function implements the pathfinding logic.

### Validating the Start Room

The traversal process begins at lines 98-103, where `traverse()` invokes `build_graph()` and validates that the requested `start_room` exists in the node map. If the room is missing, the module employs a fuzzy-matching helper to suggest similar valid room names before proceeding.

### Initializing the BFS State

Lines 104-116 initialize the algorithm’s state using simple Python data structures:
- `visited`: A set tracking explored rooms to prevent cycles
- `results`: A list seeded with the start room at hop distance 0
- `frontier`: A FIFO list of `(room, depth)` tuples acting as the BFS queue

### The Traversal Loop

The core BFS implementation occupies lines 118-145. While the frontier remains non-empty, the algorithm:
1. Pops the next `(current_room, depth)` tuple from the front of the list
2. Terminates the branch if `depth` equals the user-specified `max_hops`
3. Retrieves `current_wings` for the current room
4. Scans all rooms in the graph to find unvisited neighbors sharing at least one wing (`shared_wings`)
5. Records new results including the shared wing identifiers and queues the neighbor with `depth + 1`

This implementation leverages the graph’s **undirected** nature—rooms connect bidirectionally through shared wings—ensuring BFS naturally yields the smallest number of hops between any two ideas.

### Sorting and Truncation

Post-processing occurs at lines 146-149. The accumulated results are sorted first by **hop distance (ascending)**, then by **drawer count (descending)**. This ranking surfaces the closest rooms first, while prioritizing heavily populated (more significant) rooms among equidistant neighbors. The function returns only the **top 50 entries** to maintain lightweight API responses.

## Practical Usage Examples

The following examples demonstrate the traversal API and tunnel discovery utilities:

```python
from mempalace.palace_graph import traverse, find_tunnels

# Find rooms up to 2 hops away from "chromadb-setup"

nearby = traverse("chromadb-setup", max_hops=2)
for entry in nearby:
    print(f"{entry['room']:30}  hops={entry['hop']}  wings={entry['wings']}")

# Locate tunnel rooms bridging "wing_code" and "wing_myproject"

tunnels = find_tunnels(wing_a="wing_code", wing_b="wing_myproject")
for t in tunnels:
    print(f"{t['room']}  (wings: {t['wings']})  count={t['count']}")

```

The first call invokes the BFS loop described above, while `find_tunnels()` utilizes the same underlying graph to identify rooms spanning multiple specified wings.

## Summary

- **`build_graph()`** constructs an undirected graph from ChromaDB metadata, caching nodes and edges for 60 seconds to optimize repeated traversals.
- **BFS navigation** uses a FIFO queue to explore rooms level-by-level, guaranteeing minimum-hop paths through shared wings.
- **Validation and fuzzy matching** ensure robust handling of missing start rooms before traversal begins.
- **Result ranking** sorts by proximity then by content volume, returning only the top 50 most relevant rooms.
- **Helper utilities** including `_normalize_wing()` (lines 40-57) and `find_tunnels()` provide additional navigation capabilities for wing-based queries.

## Frequently Asked Questions

### How does the palace_graph module handle invalid room names?

When `traverse()` cannot locate the requested `start_room` in the graph, it invokes an internal `_fuzzy_match()` helper to identify similar room names based on string proximity. This allows the system to suggest corrections before raising errors, improving the user experience when navigating the memory palace.

### Why does the module use a simple list-based queue instead of a deque for BFS?

The implementation uses a basic Python list as a FIFO queue for the frontier because the graph size typically remains in the low thousands of nodes. According to the source code analysis, this deliberate simplification avoids the overhead of complex data structures while maintaining traversal times under a few milliseconds per query.

### How are wing identifiers kept consistent across the navigation system?

The module employs `_normalize_wing()` (lines 40-57), which wraps `normalize_wing_name` from [`mempalace/config.py`](https://github.com/MemPalace/mempalace/blob/main/mempalace/config.py). This utility standardizes wing identifiers by handling formatting inconsistencies such as underscores versus hyphens, ensuring that graph edges connect correctly regardless of input formatting variations.

### What limits the depth of exploration in the BFS algorithm?

The `traverse()` function accepts a `max_hops` parameter that terminates branch expansion when the current depth equals this value. During the BFS loop at lines 118-145, the algorithm checks `depth` against `max_hops` before enqueuing neighbors, allowing users to constrain search radius from 1 hop (immediate neighbors) to arbitrary distances.