Suppose that we have the above graph. The graph is directed and is unidirectional; that is, we can only traverse it from top to bottom.
We want to update the count of the nodes such that the count of any given node indicates the sum of the count of the node itself and the previous nodes, avoiding any duplicate nodes.
For $ id:5 $ the count will be the sum of counts of $id:1,2,3,4$. So, the count will be calculated as $Count(id:5) = \sum Count(ancestors) + selfCount$.
So, the $Count(id:5) = 5$ in this case.
Implementation that has been thought of
One such implementation could be traversal from top to bottom, and updating the count levelwise (breadth-first search).
We could then add the count of previous nodes, and subtract the count of the LCA(Least Common Ancestor) node.
So, if we have to find the count of node $id:5$, we would get the following count:
$ Count(id:5) = Count(id:5) + Count(id:2) + Count(id:3) + Count(id:4) - 2*Count(id:1) = 1 + 2 + 2 +2 - 2*1 = 5$
Here is the final graph that we are getting.
$ Count(id:7) = Count(id:7) + Count(id:5) + Count(id:6) - Count(id:4) = 5 + 3 - 2 +1 = 7 $
How do we remember the counts of ancestor nodes, when we are analyzing the counts of the current nodes?
It could be possible that the ancestor might not be immediately present, it could be far away at previous levels also.
Is there any algorithm that could solve the problem? I would really appreciate the help.