有向グラフの強連結判定を正しく行うことができない

Question

前提・実現したいこと

隣接行列が描かれたdatファイルを読み込んで、それをdot形式で描いた有向グラフが強連結であるか否かを判定するプログラムを作成しているのですが、強連結であるはずのグラフも「強連結ではありません」と出てしまいます。きちんと強連結のグラフに対して強連結と表示させるようにしたいです。find_path()の部分を作成したのですがどこか問題があるのでしょうか。

強連結である有向グラフ

発生している問題・エラーメッセージ

強連結であるはずのグラフも「強連結ではありません」と表示されてしまう。

該当のソースコード

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define N 100

#define boolean int
#define true 1
#define false 0
typedef boolean adjmatrix[N][N];

typedef int vindex;

typedef struct edgecell{
  vindex destination;
  struct edgecell *next;
}
  edgecell;

typedef edgecell * vertices[N];

typedef struct{
  int vertex_num;
  int edge_num;
  vertices vtop;
}graph;

int read_adjacency_matrix(char *datafile, adjmatrix mat){
  FILE *fp;
  int vertex_num;
  vindex src, dest;

  fp = fopen( datafile, "r" );
  fscanf( fp, "%d\n", &vertex_num );
  if( vertex_num > N ){
    fprintf(stderr, "##### このプログラムが扱えるのは頂点数が%dまでのグラフです\n", N);
    exit(1);
  }
  for (src = 0; src < vertex_num; src++){
    for(dest = 0; dest < vertex_num; dest++){
      fscanf( fp, "%d\n", &mat[src][dest] );
    }
  }
  fclose( fp );
  return vertex_num;
}

void add_edge(graph *g, vindex src, vindex dest){
  edgecell *edge = (edgecell *)malloc(sizeof(edgecell));
  edge->destination = dest;
  edge->next = g->vtop[src];
  g->vtop[src] = edge;
}

void translate_into_graph(adjmatrix mat, graph *g){
  vindex i,j;
  for(i = 0; i < g->vertex_num; i++){
    g->vtop[i] = NULL;
  }
  
  for(i = 0; i < g->vertex_num; i++){
    for(j = 0; j < g->vertex_num; j++){
      if (mat[i][j] == 1)
	add_edge(g, i, j);
    }
  }
}

void find_path(adjmatrix mat, graph *g){
  vindex src = 0, dest = 0, dest2 = 0, x = 0, y = 0, z = 0;
  vindex A[g->vertex_num][g->vertex_num], B[g->vertex_num][g->vertex_num], C[g->vertex_num][g->vertex_num];
  A[src][dest] = 0;
  B[src][dest2] = mat[src][dest];
  C[dest2][dest] = mat[src][dest];

  for(x = 0; x < g->vertex_num; x++){
    for(src = 0; src < g->vertex_num; src++){
      for(dest = 0; dest < g->vertex_num; dest++){
	for(dest2 = 0; dest2 < g->vertex_num; dest2++){
	  A[src][dest] += B[src][dest2] * C[dest2][dest];
	  B[src][dest2] = A[src][dest];
	}
      }
    }
  }

  for(y = 0; y < g->vertex_num; y++){
    if(A[y][y] == 1){
      z++;
    }
  }

  if(z == g->vertex_num){
    printf("強連結です\n");
  }

  else{
    printf("強連結ではありません\n");
  }
}

void print_graph(graph *g){
  vindex v;
  printf("digraph G {\n");
  printf("  size=\"14,10\"; node[fontsize=10,height=0.01,width=0.01]; edge[len=3.0];\n");
  for(v = 0; v < g->vertex_num; v++){
    edgecell *edge;
    for(edge = g->vtop[v]; edge != NULL; edge = edge->next){
      printf("  %d -> %d;\n", v+1, edge->destination+1);
    }
  }
  printf("}\n");
}

void free_graph(graph *g){
  vindex v;
  for (v = 0; v < g->vertex_num; v++){
    edgecell *edge, *next_edge;
    for(edge = g->vtop[v]; edge != NULL; edge = next_edge){
      next_edge = edge->next;
      free( edge );
    }
  }
}

int main( int argc, char *argv[] ){
  char *datafile;
  adjmatrix a;
  graph g;

  if ( argc <= 1 ){
    fprintf( stderr, "##### ファイルを指定してください\n");
    return 1;
  }
  datafile = argv[1];
  g.vertex_num = read_adjacency_matrix( datafile, a );
  translate_into_graph( a, &g );
  find_path( a, &g );
  free_graph( &g );
  return 0;
}

