R IGraph计算定向网络中的无向最短路径吗?

bt

关于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

我期望的是,不应返回最短的路径,因为在有向图中Alice没有从其自身伸出的任何边缘。这是由于以下事实:当我计算最短路径时,我正在使用以下选项:

mode="all"

而且这以某种方式甚至适用于有向图?

当然,如果我更改图形构造并设置:

directed=F

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);

返回相同的结果。

到底是怎么回事?我是否太累了,无法直截了当?

G5W

这就是什么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

即使边沿相反的方向,我们也可以获得将爱丽丝连接到另一个节点的所有路径。

我认为您想要的是:

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的边缘,因此我们一无所获。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

连接iGraph R中多个节点的最短路径

如何从 igraph R 连接最短路径

R igraph:仅计算所有顶点对的子集的最短路径

如何使用R igraph访问给定最短路径中的访问顶点

如何使用R中的igraph根据某些边缘属性找到两个节点之间的最短路径?

R igraph:在igraph中找到最短路径,为其增加权重并寻找替代方法

如何使用igraph提取R中所有最短路径的边缘类型?

R igraph:找到通过节点g的节点u和v之间最短路径的总数

计算无向加权图中一组顶点之间的最短路径

R中长度为l的最短路径

寻找网络中每对的最短路径

是否存在R函数来获得无向(无向)网络中的唯一边缘?

有向无环图中小度的最短路径

读取R中的无向图关系(AB)并使用igraph重命名顶点

有向树图中igraph R中从根到叶的所有路径

如何使用R中的igraph分别计算不同时期的网络度量?

使用R / igraph,是否有一种方法可以在考虑到唯一节点属性的数量的情况下找到节点之间的最短路径?

使用BFS搜索在无向图上查找最短路径,知道SP的长度

无向加权图中2个顶点之间的最短路径

在无向循环中查找全对最短路径的最快方法

JavaScript中的最短路径

如何使用密码计算 Neo4J 中网络的平均最短路径

计算Cypher中不同的无向路径

自我网络中自我顶点的 igraph r 约束

如何在igraph中为R置换网络?

在igraph中绘制网络时R的图边距太大

使用 igraph 在 R 中的网络图上不显示功能

r igraph lapply:在更大的网络中计算自我网络的密度、约束或其他度量

提高图Igraph R中边缘权重计算的速度