在有向无环图中找到节点值的累计和

Question

在有向无环图中找到节点值的累计和

3

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

正如您所见，D的累加和为3而不是4，因为D的值应该是A和B的累加值之和。我不明白为什么D没有增加4。

我试图理解这里给出的解决方案，但很难理解。

我该如何得到累计总和？

更新＃1

目前我不关心算法的复杂度，即使算法以O（V + E）完成也不相关。

这个问题中提到的一个重要问题是重复计数的问题，也就是说，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停止工作的情况下，剩余节点的收入和D的收入将不再可能，因此其价值为4美元。

更新 #2

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

更新＃3

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

- William

如何使节点A的累积总和为2？难道不应该是1吗？ - Onyambu

1

据我理解，D 应该是 5，而不是 4，4 只是祖先节点的总和，不包括节点值。 - Rocco

@Onyambu。因为它是累加和，当通过map_dfs应用sum函数时，A的值加上其祖先的值。一开始所有值都为1。当我们开始迭代计算累加和时，A的值将是A当前的值加上其祖先的值，这种情况下是C，因此1 + 1 = 2。 - William

@Rocco。应该值4的情景或背景如下：假设这4个节点是收入产生站点（在这种情况下，假设它们每个生成1美元）。正如您所看到的，节点C、B和A都依赖于D的工作，因为所有的“流量”都通过D。如果D崩溃或停止工作会发生什么？那么，我们将损失4美元的收入，这将是C、A、B和D所产生的收入。在这种假设下，D的价值或累积总和应为4。 - William

@j_random_hacker 是的。 - William

显示剩余5条评论

2个回答

0

现在问题已经清楚了，我提出了一种算法，但是我无法编写它，因为我不知道你使用的编程语言。

对于图中的每个节点Ni，我们将计算祖先集合Ai，然后每个节点的累积和将为| Ai | +1。

使用空祖先集合Ai = {}初始化所有节点
从包含没有传入边的所有节点的集合S0开始
初始化下一个集合Sn + 1
遍历Sn，对于每个节点N：
对于从N传入的所有节点D：
1. 将D的祖先集合与N的祖先集合加上N本身进行合并
2. 删除边缘N-> D
如果D没有其他传入边缘，则将其添加到Sn + 1
如果Sn + 1不为空，请增加通过n + 1，并从2重复。

这种解决方案的最大限制是复杂性，我稍后会尝试找到一些优化的解决方案。

- Rocco

我会尝试将您的算法翻译成代码。 - William

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ThomasIsCoding · Accepted Answer

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

如果您的节点未加权，即所有节点的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)))

which gives you

  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)))

which gives you

  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如下：

"