補足情報（FW/ツールのバージョンなど）

C言語、Cygwin64

Comments

[jimbe]

ご提示の例のデータはどのようなファイルになっているのでしょうか。
そして、そのファイルを処理する場合、 find_path 内においてそのデータが各変数内でどのように変化していき、どの行の段階でどの変数がどのような値になっているはずが、実際にはどのような値になっているのでしょうか。

[退会済みユーザー]

datファイルの内容は、上の例は
10
0 0 1 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 1
1 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0

下の例は
10
0 0 1 1 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 1 0
1 1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
0 1 0 1 0 0 0 0 0 0

となっています。
最終的にどちらの例とも z = 10となるはずが、上の例は3、下の例は5となっています。

[jimbe]

アルゴリズムは全く分からないのですが、2次元配列 C が値を入れずに使用していますが、式は合っているのでしょうか。

[退会済みユーザー]

具体的にどういうことでしょうか？

[jimbe]

計算毎に各配列の値を表示するようにして確認しては如何でしょうか。

Answer 1

チエブクロに同じコードの質問が載っています。

https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q14138814419

見た所、 z++ する if 文の条件式が異なるようです。

---

各配列の表示関数(printMat,print10x10)を作って find_path の計算の前後で表示してみては如何でしょう。
想定した値が表示されるでしょうか。

void printMat(int a[N][N]) {
  printf("mat -----\n");
  for(int i=0; i<10; i++) {
    for(int j=0; j<10; j++) {
      printf(",%d"+(j==0?1:0),a[i][j]);
    }
    printf("\n");
  }
}
void print10x10(char *prompt, int a[10][10]) {
  printf("%s -----\n",prompt);
  for(int i=0; i<10; i++) {
    for(int j=0; j<10; j++) {
      printf(",%d"+(j==0?1:0),a[i][j]);
    }
    printf("\n");
  }
}
void find_path(adjmatrix mat, graph *g){
  vindex src = 0, dest = 0, dest2 = 0, x = 0, y = 0, z = 0;
  vindex A[g->vertex_num][g->vertex_num], B[g->vertex_num][g->vertex_num], C[g->vertex_num][g->vertex_num];
  A[src][dest] = 0;
  B[src][dest2] = mat[src][dest];
  C[dest2][dest] = mat[src][dest];

  printf("g->vertex_num=%d\n",g->vertex_num);

  printMat(mat);
  print10x10("A",A);
  print10x10("B",B);
  print10x10("C",C);

  for(x = 0; x < g->vertex_num; x++){
    for(src = 0; src < g->vertex_num; src++){
      for(dest = 0; dest < g->vertex_num; dest++){
        for(dest2 = 0; dest2 < g->vertex_num; dest2++){
          A[src][dest] += B[src][dest2] * C[dest2][dest];
          B[src][dest2] = A[src][dest];
        }
      }
    }
  }

  print10x10("after A",A);

  for(y = 0; y < g->vertex_num; y++){
    if(A[y][y] >= 1){
      z++;
    }
  }

  printf("z=%d\n",z);

  if(z == g->vertex_num){
    printf("強連結です\n");
  }

  else{
    printf("強連結ではありません\n");
  }
}

---

ご質問本文のコードに単純に節毎にパスを探すコードを加えて、マクロ定義でオリジナルに戻せるように書き替えてみました。

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define TERATAIL371379

#ifdef TERATAIL371379
#include <memory.h>
#endif

#define N 100

#define boolean int
#define true 1
#define false 0
typedef boolean adjmatrix[N][N];

typedef int vindex;

typedef struct edgecell{
  vindex destination;
  struct edgecell *next;
}
  edgecell;

typedef edgecell * vertices[N];

typedef struct{
  int vertex_num;
  int edge_num;
  vertices vtop;
}graph;

int read_adjacency_matrix(char *datafile, adjmatrix mat){
  FILE *fp;
  int vertex_num;
  vindex src, dest;

  fp = fopen( datafile, "r" );
  fscanf( fp, "%d\n", &vertex_num );
  if( vertex_num > N ){
    fprintf(stderr, "##### このプログラムが扱えるのは頂点数が%dまでのグラフです\n", N);
    exit(1);
  }
  for (src = 0; src < vertex_num; src++){
    for(dest = 0; dest < vertex_num; dest++){
      fscanf( fp, "%d\n", &mat[src][dest] );
    }
  }
  fclose( fp );
  return vertex_num;
}

