Graphical algorithm for calculating node values ​​based on neighboring nodes

Question

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

• The schedule is directed.
• Each node has an initial value of f (n).
• Each edge has no cost (0).
• The value of each node is its maximum current value, and the value of each neighboring node (oriented graph, so the neighbors are those 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 imagine several ways to do this, but I do not know to what extent they are optimal.

Can anyone give suggestions and comments (how do you think your proposal is optimal) or suggest any existing graph algorithm that I can adapt?

Answer 1

Requirements:

• In each Strongly connected component V on the graph, the values ​​of all the vertices in this SCC have the same final estimate,
  "Proof" (recommendation): by using propogation in this SCC, you can iteratively set all points to the maximum value found in this SCC.

• In DAG, the value of each vertex is max{v,parent(v) | for all parents of v} max{v,parent(v) | for all parents of v} (definition), and the score can be found within one iteration from start to finish.
  "Proof" (recommendation): there are no "trailing edges", so if you know the final values ​​of all the parents, you know the final value of each vertex. By induction (base - all sources) - you can understand that one iteration is enough to determine the final result.

• It is also known that graph G' representing SCC graph g is a DAG.

From the above, you can get a simple algorithm :

• Maximum SCC Fing in the graphs (can be done using the Tarjan algorithm ) and create an SCC graph. Let it be G' . Note that G' is a DAG.
• For each SCC V : set f'(V) = max{v | v in V} f'(V) = max{v | v in V} (intuitively - set the value of each SCC as the maximum value in this SCC).
• Topological sorting in column G' .
• Make one round according to the topological type found in (3), and calculate f '(V) for each vertex in G' according to its parents.
• Set f(v) = f'(V) (where v is in SCC V)

Complexity:

• Tarjan and the creation of G' - O(V+E)
• Search f 'is also linear in the size of the graph - O(V+E)
• Topological sorting is done in O(V+E)
• Single Bypass - Linear: O(V+E)
• Give the final results: linear!

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