如何重新连接最小生成树 (R) 中的边？

Question

我有点坐标 (file .csv)。我已经读取了数据并计算了所有点对之间的距离，然后基于邻接矩阵创建了空间图。是无向正边权全图

library(igraph)

df0 <- read.csv(file="vpoints.csv", header=TRUE, sep=",")
n <- nrow(df0)
d <- matrix(0, n, n) 
## Find a distance between all nodes
for (i in 1:n) {
 for (j in 1:n) {
        d[i,j] = ((df0$cx[i] - df0$cx[j])^2 + 
             (df0$cy[i] - df0$cy[j])^2 )^(1/2) 
   }# forj 
} #for_i

g1 <- graph.adjacency(d, weighted=TRUE, mode="undirected")
V(g1)$name <- gsub("path","", df0$from)

## Find a minimum spanning tree
mst <- minimum.spanning.tree(g1)

mylayout<-as.matrix(cbind(df0$cx,df0$cy))
plot(mst, layout=mylayout, 
           vertex.label.cex=.5, 
           edge.label=round(E(g1)$weight,0),
           edge.label.cex=.5)

我需要在特定节点对之间构建 table 最短路径。大多数边缘是不可能的。

我找到了一个覆盖图所有顶点的最小生成树（MST）。但是这棵树包含了一些不可能的边，一些可能的边被省略了。

有人可以帮我如何重新布线边缘吗？

在第一种情况下，我需要重新连接边的一端（将节点“4048”连接到节点“4016”）。在第二种情况下，我需要删除节点“4020”和节点“4024”之间的边，并添加节点“4018”和节点“4022”之间的边。

更新： 1) 我认为在我的本地任务中，我可以在创建图形模型之前将节点集分成两个单独的集。然后我可以应用一种算法（Prim 的算法作为默认算法）以便在第一组节点上找到 MST。最后，我可以使用 for 循环将第二组节点连接到 MST。在这种方法中，我需要为节点分配一个新的二进制属性（例如，“0”——第一组，“1”——第二组）。第一组是中间节点的集合，第二组包括端点节点。端点节点到MST的连接标准是端点节点到树中节点的欧氏距离的最小值。

2) 另一种思路是：分析从节点“А”移动到节点“В”的机会，设置距离d[i,j]=0，否则计算d[i,j]

## Find a distance between nodes
for (i in 1:n) {
 for (j in 1:n) {
 # if (impossible) then d[i,j]=0  else
        d[i,j] = ((df0$cx[i] - df0$cx[j])^2 + 
             (df0$cy[i] - df0$cy[j])^2 )^(1/2) 
  }# forj 
} #for_i

谢谢。

Answer 1

我结合了第一个和第二个想法。为每个节点添加了二进制类别 (0/1)：0 -- 中间节点，1 -- 终点节点。然后将距离 d[i,j] 放在最大值上。

max_distance <- max(w, h) # (w)width, (h)eight of image
for (i in 1:n) {
 for (j in 1:n) {
     # the edge between node (i) and (j) is impossible
     if (df0$category[i] == 1 & df0$category[j] == 1) {
             d[i,j]= max_distance
     }
     else {
               d[i,j] = ((df0$cx[i] - df0$cx[j])^2 + 
                       (df0$cy[i] - df0$cy[j])^2 )^(1/2) 
     }
  }# forj 
} #for_i

如何重新连接最小生成树 (R) 中的边？

How to rewire edges in minimum spanning tree (R)?

r

igraph

minimum-spanning-tree

graph-algorithm