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

Question

I have coordinates of points (file .csv). I have read the data and calculated distances between all pairs of points, then based on the adjacency matrix the spatialize graph was created. It is the undirected, positive-edge-weight full graph.

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)

I need to build a table of shortest paths between the specific pairs of nodes. Most of edges are imposible.

I have found a minimum spanning tree (MST) covering all vertices of graph. But this tree includes some of imposible edges and some posible edges are ommitted.

Could some one please help me how to rewire edges?

In the 1st case I need to rewire one end of edge (form the node "4048" to the node "4016"). In the 2nd case I need to delete the egde between the node "4020" and the node "4024", and add the edge between the node "4018" and the node "4022".

Update: 1) I think in my local task I can split the set of nodes into two separated sets before creation the graph model. Then I can apply an algorithm (Prim's algorithm as default algorithm) in order to find the MST on the first set of nodes. Finally I can connect the nodes from the second set to the MST with the for-loop. I such approach I need assign a new binary attribute to the node (for example, "0" -- first set, "1" -- second set). First set is the set of intermediate nodes, second one includes the end-point nodes. The connection criteria of a end-point node to MST is minimum of the Euclid distance from a end-point node to a node in the tree.

2) Another idea is: to analyse the opportunity to move from node "А" to node "В", and set distance d[i,j]=0, else calculate 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

Thanks.

Nick Nick · Accepted Answer · 2016-02-01T13:33:40

I have applied the mix of 1st and 2nd idea. The binary category (0/1) was added for each node: 0 -- intermediate node, 1 -- end-point node. Then the distance d[i,j] was put on the maximum value.

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

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

1 Answers