Graph value propagation algorithm

Question

I've got a directed graph (N, A), where each node n[i] has a value v[i] and a threshold t[i]. For each arrow (n[i], n[j]), the invariant v[i] <= v[j] holds. I need to efficiently implement the following operations:

increaseThreshold(i, x): Set t[i] = max(t[i], x). That's trivial and only for completeness here.
increaseValue(i, x): Set v[i] = max(v[i], x) and increase other values as needed so that the above invariant holds.
evaluate(i): return true if v[i] < t[i]

The most straightforward implementation would store v[i], t[i], and the outgoing arrows with each node. On increaseValue(i, x), it'd propagate the value along all outgoing arrows (using a set of "open" nodes like many other graph algorithms do). With v[i] stored with each node, evaluate(i) is trivial.

As increaseValue is much more frequent than the other operations, this eager approach seems to be wasteful. So I wonder, if some lazy propagation where v[i] is recomputed as needed could be more efficient. For this, I'd maintain w[i] as the maximum of all x from increaseValue(i, x) and compute v[j] on the fly when evaluate(j) needs it. It can be computed as the maximum of w[i] over all nodes n[i] from which there's a path to n[j]. Actually, once I know that v[j] >= t[j], the exact value v[j] doesn't matter and I can stop the computation.

Unfortunately, this lazy algorithm is very inefficient, so it doesn't pay off even with increaseValue being orders of magnitude more frequent than evaluate.

I imagine, some "partially lazy" algorithm could be better, but that's just my intuition and I can't make any progress with it.

Is this somehow a well-known problem? Any other idea?

@Rishav Yes, the operations will be repeated again and again. — maaartinus
– maaartinus, Commented Sep 10, 2017 at 21:36
Why increaseThreshold has to propagate? It may update t[i] but why it influences other nodes? — algrid
– algrid, Commented Sep 10, 2017 at 21:42
What is the number of nodes you are looking to potentially deal with? — xrisk
– xrisk, Commented Sep 10, 2017 at 21:51
You said that an edge n[i] -> n[j] means that v[i] >= v[j]. Shouldn't that be v[j] >= v[i]? Otherwise I don't understand the propagation. — Matt Timmermans
– Matt Timmermans, Commented Sep 11, 2017 at 2:20

Stefan Haustein · Accepted Answer · 2017-11-11 15:55:20Z

3

+50

How about holding back the propagating of the increment until you need to evaluate? increaseValue would only update the value, mark the node as dirty and add it to a set of dirty nodes.

When you need to evaluate, propagate the increments for all changed nodes, starting with the largest new value. This should save propagating multiple increments for the same node and potentially nodes on paths (which might get validated on the go)?

edited Nov 11, 2017 at 15:55

answered Nov 11, 2017 at 15:44

Stefan Haustein

18.9k3 gold badges40 silver badges54 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

maaartinus Over a year ago

Nice! That's surely a good idea and simple to implement. It can be slightly refined by stopping when the value is smaller than the interesting threshold. This way the total amount of work is minimized. +++ It's pretty flexible: A background thread could poll the priority queue so that evaluate would not be slowed down by all the work (worsening the total amount of work but improving latency).

maaartinus · Accepted Answer · 2017-11-18 13:23:34Z

I've got a simple idea for the "partially lazy" algorithm (no solution, just an idea).

Let's call the "most straightforward implementation" from my question the telling algorithm as each node tells its successors what to do. Let's rename the "lazy algorithm" to asking algorithm as each node asks its predecessors if there's something to do.

The arrows can be partitioned into telling and asking ones. All the telling arrows get processed after increase, while the asking arrows wait until evaluate. I guess, this partitioning can't be arbitrary: For any two arrows (n[i], n[j]) and (n[j], n[k]), I can't imagine how to process when the former is asking and the latter is telling, so this case must be forbidden.

This may help a lot when there are many nodes with only incoming arrows which gets evaluated rarely, which seems to be the case.

It can be probably combined with the idea from the other answer.

Collectives™ on Stack Overflow

Graph value propagation algorithm

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related