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.

  • Sounds like you've already thought out the relevant issues. – Robert Harvey Jun 23 '18 at 2:56
  • But maybe someone has already solved it which is what I was hoping. – Lance Pollard Jun 23 '18 at 2: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 8:23
  • This might be relevant - stackoverflow.com/questions/314943/… – Peeyush Kushwaha Jun 24 '18 at 8:31
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

  • 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) that triggers updates in the optimal order. This also makes it easy to debounce events. – amon Jun 24 '18 at 12:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.