r - 查找 DAG 中节点值的累积和

Question

假设我有以下有向无环图 (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 package 创建于 2021-05-13 (v2.0.0)}

可以看到，D的累加和结果是3而不是4，因为D的值应该是A和B的累加值之和，不明白为什么D不加4

我试图理解给出的解决方案 here , 但很难理解它

如何获取累计金额？

更新#1

我(暂时)不关心算法的复杂性，也就是说，如果算法在 O(V + E) 内执行它是不相关的。

this 中提到的重要内容问题是关于两次计数的问题，即A的值的部分和等于C(1) + A(1) = 2，B的值的部分和等于C(1 ) + B (1) = 2，所以说 D 的值不等于 A (2) + B(2) 的部分和，因为 C 的值会重复 我认为它不适用于此原因如下:

假设这 4 个节点(A、B、C 和 D)中的每一个都是互联网节点，每个节点产生 1 美元的收入，因此这 4 个节点的总累计收入为 4 美元。如果D是其余节点的汇聚节点，那么在D停止工作的场景下，其余节点的 yield 和D的 yield 将不再可能，因此其值为$4。

更新#2

如果我添加一条从 C 到 D 的新路径，那么 D 的值应该始终为 4，因为依赖节点的数量保持不变，也就是说，重要的是累加和中依赖节点的数量。例如，在@ThomasIsCoding 提出的解决方案中，如果我添加这条新路径，D 的值现在为 5，我认为部分原因是他们的算法使用度数作为参数来计算累积和，但是，如果我添加一个附加节点则计算正确。

更新 #3

我放置的示例很简单，目的是易于理解目标，但是，我没有指定它应该可以推广到具有三种不同拓扑的许多节点的图形。最外层是树，中间层是环，最内层是全网格。

Answer 1

这是一个 igraph 选项，使用 distance 和参数 mode = "in"

• 如果您的节点未加权，即所有节点的 revenue=1

g <- graph_from_data_frame(grafo_df)

data.frame(name = names(V(g))) %>%
  mutate(revenue = 1) %>%
  mutate(cum_weight = rowSums((!is.infinite(distances(g, mode = "in"))) %*% diag(revenue)))

这给了你

  name revenue cum_weight
1    C       1          1
2    A       1          3
3    B       1          2
4    F       1          1
5    D       1          5

• 如果你的节点是加权的，例如，

data.frame(name = names(V(g))) %>%
  mutate(revenue = 1:n()) %>%
  mutate(cum_weight = rowSums((!is.infinite(distances(g, mode = "in"))) %*% diag(revenue)))

这给了你

  name revenue cum_weight
1    C       1          1
2    A       2          7
3    B       3          4
4    F       4          4
5    D       5         15

---

数据

grafo_df <- tribble(
  ~from, ~to,
  "C", "A",
  "C", "B",
  "A", "D",
  "C", "D",
  "B", "D",
  "F", "A"
)

plot(g) 给出的 DAG 为