Shortest path between two memories

Instructions

Implementation Reference

• src/tools/memory-path.ts:20-93 (handler)

  Core handler that finds the shortest path between two memories using BFS on the edges graph, returning both a text representation and structured payload.

  export async function findMemoryPath(
    memRepo: MemoriesRepo,
    edgesRepo: EdgesRepo,
    params: MemoryPathParams,
  ): Promise<{ text: string; structured: MemoryPathResult }> {
    const maxHops = params.max_hops ?? 4;
  
    const path = edgesRepo.shortestPath(params.from_id, params.to_id, maxHops, params.edge_types);
    if (!path) {
      const message = `No path from ${params.from_id} to ${params.to_id} within ${maxHops} hops`;
      return {
        text: message,
        structured: { found: false, hops: 0, path: [], message },
      };
    }
  
    if (path.length === 1) {
      const mem = memRepo.getById(path[0]);
      const title = mem ? mem.title : path[0];
      return {
        text: `${path[0]} "${title}"`,
        structured: {
          found: true,
          hops: 0,
          path: [{ id: String(path[0]), title: String(title) }],
        },
      };
    }
  
    const parts: string[] = [];
    const structuredNodes: MemoryPathResult["path"] = [];
  
    for (let i = 0; i < path.length; i++) {
      const nodeId = path[i];
      const mem = memRepo.getById(nodeId);
      const title = mem ? mem.title : nodeId;
      parts.push(`${nodeId} "${title}"`);
  
      let edgeTypeToNext: EdgeType | undefined;
      if (i < path.length - 1) {
        const nextId = path[i + 1];
        const outEdges = edgesRepo.outgoing(nodeId, params.edge_types);
        const matchingOut = outEdges.find(e => e.to_id === nextId);
        if (matchingOut) {
          parts.push(`→ ${matchingOut.edge_type} →`);
          edgeTypeToNext = matchingOut.edge_type;
        } else {
          const inEdges = edgesRepo.incoming(nodeId, params.edge_types);
          const matchingIn = inEdges.find(e => e.from_id === nextId);
          if (matchingIn) {
            parts.push(`→ ${matchingIn.edge_type} →`);
            edgeTypeToNext = matchingIn.edge_type;
          } else {
            parts.push(`→`);
          }
        }
      }
  
      structuredNodes.push({
        id: String(nodeId),
        title: String(title),
        ...(edgeTypeToNext ? { edge_type_to_next: edgeTypeToNext } : {}),
      });
    }
  
    return {
      text: parts.join(" "),
      structured: {
        found: true,
        hops: path.length - 1,
        path: structuredNodes,
      },
    };
  }

• src/tools/memory-path.ts:5-10 (schema)

  Input parameter types for the memory_path tool.

  export interface MemoryPathParams {
    from_id: string;
    to_id: string;
    max_hops?: number;
    edge_types?: EdgeType[];
  }

• src/tools/memory-path.ts:13-18 (schema)

  Structured output type for the memory_path tool result.

  export type MemoryPathResult = {
    found: boolean;
    hops: number;
    path: Array<{ id: string; title: string; edge_type_to_next?: EdgeType }>;
    message?: string;
  };

• src/index.ts:778-814 (registration)

  Registration of the 'memory_path' tool with the MCP server, including input/output schemas and invocation handler.

  server.registerTool(
    "memory_path",
    {
      title: "Shortest path between two memories",
      description: [
        "BFS shortest path between two memories — returns the chain of ids + edge types, or a `no path` message when unreachable within `max_hops`. Read-only.",
        "Use after `memory_search` (with both endpoints known) to trace cause-effect chains, supersession history, or dependency lineage.",
      ].join(" "),
      inputSchema: {
        from_id: z.string().min(1).describe("Starting memory id."),
        to_id: z.string().min(1).describe("Destination memory id."),
        max_hops: z.number().int().min(1).max(10).default(4).describe("Maximum BFS depth (1-10). Default 4. Returns `no path` if the destination is further than `max_hops` from the start."),
        edge_types: z.array(edgeTypeEnum).optional().describe("Optional whitelist of edge types to follow. Omit to allow all types."),
      },
      annotations: {
        title: "Shortest path between two memories",
        readOnlyHint: true,
        destructiveHint: false,
        idempotentHint: true,
        openWorldHint: false,
      },
      outputSchema: {
        found: z.boolean().describe("`true` when a path exists within `max_hops`; `false` otherwise (in which case `path` is empty and `message` carries the reason)."),
        hops: z.number().int().nonnegative().describe("Number of edges in the path. 0 when `from_id === to_id`."),
        path: z.array(z.object({
          id: z.string().describe("Memory id of this node along the path."),
          title: z.string().describe("Memory title (or id when the memory has been deleted)."),
          edge_type_to_next: edgeTypeEnum.optional().describe("The edge type linking this node to the next one in the path. Absent on the final node."),
        })).describe("Ordered list of nodes from `from_id` to `to_id`, each annotated with the edge type that takes you to the next node."),
        message: z.string().optional().describe("Human-readable failure reason when `found=false` (e.g. `No path from <a> to <b> within <n> hops`)."),
      },
    },
    async (params) => {
      const { text, structured } = await findMemoryPath(memRepo, edgesRepo, params);
      return { content: [{ type: "text" as const, text }], structuredContent: structured };
    }
  );

• src/db/edges.ts:119-162 (helper)

  BFS shortest path algorithm in EdgesRepo that returns array of node IDs or null if no path within maxHops.

  shortestPath(
    fromId: string,
    toId: string,
    maxHops: number,
    types?: EdgeType[]
  ): string[] | null {
    if (fromId === toId) return [fromId];
  
    const visited = new Map<string, string | null>();
    visited.set(fromId, null);
    let frontier = [fromId];
  
    for (let hop = 0; hop < maxHops; hop++) {
      const nextFrontier: string[] = [];
      for (const nodeId of frontier) {
        const outEdges = this.outgoing(nodeId, types);
        const inEdges = this.incoming(nodeId, types);
        const neighbors = [
          ...outEdges.map(e => e.to_id),
          ...inEdges.map(e => e.from_id),
        ];
        for (const neighbor of neighbors) {
          if (!visited.has(neighbor)) {
            visited.set(neighbor, nodeId);
            if (neighbor === toId) {
              // Reconstruct path
              const path: string[] = [];
              let cur: string | null = toId;
              while (cur !== null) {
                path.unshift(cur);
                cur = visited.get(cur) ?? null;
              }
              return path;
            }
            nextFrontier.push(neighbor);
          }
        }
      }
      frontier = nextFrontier;
      if (frontier.length === 0) break;
    }
  
    return null;
  }