[igraph] Kautz Graph

[Vincent Matossian]

  Hi, 

I recently implemented the Kautz graph and am posting a quick R implementation below. The Kautz graph has very interesting properties that you can read about on wikipedia (low diameter, path redundancy...), which make it a topology of choice for parallel interconnects. 

If thought relevant it may be considered for addition to the list of graphs provided by igraph?

Best,

Vincent

PS: I'm glad about that the active thread on compiling igraph for the python interface ended in success :) . Is the port to python in sync with the R interface? What are the pros and cons of each interface?


# RUN FOR EXAMPLE AS 
# kg <- kautz.graph(3,1)
# plot(kg,layout=layout.circle,vertex.label=V(k)$lbl)
 
kautz.graph <- function(M,N){
  tmp.res<<-list()

  dimension <- N+1

  current <- c()

  for(i in 1:dimension)
    current[i] <- 0

  # CREATE ALL COMBINATIONS OF POSSIBLE NODE LABELS
  enumerate(current,1,M,dimension);

  lbl <- c()

  for(i in 1:length(
tmp.res)){
    lbl[i] <- toString(tmp.res[[i]])
  }

  edges <- c()
  
  for(i in 1:length(tmp.res)){
    curr <- tmp.res[[i]]
    curr <- curr[-1]
    fin <- length(curr)+1
    for(k in 0:M){
      if(k!=curr[fin-1]){
        curr[fin] <- k
        edges <- append(edges,c(i-1,which(lbl==toString(curr))-1))
      }
    }
  }
  kautz <- graph(edges,directed=T)
  V(kautz)$lbl <- lbl
  return(kautz)
}

enumerate <- function(current,n,M,N){
  if(n>N){
    tmp.res[[length(tmp.res)+1]]<<-current
    return(current)
  }
  for(i in 0:M){
    current[n] <- i
    if (n>1){
      if(current[n-1]!=current[n])
        enumerate(current, n+1,M,N)
    }
    else enumerate(current,n+1,M,N)
  }
}