How to resolve data-binding efficiently

Question

Following this question, the solution to resolve data binding is to use DFS and Topological Sorting. I am not really sure exactly what that means. Here is an animation that roughly demonstrates what I am considering.

Say we have a data binding model like this:

 ●くろまる
 ↓
●くろまる → ●くろまる → ●くろまる → ●くろまる ●くろまる ← ●くろまる
 ↑ ↑ ↓
 ●くろまる → ●くろまる → ●くろまる ← ●くろまる → ●くろまる
 ↓ ↓ ↑
 ●くろまる ●くろまる → ●くろまる ← ●くろまる
 ↓ ↓
 ●くろまる ●くろまる
 ↑
 ●くろまる

And then we change one field.

 ●くろまる
 ↓
●くろまる → ●くろまる → ●くろまる → ●くろまる ●くろまる ← ●くろまる
 ↑ ↑ ↓
 ◌ → ●くろまる → ●くろまる ← ●くろまる → ●くろまる
 ↓ ↓ ↑
 ●くろまる ●くろまる → ●くろまる ← ●くろまる
 ↓ ↓
 ●くろまる ●くろまる
 ↑
 ●くろまる

Then it propagates:

 ●くろまる
 ↓
●くろまる → ●くろまる → ◌ → ●くろまる ●くろまる ← ●くろまる
 ↑ ↑ ↓
 ○しろまる → ◌ → ●くろまる ← ●くろまる → ●くろまる
 ↓ ↓ ↑
 ◌ ●くろまる → ●くろまる ← ●くろまる
 ↓ ↓
 ●くろまる ●くろまる
 ↑
 ●くろまる

More...

 ●くろまる
 ↓
●くろまる → ●くろまる → ○しろまる → ◌ ●くろまる ← ●くろまる
 ↑ ↑ ↓
 ○しろまる → ○しろまる → ◌ ← ●くろまる → ●くろまる
 ↓ ↓ ↑
 ○しろまる ●くろまる → ●くろまる ← ●くろまる
 ↓ ↓
 ●くろまる ●くろまる
 ↑
 ●くろまる

...

 ●くろまる
 ↓
●くろまる → ●くろまる → ○しろまる → ○しろまる ◌ ← ●くろまる
 ↑ ↑ ↓
 ○しろまる → ○しろまる → ○しろまる ← ●くろまる → ●くろまる
 ↓ ↓ ↑
 ○しろまる ◌ → ●くろまる ← ●くろまる
 ↓ ↓
 ●くろまる ●くろまる
 ↑
 ●くろまる

 ●くろまる
 ↓
●くろまる → ●くろまる → ○しろまる → ○しろまる ○しろまる ← ●くろまる
 ↑ ↑ ↓
 ○しろまる → ○しろまる → ○しろまる ← ●くろまる → ●くろまる
 ↓ ↓ ↑
 ○しろまる ○しろまる → ◌ ← ●くろまる
 ↓ ↓
 ◌ ●くろまる
 ↑
 ●くろまる

 ●くろまる
 ↓
●くろまる → ●くろまる → ○しろまる → ○しろまる ○しろまる ← ●くろまる
 ↑ ↑ ↓
 ○しろまる → ○しろまる → ○しろまる ← ◌ → ●くろまる
 ↓ ↓ ↑
 ○しろまる ○しろまる → ○しろまる ← ●くろまる
 ↓ ↓
 ○しろまる ◌
 ↑
 ●くろまる

 ●くろまる
 ↓
●くろまる → ●くろまる → ○しろまる → ○しろまる ○しろまる ← ●くろまる
 ↑ ↑ ↓
 ○しろまる → ○しろまる → ○しろまる ← ☀ → ◌
 ↓ ↓ ↑
 ○しろまる ○しろまる → ○しろまる ← ●くろまる
 ↓ ↓
 ○しろまる ○しろまる
 ↑
 ●くろまる

Sometimes it encounters a recent update, as shown with ☀. But it keeps going:

 ●くろまる
 ↓
