如何检查igraph中两个顶点之间是否存在唯一的最短路径
how to check if there exists a unique shortest path between two vertices in igraph
我想用 igraph 确定两个顶点之间是否存在唯一的最短路径或多条最短路径。如果我使用length(all_shortest_paths(g, i,j)
,那实际上对我有帮助,但我觉得有很多多余的操作。我宁愿先用 get.shortest.paths(g, i,j)
获得一条最短路径,然后再看看是否还有另一条。但是,我不知道该怎么做。
谁能帮我看看是否还有一条不同于get.shortest.paths(g, i,j)
获得的第一条最短路径?
这是一个示例图
library(igraph)
data <- read.table(text="
1 2
1 4
1 5
2 3
2 4
3 4
5 7
5 8
3 6", header=FALSE)
gmatrix <- data.matrix(data, rownames.force = NA) #convert into a matrix to use in igraph
g <- graph_from_edgelist(gmatrix, directed = FALSE)
例如,如果我想找到从 1 到 3 的最短路径,我使用 all_shortest_paths(g, 1,3)
,结果如下。
$res
$res[[1]]
+ 3/9 vertices, from 634c426:
[1] 1 4 3
$res[[2]]
+ 3/9 vertices, from 634c426:
[1] 1 2 3
我要的是求第一条最短路径。例如
get.shortest.paths(g, 1,3)
$vpath
$vpath[[1]]
+ 3/9 vertices, from 634c426:
[1] 1 2 3
现在,我想看看有没有其他路径不同于[1] 1 2 3
。在更大的图中,由于有数十条可能的最短路径,我不想使用 all_shortest_paths(g, i,j)
来进行该查询。
总的来说,我的问题是:如何检查两个顶点之间是否存在唯一的最短路径?我将给出两个顶点作为我的输入,在 return 我应该得到 TRUE 或 FALSE 指示是否存在唯一的最短路径。
收到 的回复后,这里有一个解决方案。请注意,初始网络是无向图,没有边权。
p <- get.shortest.paths(g, i, j)$vpath[[1]] #shortest path between node i and node j
g <- set_edge_attr(g, "weight", value = ifelse(E(g) %in% E(g, path = p), 1.50, 1)) #Assign slightly larger edge weights to the edges existing in path p
q <- get.shortest.paths(g, i,j , weights = E(g)$weight)$vpath[[1]] #recalculate the shortest path with edge weights
g <- delete_edge_attr(g, "weight")
if(all(p %in% q))
#If paths p and q are the same, then the shortest path is unique
但是,由于 运行 时间长,这绝对不是一个好的解决方案。当我对 400 个节点尝试此方法时,需要几分钟才能停止。
我想用 igraph 确定两个顶点之间是否存在唯一的最短路径或多条最短路径。如果我使用length(all_shortest_paths(g, i,j)
,那实际上对我有帮助,但我觉得有很多多余的操作。我宁愿先用 get.shortest.paths(g, i,j)
获得一条最短路径,然后再看看是否还有另一条。但是,我不知道该怎么做。
谁能帮我看看是否还有一条不同于get.shortest.paths(g, i,j)
获得的第一条最短路径?
这是一个示例图
library(igraph)
data <- read.table(text="
1 2
1 4
1 5
2 3
2 4
3 4
5 7
5 8
3 6", header=FALSE)
gmatrix <- data.matrix(data, rownames.force = NA) #convert into a matrix to use in igraph
g <- graph_from_edgelist(gmatrix, directed = FALSE)
例如,如果我想找到从 1 到 3 的最短路径,我使用 all_shortest_paths(g, 1,3)
,结果如下。
$res
$res[[1]]
+ 3/9 vertices, from 634c426:
[1] 1 4 3
$res[[2]]
+ 3/9 vertices, from 634c426:
[1] 1 2 3
我要的是求第一条最短路径。例如
get.shortest.paths(g, 1,3)
$vpath
$vpath[[1]]
+ 3/9 vertices, from 634c426:
[1] 1 2 3
现在,我想看看有没有其他路径不同于[1] 1 2 3
。在更大的图中,由于有数十条可能的最短路径,我不想使用 all_shortest_paths(g, i,j)
来进行该查询。
总的来说,我的问题是:如何检查两个顶点之间是否存在唯一的最短路径?我将给出两个顶点作为我的输入,在 return 我应该得到 TRUE 或 FALSE 指示是否存在唯一的最短路径。
收到
p <- get.shortest.paths(g, i, j)$vpath[[1]] #shortest path between node i and node j
g <- set_edge_attr(g, "weight", value = ifelse(E(g) %in% E(g, path = p), 1.50, 1)) #Assign slightly larger edge weights to the edges existing in path p
q <- get.shortest.paths(g, i,j , weights = E(g)$weight)$vpath[[1]] #recalculate the shortest path with edge weights
g <- delete_edge_attr(g, "weight")
if(all(p %in% q))
#If paths p and q are the same, then the shortest path is unique
但是,由于 运行 时间长,这绝对不是一个好的解决方案。当我对 400 个节点尝试此方法时,需要几分钟才能停止。