假设我有以下有向无环图 (DAG)，每个节点的权重为 1。
我有兴趣根据其祖先的值计算每个节点的累积总和。假设如我之前所说，每个节点的权重为 1，那么这就是我期望得到的
这就是我试图做的：
library(tidygraph, quietly = TRUE)
library(tidyverse)
library(ggraph)
# create adjacencies
grafo_df <- tribble(
~from, ~to,
"C", "A",
"C", "B",
"A", "D",
"B", "D")
# create the graph
grafo <- as_tbl_graph(grafo_df)
# calculate accumulated sum
grafo %>%
arrange(node_topo_order()) %>%
mutate(
revenue = 1,
cum_weight = map_dfs(1, .f = function(node, path, ...) {
sum(.N()$revenue[c(node, path$node)])
})) %>%
as_tibble() %>%
unnest("cum_weight")
#> # A tibble: 4 x 3
#> name revenue cum_weight
#> <chr> <dbl> <dbl>
#> 1 C 1 1
#> 2 A 1 2
#> 3 B 1 2
#> 4 D 1 3
由reprex 包于 2021-05-13 创建 (v2.0.0 )
可以看到，D的累加和结果是3而不是4，因为D的值应该是A和B的累加值之和。我不明白为什么D不加4
我试图理解这里给出的解决方案，但很难理解它
我怎样才能得到累积的金额？
更新#1
我（暂时）不关心算法的复杂性，也就是说，如果算法在 O(V + E) 中执行它，它是不相关的。
这个问题中提到的一个重要的事情是关于两次计数的问题，即A的值的部分和等于C(1) + A(1) = 2，而A的值的部分和B 等于 C(1) + B (1) = 2，所以说 D 的值不等于 A (2) + B(2) 的部分和，因为 C 的值将重复 I认为它不适用于这种情况，原因如下：
假设这 4 个节点（A、B、C 和 D）中的每一个都是互联网节点，每个节点产生 1 美元的收入，因此 4 个节点的总累计收入为 4 美元。如果 D 是其余节点的收敛节点，那么在 D 停止工作的情况下，其余节点和 D 的收益将不再可能，因此，它的价值是 4 美元。
更新#2
如果我添加从 C 到 D 的新路径，则 D 的值应该始终为 4，因为依赖节点的数量保持不变，也就是说，重要的是累加和中依赖节点的数量。例如，在@ThomasIsCoding 提出的解决方案中，如果我添加这个新路径，D 的值现在是 5，我认为部分原因是他们的算法使用度数作为参数来计算累积和，但是，如果我添加一个附加节点，则计算正确。
更新#3
我放置的示例很简单，目的是易于理解目标，但是，我没有指定它应该适用于具有许多具有三种不同拓扑结构的节点的图。最外层是树，中间层是环，最内层是全网格。
