dag-solve
Directed acyclic graph (DAG) based solver. The graphs built here always has a single root node, and this root node, can only ever have one in degree and my not have out degrees. Below the root node no further restrictions apply save for the prevention of cycles.
Each node created in the graph can be configured to be a:
- math solver
- an enum solver
- a comparator (equality, identity, inequality, non-identity, bigger-than, smaller-than, bigger-or-equal, smaller-or-equal)
- a band-pass filter (check that a number is between two stops)
- a number rounder
- a data reader
The graph can be serialised to JSON and deserialised back into a DAG object. The graph has a "solve" method that solves the graph. The graph can return a stand-alone solver function that can be applied to large data sets.
Declare a graph
const DAG = ; // Declare the graphconst g = ; // Add named nodesconst A = g;const B = g;const C = g;const D = g; // Connect the nodes// Read connect A to Bg ; groot; // The root node. Auto created and can not be // deleted from the graph. ggraph; // The graph as a Map of Nodes to a Set of Nodes gnodes; // An array of nodes in order of insertion gtopo; // A topo sorted array of nodes gids; // An array of node ids in order of insertion // [ 0, 1, 2, 3, 4 ] gtopoIds; // An array of node ids in topo order // [ 4, 3, 2, 1, 0 ] gnames; // An array of node names in order of insertion // [ 'D', 'C', 'B', 'A', 'ROOT' ] gtopoNames; // An array of node names in order of insertion // [ 'ROOT', 'A', 'B', 'C', 'D' ] gleafs; // An array of leaf nodes. Nodes without any // in-degrees gorphans; // An array of nodes without out-degrees. // Excludes the root node // Getter and setter methods are available to store human readable// stuff about the graph gdescription = 'Calculates temp';gdescription; // 'Calculates temp' gunits = '°C';gunits; // '°C'; gref = 123;gref; // 123 // Note: meta is not dumped or restored via the dump/read cycle.// It is intended for as an in-memory placeholder if needed.gmeta = 'Anything': 'goes';gmeta; // { Anything: [ 'goes' ] }
Structure the graph
// A simple 4 node graph.// C ---→ B ---→ A --→ rootconst g = ;const A = g;const B = g;const C = g;g; gleafs; // [ C ] gorphans; // [] // Disconnect nodesg; // Read disconnect B from Agleafs; // [ A, C ] The don't have in degreesgorphans; // [ B ] It has no out degree. // Who is connected to B?g; // [ C ] remains connected even // if B is orphaned. // Is B really not connected to anything?g; // [] Yep. No out degrees. // So lets delete B from the graph.let b = g; // b === true. Node B is not part of // the graph any more // Oh no! Wait, we need it back.b = g; // b === B. The B node is added back // B remains disconnected // By now, B, and C are orphaned, // and B, C, and A are all leaf nodes.gorphans; // [ C, B ] Note the order of insertiongleafs; // [ A, C, B ] // Lets just clean the graph. Delete all orphans.g; // Recursively deletes all the orphan nodes.gnodes; // [ root, A ]gorphans; // []gleafs; // [ A ]
Nodes can do things
const DAG = ;g = ;gdescription = 'Calc Temp';gunits = '°C';gref = 123;const A = g;const B = g;const C = g;const D = g const E = g;const F = g;const G = g;const H = g;const J = g; g; // In F: G is $1g; // In F: J is $1g; // In B: A is $1g; // In B: D is $2g; // In B: C is $3g; // In A: C is $1g; // In C: F is $1g; // In A: F is $2g; // In C: J is $2g; // In A: H is $3g; // In E: B is $1g; // Lests just declare some date we want to operate on:let event = '123':data:v:332211let data = _ev:event a:b:45 // Solve with the data.g; // undefinedg // 11.5 // What happened at each step?g; // Map { // 'topoIds' => [ 9, 4, 8, 7, 6, 3, 1, 2, 5, 0 ], // 'data' => { _ev: { '123': [Object] }, a: { b: 45 } }, // 9 => 45, // 4 => 12.5, // 8 => 10.5, // 7 => { v: [ 33, 22, 11 ] }, // 6 => 11, // 3 => 11, // 1 => 11.523809523809524, // 2 => 11.523809523809524, // 5 => 11.5, // 0 => 11.5, // 'topoNames' => [ 'J', 'D', 'H', 'G', 'F', 'C', 'A', 'B', 'E', 'ROOT' ] }
Use the solver
Using the exact graph as above, we can get a solver function that can be applied to an array of values.
// Previously we used the the graph directly to solve.// But we can get a solver from the graph that has done some pre-processing// in it's setup. Using this solver is much more efficient than solving// the graph directly.// Now get a standalone solver function from the graphconst s = g; // 11.5 // Solve multiple data points.d1 d2 d3; // [ 4.6, 11.5, 22.9 ... ]
A note on the solver function: It is divorced from the graph, and changes to the graph won't be propagated to the solver function. If the graph changes, (either in structure, or in the set-up of any of its nodes) the solver function needs to be replaced.
Serialise and restore a graph via JSON
Once a graph is configured it can be dumped to JSON for storage, and read back when needed. Using the above graph:
const json = g;
which produces this JSON...
which can be read back into a new graph...
g2 = DAG // A static method to create a DAG from an object;g2; // 11.5g2 === g; // False
Dump a graph to GraphViz DOT format file
var fs = ;const write = fs;;
Optionally pass in data to see the calculation results at each step.
;
digraph {
node [shape=record];
label = "Calc Temp - °C";
0 [label="{{<5>$1}|Root|Final|{ID:0|ROOT}|11.5}"];
1 [label="{{<3>$1|<6>$2|<8>$3}|Math|$1 * $2 / $3|{ID:1|A}|11.523809523809524}"];
2 [label="{{<1>$1|<4>$2|<3>$3}|Range|$1 $2 $3 vu|{ID:2|B}|Default: 4.56|11.523809523809524}"];
3 [label="{{<6>$1|<9>$2}|Comparator|$1 \<= $2 ab|{ID:3|C}|11}"];
4 [label="{{<9>$1}|Enumerator|{10 🠚 0.1}|{3 🠚 -5}|{123 🠚 -432}|{ID:4|D}|Default: 12.5|12.5}"];
5 [label="{{<2>$1}|Rounding|1|{ID:5|E}|11.5}"];
6 [label="{{<7>$1}|Data Access|v 2|{ID:6|F}|11}"];
7 [label="{{}|Event Access|123 data|{ID:7|G}|[object Object]}"];
8 [label="{{}|Constant|10.5|{ID:8|H}|Default: 10.5|10.5}"];
9 [label="{{}|Data Access|a b|{ID:9|J}|45}"];
1 -> 2:1[label="11.523809523809524"];
2 -> 5:2[label="11.523809523809524"];
3 -> 2:3[label="11"];
3 -> 1:3[label="11"];
4 -> 2:4[label="12.5"];
5 -> 0:5[label="11.5"];
6 -> 3:6[label="11"];
6 -> 1:6[label="11"];
7 -> 6:7[label="[object Object]"];
8 -> 1:8[label="10.5"];
9 -> 4:9[label="45"];
9 -> 3:9[label="45"]; }
These DOT-file strings can be used to visualize the graph. See for instance tools like: http://www.webgraphviz.com/ or http://viz-js.com/