void add_edge(graph *g, vindex src, vindex dest){
  edgecell *edge = (edgecell *)malloc(sizeof(edgecell));
  edge->destination = dest;
  edge->next = g->vtop[src];
  g->vtop[src] = edge;
}

void translate_into_graph(adjmatrix mat, graph *g){
  vindex i,j;
  for(i = 0; i < g->vertex_num; i++){
    g->vtop[i] = NULL;
  }

  for(i = 0; i < g->vertex_num; i++){
    for(j = 0; j < g->vertex_num; j++){
      if (mat[i][j] == 1)
    add_edge(g, i, j);
    }
  }
}

#ifdef TERATAIL371379
//i から goal への経路を探す. 有ったら true
boolean find_path_sub(adjmatrix mat, int vertex_num, int goal, int i, boolean *treated) {
  if(mat[i][goal]) return true;

  treated[i] = true;
  for(int j=0; j<vertex_num; j++) {
    if(mat[i][j] && !treated[j]) {
      if(find_path_sub(mat,vertex_num,goal,j,treated)) return true;
    }
  }
  return false;
}

//mat のうち、 vertex_num × vertex_num の範囲の隣接行列がグラフとして強連結かを表示
void find_path(adjmatrix mat, int vertex_num) {
  int found = true;
  boolean treated[vertex_num];

  for(int i=0; i<vertex_num && found; i++) {
    found = false;
    memset(treated, false, sizeof(treated));
    for(int j=0; j<vertex_num && !found; j++) {
      if(mat[i][j]) {
        found = find_path_sub(mat,vertex_num,i,j,treated);
      }
    }
  }

  if(found) {
    printf("強連結です\n");
  } else {
    printf("強連結ではありません\n");
  }
}
#else
void find_path(adjmatrix mat, graph *g){
  vindex src = 0, dest = 0, dest2 = 0, x = 0, y = 0, z = 0;
  vindex A[g->vertex_num][g->vertex_num], B[g->vertex_num][g->vertex_num], C[g->vertex_num][g->vertex_num];
  A[src][dest] = 0;
  B[src][dest2] = mat[src][dest];
  C[dest2][dest] = mat[src][dest];

  for(x = 0; x < g->vertex_num; x++){
    for(src = 0; src < g->vertex_num; src++){
      for(dest = 0; dest < g->vertex_num; dest++){
    for(dest2 = 0; dest2 < g->vertex_num; dest2++){
      A[src][dest] += B[src][dest2] * C[dest2][dest];
      B[src][dest2] = A[src][dest];
    }
      }
    }
  }

  for(y = 0; y < g->vertex_num; y++){
    if(A[y][y] == 1){
      z++;
    }
  }

  if(z == g->vertex_num){
    printf("強連結です\n");
  }

  else{
    printf("強連結ではありません\n");
  }
}
#endif

void print_graph(graph *g){
  vindex v;
  printf("digraph G {\n");
  printf("  size=\"14,10\"; node[fontsize=10,height=0.01,width=0.01]; edge[len=3.0];\n");
  for(v = 0; v < g->vertex_num; v++){
    edgecell *edge;
    for(edge = g->vtop[v]; edge != NULL; edge = edge->next){
      printf("  %d -> %d;\n", v+1, edge->destination+1);
    }
  }
  printf("}\n");
}

void free_graph(graph *g){
  vindex v;
  for (v = 0; v < g->vertex_num; v++){
    edgecell *edge, *next_edge;
    for(edge = g->vtop[v]; edge != NULL; edge = next_edge){
      next_edge = edge->next;
      free( edge );
    }
  }
}

int main( int argc, char *argv[] ){
  char *datafile;
  adjmatrix a;
  graph g;

  if ( argc <= 1 ){
    fprintf( stderr, "##### ファイルを指定してください\n");
    return 1;
  }
  datafile = argv[1];
  //datafile = "371379sample1.dat"; //テスト用 ☆型

  g.vertex_num = read_adjacency_matrix( datafile, a );
  translate_into_graph( a, &g );

#ifdef TERATAIL371379
  find_path( a, g.vertex_num );
#else
  find_path( a, &g );
#endif

  free_graph( &g );
  return 0;
}

Comments

[退会済みユーザー]

その部分は修正しましたが、やはり正しく動かないようです。

[jimbe]

回答にデバッグ用コードの例を追加しました。
各変数の値が計算前後で想定通りの値になっているか確認してみてください。

