# core/validators/graph.validator.ts

> 92 lines of code and 14 definitions.

Tree: GovLab Patterns
Language: typescript
Layer: processing
Canonical: https://banes-lab.com/anatomy/patterns#file-patterns-core-validators-graph-validator-ts
Source text: https://banes-lab.com/source/patterns/core/validators/graph.validator.ts.txt

Listed in [core/validators](https://banes-lab.com/api/source/patterns/core/validators.md), before [core/validators/markup.validator.ts](https://banes-lab.com/source/patterns/core/validators/markup.validator.ts.md).

## Definitions

- `validateGraph` (lexical_declaration, line 95, exported)
- `checkMonotone` (lexical_declaration, line 72)
- `checkEdges` (lexical_declaration, line 37)
- `checkReachable` (lexical_declaration, line 83)
- `walk` (lexical_declaration, line 50)
- `checkAcyclic` (lexical_declaration, line 65)
- `indexNodes` (lexical_declaration, line 26)
- `GraphError` (class_declaration, line 13, exported)
- `constructor` (method_definition, line 14, exported)
- `WalkState` (interface_declaration, line 20)
- `state` (lexical_declaration, line 66)
- `upstream` (lexical_declaration, line 75)
- `consumed` (lexical_declaration, line 84)
- `index` (lexical_declaration, line 96, exported)

## Contained in

- [core/validators](https://banes-lab.com/anatomy/patterns/folder-patterns-core-validators.md)

## Uses

- [configuration/strings/graph.strings.ts](https://banes-lab.com/source/patterns/configuration/strings/graph.strings.ts.md)
- [core/resolvers/axis.resolver.ts](https://banes-lab.com/source/patterns/core/resolvers/axis.resolver.ts.md)

## Used by

- [core/models/graph.model.ts](https://banes-lab.com/source/patterns/core/models/graph.model.ts.md)

## Linked from

- [configuration/strings](https://banes-lab.com/anatomy/patterns/folder-patterns-configuration-strings.md)
- [core/models](https://banes-lab.com/anatomy/patterns/folder-patterns-core-models.md)
- [core/resolvers](https://banes-lab.com/anatomy/patterns/folder-patterns-core-resolvers.md)
- [core/validators](https://banes-lab.com/anatomy/patterns/folder-patterns-core-validators.md)

## Source

```typescript
import {
    deadNode,
    effectCycle,
    missingProducer,
    orphanNode,
    ownProducer,
    producedTwice,
    stepsBack,
} from "#configuration/strings/graph.strings";
import type { Node } from "#types/graph.types";
import { reasoningRank } from "#core/resolvers/axis.resolver";

export class GraphError extends Error {
    public constructor(message: string) {
        super(message);
        this.name = "GraphError";
    }
}

interface WalkState {
    index: ReadonlyMap<string, Node>;
    visiting: Set<string>;
    done: Set<string>;
}

const indexNodes = function indexNodes(nodes: readonly Node[]): Map<string, Node> {
    const index = new Map<string, Node>();
    for (const node of nodes) {
        if (index.has(node.id)) {
            throw new GraphError(producedTwice(node.id));
        }
        index.set(node.id, node);
    }
    return index;
};

const checkEdges = function checkEdges(nodes: readonly Node[], index: ReadonlyMap<string, Node>): void {
    for (const node of nodes) {
        for (const producer of node.inputs) {
            if (!index.has(producer)) {
                throw new GraphError(missingProducer(node.id, producer));
            }
            if (producer === node.id) {
                throw new GraphError(ownProducer(node.id));
            }
        }
    }
};

const walk = function walk(nodeId: string, state: WalkState): void {
    if (state.done.has(nodeId)) {
        return;
    }
    if (state.visiting.has(nodeId)) {
        throw new GraphError(effectCycle(nodeId));
    }
    state.visiting.add(nodeId);
    for (const producer of state.index.get(nodeId)?.inputs ?? []) {
        walk(producer, state);
    }
    state.visiting.delete(nodeId);
    state.done.add(nodeId);
};

const checkAcyclic = function checkAcyclic(nodes: readonly Node[], index: ReadonlyMap<string, Node>): void {
    const state: WalkState = { done: new Set<string>(), index, visiting: new Set<string>() };
    for (const node of nodes) {
        walk(node.id, state);
    }
};

const checkMonotone = function checkMonotone(nodes: readonly Node[], index: ReadonlyMap<string, Node>): void {
    for (const node of nodes) {
        for (const producer of node.inputs) {
            const upstream = index.get(producer);
            if (upstream && reasoningRank(upstream.reasoning) > reasoningRank(node.reasoning)) {
                throw new GraphError(stepsBack(producer, node.id));
            }
        }
    }
};

const checkReachable = function checkReachable(nodes: readonly Node[]): void {
    const consumed = new Set(nodes.flatMap((node) => node.inputs));
    for (const node of nodes) {
        if (node.kind !== "source" && node.inputs.length === 0) {
            throw new GraphError(orphanNode(node.id));
        }
        if (node.kind === "analysis" && !consumed.has(node.id)) {
            throw new GraphError(deadNode(node.id));
        }
    }
};

export const validateGraph = function validateGraph(nodes: readonly Node[]): void {
    const index = indexNodes(nodes);
    checkEdges(nodes, index);
    checkAcyclic(nodes, index);
    checkMonotone(nodes, index);
    checkReachable(nodes);
};
```