グラフの単体の列挙

  • オイラー三角化グラフができたら、三角形の列挙がしたい
  • こちらにあるように行列操作でそれができる
  • やってみる
plot(g)
ad <- as.matrix(get.adjacency(g))

E <- ad
E[lower.tri(E)] <- 0
g <- graph.adjacency(E)
#plot(g)
#el <- get.edgelist(g)
S.list <- list()
n <- ncol(E)
S.list[[1]] <- diag(rep(1,n))
cnt <- 1
loop <- TRUE
for(ii in 2:3){
#while(loop){
	if(length(S.list[[cnt]][,1])==0){
		break
	}
	tmp <- S.list[[cnt]] %*% E
	tmp2 <- which(tmp==cnt,arr.ind=TRUE)
	if(length(tmp2[,1])>0){
		cnt <- cnt
		S.list[[cnt+1]] <- matrix(0,length(tmp2[,1]),n)
		for(i in 1:length(tmp2[,1])){
			u <- tmp2[i,1]
			v <- tmp2[i,2]
			pre <- which(S.list[[cnt]][u,]==1)
			S.list[[cnt+1]][i,c(pre,v)] <- 1
		}
	}else{
		loop <- FALSE
	}
	cnt <- cnt+1
}

tmp <- sapply(S.list,nrow)