回答編集履歴

4

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

2021/11/30 02:38

投稿

jimbe
jimbe

スコア13209

test CHANGED
@@ -148,11 +148,7 @@
148
148
 
149
149
  ----
150
150
 
151
- すいませんが、アルゴリズム的に正しいのか間違っているのかが確認出来ませんので、単純に各節に対して戻ってこれるかを再帰で探す形のサンプルプログラムを作りました。
152
-
153
- ファイル読み込みやプロット部分は find_path は関係ありませんので、デ書きあり
151
+ ご質問本文コード単純に節毎にパスを探すコ加えて、マクロ定義でオリジナルに戻せるように書き替えした
154
-
155
- 現状で☆型の例で動作し、 #define SAMPLE2 のコメントを外すともう一方の例で動作します。
156
152
 
157
153
  ```c
158
154
 
@@ -160,8 +156,20 @@
160
156
 
161
157
  #include <stdlib.h>
162
158
 
159
+ #include <malloc.h>
160
+
161
+
162
+
163
+ #define TERATAIL371379
164
+
165
+
166
+
167
+ #ifdef TERATAIL371379
168
+
163
169
  #include <memory.h>
164
170
 
171
+ #endif
172
+
165
173
 
166
174
 
167
175
  #define N 100
@@ -178,9 +186,121 @@
178
186
 
179
187
 
180
188
 
189
+ typedef int vindex;
190
+
191
+
192
+
193
+ typedef struct edgecell{
194
+
195
+ vindex destination;
196
+
197
+ struct edgecell *next;
198
+
199
+ }
200
+
201
+ edgecell;
202
+
203
+
204
+
205
+ typedef edgecell * vertices[N];
206
+
207
+
208
+
209
+ typedef struct{
210
+
211
+ int vertex_num;
212
+
213
+ int edge_num;
214
+
215
+ vertices vtop;
216
+
217
+ }graph;
218
+
219
+
220
+
221
+ int read_adjacency_matrix(char *datafile, adjmatrix mat){
222
+
223
+ FILE *fp;
224
+
225
+ int vertex_num;
226
+
227
+ vindex src, dest;
228
+
229
+
230
+
231
+ fp = fopen( datafile, "r" );
232
+
233
+ fscanf( fp, "%d\n", &vertex_num );
234
+
235
+ if( vertex_num > N ){
236
+
237
+ fprintf(stderr, "##### このプログラムが扱えるのは頂点数が%dまでのグラフです\n", N);
238
+
239
+ exit(1);
240
+
241
+ }
242
+
243
+ for (src = 0; src < vertex_num; src++){
244
+
245
+ for(dest = 0; dest < vertex_num; dest++){
246
+
247
+ fscanf( fp, "%d\n", &mat[src][dest] );
248
+
249
+ }
250
+
251
+ }
252
+
253
+ fclose( fp );
254
+
255
+ return vertex_num;
256
+
257
+ }
258
+
259
+
260
+
261
+ void add_edge(graph *g, vindex src, vindex dest){
262
+
263
+ edgecell *edge = (edgecell *)malloc(sizeof(edgecell));
264
+
181
- //#define SAMPLE2
265
+ edge->destination = dest;
266
+
182
-
267
+ edge->next = g->vtop[src];
268
+
183
-
269
+ g->vtop[src] = edge;
270
+
271
+ }
272
+
273
+
274
+
275
+ void translate_into_graph(adjmatrix mat, graph *g){
276
+
277
+ vindex i,j;
278
+
279
+ for(i = 0; i < g->vertex_num; i++){
280
+
281
+ g->vtop[i] = NULL;
282
+
283
+ }
284
+
285
+
286
+
287
+ for(i = 0; i < g->vertex_num; i++){
288
+
289
+ for(j = 0; j < g->vertex_num; j++){
290
+
291
+ if (mat[i][j] == 1)
292
+
293
+ add_edge(g, i, j);
294
+
295
+ }
296
+
297
+ }
298
+
299
+ }
300
+
301
+
302
+
303
+ #ifdef TERATAIL371379
184
304
 
185
305
  //i から goal への経路を探す. 有ったら true
186
306
 
@@ -250,67 +370,167 @@
250
370
 
251
371
  }
252
372
 
373
+ #else
374
+
375
+ void find_path(adjmatrix mat, graph *g){
376
+
377
+ vindex src = 0, dest = 0, dest2 = 0, x = 0, y = 0, z = 0;
378
+
379
+ vindex A[g->vertex_num][g->vertex_num], B[g->vertex_num][g->vertex_num], C[g->vertex_num][g->vertex_num];
380
+
381
+ A[src][dest] = 0;
382
+
383
+ B[src][dest2] = mat[src][dest];
384
+
385
+ C[dest2][dest] = mat[src][dest];
386
+
387
+
388
+
389
+ for(x = 0; x < g->vertex_num; x++){
390
+
391
+ for(src = 0; src < g->vertex_num; src++){
392
+
393
+ for(dest = 0; dest < g->vertex_num; dest++){
394
+
395
+ for(dest2 = 0; dest2 < g->vertex_num; dest2++){
396
+
397
+ A[src][dest] += B[src][dest2] * C[dest2][dest];
398
+
399
+ B[src][dest2] = A[src][dest];
400
+
401
+ }
402
+
403
+ }
404
+
405
+ }
406
+
407
+ }
408
+
409
+
410
+
411
+ for(y = 0; y < g->vertex_num; y++){
412
+
413
+ if(A[y][y] == 1){
414
+
415
+ z++;
416
+
417
+ }
418
+
419
+ }
420
+
421
+
422
+
423
+ if(z == g->vertex_num){
424
+
425
+ printf("強連結です\n");
426
+
427
+ }
428
+
429
+
430
+
431
+ else{
432
+
433
+ printf("強連結ではありません\n");
434
+
435
+ }
436
+
437
+ }
438
+
439
+ #endif
440
+
441
+
442
+
443
+ void print_graph(graph *g){
444
+
445
+ vindex v;
446
+
447
+ printf("digraph G {\n");
448
+
449
+ printf(" size=\"14,10\"; node[fontsize=10,height=0.01,width=0.01]; edge[len=3.0];\n");
450
+
451
+ for(v = 0; v < g->vertex_num; v++){
452
+
453
+ edgecell *edge;
454
+
455
+ for(edge = g->vtop[v]; edge != NULL; edge = edge->next){
456
+
457
+ printf(" %d -> %d;\n", v+1, edge->destination+1);
458
+
459
+ }
460
+
461
+ }
462
+
463
+ printf("}\n");
464
+
465
+ }
466
+
467
+
468
+
469
+ void free_graph(graph *g){
470
+
471
+ vindex v;
472
+
473
+ for (v = 0; v < g->vertex_num; v++){
474
+
475
+ edgecell *edge, *next_edge;
476
+
477
+ for(edge = g->vtop[v]; edge != NULL; edge = next_edge){
478
+
479
+ next_edge = edge->next;
480
+
481
+ free( edge );
482
+
483
+ }
484
+
485
+ }
486
+
487
+ }
488
+
253
489
 
254
490
 
255
491
  int main( int argc, char *argv[] ){
256
492
 
493
+ char *datafile;
494
+
257
- adjmatrix adjmatrix = {
495
+ adjmatrix a;
496
+
258
-
497
+ graph g;
498
+
499
+
500
+
501
+ if ( argc <= 1 ){
502
+
503
+ fprintf( stderr, "##### ファイルを指定してください\n");
504
+
505
+ return 1;
506
+
507
+ }
508
+
509
+ datafile = argv[1];
510
+
511
+ //datafile = "371379sample1.dat"; //テスト用 ☆型
512
+
513
+
514
+
515
+ g.vertex_num = read_adjacency_matrix( datafile, a );
516
+
517
+ translate_into_graph( a, &g );
518
+
519
+
520
+
259
- #ifndef SAMPLE2
521
+ #ifdef TERATAIL371379
260
-
522
+
261
- {0,0,1,1,0,0,0,0,0,0},
523
+ find_path( a, g.vertex_num );
262
-
263
- {0,0,0,0,1,0,0,0,0,0},
264
-
265
- {0,0,0,0,1,1,0,0,0,0},
266
-
267
- {0,0,0,0,0,0,1,0,0,0},
268
-
269
- {0,0,0,0,0,0,1,1,0,0},
270
-
271
- {0,0,0,0,0,0,0,0,1,0},
272
-
273
- {0,0,0,0,0,0,0,0,1,1},
274
-
275
- {1,0,0,0,0,0,0,0,0,0},
276
-
277
- {1,1,0,0,0,0,0,0,0,0},
278
-
279
- {0,0,1,0,0,0,0,0,0,0},
280
524
 
281
525
  #else
282
526
 
283
- {0,0,1,1,0,0,0,0,0,0},
527
+ find_path( a, &g );
284
-
285
- {0,0,0,0,1,1,0,0,0,0},
286
-
287
- {0,0,0,0,1,0,0,0,0,0},
288
-
289
- {0,0,0,0,0,0,0,1,0,0},
290
-
291
- {0,0,0,0,0,0,1,0,0,0},
292
-
293
- {0,0,0,0,0,0,0,1,0,1},
294
-
295
- {0,0,0,0,0,0,0,0,1,0},
296
-
297
- {1,1,0,0,0,0,0,0,0,0},
298
-
299
- {1,0,0,0,0,0,0,0,0,0},
300
-
301
- {0,1,0,1,0,0,0,0,0,0},
302
528
 
303
529
  #endif
304
530
 
305
- };
531
+
306
-
532
+
307
- int vertex_num = 10;
533
+ free_graph( &g );
308
-
309
-
310
-
311
- find_path(adjmatrix, vertex_num);
312
-
313
-
314
534
 
315
535
  return 0;
316
536
 

3

脱字

2021/11/30 02:38

投稿

jimbe
jimbe

スコア13209

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

2

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

2021/11/29 13:13

投稿

jimbe
jimbe

スコア13209

test CHANGED
@@ -145,3 +145,175 @@
145
145
  }
146
146
 
147
147
  ```
