如何限制igraph/R中的最短路径数
How to limit the number of shortest path in igraph/R
使用 shortest.paths
函数,我们从图中得到最短路径。现在,我想限制最短路径的长度。
例如,当我运行下面的代码时,我得到了从一个顶点到任何顶点的所有最短路径。
df <- read.csv("~/data.csv")
g1 <- df
graph1 <- graph_from_data_frame(g1, directed = FALSE)
plot(graph1, vertex.label = V(graph1)$name)
mat <- shortest.paths(graph1)
我得到的输出
ID_1 ID_2 ID_3 ID_4 ID_8 ID_5 ID_7 ID_100
ID_1 0 1 1 1 Inf 2 2 Inf
ID_2 1 0 2 1 Inf 1 2 Inf
ID_3 1 2 0 2 Inf 3 1 Inf
ID_4 1 1 2 0 Inf 2 1 Inf
ID_8 Inf Inf Inf Inf 0 Inf Inf 1
ID_5 2 1 3 2 Inf 0 3 Inf
ID_7 2 2 1 1 Inf 3 0 Inf
ID_100 Inf Inf Inf Inf 1 Inf Inf 0
但是,我只想保留(比如说)路径长度为 3,另一个为 0 or Inf
。实际上,除了(路径长度=3)之外我不需要其他的。
而且,我要的sum of the path weight
不仅是路径数。我以为我可以只改变一行就可以做到这一点
mat <- shortest.paths(graph1, weights=E(graph1)$weight)
但是,如何限制路径长度呢?
可重现的数据
structure(list(nodeA = structure(c(1L, 1L, 1L, 2L, 2L, 3L, 4L,
5L), .Label = c("ID_1", "ID_2", "ID_3", "ID_4", "ID_8"), class = "factor"),
nodeB = structure(c(2L, 3L, 4L, 5L, 4L, 6L, 6L, 1L), .Label = c("ID_100",
"ID_2", "ID_3", "ID_4", "ID_5", "ID_7"), class = "factor"),
weight = c(0.5, 0.77, 0.5, 0.9, 0.44, 0.32, 0.45, 0.543)), class = "data.frame", row.names = c(NA,
-8L))
运行shortest.path
根据你提供的数据returns直接对所有节点组合求最短路径(路径权值之和的最小值)
g1 <- structure(list(nodeA = structure(c(1L, 1L, 1L, 2L, 2L, 3L, 4L,
5L), .Label = c("ID_1", "ID_2", "ID_3", "ID_4", "ID_8"), class = "factor"),
nodeB = structure(c(2L, 3L, 4L, 5L, 4L, 6L, 6L, 1L), .Label = c("ID_100",
"ID_2", "ID_3", "ID_4", "ID_5", "ID_7"), class = "factor"),
weight = c(0.5, 0.77, 0.5, 0.9, 0.44, 0.32, 0.45, 0.543)), class = "data.frame", row.names = c(NA,
-8L))
library(igraph)
graph1 <- graph_from_data_frame(g1, directed = FALSE)
plot(graph1, vertex.label = V(graph1)$name)
mat <- shortest.paths(graph1)
mat
#> ID_1 ID_2 ID_3 ID_4 ID_8 ID_5 ID_7 ID_100
#> ID_1 0.00 0.50 0.77 0.50 Inf 1.40 0.95 Inf
#> ID_2 0.50 0.00 1.21 0.44 Inf 0.90 0.89 Inf
#> ID_3 0.77 1.21 0.00 0.77 Inf 2.11 0.32 Inf
#> ID_4 0.50 0.44 0.77 0.00 Inf 1.34 0.45 Inf
#> ID_8 Inf Inf Inf Inf 0.000 Inf Inf 0.543
#> ID_5 1.40 0.90 2.11 1.34 Inf 0.00 1.79 Inf
#> ID_7 0.95 0.89 0.32 0.45 Inf 1.79 0.00 Inf
#> ID_100 Inf Inf Inf Inf 0.543 Inf Inf 0.000
library(reshape)
edges <- melt(mat)
edges[as.character(edges$X1)>as.character(edges$X2)&!is.infinite(edges$value),]
X1 X2 value
2 ID_2 ID_1 0.500
3 ID_3 ID_1 0.770
4 ID_4 ID_1 0.500
6 ID_5 ID_1 1.400
7 ID_7 ID_1 0.950
11 ID_3 ID_2 1.210
12 ID_4 ID_2 0.440
14 ID_5 ID_2 0.900
15 ID_7 ID_2 0.890
20 ID_4 ID_3 0.770
22 ID_5 ID_3 2.110
23 ID_7 ID_3 0.320
30 ID_5 ID_4 1.340
31 ID_7 ID_4 0.450
47 ID_7 ID_5 1.790
61 ID_8 ID_100 0.543
使用 shortest.paths
函数,我们从图中得到最短路径。现在,我想限制最短路径的长度。
例如,当我运行下面的代码时,我得到了从一个顶点到任何顶点的所有最短路径。
df <- read.csv("~/data.csv")
g1 <- df
graph1 <- graph_from_data_frame(g1, directed = FALSE)
plot(graph1, vertex.label = V(graph1)$name)
mat <- shortest.paths(graph1)
我得到的输出
ID_1 ID_2 ID_3 ID_4 ID_8 ID_5 ID_7 ID_100
ID_1 0 1 1 1 Inf 2 2 Inf
ID_2 1 0 2 1 Inf 1 2 Inf
ID_3 1 2 0 2 Inf 3 1 Inf
ID_4 1 1 2 0 Inf 2 1 Inf
ID_8 Inf Inf Inf Inf 0 Inf Inf 1
ID_5 2 1 3 2 Inf 0 3 Inf
ID_7 2 2 1 1 Inf 3 0 Inf
ID_100 Inf Inf Inf Inf 1 Inf Inf 0
但是,我只想保留(比如说)路径长度为 3,另一个为 0 or Inf
。实际上,除了(路径长度=3)之外我不需要其他的。
而且,我要的sum of the path weight
不仅是路径数。我以为我可以只改变一行就可以做到这一点
mat <- shortest.paths(graph1, weights=E(graph1)$weight)
但是,如何限制路径长度呢?
可重现的数据
structure(list(nodeA = structure(c(1L, 1L, 1L, 2L, 2L, 3L, 4L,
5L), .Label = c("ID_1", "ID_2", "ID_3", "ID_4", "ID_8"), class = "factor"),
nodeB = structure(c(2L, 3L, 4L, 5L, 4L, 6L, 6L, 1L), .Label = c("ID_100",
"ID_2", "ID_3", "ID_4", "ID_5", "ID_7"), class = "factor"),
weight = c(0.5, 0.77, 0.5, 0.9, 0.44, 0.32, 0.45, 0.543)), class = "data.frame", row.names = c(NA,
-8L))
运行shortest.path
根据你提供的数据returns直接对所有节点组合求最短路径(路径权值之和的最小值)
g1 <- structure(list(nodeA = structure(c(1L, 1L, 1L, 2L, 2L, 3L, 4L,
5L), .Label = c("ID_1", "ID_2", "ID_3", "ID_4", "ID_8"), class = "factor"),
nodeB = structure(c(2L, 3L, 4L, 5L, 4L, 6L, 6L, 1L), .Label = c("ID_100",
"ID_2", "ID_3", "ID_4", "ID_5", "ID_7"), class = "factor"),
weight = c(0.5, 0.77, 0.5, 0.9, 0.44, 0.32, 0.45, 0.543)), class = "data.frame", row.names = c(NA,
-8L))
library(igraph)
graph1 <- graph_from_data_frame(g1, directed = FALSE)
plot(graph1, vertex.label = V(graph1)$name)
mat <- shortest.paths(graph1)
mat
#> ID_1 ID_2 ID_3 ID_4 ID_8 ID_5 ID_7 ID_100
#> ID_1 0.00 0.50 0.77 0.50 Inf 1.40 0.95 Inf
#> ID_2 0.50 0.00 1.21 0.44 Inf 0.90 0.89 Inf
#> ID_3 0.77 1.21 0.00 0.77 Inf 2.11 0.32 Inf
#> ID_4 0.50 0.44 0.77 0.00 Inf 1.34 0.45 Inf
#> ID_8 Inf Inf Inf Inf 0.000 Inf Inf 0.543
#> ID_5 1.40 0.90 2.11 1.34 Inf 0.00 1.79 Inf
#> ID_7 0.95 0.89 0.32 0.45 Inf 1.79 0.00 Inf
#> ID_100 Inf Inf Inf Inf 0.543 Inf Inf 0.000
library(reshape)
edges <- melt(mat)
edges[as.character(edges$X1)>as.character(edges$X2)&!is.infinite(edges$value),]
X1 X2 value
2 ID_2 ID_1 0.500
3 ID_3 ID_1 0.770
4 ID_4 ID_1 0.500
6 ID_5 ID_1 1.400
7 ID_7 ID_1 0.950
11 ID_3 ID_2 1.210
12 ID_4 ID_2 0.440
14 ID_5 ID_2 0.900
15 ID_7 ID_2 0.890
20 ID_4 ID_3 0.770
22 ID_5 ID_3 2.110
23 ID_7 ID_3 0.320
30 ID_5 ID_4 1.340
31 ID_7 ID_4 0.450
47 ID_7 ID_5 1.790
61 ID_8 ID_100 0.543