近頃Rのigraphパッケージで遊んでるんだけど割と面白いので使い方を忘れないうちにメモっておく.
グラフはプロットした方が理解しやすいんだけどとりあえず今回はグラフオブジェクトの作成と要素へのアクセスとかその辺.プロットは次回.
グラフって何ぞとか用語の意味とかはグラフ理論 - Wikipedia.
グラフオブジェクトの作成
基本
エッジをベクトルにまとめてgraph()関数に与えることでグラフオブジェクトが作成される.デフォルトで有向グラフ.有向,無向の制御は引数directedにTRUEかFALSEを与えることで可能.ループや多重エッジも含める事ができる.
> ## エッジの一覧をgraph()関数に与える > edge <- c(0,1, 0,2, 0,3, 1,2, 2,2, 1,3, 1,3) > g <- graph(edge, directed=FALSE) > g Vertices: 4 Edges: 7 Directed: FALSE Edges: [0] 0 -- 1 [1] 0 -- 2 [2] 0 -- 3 [3] 1 -- 2 [4] 2 -- 2 [5] 1 -- 3 [6] 1 -- 3
特殊なグラフ
一部の特徴的なグラフについては簡単に作成するための関数が用意されている.引数としては基本的にノード数または次元数を与え,オプションで有向,無向などを指定できる.
graph.full(3) # 完全グラフ graph.tree(5) # 木 graph.star(3) # 星 graph.ring(3) # リング graph.lattice(c(3,3)) # 格子
行列からの作成
行列をエッジリストとして利用する場合は並べ方に注意する(行列の添字は下方向に増加するため並べ方によっては転置が必要).
> ## 行列からの作成 > edge <- matrix(c(0,1, 1,2, 2,3), byrow=TRUE, ncol=2) > edge [,1] [,2] [1,] 0 1 [2,] 1 2 [3,] 2 3 > graph(t(edge)) Vertices: 4 Edges: 3 Directed: TRUE Edges: [0] 0 -> 1 [1] 1 -> 2 [2] 2 -> 3
隣接行列,距離行列からの作成
graph.adjacency()関数により,隣接行列(隣接行列 - Wikipedia)からグラフオブジェクトを作成できる.対角成分が0でなければループになる.
> ## 隣接行列からグラフオブジェクト作成 > adj.mat <- c(1, 1, 0, 0, + 1, 0, 1, 0, + 0, 1, 0, 1, + 0, 0, 1, 0) > adj.mat <- matrix(adj.mat, nrow=4) > adj.mat [,1] [,2] [,3] [,4] [1,] 1 1 0 0 [2,] 1 0 1 0 [3,] 0 1 0 1 [4,] 0 0 1 0 > graph.adjacency(adj.mat) Vertices: 4 Edges: 7 Directed: TRUE Edges: [0] 0 -> 0 [1] 0 -> 1 [2] 1 -> 0 [3] 1 -> 2 [4] 2 -> 1 [5] 2 -> 3 [6] 3 -> 2
また,graph.adjacency()関数の引数weightedにTRUEを与えることで距離行列からグラフオブジェクトを作成できる.このときグラフは重み付きグラフになり,属性(後述)weightに重みが記録されたグラフになる.
> ## 距離行列から重み付きグラフオブジェクト作成 > dis.mat <- c(0, 3, 0, 5, + 3, 0, 4, 0, + 0, 4, 0, 0, + 5, 0, 0, 0) > dis.mat <- matrix(dis.mat, nrow=4) > dis.mat [,1] [,2] [,3] [,4] [1,] 0 3 0 5 [2,] 3 0 4 0 [3,] 0 4 0 0 [4,] 5 0 0 0 > g <- graph.adjacency(dis.mat, weighted=TRUE) > g Vertices: 4 Edges: 6 Directed: TRUE Edges: [0] 0 -> 1 [1] 0 -> 3 [2] 1 -> 0 [3] 1 -> 2 [4] 2 -> 1 [5] 3 -> 0 > E(g)$weight [1] 3 5 3 4 4 5
属性
グラフオブジェクトに含まれているグラフのノード(vertex; pl. vertices)はV()関数で,エッジはE()関数で参照できる.
> ## ノード > V(g) Vertex sequence: [1] 0 1 2 3 > ## エッジ > E(g) Edge sequence: [0] 0 -> 1 [1] 0 -> 3 [2] 1 -> 0 [3] 1 -> 2 [4] 2 -> 1 [5] 3 -> 0
グラフオブジェクトの属性はグラフ,ノード,エッジそれぞれに存在しており,list.~.attributes()関数でそれぞれがどのような属性を保持しているかを確認できる.
> ## グラフ,ノード,エッジの属性 > list.graph.attributes(g) character(0) > list.vertex.attributes(g) character(0) > list.edge.attributes(g) [1] "weight"
この例ではグラフgが重み付きグラフなので,エッジの属性としてweightを持っていることが分かる.
属性値の参照は$演算子を用いる.
> ## $演算子により属性値にアクセスできる > E(g)$weight [1] 3 5 3 4 4 5
属性は任意のものを追加できる.もし添字(後述)を利用するなどして一部のノード,エッジに対してのみ属性値を指定した場合,属性がベクトルで与えられていればNA,リストで与えられていればNULLにより空白が埋められる.
> ## 属性値は任意のものを追加できる > V(g)[2]$foo <- "foo" > V(g)$foo [1] NA NA "foo" NA > V(g)[2]$bar <- list(bar="bar") > V(g)$bar [[1]] NULL [[2]] NULL [[3]] [1] "bar" [[4]] NULL
添字
これまでの例で気づいているかもしれないがグラフオブジェクトの添字は0から始まっている.一方,$演算子による参照結果はベクトル(リストも可能)なので添字は1から始まる.
> ## グラフオブジェクトの添字は0オリジン > E(g)[0]$weight [1] 3 > ## 属性値参照結果は普通のベクトル(またはリスト) > E(g)$weight[1] [1] 3
それだけではなく,グラフオブジェクトの添字は添字操作などにより抽出された後でもリセットされないという点も注意が必要.添字を$演算子の前に付けるか後につけるかで結果が大きく異なる場合がある.グラフオブジェクトの添字は特殊なものであると意識しておく必要がある.
> ## グラフオブジェクトの添字は添字などにより抽出された後でもリセットされない > E(g)[2:3]$weight [1] 3 4 > E(g)[2:3][1]$weight numeric(0) > E(g)[2:3][3]$weight [1] 4 > ## 属性値参照結果はベクトルなので添字により抽出される度添字はリセットされる > E(g)$weight[3:4][1] [1] 3
ノード,エッジの抽出
ノード,エッジの添字中では特定の関係にあるノード,エッジを抽出するための関数や演算子を使用できる.
> ## 特定のノードに隣接するノードの抽出 > V(g)[nei(1)] # ノード1に隣接するノード Vertex sequence: [1] 0 2 > ## 特定の接続状態にあるエッジの抽出 > E(g)[1 %->% 0:2] # ノード1から伸びるエッジで,ノード0,1,2へ伸びているもの Edge sequence: [2] 1 -> 0 [3] 1 -> 2 > E(g)[1 %<-% 0:2] # ノード1へ伸びるエッジで,ノード0,1,2が開始であるもの Edge sequence: [0] 0 -> 1 [4] 2 -> 1 > E(g)[1 %--% 0:2] # ノード1とノード0,1,2を相互に繋ぐエッジ Edge sequence: [0] 0 -> 1 [2] 1 -> 0 [3] 1 -> 2 [4] 2 -> 1
詳細はWelcome to igraph's new home.
とりあえず今回はここまで.イマイチイメージができなくてよく分からないという場合はとりあえずグラフオブジェクトをplot()に投げてみると多少わかりやすくなるかもしれない.ただ調整しないとノードがランダムに配置されるので少し見辛い.そのあたりもまた次回ということで.