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?

Answer 1

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)?

Answer 2

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.