0

Wondering if there is anything closely resembling data-binding but for boolean values / triggers. It seems like it could be related to Binary Decision Diagrams (BDDs), but they are precomputed rather than dynamic I think.

Say you have 100 or 1000 boolean variables all inter-related in a graph. And one of them changes. The simplest thing is to then just recompute all 1000 values. But it might be more optimal to instead follow the trail from the changed node to the things depending on it. But then again it might lead to a long chase where you have to prevent against re-updating the same boolean more than once, so you could end up with more than 1000 operations.

Wondering if there is anything done on this topic. How to optimally update boolean values that depend on each other in a complex graph.

Lance
  • 2,537
  • 15
  • 34
  • Sounds like you've already thought out the relevant issues. – Robert Harvey Jun 23 '18 at 02:56
  • But maybe someone has already solved it which is what I was hoping. – Lance Jun 23 '18 at 02:57
  • 2
    Seems this has not much to do with boolean values, more like graph traversal algorithms for directed graphs. That is a whole field of research, it probably fills whole book shelves, way too broad to be answered here in this generality. Can't you make your question more focussed? For example, if you have a real problem to solve, for a real program, not just some vague idea about a theoretical issue, describe the problem and you can probably get an answer here. – Doc Brown Jun 23 '18 at 08:23
  • This might be relevant - https://stackoverflow.com/questions/314943/what-algorithm-does-excel-use-to-recalculate-formulas – Peeyush Kushwaha Jun 24 '18 at 08:31

1 Answers1

1

Here's what I'm able to understand from your question:

You have a set S of boolean variables and a dependency graph G. If one of the variables X in S changes you want to recompute only other variables in S depending on X, and in a way that you don't recompute the same variable twice because what it depended on changed again.

Solution: You could use DFS and Topological Sorting to manage this.

Suppose you have variables A, B, C and D with edges as

B -> A // i.e. A depends on B
D -> B // i.e. B depends on D

If you have the direction of the edges other way around, you can always reverse them.

So if you change D, you want to update both B and A but not C.

You can do a DFS traversal starting at D and just find every node reachable from D (i.e. anything that directly or indirectly depends on D). Shortlist these variables, anything apart from these will not be updated.

Now topologically sort everything you shortlisted. In this way, everything which some variable X depends on will be updated before you recompute X.

In this way your number of computations will never exceed the number of variables you have

Peeyush Kushwaha
  • 665
  • 3
  • 15
  • 1
    In the context of data binding, this means that simply using Observable values or callbacks is insufficient. Instead, we need a central dependency solver (sometimes called the [Reactor](https://en.wikipedia.org/wiki/Reactor_pattern)) that triggers updates in the optimal order. This also makes it easy to debounce events. – amon Jun 24 '18 at 12:13