[退会済みユーザー]

after Aではマイナスの値が多く、z++される条件であるA[y][y] >= 1を満たしているものが少ないことが分かりました。また、A[y][y] だとA[0][0], A[1][1], ... などと配列の全てを調べることができないように感じるのですが、他の部分を調べるにはどうすれば良いでしょうか。

[jimbe]

このアルゴリズムでマイナス値は出るものなのでしょうか。
そもそも、計算前でも A や B 、C にマイナスの値などが見られると思います(しかも実行する毎に違う値だったりします)が、それで良いのでしょうか?

z をカウントしている for で、 y の価は (vertex_num が 10 なら ) 0～9 となります。従って、 A[y][y] であれば A[0][0],A[1][1],…,A[8][8],A[9][9] の全 9 箇所、イメージ的には二次元配列の左上から右下への斜めの範囲を判定している事になります。
これは、そうなるように debcold さんが書かれたのではないのでしょうか?

[退会済みユーザー]

すみません、自分でもなぜマイナス値が出るのか分かりません。
そうなるように書いたのですが、全部を調べようとして二重ループにすると逆に多過ぎになってしまいます。

[jimbe]

確認したいのは、A,B,C 各2次元配列の計算前の各要素値は、どんな状態であるという前提のアルゴリズムなのかということです。
例えば A は全て 0 で B や C は mat の 10x10 範囲の値のコピーである…とかです。

プログラムはそのような前提も含めて書く必要があり、(表示してみて)前提と異なっているならば、前提をまず達成するコードを書くことがプログラムを作る上での基本です。

> 自分でもなぜマイナス値が出るのか分かりません。

c におきましての基本は、変数の宣言は場所の確保だけであり、中身は "不定" です。ですので、 A, B, C 各配列も最初は何が入っているか分かりません。 A でいいますと、 A[src][dest]=0 により、 src=0,dest=0 で A[0][0] だけは 0 となりますが、 A の他の 99 個の要素の値は以前 "不定" なままです。

> 全部を調べようとして二重ループにすると逆に多過ぎになってしまいます

何が「多過ぎ」になるのでしょうか。
そもそも A の各要素の値が "想定" 通りかどうか、というか "想定" そのものがされているのかも分かりませんが、とにかく計算の前提もコードとして達成できていなければ、結果をどう求めようとしても "想定" 通りにはならないでしょう。
どこかに出かけようとして、そもそも進む方向が間違っているのにいくら道を "想定" 通りに曲がったところで、目的には着けません。

[退会済みユーザー]

A は全て0, B,C は0または1のみで構成された10×10行列にしたいです。
Aは全て0にすることができましたが、B, C のイコールである mat[src][dest]を0,1のみにするにはどうすれば良いでしょうか。
多過ぎなのは「z」です。

[jimbe]

> B, C のイコールである mat[src][dest]を0,1のみにする

表現の意味するところがイメージ出来ません。
デバッグ用として入れて頂いた print10x10 の表示に基づいた場合、「Aは全て0にすることができました」ということは A は

A -----
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0

と表示されたのだと思います。
では、 B や C はどのように表示されたいのでしょうか。(☆型の例の場合で結構です。)

[退会済みユーザー]

グラフの上の例であればBは
0,0,0,0,1,0,1,1,1,1
1,1,1,1,1,0,0,0,1,0
1,1,1,1,1,0,1,1,1,1
1,0,0,0,1,1,1,1,1,1
1,0,0,0,1,0,1,0,1,0
1,1,1,0,1,0,0,0,0,0
0,0,0,1,1,0,1,0,1,0
0,0,0,0,1,1,1,0,0,0
0,0,0,0,0,0,1,0,0,0
1,1,0,0,0,0,0,0,0,0

Cは
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
1,1,0,0,0,0,0,0,0,0
1,1,0,0,0,0,0,0,0,0
0,0,1,1,1,1,1,1,1,0
1,1,0,0,0,0,0,0,0,0
1,0,1,0,1,0,1,0,0,0

と表示されるようにしたいです。所々では0,1のみになっているのですが、大きすぎる値なども表示されているため、そこの部分を0,1のみにしたいです。

[jimbe]

大分具体的になってきましたが、ご提示のデータは mat のデータとも大分異なりますね。
(B のほうが 11 列ありますけども ^^; )
恐らく mat を元にしてそうなると思うのですが、どうやったら求まるのでしょうか。

[退会済みユーザー]

