如何从图中求出一个结点到一个结点的边权和 [英] How to get the sum of edge weight from a node to a node from a graph

问题描述

我们可以使用igraph包的strength函数对每个顶点的相邻边的边权重进行求和。假设我们有一个如下图

可复制的数据和代码

nodeA <- c("ID_1", "ID_2", "ID_3", "ID_4", "ID_5", "ID_16", "Node_30")
nodeB <- c("ID_11", "ID_3", "ID_4", "ID_5", "ID_3", "ID_11", "Node_3")
edge_weight <- c(0.5, 0.9, 0.8, 0.7, 0.5, 0.09, 0.7)
df_1 <- data.frame(nodeA, nodeB, edge_weight)

graph1 <- graph_from_data_frame(df_1, directed = FALSE)
E(graph2)$weight <- df_1$edge_weight
plot(graph1)

edge_strengts <- strength(graph1)

我从strength函数获得的输出是图形每个顶点的边权重之和。

 ID_1    ID_2    ID_3    ID_4    ID_5   ID_16 Node_30   ID_11  Node_3 
   0.50    0.90    2.20    1.50    1.20    0.09    0.70    0.59    0.70

现在，我有一个边列表，我只想得到这些列表的边权重之和(而不是一个顶点的边之和)。为了获得更多澄清，假设我有给定的边缘列表

         nodeA      nodeB 
1        ID_2       ID_4  
2        ID_2       ID_5 
3        ID_1       ID_16 

我只想从给定图中获得上面列出的边的总和(请注意，该图是无向的)。输出应如下所示

         nodeA      nodeB    some_of_weight
1        ID_2       ID_4     1.70
2        ID_2       ID_5     1.40
3        ID_1       ID_16    0.59

对于第一条边(ID_2 to ID_4)，求和是1.70(例如：ID_2到ID_3=0.9，ID_3到ID_4=0.8，因此，0.9+0.8=1.70)，依此类推。

你能告诉我，我怎样才能做这份工作吗？

一条边有多条路径

图可以包含边的多条路径(即，对于一条边，我们可以有一条或多条不同的路径)。比方说，我们可以通过两种方式：(I)ID_3--ID_2--ID_4(总路径权重为2.4)和(Ii)ID_3--ID_5--ID_4(总路径权重为1.5)。在这种情况下，我希望采用最大路径权重。

多个路径的可复制数据

nodeA <- c("ID_1", "ID_2",  "ID_4", "ID_5", "ID_16", "Node_30", "ID_6", "ID_2")
nodeB <- c("ID_11", "ID_3",  "ID_5", "ID_3", "ID_11", "Node_3", "ID_3", "ID_4")
edge_weight <- c(0.5, 0.9, 0.8, 0.7, 0.5, 0.09, 0.7, 1.5)

推荐答案

更新

由于您正在寻找两个顶点之间的最长路径，您可以尝试下面的代码

df_2$max_sum_weight <- apply(
  df_2,
  1,
  function(x) {
    max(sapply(
      all_simple_paths(graph1, x[["v"]], x[["to"]]),
      function(v) {
        sum(E(graph1)$weight[get.edge.ids(graph1, c(rbind(head(v, -1), v[-1])))])
      }
    ))
  }
)

这给了

> df_2
     v    to max_sum_weight
1 ID_2  ID_4            2.4
2 ID_2  ID_5            2.3
3 ID_1 ID_16            1.0
4 ID_3  ID_4            2.4

数据

df_2 <- data.frame(
  v = c("ID_2", "ID_2", "ID_1", "ID_3"),
  to = c("ID_4", "ID_5", "ID_16", "ID_4")
)

上一个答案(最短路径)

---

尝试shortest.paths

transform(
  df_2,
  sum_of_weight = diag(shortest.paths(graph1, v, to))
)

或

transform(
  df_2,
  sum_of_weight = shortest.paths(graph1)[as.matrix(df_2)]
)

这给了

     v    to sum_of_weight
1 ID_2  ID_4          1.70
2 ID_2  ID_5          1.40
3 ID_1 ID_16          0.59

这篇关于如何从图中求出一个结点到一个结点的边权和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！