Skip to content

Instantly share code, notes, and snippets.

@pboyer
Last active October 5, 2018 00:38
Show Gist options
  • Save pboyer/81b3b53b24e71cb4ff6f2aa9cd8a2052 to your computer and use it in GitHub Desktop.
Save pboyer/81b3b53b24e71cb4ff6f2aa9cd8a2052 to your computer and use it in GitHub Desktop.
A node graph evaluator with asynchronous evaluation, memoization, and automatic parallelization.
// 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);
});
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment