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).

enter image description here

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.)

enter image description here

directed node path:

the following algorithm interpret graph node:

enter image description here

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

    enter image description here

    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

    enter image description here

  • 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 --


Comments

Post a Comment

Popular posts from this blog

php - Vagrant up error - Uncaught Reflection Exception: Class DOMDocument does not exist -

i've set bento/ubuntu-16.04 vagrant box using php 5.6, , getting following error quite few times when try , run shell script: "uncaught reflection exception: class domdocument not exist". i've tried adding following top of script (not together), each no success: "sudo apt-get install php5.6-xml", "sudo apt-get install php5-xml", "sudo apt-get install php-dom" i've tried resetting server "sudo service apache2 restart". does have suggestions?
Read more

vue.js - Create hooks for automated testing -

Image
qa guys complained can't automate frontend testing. because our html looks same outside. lazy hack did this <template> <div :role="$options.name"> ... </div> </template> <script> export default { name: 'vmcomponentname' } </script> which takes name script , applies html. in browser get: <div role="vmcomponentname"> ... </div> line :role="$options.name" goes in every component. is there dry er solutions? please share. additional details i'll explain in details looking for. imagine have vmusercreate form creates user. test case can create user . to automatically test without role, have use following selector: .wrapper > .wrapper > .wrapper > .submit-button the test extremely brittle (will break lot). if use roles can use [role="vmusercreateform"] .submit-button selector. many folds less brittle. so basically, i'm ...
Read more

Add new key value to json node in java -

i have json file : { "id":1, "name":"abc", "addressdetails": { "city":"newyork" } } i wanted add 1 more key-value ("pincode" : "414141") node 'addressdetails'. i tried using : objectmapper mapper = new objectmapper(); jsonnode root = mapper.readtree(new file("d://test.json")); objectnode node = mapper.createobjectnode(); node.with("addressdetails").put("pincode", "414141"); but it's not getting added, there way can ? you can try you should modify file path objectmapper mapper = new objectmapper(); objectnode nodes = mapper.readvalue(new file("d:\\test.txt"), objectnode.class); nodes.with("addressdetails").put("pincode", "414141"); mapper.writer().writevalue(new file("d:\\test.txt"), nodes);
Read more