How can an algorithm interpret a directed node graph -

problem: interpreting node graph

recently have been interested in node editors, , i'm referring editors such ones seen , used in maya, blender, substance painter, , in unreal engine 4.

my code separated in 2 parts, 1 side handles ui (creating nodes, moving nodes, attaching nodes) , other one, 1 i'm working on right interpreter reads graph.

here's screenshot of showing 3 nodes connected edges (they directed go way: pink -> green). 1 node can have multiple parameters (green docks) , multiple return values (green docks).

just clear, have object updates when things change onscreen (node connection, node creation/deletion). want create algorithm interprets/read graph in order run program described nodes.

i found this reddit thread helped me bit in understanding problem. i'm still not confident enough start writing code it.

i'm assuming there needs starting node, initiate reading of graph problem face when gets more complicated, such graph multiple input nodes.

(bellow image has annotation in red.)

directed node path:

the following algorithm interpret graph node:

some more details on node graph:

1. green docks variables come other nodes, objects outputted previous node. on other hand square docks constants.

2. i refer "control object" object holds links between docks in graph.

---

-- start of algorithm --

• search input nodes, meaning nodes have no links attached on left (no parameter).

  there 5 on graph: a, b, c, e, , k have constant docks on left: a1, b1, b2, c1, e1, e2, k1 , k2 defined variables.

• nodes functions, , input nodes functions without parameters. no other values needed, therefore can calculate output of 5 nodes.

  these outputs are: a2, b3, c2, e3, e4, k3.

• with our control object know docks connected these 4 outputs

  they link so: a2 -> d1; b3 -> d2; c2 -> d3; c2 -> f1; e3 -> g2; e4 -> j1; k3 -> n3

note: pink docks link multiple green docks processed if there multiple identical pink docks. here exemple output c2 of node c can seen c2 , c2' (because c2 links d3 , f1). in total have 7 links analyze.

• yet again our control object @ 7 links end up.

  they end in d, f, g, j , n nodes

• they end on 5 different nodes. now, can calculate d output, f output, g output, j output , n output? or need other variables don't have right now?

  node d has 3 parameters , happens have 3 parameters: d1, d2, d3 can calculate d's output right now: d4 node f has 1 parameter , have f1, can calculate f's output: f2 node g has 2 parameters have g2, can't calculate g's output => store g2 in g's waiting queue in control object node j same thing have j1 not j2 => store j1 in j's waiting queue in control object node n has 3 parameters have n3

• at end of step have calculated d4 , f2 , stored in our control object following values: n3 (which hasn't been used because don't yet have n1, n2), g2 (because don't have g1) , j1 (because don't have j2). let's @ d4 , f2 end up

  

  d4 ends on g node: on g1 dock (therefore object in d4 dock equals object in g1) f2 ends on j node: on j2 dock (same here)

• can calculate g , j?

  for g have 2 parameters on 2 can g3 j have 2 parameters on 2 can j3

  

• check g3 , j3 end

  h, , l nodes

• can calculate them?

  h has 2 parameters: h2 equal g3 , other 1 set => calculate h3 has 2 parameters: i1 equal g3 , other 1 set => calculate i3 l has 1 parameter: l1 => calculate l2

• where h3, i3, l2 end at?

  m , n

• can calculate m , n?

  m has 2 parameters, have m1 , m2 => can calculate m3 n has 3 parameters, have n3 first step stored in n's parameters array , n2 equal l2 => cannot calculate n

• we have last vertex sort out: m3

  it goes n, m3 = n1

• can calculate n?

  now can because have n1, n2, n3 => can calculate node n (no output in case)

• no more vertices sort

-- end of algorithm --