Counting the nodes of a unidirectional graph

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.

Example

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.

Example

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) - 2Count(id:1) = 1 + 2 + 2 +2 - 21 = 5$

Here is the final graph that we are getting.

Another example:

$ Count(id:7) = Count(id:7) + Count(id:5) + Count(id:6) - Count(id:4) = 5 + 3 - 2 +1 = 7 $

Problem

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.

You can build a graph $G'=(V,E')$ that comprises the same set of vertices $V$ from the input graph $G=(V,E)$ and whose set of edges $E'$ includes an edge $(v,u)$ for every edge $(u,v) \in E$. That is, $G'$ is the same graph as $G$, but with the edges reversed; therefore, $G'$ is also topologically sorted (in the same way as $G$, but in the opposite direction). You are looking for the number of successors (+1) of every vertex in $G'$. This can be found using depth-first search, starting a new traversal from every vertex and counting the nodes that you find. The running time of this algorithm is $O(mn)$, where $n$ is the number of vertices of the graph and $m$ is the number of edges. D.W.'s answer provides some useful links with approaches with slightly better running times.

StackExchange Computer Science Q#70416, answer score: 2