如何使用r-igraph包获取图的最长流矩阵？

debugcn 发表于 Dev

头牟

假设我使用igraph包创建了一个随机图：

n=6  # number of vertices 
F <- erdos.renyi.game(n, p.or.m=0.7, directed=FALSE)
m=ecount(F)
min = 1    # 1 km
max = 50   # 50 km 
F <- set.edge.attribute(F, name="distance", value=runif(m , min , max))
plot(F, layout=layout.fruchterman.reingold)
distances(F)
distances(F, weights = E(F)$distance)
distances(F, v = 1, to = 6, weights = E(F)$distance)
get.all.shortest.paths(F, 1, to = V(F))

我们知道distances(F, weights = E(F)$distance)给出与图内最短路径相关的流立方矩阵。

我想要与以下行相同的内容：

distances(F, weights = E(F)$distance) # matrix of shortests paths flows between any two vertices
distances(F, v = 1, to = 6, weights = E(F)$distance)
get.all.shortest.paths(F, 1, to = V(F)) # gives the shortests paths between 1 and other vertices

这次我需要最长的路径以及矩阵中关联的流。我不知道“ igraph”是否可行。

谢谢你的帮助！

瑞·巴拉达斯（Rui Barradas）

如果首先计算最大距离，然后从最大距离中减去该距离作为权重，则该算法将计算最长路径。

以下两种方法是等效的。

library(igraph)

max_dist <- max(E(G)$distance)
all_shortest_paths(G, from = 1, to = V(G), weights = max_dist - E(G)$distance)
get.all.shortest.paths(G, 1, to = V(G), weights = max_dist - E(G)$distance)

笔记：

我将图形对象的名称更改为G，因为F它也是的符号FALSE。
这次使用RNG设置来重新创建图形，以使结果可再现。

图形创建代码。

set.seed(1234)

n <- 6  # number of vertices 
G <- erdos.renyi.game(n, p.or.m = 0.7, directed = FALSE)
m <- ecount(G)
min <- 1    # 1 km
max <- 50   # 50 km 
G <- set.edge.attribute(G, name = "distance", value = runif(m , min , max))

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

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