printfして得られたB,Cを見て0でない部分を1に変えたものを提示しました。
BとCを掛けて単位行列の形になれば強連結と判定するようにしたいです。

[jimbe]

> printfして得られたB,Cを見て0でない部分を1に変えたものを提示しました
いえ、それは意味がありません。現状 B, C として表示されているものは、メモリに残っている "ゴミ" です。
必要なのは「アルゴリズム上での B と C の初期値」です。

[退会済みユーザー]

for文によりループを作るように書き換えるとBとCが0,1のみとなりました。
ここから最終的なAを単位行列にするにはどうすれば良いでしょうか。

[jimbe]

こちらには B, C がどのような値になったのか全く分かりませんが…。

何度も言いますが、私はこのアルゴリズムは分かりません。ですので、ABC 各変数にアルゴリズムの想定通りの初期値が設定されたのなら、後は計算結果がどうなのかは判断できません。
debcold さんご自身が、この課題がこのアルゴリズムで出来ると判断され、そのアルゴリズムを c で書いているはずです。
それが「どうすれば」とはどういうことでしょう。

[退会済みユーザー]

B -----
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
1,1,1,1,1,1,1,1,1,1
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
C -----
0,0,1,0,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0

となりました。これでは掛けても単位行列にならないのでこれらを掛けると単位行列になるようにしたいです。

for(src = 0; src < g->vertex_num; src++){
for(dest = 0; dest < g->vertex_num; dest++){
A[src][dest] = 0;
}
}

for(src = 0; src < g->vertex_num; src++){
for(dest2 = 0; dest2 < g->vertex_num; dest2++){
for(dest = 0; dest < g->vertex_num; dest++){
B[src][dest2] = mat[src][dest];
}
}
}

for(dest2 = 0; dest2 < g->vertex_num; dest2++){
for(dest = 0; dest < g->vertex_num; dest++){
for(src = 0; src < g->vertex_num; src++){
C[dest2][dest] = mat[src][dest];
}
}
}

コードを上のようにした結果BとCが上のようになったのですが、どこかまずい点はあるでしょうか。

[jimbe]

どうもお使いのアルゴリズムが分かりませんので、単純に探す形のサンプルコードを回答に追加致しました。

[退会済みユーザー]

ありがとうございます。これを読み込んだdatファイルに対して強連結判定をするようなプログラムにしたいのですが、どこを変更すれば良いでしょうか。
元のプログラムのread_adjacency_matrix()を使うことは分かっているのですが、それ以外には変更点はあるでしょうか。

[jimbe]

ご提示のコードを修正するとしますと、 find_path 関数を交換(上書き)し、 find_path_sub 関数を追加、 main 関数で find_path( a, &g ); としている所を find_path( a, g.vertex_num ); とする感じでしょうか。

[退会済みユーザー]

すみません、その通りにしたのですが「強連結です」も「強連結ではありません」も表示されなくなってしまいました。

[jimbe]

紛らわしい書き方をしてしまったかもしれません。
「ご提示のコード」というのは、 debcold さんのご質問本文の「該当のソースコード」のコードのことですが、間違っておられないでしょうか。

[退会済みユーザー]

はい、私が書いたコードにfind_path()の書き換え、find_path_sub()の追加、mainの書き換えを行った結果、「強連結です」も「強連結ではありません」も表示されません。

[jimbe]

find_path は無限ループしていなければ必ずどちらかが表示されますから、プログラムは正常終了したのに表示されないとすれば、find_path の呼び出しがされていないと思われます。
また状況をご説明頂くのも時間も掛かりそうですしご質問と離れてしまいますので、回答に追加したコードをご質問本文のコードを編集したものに差し替えました。

[退会済みユーザー]

出来ました！本当にありがとうございました！

[jimbe]

とりあえずは一安心ですが、 debcold さんのアルゴリズムの問題は全く分からないままです。
4 重ループで 3 つの行列(?)を使って判定する方法は、ネットのどこかに紹介されているでしょうか。ありましたら URL を教えて頂きたいのですが。

[退会済みユーザー]

https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q14138814419
このURL のものを参考にしたのですが、自分もよく分かっていません。

[jimbe]

つまり、アルゴリズムとしても動作するのか分からないものを動かそうとしていたということですね。今後ご質問されることがあれば、そのような「元にした情報」等はご質問に予め書いておいて頂けると手間が省けるかと思います。
かなり遠回りしてしまいましたが、リンク先のアルゴリズムは忘れたほうが良さそうです。
おつかれさまでした。