格子グラフの距離行列

  • 多次元立方格子上の点の占拠状態を把握したい
  • 点の座標からペアワイズの距離行列を作ることは容易
  • 距離行列と格子をグラフとみなした場合の隣接行列との関係を確認しよう
  • 1辺の長さが1の場合で考える
# 距離行列M、隣接行列E
M <- E <- list()
# 次元0=ノード数1の場合
M[[1]] <- matrix(0,1,1)
E[[1]] <- matrix(0,1,1)
# 次元をnまで
n <- 10
# だんだん次数を上げる
for(i in 2:n){
# 隣接行列は、1次元低い隣接行列と、対角成分が1の対角行列とを並べたもの
	#print(E[[i-1]])
	#print(diag(rep(1,2^(i-1))))
	up.e <- cbind(E[[i-1]],diag(rep(1,2^(i-2))))
	lw.e <- cbind(diag(rep(1,2^(i-2))),E[[i-1]])
	E[[i]] <- rbind(up.e,lw.e)
# 距離行列は、1次元低い距離行列と、それに1を加えたものとを並べたもの
# 隣接行列からグラフを作って、その上で距離行列を求めてもよいが…
	up.m <- cbind(M[[i-1]],M[[i-1]]+1)
	lw.m <- cbind(M[[i-1]]+1,M[[i-1]])
	M[[i]] <- rbind(up.m,lw.m)
}
library(igraph)
G <- list()
par(ask = TRUE)
for(i in 1:n){
	G[[i]] <- graph.adjacency(E[[i]],mode = "undirected")
# グラフから求めた最短距離行列が上の算出方法と等しいことの確認
	tmp.sh.paths <- shortest.paths(G[[i]])
	#print(tmp.sh.paths-M[[i]])
	print(sum((tmp.sh.paths-M[[i]])^2))
	#print(M[[i]])
	plot(G[[i]])
}
  • 格子グラフの作り方はこちらにも