148
+
149
+ ----
150
+
151
+ すいませんが、アルゴリズム的に正しいのか間違っているのかが確認出来ませんので、単純に各節に対して戻ってこれるかを再帰で探す形のサンプルプログラムを作りました。
152
+
153
+ ファイル読み込みやプロットの部分は find_path には関係ありませんので、データを直書きしてあります。
154
+
155
+ 現状で☆型の例で動作し、 #define SAMPLE2 のコメントを外すともう一方の例で動作します。
156
+
157
+ ```c
158
+
159
+ #include <stdio.h>
160
+
161
+ #include <stdlib.h>
162
+
163
+ #include <memory.h>
164
+
165
+
166
+
167
+ #define N 100
168
+
169
+
170
+
171
+ #define boolean int
172
+
173
+ #define true 1
174
+
175
+ #define false 0
176
+
177
+ typedef boolean adjmatrix[N][N];
178
+
179
+
180
+
181
+ //#define SAMPLE2
182
+
183
+
184
+
185
+ //i から goal への経路を探す. 有ったら true
186
+
187
+ boolean find_path_sub(adjmatrix mat, int vertex_num, int goal, int i, boolean *treated) {
188
+
189
+ if(mat[i][goal]) return true;
190
+
191
+
192
+
193
+ treated[i] = true;
194
+
195
+ for(int j=0; j<vertex_num; j++) {
196
+
197
+ if(mat[i][j] && !treated[j]) {
198
+
199
+ if(find_path_sub(mat,vertex_num,goal,j,treated)) return true;
200
+
201
+ }
202
+
203
+ }
204
+
205
+ return false;
206
+
207
+ }
208
+
209
+
210
+
211
+ //mat のうち、 vertex_num × vertex_num の範囲の隣接行列が強連結を表示
212
+
213
+ void find_path(adjmatrix mat, int vertex_num) {
214
+
215
+ int found = true;
216
+
217
+ boolean treated[vertex_num];
218
+
219
+
220
+
221
+ for(int i=0; i<vertex_num && found; i++) {
222
+
223
+ found = false;
224
+
225
+ memset(treated, false, sizeof(treated));
226
+
227
+ for(int j=0; j<vertex_num && !found; j++) {
228
+
229
+ if(mat[i][j]) {
230
+
231
+ found = find_path_sub(mat,vertex_num,i,j,treated);
232
+
233
+ }
234
+
235
+ }
236
+
237
+ }
238
+
239
+
240
+
241
+ if(found) {
242
+
243
+ printf("強連結です\n");
244
+
245
+ } else {
246
+
247
+ printf("強連結ではありません\n");
248
+
249
+ }
250
+
251
+ }
252
+
253
+
254
+
255
+ int main( int argc, char *argv[] ){
256
+
257
+ adjmatrix adjmatrix = {
258
+
259
+ #ifndef SAMPLE2
260
+
261
+ {0,0,1,1,0,0,0,0,0,0},
262
+
263
+ {0,0,0,0,1,0,0,0,0,0},
264
+
265
+ {0,0,0,0,1,1,0,0,0,0},
266
+
267
+ {0,0,0,0,0,0,1,0,0,0},
268
+
269
+ {0,0,0,0,0,0,1,1,0,0},
270
+
271
+ {0,0,0,0,0,0,0,0,1,0},
272
+
273
+ {0,0,0,0,0,0,0,0,1,1},
274
+
275
+ {1,0,0,0,0,0,0,0,0,0},
276
+
277
+ {1,1,0,0,0,0,0,0,0,0},
278
+
279
+ {0,0,1,0,0,0,0,0,0,0},
280
+
281
+ #else
282
+
283
+ {0,0,1,1,0,0,0,0,0,0},
284
+
285
+ {0,0,0,0,1,1,0,0,0,0},
286
+
287
+ {0,0,0,0,1,0,0,0,0,0},
288
+
289
+ {0,0,0,0,0,0,0,1,0,0},
290
+
291
+ {0,0,0,0,0,0,1,0,0,0},
292
+
293
+ {0,0,0,0,0,0,0,1,0,1},
294
+
295
+ {0,0,0,0,0,0,0,0,1,0},
296
+
297
+ {1,1,0,0,0,0,0,0,0,0},
298
+
299
+ {1,0,0,0,0,0,0,0,0,0},
300
+
301
+ {0,1,0,1,0,0,0,0,0,0},
302
+
303
+ #endif
304
+
305
+ };
306
+
307
+ int vertex_num = 10;
308
+
309
+
310
+
311
+ find_path(adjmatrix, vertex_num);
312
+
313
+
314
+
315
+ return 0;
316
+
317
+ }
318
+
319
+ ```

