Graph Computation

The graph computation system manages dependency relationships between nodes, propagates effective states across the graph, and enforces acyclicity through cycle detection. It enables users to model complex systems where the health of one component affects others transitively.

Dependency Graph Model

Nodes represent components (e.g., services, resources) with states "green", "yellow", or "red". Edges represent dependencies stored in the Database Schema: an edge from_node -> to_node means from_node depends on to_node. State problems propagate upstream: if a dependency fails, dependents inherit the worst state.

The graph remains a directed acyclic graph (DAG) due to runtime checks. Computations use breadth-first search (BFS) traversals on SQLite queries for efficiency with small-to-medium graphs.

Cycle Detection

Before inserting an edge fromNode -> toNode, wouldCreateCycle verifies it does not form a cycle. It treats self-loops (fromNode === toNode) as cycles and performs BFS from toNode along outgoing edges (SELECT to_node FROM edges WHERE ... from_node = current). If fromNode is reachable, a cycle exists.

This prevents invalid graphs during node updates (/nodes) or YAML imports (/graph PUT).

// src/graph/cycle.ts
export function wouldCreateCycle(
  db: Database,
  nsId: number,
  fromNode: string,
  toNode: string,
): boolean {
  if (fromNode === toNode) return true;

  const visited = new Set<string>();
  const queue = [toNode];

  while (queue.length > 0) {
    const current = queue.shift();
    if (current === undefined) continue;
    if (current === fromNode) return true;
    if (visited.has(current)) continue;
    visited.add(current);

    const rows = db
      .query("SELECT to_node FROM edges WHERE ns_id = ? AND from_node = ?")
      .all(nsId, current) as { to_node: string }[];

    for (const row of rows) {
      if (!visited.has(row.to_node)) {
        queue.push(row.to_node);
      }
    }
  }

  return false;
}

Errors like "Cycle detected: A -> B would create a cycle" return HTTP 409.

Node State Resolution (TTL)

A node's raw state may auto-degrade via ttl (time-to-live in seconds). If state is "green", ttl is set, and time since last_state_write exceeds ttl, the resolved state becomes "yellow". Non-green states and missing TTL ignore this.

// src/graph/effective.ts
function resolveNodeState(node: {
  state: string;
  ttl: number | null;
  last_state_write: string | null;
}): string {
  if (!node.ttl || !node.last_state_write) return node.state;
  if (node.state !== "green") return node.state;

  const lastWrite = new Date(`${node.last_state_write}Z`).getTime();
  const now = Date.now();
  const elapsed = (now - lastWrite) / 1000;

  if (elapsed > node.ttl) return "yellow";
  return node.state;
}

last_state_write updates on every state write (even no-change). TTL prevents stale "green" assumptions.

Effective State Propagation

computeEffectiveState yields the worst resolved state across the node and its transitive dependencies (outgoing edges). States prioritize as green (0) < yellow (1) < red (2); worstState(a, b) selects the higher priority.

BFS starts at nodeId, resolves each node's state, and aggregates:

// src/graph/effective.ts (excerpt)
export function computeEffectiveState(
  db: Database,
  nsId: number,
  nodeId: string,
): string {
  // Fetch and resolve local node
  let worst = resolveNodeState(node);

  const visited = new Set<string>();
  const queue = [nodeId];

  while (queue.length > 0) {
    // ... visit, fetch deps
    for (const dep of deps) {
      const depNode = // fetch
      if (depNode) {
        worst = worstState(worst, resolveNodeState(depNode));
        if (!visited.has(dep.to_node)) {
          queue.push(dep.to_node);
        }
      }
    }
  }

  return worst;
}

Called on-the-fly in /nodes listing, /graph export, state updates, and CLI status. Design favors recomputation over caching to reflect instant changes without staleness.

Upstream and Downstream Traversal

From code:

// src/graph/effective.ts
export function getUpstreamNodes( // dependencies of nodeId
  db: Database,
  nsId: number,
  nodeId: string,
): string[] {
  // queue = [nodeId]
  // dependents = SELECT to_node FROM edges WHERE from_node = current  ? No:
  const deps = db
    .query("SELECT to_node FROM edges WHERE ns_id = ? AND from_node = ?")  // outgoing: deps of current
    .all(nsId, current) as { to_node: string }[];
  // Yes: upstream = transitive {to_node} from nodeId (dependencies).
}

Clarification:

Used in API subgraphs: /graph/{ns}/{node} (upstream + node + downstream), /upstream, /downstream.

CLI Integration

CLI graph fetches full graph JSON, builds inverted adjacency (dependedOnBy), identifies roots (no outgoing? No: roots have no incoming deps, i.e., no dependents? Wait:

From src/cli/commands/graph.ts:

In dep graphs, roots have no incoming? Convention:

Tree prints from roots (no deps) downward to dependents (using dependedOnBy as children).

Uses effective_state for coloring.

Design Decisions

See Graph Visualization for rendering, Notifications for propagation triggers, Api Reference for endpoints, Cli for tree printing.

Recent changes