r - R IGraph 是在有向网络中计算无向最短路径吗?
问题描述
关于 IGraph 最短路径计算,我缺少一些东西。
假设我生成了一个网络(在 stackoverflow 中找到某处)并执行简单的计算:
library(igraph);
relations <- data.frame(from=c("Bob", "Cecil", "Cecil", "David", "David", "Esmeralda"), to=c("Alice", "Bob", "Alice", "Alice", "Bob", "Alice"));
g = simplify(graph_from_data_frame(d=relations, directed=T), remove.multiple = F, remove.loops = T);
#plotting the network in order to appreciate the directions of the edges
plot(g,edge.arrow.size=0.5);
#V(g)[5] is "Alice" which apparently should not be able to reach any node
print(all_shortest_paths(g,from=V(g)[5],to=V(g),mode="all")$res);
如您所见,找到的最短路径是:
> print(all_shortest_paths(g,from=V(g)[5],to=V(g),mode="all")$res);
[[1]]
+ 2/5 vertices, named, from 823c15d:
[1] Alice Bob
[[2]]
+ 2/5 vertices, named, from 823c15d:
[1] Alice Cecil
[[3]]
+ 2/5 vertices, named, from 823c15d:
[1] Alice David
[[4]]
+ 2/5 vertices, named, from 823c15d:
[1] Alice Esmeralda
[[5]]
+ 1/5 vertex, named, from 823c15d:
[1] Alice
我期望的是不应该返回最短路径,因为在有向图中,爱丽丝没有从自身向外延伸的边。这是因为当我计算最短路径时,我使用的是以下选项:
mode="all"
不知何故,这甚至适用于有向图?
当然,如果我更改图形构造并设置:
directed=F
IE
library(igraph);
relations <- data.frame(from=c("Bob", "Cecil", "Cecil", "David", "David", "Esmeralda"), to=c("Alice", "Bob", "Alice", "Alice", "Bob", "Alice"));
g = simplify(graph_from_data_frame(d=relations, directed=F), remove.multiple = F, remove.loops = T);
#plottin the network in order to appreciate the directions of the edges
plot(g,edge.arrow.size=0.5);
#V(g)[5] is "Alice" which apparently should not be able to reach any node
print(all_shortest_paths(g,from=V(g)[5],to=V(g),mode="all")$res);
返回相同的结果。
到底是怎么回事?我是不是太累了,无法直截了当?
解决方案
这就是什么mode="all"
意思 - 无论方向如何,都使用所有边缘。
我将使用一个更简单的图表来轻松查看正在发生的事情。
rel2 <- data.frame(from=c("Bob", "Bob", "David"),
to=c("Alice", "Carol", "Carol"))
g = simplify(graph_from_data_frame(d=rel2, directed=T))
LO = layout_as_bipartite(g, types=c(F,F,T,T))
plot(g, layout=LO)
现在用你的最短路径语句
print(all_shortest_paths(g,from=V(g)[3],to=V(g),mode="all")$res)
[[1]]
+ 2/4 vertices, named:
[1] Alice Bob
[[2]]
+ 4/4 vertices, named:
[1] Alice Bob Carol David
[[3]]
+ 1/4 vertex, named:
[1] Alice
[[4]]
+ 3/4 vertices, named:
[1] Alice Bob Carol
我们得到了将 Alice 连接到另一个节点的所有路径,即使边的方向相反。
我认为你想要的是:
print(all_shortest_paths(g,from=V(g)[3],to=V(g),mode="out")$res)
[[1]]
+ 1/4 vertex, named:
它只给出了从 Alice 到它自己的零长度路径。
只是为了完整,
print(all_shortest_paths(g,from=V(g)[3],to=V(g),mode="in")$res)
[[1]]
+ 2/4 vertices, named:
[1] Alice Bob
[[2]]
+ 1/4 vertex, named:
[1] Alice
这遵循仅使用传入边缘的路径,因此我们使用边缘到 Alice 获得“从”Alice“到”Bob 的路径,但我们没有得到其他任何东西,因为没有边缘进入 Bob。
推荐阅读
- javascript - 杏仁糖 + ReactJS?
- angular - 未找到模块:错误:无法解析“fs”角度
- python - 管理员无法创建新条目
- javascript - 根据属性将数组转换为地图的快捷方式
- javascript - setInterval() 在 Firefox 上不起作用
- azure - Azure Service Fabric 中 Reliable Dictionary 中的数据如何保存到磁盘
- javascript - 在 Javascript 中以 CSV 格式下载数据
- bash - 将自定义环境变量传递给 nohup
- c - 如何使用嵌入式 C 启动 ARM Cortex 编程?
- javascript - FormArray 的用法和动态添加一行控件