349 lines
11 KiB
JavaScript
349 lines
11 KiB
JavaScript
/**
|
|
* Deterministic graph utilities for situation graph operations.
|
|
* These functions perform safe, validated operations on the graph.
|
|
* The LLM should never directly modify the graph — it proposes changes,
|
|
* and these utilities apply them safely.
|
|
*/
|
|
|
|
import { situationNodeSchema, situationEdgeSchema, situationGraphSchema } from "./schema.js";
|
|
|
|
// ── Validate that all edge references point to existing nodes ──
|
|
|
|
export function validateGraphReferences(graph) {
|
|
const errors = [];
|
|
const nodeIds = new Set(graph.nodes.map((n) => n.id));
|
|
|
|
for (const node of graph.nodes) {
|
|
if (node.parentId !== null && !nodeIds.has(node.parentId)) {
|
|
errors.push(`Node "${node.id}" references parentId "${node.parentId}" which does not exist`);
|
|
}
|
|
for (const cid of node.childIds) {
|
|
if (!nodeIds.has(cid)) {
|
|
errors.push(`Node "${node.id}" references childIds "${cid}" which does not exist`);
|
|
}
|
|
}
|
|
for (const dep of node.dependsOn) {
|
|
if (!nodeIds.has(dep)) {
|
|
errors.push(`Node "${node.id}" depends on "${dep}" which does not exist`);
|
|
}
|
|
}
|
|
for (const aff of node.affects) {
|
|
if (!nodeIds.has(aff)) {
|
|
errors.push(`Node "${node.id}" affects "${aff}" which does not exist`);
|
|
}
|
|
}
|
|
}
|
|
|
|
for (const edge of graph.edges) {
|
|
if (!nodeIds.has(edge.fromNodeId)) {
|
|
errors.push(`Edge "${edge.id}" references non-existent fromNodeId "${edge.fromNodeId}"`);
|
|
}
|
|
if (!nodeIds.has(edge.toNodeId)) {
|
|
errors.push(`Edge "${edge.id}" references non-existent toNodeId "${edge.toNodeId}"`);
|
|
}
|
|
}
|
|
|
|
return { valid: errors.length === 0, errors };
|
|
}
|
|
|
|
// ── Detect duplicate node IDs ──
|
|
|
|
export function detectDuplicateNodeIds(nodes) {
|
|
const countMap = new Map();
|
|
const seen = new Set();
|
|
|
|
for (const node of nodes) {
|
|
if (countMap.has(node.id)) {
|
|
countMap.set(node.id, countMap.get(node.id) + 1);
|
|
} else {
|
|
countMap.set(node.id, 1);
|
|
}
|
|
}
|
|
|
|
const duplicates = [];
|
|
for (const [id, count] of countMap.entries()) {
|
|
if (count > 1 && !seen.has(id)) {
|
|
duplicates.push({ nodeId: id, count });
|
|
seen.add(id);
|
|
}
|
|
}
|
|
|
|
return duplicates;
|
|
}
|
|
|
|
// ── Detect duplicate edges ──
|
|
|
|
export function detectDuplicateEdges(edges) {
|
|
const seen = new Set();
|
|
const duplicates = [];
|
|
|
|
for (const edge of edges) {
|
|
const key = `${edge.fromNodeId}->${edge.toNodeId}:${edge.relationship}`;
|
|
if (seen.has(key)) {
|
|
duplicates.push({ edgeId: edge.id, fromNodeId: edge.fromNodeId, toNodeId: edge.toNodeId, relationship: edge.relationship });
|
|
}
|
|
seen.add(key);
|
|
}
|
|
|
|
return duplicates;
|
|
}
|
|
|
|
// ── Find all nodes that depend on a given node (transitive) ──
|
|
|
|
export function findDependentNodes(graph, nodeId) {
|
|
const direct = graph.nodes.filter((n) => n.dependsOn.includes(nodeId)).map((n) => n.id);
|
|
const affected = new Set(direct);
|
|
|
|
// Also propagate through edges where the relationship is depends_on
|
|
for (const edge of graph.edges) {
|
|
if (edge.toNodeId === nodeId && !affected.has(edge.fromNodeId)) {
|
|
direct.push(edge.fromNodeId);
|
|
affected.add(edge.fromNodeId);
|
|
}
|
|
}
|
|
|
|
// Transitive propagation — BFS
|
|
const queue = [...direct];
|
|
while (queue.length > 0) {
|
|
const current = queue.shift();
|
|
if (!current || !affected.has(current)) continue;
|
|
|
|
for (const node of graph.nodes) {
|
|
if (node.dependsOn.includes(current) && !affected.has(node.id)) {
|
|
affected.add(node.id);
|
|
queue.push(node.id);
|
|
}
|
|
}
|
|
}
|
|
|
|
return [...affected];
|
|
}
|
|
|
|
// ── Find all nodes that are directly or indirectly affected by a change in nodeId ──
|
|
|
|
export function findAffectedNodes(graph, nodeId) {
|
|
// Direct effects: two sources
|
|
// 1. Nodes that depend on this node (they list it in their dependsOn)
|
|
const directFromDepends = graph.nodes.filter((n) => n.id !== nodeId && n.dependsOn.includes(nodeId)).map((n) => n.id);
|
|
|
|
// 2. Targets of the node's affects relationships (this node directly affects them)
|
|
const myAffectedTargets = new Set(graph.nodes.find((n) => n.id === nodeId)?.affects || []);
|
|
|
|
// Merge: also add edge targets where this node is the source
|
|
for (const edge of graph.edges) {
|
|
if (edge.fromNodeId === nodeId && !myAffectedTargets.has(edge.toNodeId)) {
|
|
myAffectedTargets.add(edge.toNodeId);
|
|
}
|
|
}
|
|
|
|
// Combine both sources
|
|
const direct = [...new Set([...directFromDepends, ...myAffectedTargets])];
|
|
|
|
// Transitive propagation — BFS through dependsOn and affects of affected nodes
|
|
const affected = new Set(direct);
|
|
const queue = [...direct];
|
|
while (queue.length > 0) {
|
|
const current = queue.shift();
|
|
if (!current || !affected.has(current)) continue;
|
|
|
|
for (const node of graph.nodes) {
|
|
if (node.id !== nodeId && !affected.has(node.id) && (node.dependsOn.includes(current) || node.affects.includes(current))) {
|
|
affected.add(node.id);
|
|
queue.push(node.id);
|
|
}
|
|
}
|
|
}
|
|
|
|
return [...affected];
|
|
}
|
|
|
|
// ── Resolve an unknown node ──
|
|
|
|
export function resolveUnknownNode(graph, nodeId, newStatus, newValue, reason) {
|
|
const nodeIdx = graph.nodes.findIndex((n) => n.id === nodeId);
|
|
if (nodeIdx === -1) {
|
|
return { success: false, error: `Node "${nodeId}" not found in graph` };
|
|
}
|
|
|
|
const previousStatus = graph.nodes[nodeIdx].status;
|
|
const previousValue = graph.nodes[nodeIdx].value;
|
|
|
|
return {
|
|
success: true,
|
|
previousStatus,
|
|
newStatus,
|
|
previousValue,
|
|
newValue,
|
|
reason,
|
|
affectedNodes: findAffectedNodes(graph, nodeId),
|
|
};
|
|
}
|
|
|
|
// ── Select the next highest-value active unknown candidate ──
|
|
|
|
export function selectActiveUnknownCandidate(graph, resolvedNodeIds) {
|
|
// Skip already resolved nodes
|
|
const unresolved = graph.nodes.filter(
|
|
(n) => n.kind === "unknown" && !resolvedNodeIds.includes(n.id)
|
|
);
|
|
|
|
if (unresolved.length === 0) return null;
|
|
|
|
// Prioritise: critical unknowns first, then those that are depended upon most
|
|
const dependencyCount = unresolved.map((n) => {
|
|
const deps = findDependentNodes(graph, n.id).length;
|
|
const importanceOrder = { critical: 3, important: 2, supporting: 1, incidental: 0 };
|
|
const impScore = importanceOrder[n.confidence] || 0;
|
|
return { node: n, score: deps * 2 + impScore };
|
|
});
|
|
|
|
dependencyCount.sort((a, b) => b.score - a.score);
|
|
|
|
// Return the highest-scoring unresolved unknown
|
|
const best = dependencyCount[0];
|
|
if (!best) return null;
|
|
|
|
return { nodeId: best.node.id, label: best.node.label, score: best.score };
|
|
}
|
|
|
|
// ── Apply a graph update deterministically ──
|
|
|
|
export function applyGraphUpdate(graph, update) {
|
|
const errors = [];
|
|
const updatedNodesMap = new Map();
|
|
|
|
// Validate that update references existing nodes or newly added ones
|
|
const allNodeIds = new Set(graph.nodes.map((n) => n.id));
|
|
for (const added of update.addedNodes) {
|
|
if (allNodeIds.has(added.id)) {
|
|
errors.push(`Cannot add node with duplicate ID: "${added.id}"`);
|
|
continue;
|
|
}
|
|
allNodeIds.add(added.id);
|
|
}
|
|
|
|
// Validate updated nodes exist
|
|
for (const upd of update.updatedNodes) {
|
|
if (!allNodeIds.has(upd.nodeId)) {
|
|
errors.push(`Cannot update non-existent node: "${upd.nodeId}"`);
|
|
}
|
|
}
|
|
|
|
// Validate added edges reference existing or new nodes
|
|
for (const edge of update.addedEdges) {
|
|
if (!allNodeIds.has(edge.fromNodeId)) {
|
|
errors.push(`Added edge references non-existent fromNodeId: "${edge.fromNodeId}"`);
|
|
}
|
|
if (!allNodeIds.has(edge.toNodeId)) {
|
|
errors.push(`Added edge references non-existent toNodeId: "${edge.toNodeId}"`);
|
|
}
|
|
}
|
|
|
|
if (errors.length > 0) return { success: false, errors };
|
|
|
|
// Build the new nodes list — start with a deep copy of existing
|
|
const newNodes = graph.nodes.map((n) => ({ ...n }));
|
|
|
|
// Apply updated nodes
|
|
for (const upd of update.updatedNodes) {
|
|
const idx = newNodes.findIndex((n) => n.id === upd.nodeId);
|
|
if (idx === -1) continue; // already validated above
|
|
|
|
if (upd.newStatus !== undefined && upd.newStatus !== null) {
|
|
newNodes[idx].status = upd.newStatus;
|
|
}
|
|
if (upd.newValue !== undefined) {
|
|
newNodes[idx].value = upd.newValue;
|
|
}
|
|
updatedNodesMap.set(upd.nodeId, newNodes[idx]);
|
|
}
|
|
|
|
// Add new nodes
|
|
for (const newNode of update.addedNodes) {
|
|
if (!allNodeIds.has(newNode.id)) continue;
|
|
allNodeIds.add(newNode.id);
|
|
newNodes.push({ ...newNode });
|
|
}
|
|
|
|
// Remove edges if requested
|
|
const removedEdgeSet = new Set(update.removedEdgeIds);
|
|
const newEdges = graph.edges.filter((e) => !removedEdgeSet.has(e.id));
|
|
|
|
// Add new edges
|
|
for (const newEdge of update.addedEdges) {
|
|
newEdges.push({ ...newEdge });
|
|
|
|
// Update dependsOn / affects on the nodes
|
|
const fromNode = newNodes.find((n) => n.id === newEdge.fromNodeId);
|
|
const toNode = newNodes.find((n) => n.id === newEdge.toNodeId);
|
|
if (fromNode && !fromNode.childIds.includes(newEdge.toNodeId)) {
|
|
fromNode.childIds.push(newEdge.toNodeId);
|
|
}
|
|
if (toNode && !toNode.dependsOn.includes(newEdge.fromNodeId)) {
|
|
toNode.dependsOn.push(newEdge.fromNodeId);
|
|
}
|
|
}
|
|
|
|
// Add resolved node IDs
|
|
const newResolved = [...new Set([...graph.resolvedNodeIds, ...update.resolvedUnknownNodeIds])];
|
|
|
|
return {
|
|
success: true,
|
|
nodes: newNodes,
|
|
edges: newEdges,
|
|
resolvedNodeIds: newResolved,
|
|
};
|
|
}
|
|
|
|
// ── Validate a proposed graph update before application ──
|
|
|
|
export function validateGraphUpdate(graph, update) {
|
|
const errors = [];
|
|
|
|
// Check for duplicate node IDs against existing and newly added nodes
|
|
const extendedIds = new Set(graph.nodes.map((n) => n.id));
|
|
for (const newNode of update.addedNodes) {
|
|
if (extendedIds.has(newNode.id)) {
|
|
errors.push(`Cannot add node with duplicate ID: "${newNode.id}"`);
|
|
} else {
|
|
extendedIds.add(newNode.id);
|
|
}
|
|
}
|
|
|
|
// Check updated nodes exist (in original graph, not newly added ones)
|
|
const existingIds = new Set(graph.nodes.map((n) => n.id));
|
|
for (const upd of update.updatedNodes) {
|
|
if (!existingIds.has(upd.nodeId)) {
|
|
errors.push(`Cannot update non-existent node: "${upd.nodeId}"`);
|
|
}
|
|
}
|
|
|
|
// Reject updates with no meaningful change
|
|
const statusChanged = update.updatedNodes.some(
|
|
(u) => u.previousStatus !== null && u.newStatus !== u.previousStatus
|
|
);
|
|
const valueChanged = update.updatedNodes.some(
|
|
(u) => u.previousValue !== null && u.newValue !== u.previousValue
|
|
);
|
|
|
|
const hasMeaningfulChange =
|
|
update.addedNodes.length > 0 ||
|
|
statusChanged ||
|
|
valueChanged ||
|
|
update.addedEdges.length > 0 ||
|
|
update.removedEdgeIds.length > 0;
|
|
|
|
if (!hasMeaningfulChange) {
|
|
errors.push("Update contains no meaningful change");
|
|
}
|
|
|
|
// Reject oversized input
|
|
const totalSize = JSON.stringify(update).length;
|
|
if (totalSize > 100000) {
|
|
errors.push(`Proposed graph update exceeds 100KB (${totalSize} bytes)`);
|
|
}
|
|
|
|
return { valid: errors.length === 0, errors };
|
|
}
|
|
|