●くろまる → ●くろまる → ○しろまる → ○しろまる ○しろまる ← ●くろまる
 ↑ ↑ ↓
 ○しろまる → ○しろまる → ○しろまる ← ○しろまる → ○しろまる
 ↓ ↓ ↑
 ○しろまる ○しろまる → ○しろまる ← ●くろまる
 ↓ ↓
 ○しろまる ○しろまる
 ↑
 ●くろまる

Now it has had no more changes, so it goes back into the unchanged state.

 ●くろまる
 ↓
●くろまる → ●くろまる → ●くろまる → ●くろまる ●くろまる ← ●くろまる
 ↑ ↑ ↓
 ●くろまる → ●くろまる → ●くろまる ← ●くろまる → ●くろまる
 ↓ ↓ ↑
 ●くろまる ●くろまる → ●くろまる ← ●くろまる
 ↓ ↓
 ●くろまる ●くろまる
 ↑
 ●くろまる

So in this process, there are a few things:

1. All the nodes go into a "changed" state, until all nodes have been changed.
2. Somehow it figures out that all nodes that will be changed have been changed. This allows it to go back into the "unchanged" state.

This graph is pretty simplified because in reality there could be many complicated cycles and many more bindings per node.

However, given that the arrows indicate the direction in this Directed Cyclic Graph, I am wondering how this algorithm can efficiently perform this update propagation.

The naïve approach would iterate through all of the nodes that have changed each step, to see if there is anything left to change. Maybe there is a third state, "changed and no more propagation". Once everything is in that third state (by checking every node every step), then it would be done. Wondering if there is an efficient way to accomplish this, so it doesn't need to iterate through every node each step somehow.

Also, it is possible that multiple values are changed at once, so it should be able to handle that as well, i.e.:

 ●くろまる
 ↓
●くろまる → ●くろまる → ●くろまる → ●くろまる ●くろまる ← ◌
 ↑ ↑ ↓
 ◌ → ●くろまる → ●くろまる ← ●くろまる → ●くろまる
 ↓ ↓ ↑
 ●くろまる ●くろまる → ●くろまる ← ●くろまる
 ↓ ↓
 ●くろまる ◌
 ↑
 ●くろまる

Answer 1

This is either fundamentally meaningless or you've left out an important detail.

Your diagrams give each node 3 states:

●くろまる Unchanged, don't propagate
◌ Just now changed and in need of propagation
○しろまる Old change, don't propagate

But in the end it all goes back to ●くろまる unchanged. So nothing is learned.

Which makes me think it's not really the same state as we started. It's just considered the same as far as propagation is concerned.

Which means that ●くろまる and ○しろまる are really the same state: don't propagate.

But you've chosen to give us a 4th state ☀ recent update which gets destroyed in this example.

All of which adds up to me thinking your symbols are just messed up.

Try it like this:

 0
 ↓
0 → 0 → 0 → 0 0 ← 0
 ↑ ↑ ↓
 0 → 0 → 0 ← 0 → 0
 ↓ ↓ ↑
 0 0 → 0 ← 0
 ↓ ↓
 0 0
 ↑
 0

And then we change one field.

 0
 ↓
0 → 0 → 0 → 0 0 ← 0
 ↑ ↑ ↓
 1 → 0 → 0 ← 0 → 0
 ↓ ↓ ↑
 0 0 → 0 ← 0
 ↓ ↓
 0 0
 ↑
 0

Then it propagates:

 0
 ↓
0 → 0 → 1 → 0 0 ← 0
 ↑ ↑ ↓
 1 → 1 → 0 ← 0 → 0
 ↓ ↓ ↑
 1 0 → 0 ← 0
 ↓ ↓
 0 0
 ↑
 0

More...

 0
 ↓
0 → 0 → 1 → 1 0 ← 0
 ↑ ↑ ↓
 1 → 1 → 1 ← 0 → 0
 ↓ ↓ ↑
 1 0 → 0 ← 0
 ↓ ↓
 0 0
 ↑
 0

...

 0
 ↓
