python - 计算有向图中的累积流量

Question

我有一个以点“L”结束的有向图。当我将“L”点处的所有传入度数相加时，得到的值是:13。但我想根据给定的图修改图形(见图)。在图中，传入的度将分布在以下节点中。例如，点“F”的传入度为 2，因此“F”的值为 2。但对于点“K”和“G”，该值将是 0.5 和 0.5，因为“的值H”分为两部分。点“J”的值将是来自上层节点(即G、E、F)的传入值的总和。

需要 R 或 python 中的解决方案。

这是我使用的示例代码...

library(igraph)
library(dplyr)
g1<- graph (edges = c("A","E", "E","I", "I","L", "E","J", "J","L", 
"B","F", "C","F", "F","J", "D","H", "H","K", "H","G", "G","J", "K","L"), 
directed = T)
cum_deg <- data.frame(name=names(V(g1))) %>%
        mutate(deg_1=degree(g1, mode="in")) %>%
        mutate(cum_degree = rowSums 
        ((!is.infinite(distances(g1,mode="in"))) %*% diag (deg_1)))

        > cum_deg
         name deg_1 cum_degree
         A     0          0
         B     0          0
         C     0          0
         D     0          0
         E     1          1
         F     2          2
         G     1          2
         H     1          1
         I     1          2
         J     3          8
         K     1          2
         L     3         13

Answer 1

一种可能的解决方案是使用all_simple_paths“分割”图形，然后使用累积权重聚合路径，例如，

# all source vertices
vs <- V(g1)[degree(g1, mode = "in") == 0]
# all sink vertices
vt <- V(g1)[degree(g1, mode = "out") == 0]
# cumulative weights along each simple path
df <- do.call(
    rbind,
    lapply(
        unlist(sapply(
            vs,
            function(x) all_simple_paths(g1, x, vt)
        ),
        recursive = FALSE
        ),
        function(s) {
            stack(
                replace(
                    cumprod(
                        replace(
                            1 / degree(g1, s, mode = "out"),
                            length(s),
                            1
                        )
                    ),
                    1,
                    0
                )
            )
        }
    )
)
# aggregate weights
out <- rev(stack(xtabs(df)[order(names(V(g1)))]))

给出

> out
   ind values
1    A    0.0
2    B    0.0
3    C    0.0
4    D    0.0
5    E    1.0
6    F    2.0
7    G    0.5
8    H    1.0
9    I    0.5
10   J    3.0
11   K    0.5
12   L    4.0