1

デバッグ例コード追加

2021/11/29 13:10

投稿

jimbe
jimbe

スコア13209

test CHANGED
@@ -7,3 +7,141 @@
7
7
 
8
8
 
9
9
  見た所、 z++ する if 文の条件式が異なるようです。
10
+
11
+
12
+
13
+ ----
14
+
15
+
16
+
17
+ 各配列の表示関数(printMat,print10x10)を作って find_path の計算の前後で表示してみては如何でしょう。
18
+
19
+ 想定した値が表示されるでしょうか。
20
+
21
+
22
+
23
+ ```c
24
+
25
+ void printMat(int a[N][N]) {
26
+
27
+ printf("mat -----\n");
28
+
29
+ for(int i=0; i<10; i++) {
30
+
31
+ for(int j=0; j<10; j++) {
32
+
33
+ printf(",%d"+(j==0?1:0),a[i][j]);
34
+
35
+ }
36
+
37
+ printf("\n");
38
+
39
+ }
40
+
41
+ }
42
+
43
+ void print10x10(char *prompt, int a[10][10]) {
44
+
45
+ printf("%s -----\n",prompt);
46
+
47
+ for(int i=0; i<10; i++) {
48
+
49
+ for(int j=0; j<10; j++) {
50
+
51
+ printf(",%d"+(j==0?1:0),a[i][j]);
52
+
53
+ }
54
+
55
+ printf("\n");
56
+
57
+ }
58
+
59
+ }
60
+
61
+ void find_path(adjmatrix mat, graph *g){
62
+
63
+ vindex src = 0, dest = 0, dest2 = 0, x = 0, y = 0, z = 0;
64
+
65
+ vindex A[g->vertex_num][g->vertex_num], B[g->vertex_num][g->vertex_num], C[g->vertex_num][g->vertex_num];
66
+
67
+ A[src][dest] = 0;
68
+
69
+ B[src][dest2] = mat[src][dest];
70
+
71
+ C[dest2][dest] = mat[src][dest];
72
+
73
+
74
+
75
+ printf("g->vertex_num=%d\n",g->vertex_num);
76
+
77
+
78
+
79
+ printMat(mat);
80
+
81
+ print10x10("A",A);
82
+
83
+ print10x10("B",B);
84
+
85
+ print10x10("C",C);
86
+
87
+
88
+
89
+ for(x = 0; x < g->vertex_num; x++){
90
+
91
+ for(src = 0; src < g->vertex_num; src++){
92
+
93
+ for(dest = 0; dest < g->vertex_num; dest++){
94
+
95
+ for(dest2 = 0; dest2 < g->vertex_num; dest2++){
96
+
97
+ A[src][dest] += B[src][dest2] * C[dest2][dest];
98
+
99
+ B[src][dest2] = A[src][dest];
100
+
101
+ }
102
+
103
+ }
104
+
105
+ }
106
+
107
+ }
108
+
109
+
110
+
111
+ print10x10("after A",A);
112
+
113
+
114
+
115
+ for(y = 0; y < g->vertex_num; y++){
116
+
117
+ if(A[y][y] >= 1){
118
+
119
+ z++;
120
+
121
+ }
122
+
123
+ }
124
+
125
+
126
+
127
+ printf("z=%d\n",z);
128
+
129
+
130
+
131
+ if(z == g->vertex_num){
132
+
133
+ printf("強連結です\n");
134
+
135
+ }
136
+
137
+
138
+
139
+ else{
140
+
141
+ printf("強連結ではありません\n");
142
+
143
+ }
144
+
145
+ }
146
+
147
+ ```