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.

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.