編集履歴

回答編集履歴

サンプルコードを書き換え

2021/11/30 02:38

投稿

スコア12639

test CHANGED Viewed

@@ -148,11 +148,7 @@
 ----
-すいませんが、アルゴリズム的に正しいのか間違っているのかが確認出来ませんので、単純に各節に対して戻ってこれるかを再帰で探す形のサンプルプログラムを作りました。
-ファイル読み込みやプロットの部分は find_path には関係ありませんので、データを直書きしてあります。
+ご質問本文のコードに単純に節毎にパスを探すコードを加えて、マクロ定義でオリジナルに戻せるように書き替えてみました。
-現状で☆型の例で動作し、 #define SAMPLE2 のコメントを外すともう一方の例で動作します。
 ```c
@@ -160,8 +156,20 @@
 #include <stdlib.h>
+#include <malloc.h>
+#define TERATAIL371379
+#ifdef TERATAIL371379
 #include <memory.h>
+#endif
 #define N 100
@@ -178,9 +186,121 @@
+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));
-//#define SAMPLE2
+  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
@@ -250,67 +370,167 @@
 }
+#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 adjmatrix = {
+  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 );
-#ifndef SAMPLE2
+#ifdef TERATAIL371379
-      {0,0,1,1,0,0,0,0,0,0},
+  find_path( a, g.vertex_num );
-      {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},
 #else
-      {0,0,1,1,0,0,0,0,0,0},
+  find_path( a, &g );
-      {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},
 #endif
-  };
-  int vertex_num = 10;
+  free_graph( &g );
-  find_path(adjmatrix, vertex_num);
   return 0;

脱字

2021/11/30 02:38

投稿

jimbe

スコア12639

test CHANGED Viewed

@@ -208,7 +208,7 @@
-//mat のうち、 vertex_num × vertex_num の範囲の隣接行列が強連結を表示
+//mat のうち、 vertex_num × vertex_num の範囲の隣接行列がグラフとして強連結かを表示
 void find_path(adjmatrix mat, int vertex_num) {

再帰で探すサンプルコードを追加

2021/11/29 13:13

投稿

jimbe

スコア12639

test CHANGED Viewed

@@ -145,3 +145,175 @@
 }
 ```
+----
+すいませんが、アルゴリズム的に正しいのか間違っているのかが確認出来ませんので、単純に各節に対して戻ってこれるかを再帰で探す形のサンプルプログラムを作りました。
+ファイル読み込みやプロットの部分は find_path には関係ありませんので、データを直書きしてあります。
+現状で☆型の例で動作し、 #define SAMPLE2 のコメントを外すともう一方の例で動作します。
+```c
+#include <stdio.h>
+#include <stdlib.h>
+#include <memory.h>
+#define N 100
+#define boolean int
+#define true 1
+#define false 0
+typedef boolean adjmatrix[N][N];
+//#define SAMPLE2
+//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");
+  }
+}
+int main( int argc, char *argv[] ){
+  adjmatrix adjmatrix = {
+#ifndef SAMPLE2
+      {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},
+#else
+      {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},
+#endif
+  };
+  int vertex_num = 10;
+  find_path(adjmatrix, vertex_num);
+  return 0;
+}
+```

デバッグ例コード追加

2021/11/29 13:10

投稿

jimbe

スコア12639

test CHANGED Viewed

@@ -7,3 +7,141 @@
 見た所、 z++ する if 文の条件式が異なるようです。
+----
+各配列の表示関数(printMat,print10x10)を作って find_path の計算の前後で表示してみては如何でしょう。
+想定した値が表示されるでしょうか。
+```c
+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");
+  }
+}
+```