木のグラフにおける相関（１）木グラフを線分成分の木として取り扱う

• 木のグラフがある
• ノードに値が与えられている
• 木の上で、この値が順序よく並んでいるのかを評価したい
• そのために、次のようにする
• ノードの並びのうち、値が昇順(降順でもよい)になっている鎖状のセグメントに分割する
• そのセグメントを１つのノードとみたてて、それらが作る木として、元の木グラフをとらえる
• セグメントの連結にあたっては、隣接セグメントを定めるほかに、セグメントの最小端と最大端とを区別する必要がある
• 具体的には、２セグメントを連結する場合には、第１セグメントの最小端と第２セグメントの最小端が連結する場合、第１セグの最小端と第二セグの最大端、第１セグの最大端と第２セグの最小端、第１セグの最大端と第２セグの最大端とが連結する４つの場合がある
• ノードの連結の具合が１通りのグラフは無向グラフ、２通りのグラフは有向グラフ。この場合は、４通りの連結の仕方のあるグラフということになる
• そんなのをRでハンドリングするための覚書き

library(igraph)

N<-3
M<-matrix(0,N,N)
for(i in 1:(N-2)){
	M[i,sample((i+1):N,1)]<-1
}
M[N-1,N]<-1
M

s<-sample(1:N)

M<-M[s,s]
M

M2<-(M+t(M))
M2[lower.tri(M2)]<-0
M2
g<-graph.adjacency(M)
is.connected(g,"strong")
plot(g)



# Nノードは値でソートされた複数のノードの直線木
# 各直線木の構成ノード数

L<-sample(2:5,N,replace=TRUE)

# 全ノード数
AllN<-sum(L)

V<-sample(1:AllN)

minMax<-matrix(0,N,2)
st<-1
end<-0

Segs<-list()
Mall<-matrix(0,AllN,AllN)


for(i in 1:N){
	end<-st+L[i]-1
	Segs[[i]]<-sort(V[st:end])
	minMax[i,]<-range(Segs[[i]])
	st<-end+1
	for(j in 1:(length(Segs[[i]])-1)){
		Mall[Segs[[i]][j],Segs[[i]][j+1]]<-1
	}
	
}
minMax

Segs


# sorted segmentsの連結には、連結される２セグメントがそれぞれに持つ
# ２端点のどれとどれを結ぶかの４通りがある
# その４通りの区別をするのに、隣接行列を有向の枠組みで使った上で
# 辺ありの値に-1,1の２値を用いて、４通りを表すことにする
# i行　j列に1が入っていたら、iのminからjのminへ
# i行　j列に-1が入っていたら、iのminからjのmaxへ


M2<-M*sample(c(-1,1),N^2,replace=TRUE)
M2


for(i in 1:N){
	for(j in 1:N){
		if(M[i,j]==1){
			Mall[minMax[i,1],minMax[j,1]]<-1
		}else if(M[i,j]==-1){
			Mall[minMax[i,1],minMax[j,2]]<-1
		}
	}
}
diag(Mall)<-0

Mall
Mall<-(Mall+t(Mall))

Mall[lower.tri(Mall)]<-0
Mall
g<-graph.adjacency(Mall)
is.connected(g,"weak")
plot(g)