How the Path Finder Panel Computes Entity Relationships Using Breadth‑First Search

The Path Finder panel uses a Breadth‑First Search (BFS) algorithm to compute the shortest directed path between two ontology entities by traversing relationship graphs level by level.

The Microsoft Ontology‑Playground provides a Path Finder panel that helps users visualize connections between ontology entities. When you select a source and target entity, the panel calculates the relationship path using a graph traversal algorithm implemented in TypeScript that guarantees optimal results.

How BFS Powers the Path Finder Panel

The algorithm treats ontology relationships as a directed graph where entities are nodes and relationships are directional edges. It executes three distinct phases to discover the optimal path.

Building the Relationship Adjacency Map

First, the system transforms all Relationship objects into an adjacency map. In src/lib/pathFinder.ts, the algorithm constructs a lookup where each from entity points to its outgoing neighbors along with the underlying relationship record. This preprocessing step enables O(1) access to neighboring nodes during the traversal phase.

Traversing the Graph Level by Level

The core BFS implementation starts by enqueueing the source entity. It then iteratively expands the frontier level‑by‑level, exploring all neighbors at the current depth before moving to the next. Each visited entity is recorded in a tracking set to prevent revisiting nodes, which naturally handles cycles in the ontology graph and prevents infinite loops.

Reconstructing the Shortest Path

When the target entity is dequeued, the algorithm reconstructs the path by following the accumulated PathNode objects. Each node optionally stores the traversed Relationship, allowing the UI to display both the entity sequence and the connecting relationships. If the queue empties without finding the target, the function returns null, indicating no directed path exists between the selected entities.

Implementation in src/lib/pathFinder.ts

The findShortestPath function in src/lib/pathFinder.ts implements this BFS logic. It accepts a source entity ID, target entity ID, and an array of Relationship objects, returning an array of PathNode objects representing the shortest path.

import { findShortestPath } from '@/lib/pathFinder';
import type { Relationship } from '@/data/ontology';

// Example relationships defining a simple ontology
const relationships: Relationship[] = [
  { id: 'r1', name: 'hasPart', from: 'Car', to: 'Engine', cardinality: 'one-to-many' },
  { id: 'r2', name: 'hasPart', from: 'Engine', to: 'Piston', cardinality: 'one-to-many' },
  { id: 'r3', name: 'relatedTo', from: 'Car', to: 'Wheel', cardinality: 'one-to-many' },
];

// Compute the shortest directed path from "Car" to "Piston"
const path = findShortestPath('Car', 'Piston', relationships);

if (path) {
  console.log('Path found:', path.map(p => p.entityId).join(' → '));
  // Output: Path found: Car → Engine → Piston
} else {
  console.log('No path exists between the selected entities.');
}

Because BFS explores nodes in order of increasing hop count, the function always yields the path with the minimum number of edges. This matches the UI's "shortest path" view requirement in the Path Finder panel.

Handling Directionality and Cycles

Unlike undirected graph algorithms, this implementation strictly respects relationship directionality—it only traverses from from entities to to entities as defined in each Relationship record. The visited set tracked during traversal prevents infinite loops when ontology definitions contain cyclic references, such as mutual dependencies between classes.

Unit tests in src/lib/pathFinder.test.ts verify these behaviors, including validation of simple paths, directionality constraints, cycle handling, disconnected graphs, and correct shortest‑path selection when multiple routes exist.

Summary

• Breadth‑First Search (BFS) powers the Path Finder panel's relationship computation, guaranteeing the shortest directed path in terms of edge count.
• The algorithm is implemented in src/lib/pathFinder.ts within the findShortestPath function.
• Cycle detection occurs through a visited set maintained during traversal, allowing safe handling of cyclic ontologies.
• Directionality is strictly enforced—edges are traversed only from from to to entities as specified in Relationship records.
• The function returns a sequence of PathNode objects or null when no valid path exists between entities.

Frequently Asked Questions

What algorithm does the path finder panel use to compute entity relationships?

The path finder panel uses a Breadth‑First Search (BFS) algorithm. It explores the ontology graph level by level to discover the shortest directed path between two entities while maintaining a visited set to avoid cycles.

How does the path finder panel handle cyclic relationships in ontologies?

The algorithm maintains a visited set during BFS traversal. Before enqueueing a neighbor, it checks whether the entity has already been processed. This prevents the algorithm from entering infinite loops when encountering cyclic references in the ontology structure.

Why does the path finder panel return only one path instead of all possible paths?

The implementation specifically targets the shortest path (minimum edge count) between entities. BFS naturally discovers this first due to its level‑by‑level expansion. While the underlying graph may contain multiple paths, the UI's "shortest path" view requires only the optimal route, which findShortestPath in src/lib/pathFinder.ts provides.

What happens if no relationship exists between the selected entities?

If the BFS queue empties without reaching the target entity, the findShortestPath function returns null. The Path Finder panel interprets this result to display a "No path exists" message to the user, accurately reflecting disconnected components in the ontology graph.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}