A node graph evaluator with asynchronous evaluation, memoization, and automatic parallelization.

AsyncNodeGraph.ts

// GraphNodeValue is the type of value a GraphNode evaluation can produce
type GraphNodeValue = any;

// GraphNodeArgs are the arguments of a GraphNode evaluation
type GraphNodeArgs = GraphNodeValue[];

// GraphNodeResult is the result of a GraphNode evaluation
type GraphNodeResult = GraphNodeValue[];

// GraphEnv is the result of a Graph evaluation. Env is short for "environment" in programming language jargon.
type GraphEnv = { [id: number]: GraphNodeResult };

// GraphLink is a connection in the graph
class GraphLink {
    constructor(
        readonly inID: string,
        readonly inSlot: number,
        readonly outID: string,
        readonly outSlot: number) {}
}

// GraphNode is a node in the Graph. It has input slots and output slots.
interface GraphNode {
    readonly numIn: number;
    readonly numOut: number;
    eval(args: GraphNodeArgs, done: (res: GraphNodeResult) => void);
}

// DelayedGraphNode evaluates a function passed as an argument asynchronously with the given delay
class DelayedGraphNode {
    constructor(readonly numIn: number, readonly numOut: number, readonly f: (args: GraphNodeArgs) => GraphNodeResult, readonly delayMs: number)
    {}

    eval(args: GraphNodeArgs, done: (res: GraphNodeResult) => void) {
        // for demonstration purposes, this node is always evaluate asynchronously
        setTimeout( () => done(this.f(args)), this.delayMs);
    }
}

// Graph is simply Nodes and Links

type Nodes = { [id: number]: GraphNode };
type Links = { [id: number]: GraphLink };

class Graph {
    constructor(readonly nodes: Nodes, readonly links: Links) {}
}

// A library of simple nodes

// oneNode evaluates to 1
const oneNode =    () => new DelayedGraphNode(0, 1, () => [1], 500);

// addNode evaluates the sum of two input values
const addNode =    () => new DelayedGraphNode(2, 1, (args) => [args[0] + args[1]], 200);

// incNode evaluates the value plus one
const incNode =    () => new DelayedGraphNode(1, 1, (args) => [args[0] + 1], 1000);

// logNode prints out its input value
const logNode =    () => new DelayedGraphNode(1, 1, (args) => { console.log(args[0]); return []; }, 200);

// evalSlot evaluates the value necessary to satisfy an input slot of a GraphNode. It does this by looking up the GraphNode
// on the source end of the Link connected to the InputSlot.
function evalSlot(graph: Graph, nodeID: string, slot: number, env: GraphEnv, done: (res: GraphNodeValue) => void) {
    // find the source node
    const links = graph.links;

    let srcNodeID = "";
    let srcNodeSlot = -1;

    for (const linkID in links) {
        const link = links[linkID];

        if (link.outID === nodeID && link.outSlot === slot) {
            srcNodeID = link.inID;
            srcNodeSlot = link.inSlot;
        }
    }

    if (srcNodeID === "") {
        throw new Error("Could not find source node");
    }

    evalNode(graph, srcNodeID, env, () => {
        done(env[srcNodeID][srcNodeSlot]);
    });
}

// evalNode evaluates the GraphNode by recursively evaluating its inputs. It stores the NodeResults in the provided GraphEnv.
function evalNode(graph: Graph, nodeID: string, env: GraphEnv, done: (env: GraphEnv) => void) {
    // if memoized, return fast
    if (env[nodeID]) {
        return done(env);
    }

    const node = graph.nodes[nodeID];

    let inputsLeft = node.numIn;
    const args: GraphNodeArgs = [];

    // evaluates the node and stores its result in the env
    function evalNodeMemo() {
        return node.eval(args, (res) => {
            env[nodeID] = res;
            done(env);
        });
    }

    // if the node has no inputs, return the value immediately
    if (inputsLeft === 0) {
        evalNodeMemo();
    }

    // eval all inputs in parallel
    for (let i = 0, l = node.numIn; i < l; i++) {
        const portIndex = i;

        evalSlot(graph, nodeID, i, env, (res) => {
            args[portIndex] = res;

            // once the input are complete, evaluate the node
            if (--inputsLeft === 0) {
                evalNodeMemo();
            }
        });
    }
}

// evalGraphEnv evaluates the given Graph in the given GraphEnv. This allows you to supply memoized results to the graph
// computation.
function evalGraphEnv(graph: Graph, env: GraphEnv, done: (env: GraphEnv) => void) {
    const { nodes, links } = graph;

    // find the "end nodes" - nodes with no links connected to their output slots
    const endNodes = [];

    for (const nodeID in nodes) {
        let isEndNode = true;
        for (const linkID in links) {
            const link = links[linkID];
    
            if (link.inID === nodeID) {
                isEndNode = false;
                break;
            }
        }
    
        if (isEndNode) {
            endNodes.push(nodeID);
        }
    }

    let nodesLeft = endNodes.length;

    if (nodesLeft === 0) {
        done(env);
    }
    
    // evaluate all end nodes in parallel
    for (const nodeID of endNodes) {
        evalNode(graph, nodeID, env, () => {
            if (--nodesLeft === 0) {
                done(env);
            }
        });
    }
}

// evalGraph evaluates the Graph, producing the resultant environment with all node values stored
function evalGraph(graph: Graph, done: (env: GraphEnv) => void) {
    evalGraphEnv(graph, {}, done);
}

// evalGraphDelta uses the memoized results from a previous call to evalGraph, but evicts the NodeResults for the modified nodes
// and any Nodes that consume those values.
function evalGraphDelta(graph: Graph, env: GraphEnv, modifiedNodeIDs: string[], done: (env: GraphEnv) => void) {
    const { links } = graph;

    function markDirtyRec(nodeID: string) {
        delete env[nodeID];

        for (const linkID in links) {
            const link = links[linkID];
            if (link.inID === nodeID) {
                markDirtyRec(link.outID);
            }
        }
    }

    // delete the memoized results of all modified nodes recursively
    for (const nodeID of modifiedNodeIDs) {
        markDirtyRec(nodeID);
    }

    evalGraphEnv(graph, env, done);
}

// Create a simple graph

const g = new Graph(
{
    0: oneNode(),
    1: incNode(),
    2: oneNode(),
    3: addNode(),
    4: logNode()
},
{
    0: new GraphLink("0",0,"1",0),
    1: new GraphLink("1",0,"3",0),
    2: new GraphLink("2",0,"3",1),
    3: new GraphLink("3",0,"4",0)
});

// evaluate it
evalGraph(g, (env) => {
    console.log("done 1", env);

    evalGraphDelta(g, env, ["3"], (env2) => {
        console.log("done delta", env);
    });
});