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?

Ratha

Do you need an online algorithm? – Digester

@Rishav Yes, the operations will be repeated again and again. – Ratha

Why increaseThreshold has to propagate? It may update t[i] but why it influences other nodes? – Retrospect

What is the number of nodes you are looking to potentially deal with? – Digester

@Retrospect Thanks, fixed, it was a "mental typo". – Ratha

@Rishav Maybe tens of thousands with maybe ten arrows per node. – Ratha

@Ratha Why do you consider your lazy approach inefficient? It makes evaluate(i) longer but increaseValue is very fast. When you're doing evaluate(i) you could also do kind of propagation but considering only those nodes with w[i] != v[i] and updating v[i] simultaneously. In this scenario the second call for evaluate(i) with the same argument will work almost instantly (with no increaseValue calls in between). – Retrospect

@Retrospect Each evaluate has to look at each node from which there's a path and this may be a substantial portion of the graph. When the values don't get propagated immediately, then you know nothing about what may have changed and you must inspect a lot of nodes. – Ratha

@Ratha ah, you're right it's not enough to consider nodes with w[i] != v[i] only – Retrospect

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. – Goldbrick

@MattTimmermans Thanks, fixed (it's sad that I've made so many mistakes in such a short post). – Ratha

How do your determine the nodes that have a path to n[j] in eval in the lazy approach? Is that something that could be optimized? – Esteresterase

@StefanHaustein I guess, no. I can store the outgoing and/or the incoming arrows with each node as needed. In the lazy approach, I'd do a depth-first search with tracking of already visited nodes. That's simple and efficient, except for the fact that there are too many nodes. – Ratha

Is Threshold also increasing? – Suppletion

@LuaiGhunim Sure, the only operation modifying it is increaseThreshold. It gets never smaller, but unlike the value, there's no relation between thresholds of connected nodes. – Ratha

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

Esteresterase

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). – Ratha

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.

Ratha