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