線グラフ(line graph):グラフ代数

• Line graphは無向グラフのエッジをノードに置き換え、頂点をエッジに置き換えたもの(Wiki)
• ひとまずRでたどって処理を追ってみる

# 適当にグラフオブジェクトとその隣接行列を作る
g <- make.graph.adj(5)
# 補助関数
# ベクトルの要素ごとにxor(),&関数を適用して、「すべて(prod)」、「ひとつでも(sum)」でくくる
# bitごと演算に相当
set.equal <- function(u,v){
	as.logical(prod(xor(u,v)))
}
set.intersec <- function(u,v){
	as.logical(sum(u & v))
}
# エッジのリストは２端点の情報を持つ
# 個々のエッジについて、その端点を１とし、それ以外のノードに対して０を持つようなベクトルを作り
# 行列状にしたものを返す関数
# エッジに限らず、要素集合に対して、含む要素に１を立て、含まない要素に０を立てたベクトルを作って
# 要素集合を行とした行列を返すように作る
# ハイパーグラフへの対応のため

make.set.mat <- function(a){
	ns <- 1:max(a)
	m <- matrix(FALSE,length(a[,1]),length(ns))
	for(i in 1:length(a[,1])){
		m[i,a[i,]] <- TRUE
	}
	return(list(v = ns,m = m))
}
# 線グラフを作る
# グラフの隣接行列mを受け取る
graph.line <- function(m){
	up.m <- m
	up.m[lower.tri(m)] <- FALSE
# これはエッジリスト
	relation <- which(up.m==1,arr.ind=TRUE)
# 要素集合表現にする
	set.mat <- make.set.mat(relation)
# 元のグラフのノード数
	n.v <- length(set.mat$v)
# 線グラフのノード数
	new.n.v <- length(set.mat$m[,1])
# 線グラフの隣接行列は、エッジの要素集合に共通要素があれば１
	new.m <- matrix(0,new.n.v,new.n.v)
	if(new.n.v > 1){
		for(i in 1:(new.n.v-1)){
			for(j in (i+1):new.n.v){
				new.m[i,j] <- set.intersec(set.mat$m[i,],set.mat$m[j,])
			}
		}
	}
	new.m
}
line.m <- graph.line(g$m)
par(mfcol=c(1,2))
plot(g$g)
plot(graph.adjacency(line.m,mode="undirected"))
par(mfcol=c(1,1))

• igraphパッケージではline.graph()関数？？？