CODEWITHSUNDEEP
rfor-looprecursionigraph
Nick
Nick

Reputation: 1116

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

I have a random graph with 10 nodes where 4 nodes have the zero degree.

It is required to obtain the connected graph by 1) select a node with zero degree and a minimal feature (for exmaple, random number from uniform distribautin) corresponding to each edge and connect it with graph by creation two incident edges to the node and deleting the 3rd edge, 2) repeat step 1 for all zero degree nodes.

The original graph in left, the resulting one in right.

enter image description here

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.

Upvotes: 0

Views: 157

Answers (2)

ThomasIsCoding
ThomasIsCoding

Reputation: 102439

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
  }
}

enter image description here

Upvotes: 1

Ali Hassan
Ali Hassan

Reputation: 66

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:

  1. maintain a stack of all the leaf nodes
  2. every time you iterate empty your stack by matching the leaf node values
  3. if there's a new value and count of the stack != to old count.
  4. Now iterate again.

Upvotes: 1

Related Questions