igraph-help
[Top][All Lists]

## [igraph] Kautz Graph

 From: Vincent Matossian Subject: [igraph] Kautz Graph Date: Tue, 29 May 2007 10:16:02 -0700

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