4
$\begingroup$

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

Here is the final graph that we are getting.

Final Graph

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Cool, looks good! I don't think you should delete your answer. $\endgroup$ – D.W. Feb 21 '17 at 16:51
1
$\begingroup$

If the original value of count is 1 in every node, then this is the problem of counting the number of successors of each node in a dag. That problem is discussed in https://cstheory.stackexchange.com/q/553/5038, which cites the best algorithms known for this problem. For sparse graphs, it is hard to do much better than running DFS separately from each vertex, which has running time approximately $O(VE)$. For dense graphs, you can build an algorithm whose running time is $O(V^\omega)$, where $\omega$ is the exponent for fast matrix multiplication ($\omega \approx 2.8$ in practice).

If the original value of the counts can be different from 1, then your problem is https://cstheory.stackexchange.com/q/736/5038, which discusses the best running times known, and even mentions an approximation algorithm you could consider.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.