こんにちは、JOKERです。
先日、大学の課題で隣接行列を用いてグラフが強連結であるかを判定するプログラムを作りました。
その時にネットで強連結判定アルゴリズムを調べたのですが、隣接行列を使ったものがあまり見つかりませんでした。
そこで、持っている教科書から隣接行列の累乗が使えることを見つけたので、備忘録も兼ねて記事にすることにしました。
需要があるかわかりませんが、もし同じ課題が今後もでていて、やり方が分からなくてネットで調べた人がこの記事にたどり着くのでしょうか？笑
プログラムだけ見れればいい人は最後の方まで飛ばしちゃってください。
隣接行列の累乗が意味すること
これは「隣接行列 冪乗」とかで検索すれば割とヒットしますが、ここでも簡単に説明します。
まず、隣接行列とはグラフの辺が結ぶ頂点の組み合わせを正方行列の要素に表したものです。
この正方行列の一辺の長さは頂点の数に等しく、例えば頂点1から頂点2への有向辺があれば縦（行）1番目、横（列）2番目の要素が1となるということです。
辺に向きがない「無向グラフ」であればこの行列は対角線に対して対称な「対称行列」となったり、辺一つ一つに重みがついた「重み付きグラフ」には要素の数値をその重み（の比）に変えたりと、いろんな種類のグラフにもこの隣接行列は考えることができます。（詳しくはwikiで）
ここでこの隣接行列をn乗してできる行列の各要素は、その行番号から列番号への頂点までを、そのグラフの辺をちょうどn回使うルートの総数（同じ頂点や辺を何回通ってもいい）となります。
証明はここでしませんが、隣接行列の行は辺の始点、列は辺の終点を意味していることと、行列の掛け算をどうやって計算するかを考えれば理解できるはずです。
また、0乗は単位行列になるとします。つまり、行と列の番号がおなじである対角成分のみ1、その他は0となる行列ということです。これは辺を0個使う、すなわち1回も辺を通らずにたどり着ける頂点はその頂点自身だけということを表していると解釈できます。
n乗したものが表すのはn辺通るルートの総数であり、n辺以内にたどり着けるルートの数ではありません。n乗の要素は1以上だったのにn+1乗したら0になることもあります。
強連結とは
グラフ理論における「強連結」とは、有向グラフの任意の2点間を行き来できる道が存在することを指します。
無向グラフの「連結」よりも、辺に向きの制限があるので「”強”連結」というのですね。
ある頂点vから別の頂点wまでの道のりで通る頂点数は最大でもn-1個なので、
全ての2頂点に対して、 n-1個までの辺を使うルートを調べればそのグラフが強連結かどうかがわかります。
実際のプログラム
隣接行列の累乗を強連結判定に使うためには、0 〜 n-1個の辺を通るルートの総数、すなわち0乗からn-1乗した隣接行列n個を全て足し合わせる必要があります。
0乗の行列は自明なので絶対に必要というわけではありませんが、0乗まで足し合わせてあった方がプログラムで判定する時に楽です。
以下に提出したプログラムを貼っておきます。言語はC言語です。
#include <stdio.h>
#include <stdlib.h>
# define N 100
# define true 1
# define false 0
// 隣接行列を2次配列として使う
typedef int adjmatrix[N][N];
// .datファイルから隣接行列を読み込む関数
int read_adjacency_matrix(char *datafile, adjmatrix matrix){
FILE *fp;
int vertex_num; // 頂点の数を入れる変数
int start, dest; // start = 始点となる頂点番号（行番号）, dest = 終点となる頂点番号（列番号）
fp = fopen(datafile, "r"); // 読み取り用にファイルを開く
fscanf(fp, "%d\n", &vertex_num); // 頂点数の読み込み vertex_num = fscanf(fp, "%d\n"); と同じ
// 読み取るグラフの頂点数が N より大きい場合のエラー表示
if(vertex_num > N){
fprintf(stderr, "##### このプログラムが扱えるのは頂点数が%dまでのグラフです\n", N);
exit(1);
}
// ファイルから読み取る数字（今回は0or1）を隣接行列の2次元配列の各成分に書き込む
for(start = 0; start < vertex_num; start++){
for(dest = 0; dest < vertex_num; dest++){
fscanf(fp, "%d\n", &matrix[start][dest]);
}
}
fclose(fp); // ファイルを閉じる
return vertex_num; // 今後よく使う頂点数を返しておく
}
// 単位行列に書き換える関数
void make_identity_matrix(adjmatrix a, int vertex_num){
for(int i = 0; i < vertex_num; i++){
for(int j = 0; j < vertex_num; j++){
if(i != j){ // 対角成分は1、それ以外は0にする
a[i][j] = 0;
}else
a[i][j] = 1;
}
}
}
void make_reachability_matrix(adjmatrix a, adjmatrix b, int vertex_num){
adjmatrix multiplicand_matrix; // 被積行列
adjmatrix product_matrix; // 積の結果を入れる行列
make_identity_matrix(b, vertex_num);
make_identity_matrix(multiplicand_matrix, vertex_num);
for(int n = 0; n < vertex_num - 1; n++){ // aの冪乗を計算していきながら到達可能性行列に足していくループ 0 ~ n-1 乗まで
for(int i = 0; i < vertex_num; i++){ // a^n * a = a^(n+1)
for(int j = 0; j < vertex_num; j++){
for(int k = 0; k < vertex_num; k++){
product_matrix[i][j] += multiplicand_matrix[i][k] * a[k][j];
}
}
}
for(int i = 0; i < vertex_num; i++){ // 到達可能性行列 b += a^(n+1)
for(int j = 0; j < vertex_num; j++){
b[i][j] += product_matrix[i][j];
}
}
for(int i = 0; i < vertex_num; i++){ // 被積行列 a^n <- a^(n+1) に上書き
for(int j = 0; j < vertex_num; j++){
multiplicand_matrix[i][j] = product_matrix[i][j];
}
}
}
}
int is_scg(adjmatrix b, int vertex_num){
int reachability = true; // 最初に到達可能性は真に設定
for(int i = 0; i < vertex_num; i++){ //
for(int j = 0; j < vertex_num; j++){
if(b[i][j] == 0){ // 到達可能性行列の成分に0が一つでもあったら到達可能性を偽（0）に変える
reachability = false;
}
}
}
return reachability;
}
void print_matrix(adjmatrix a, int vertex_num){ // （到達可能性）行列の各成分の値を表示することで確認するための関数（デバッグ用）
for(int i = 0; i < vertex_num; i++){
for(int j = 0; j < vertex_num; j++){
printf("%5d ", a[i][j]);
}
printf("\n");
}
}
int main(int argc, char * argv[]) {
char *datafile; // read_adjacency_matrix関数で開くファイル名を渡すための文字列ポインタ変数
adjmatrix a, b; // 行列aは読み込んだ隣接行列を入れる。 行列bはaの隣接行列が表すグラフの到達可能性行列
int vertex_num; // 頂点数
if(argc <= 1){ // プログラム実行時に読み込むファイルを入力しなかったときのエラー表示
fprintf( stderr, "##### ファイルを指定してください\n" );
return 1;
}
datafile = argv[1]; // ファイル名の取得
vertex_num = read_adjacency_matrix( datafile, a );
make_reachability_matrix(a, b, vertex_num);
if(is_scg(b, vertex_num)){
printf("強連結である\n");
}else{
printf("強連結でない\n");
}
// print_matrix(b, vertex_num); // 到達可能性行列の中身を確認する時用
return 0;
}
長くて読みにくいかもしれませんが、上のプログラムのmake_reachability_matrix()で頂点から頂点までのルートの数を計算し、行列にしています。
その行列の要素に一つでも0があれば、その行番号から列番号へのルートは存在しないということで非強連結と判定しています。逆に全ての要素が0でなければ強連結です。（負や小数にならないはずなので）
実際に次の隣接行列(adjmatrix10.datという名前のファイル)をこのプログラムに投げてみると以下のようになります。
・adjmatrix10.datの中身 (１行目に頂点数、２行目以降に隣接行列)
7
0 1 0 0 0 0 0
0 0 0 1 0 0 0
1 0 0 1 0 0 0
0 0 0 0 0 1 0
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 0 1 0 0 0 0
・adjmatrix10.datのグラフ
・実行結果 (make_reachability_matrixの結果も表示しています)
黒塗りで見にくくなっていますが、しっかり「強連結でない」と出力されています。
また、出力された行列を見ても、1〜6番の頂点から7番の頂点へのルート数が0となっていて、上のグラフとちゃんと対応していることも確認できます。
他の隣接行列でもしっかり判定できているのでプログラムの正確性は問題ないと思います。
なにかお気付きな点やご不明点等ございましたら、お気軽にコメントしてください。
コメント