Graph algorithm to compute node values based on neighbouring nodes

Question

I would like to make a graph algorithm that updates/computes the value of a node f(n) as a function of each of the f(n) values of neighboring nodes.

• The graph is directed.
• Each node has as initial f(n) value.
• Each edge has NO cost (0).
• The value of each node is the maximum of its current value and the value of each neighboring nodes (directed graph, so neighbors are the ones from where the node has incoming edges).

More formally,

f(n) = max(f(n),max_i(f(n_i))), where i from neighbor 1 to neighbor k.

I can visualize a few ways of doing so, however I do not know to what extend they are optimal.

Can anyone please give suggestions and commentaries (whether do you think your suggestion is optimal) or suggest any existent graph algorithm I can adapt?

Answer 1

Claims:

1. In each Strongly Connected Component V in the graph, the values of all vertices in this SCC have the same final score.
   "Proof" (guideline): by doing propogation in this SCC, you can iteratively set all the scores to the maximal value found in this SCC.

2. In a DAG, the value of each vertex is max{v,parent(v) | for all parents of v} (definition) and the score can be found within a single iteration from the start to the end.
   "Proof" (guideline): There are no "back edges", so if you know the final values of all parents, you know the final value of each vertex. By induction (base is all sources) - you can get to the fact that a single iteration is enough to determine the final score.

3. Also, it is known that the graph G' representing the SCC of a graph g is a DAG.

From the above we can derive a simple algorithm:

1. Fing maximal SCCs in the graphs (can be done with Tarjan algorithm), and create the SCC graph. Let it be G'. Note that G' is a DAG.
2. For each SCC V: set f'(V) = max{v | v in V} (intuitively - set the value of each SCC as the max value in this SCC).
3. Topological sort the graph G'.
4. Do a single traversal according to the topological sort found in (3) - and calculate the f'(V) for each vertex in G' according to its parents.
5. Set f(v) = f'(V) (where v is in the SCC V)

Complexity:

1. Tarjan and creating G' is O(V+E)
2. Finding f' is also linear in the size of the graph - O(V+E)
3. Topological sort runs in O(V+E)
4. Single traversal - linear: O(V+E)
5. Giving final scores: linear!

So the above algorithm is linear in the size of the graph - O(V+E)