0 → 0 → 1 → 1 1 ← 0
 ↑ ↑ ↓
 1 → 1 → 1 ← 0 → 0
 ↓ ↓ ↑
 1 1 → 0 ← 0
 ↓ ↓
 0 0
 ↑
 0

 0
 ↓
0 → 0 → 1 → 1 1 ← 0
 ↑ ↑ ↓
 1 → 1 → 1 ← 0 → 0
 ↓ ↓ ↑
 1 1 → 1 ← 0
 ↓ ↓
 1 0
 ↑
 0

 0
 ↓
0 → 0 → 1 → 1 1 ← 0
 ↑ ↑ ↓
 1 → 1 → 1 ← 1 → 0
 ↓ ↓ ↑
 1 1 → 1 ← 0
 ↓ ↓
 1 1
 ↑
 0

Sometimes it encounters a recent update, as shown with 2.

 0
 ↓
0 → 0 → 1 → 1 1 ← 0
 ↑ ↑ ↓
 1 → 1 → 1 ← 2 → 1
 ↓ ↓ ↑
 1 1 → 1 ← 0
 ↓ ↓
 1 1
 ↑
 0

But it keeps going:

 0
 ↓
0 → 0 → 1 → 1 1 ← 0
 ↑ ↑ ↓
 1 → 1 → 2 ← 2 → 2
 ↓ ↓ ↑
 1 1 → 1 ← 0
 ↓ ↓
 1 1
 ↑
 0

And eventually both updates spread as far as they can

 0
 ↓
0 → 0 → 1 → 1 2 ← 0
 ↑ ↑ ↓
 1 → 1 → 2 ← 2 → 2
 ↓ ↓ ↑
 1 2 → 2 ← 0
 ↓ ↓
 2 2
 ↑
 0

Now it has had no more changes, so it does nothing.

 0
 ↓
0 → 0 → 1 → 1 2 ← 0
 ↑ ↑ ↓
 1 → 1 → 2 ← 2 → 2
 ↓ ↓ ↑
 1 2 → 2 ← 0
 ↓ ↓
 2 2
 ↑
 0

So the only thing you have to check to determine if you should propagate is which update is the most recent.

enter image description here

Also, it is possible that multiple values are changed at once, so it should be able to handle that as well, i.e

 0
 ↓
0 → 0 → 0 → 0 0 ← 1b
 ↑ ↑ ↓
 1a→ 0 → 0 ← 0 → 0
 ↓ ↓ ↑
 0 0 → 0 ← 0
 ↓ ↓
 0 1c
 ↑
 0

It can handle this but you've created a non deterministic race. Some final values will be determined not by the data but by processing order. There is no algorithm to fix this. Once you decide that all three updates "changed at once" they all have equal validity.

 0
 ↓
0 → 0 → 1a→ 1a 1b← 1b
 ↑ ↑ ↓
 1a→ 1a→ 1?← 1b→ 1b
 ↓ ↓ ↑
 0 1?→ 1?← 0
 ↓ ↓
 1? 1c
 ↑
 0

And this situation pokes a hole in DFS because you can't emulate real propagation, in this situation, that way. Propagation happens breadth first.

So if you want to handle distributed updates you need some way to put them in order and decide which one wins, unless you don't mind letting them race for it.

• Lance Pollard: The symbols I was using was more of a visual animation then actual states, but probably should've mentioned that. Thank you for pointing out the race condition, I totally missed that. I have no idea what to do there, hmm...
• candied_orange: @LancePollard I suspected something like that but really can't see a way to say something useful using it. So I changed the symbols.
• Lance Pollard: It goes back to the unchanged state because I assumed that, once all the values have been updated, you want to treat it as if it is in a brand new fresh state, so it can receive the next batch of updates. Also, it doesn't need to necessarily propagate the way I showed, if DFS is better, I wasn't too particular about that.
• candied_orange: @LancePollard I get that but it hides what's going on. I used symbols that make what happens brutally clear.
• Lance Pollard: Makes sense, I like it.