How to iterate with dynamic changing the number edges and nodes?-CodePudding

The

My attempt is:

library(igraph) ###################################################################### set.seed(5) g <- sample_gnm(10, 4) xy <- cbind(runif(10), runif(10)) par(mfrow=c(1,2)) plot(g, vertex.size=5, layout=xy) num_point <- length(V(g)[degree(g)==0]) for(k in 1:num_point){ points = V(g)[degree(g)==0] for(i in 1:length(E(g))) { # loop over all edges head <- get.edgelist(g)[i,][1]; h <- c(V(g)[head]$x, V(g)[head]$y) tail <- get.edgelist(g)[i,][2]; t <- c(V(g)[tail]$x, V(g)[tail]$y) d <- NULL # loop over all points for(j in points) d <- c(d, runif(1)) E(g)[i]$d <- min(d) # local min E(g)[i]$p <- points[which(d == min(d))] } # i ei = which.min(E(g)$d) # edge with the global min vi = E(g)[ei]$p # head and tail of edge with global min head <- get.edgelist(g)[E(g)[ei],][1]; tail <- get.edgelist(g)[E(g)[ei],][2] g <- add_edges(g, c(head, V(g)[vi], V(g)[vi], tail)); g <- delete_edges(g, get.edge.ids(g, c(head, tail) )) } plot(g, vertex.size=5, layout=xy)

Question. How to organize the loop over all edges when the number of edges increase by 1 and number of point decrising by 1 evety step? One can see, I don't use the k variable in explicit form.

CodePudding user response：

I will recommend you to use recursion for this and drop for loop- using recursion for tree and graph structures will definitely make your life easier.

Answer:

maintain a stack of all the leaf nodes

every time you iterate empty your stack by matching the leaf node values

if there's a new value and count of the stack != to old count.

Now iterate again.

CodePudding user response：

Instead of for loop, I think you can use repeat plus a termination condition, i.e., no isolated vertices any more

repeat { points <- V(g)[degree(g) == 0] for (i in 1:length(E(g))) { # loop over all edges head <- get.edgelist(g)[i, ][1] h <- c(V(g)[head]$x, V(g)[head]$y) tail <- get.edgelist(g)[i, ][2] t <- c(V(g)[tail]$x, V(g)[tail]$y) d <- NULL # loop over all points for (j in points) d <- c(d, runif(1)) E(g)[i]$d <- min(d) # local min E(g)[i]$p <- points[which(d == min(d))] } # i ei <- which.min(E(g)$d) # edge with the global min vi <- E(g)[ei]$p # head and tail of edge with global min head <- get.edgelist(g)[E(g)[ei], ][1] tail <- get.edgelist(g)[E(g)[ei], ][2] g <- add_edges(g, c( head, V(g)[vi], V(g)[vi], tail )) g <- delete_edges(g, get.edge.ids(g, c(head, tail))) if (sum(degree(g) == 0) == 0) { break } }