/* Output from p2c 1.21alpha-07.Dec.93, the Pascal-to-C translator */ /* From input file "dirgra.p" */ #include /* dirgra: directed graph Monte Carlo analysis Tom Schneider NCI/FCRDC Bldg 469. Room 144 P.O. Box B Frederick, MD 21702-1201 (301) 846-5581 (-5532 for messages) network address: toms@ncifcrf.gov National Cancer Institute Laboratory of Mathematical Biology 1994 */ /* end of program */ /* begin module version */ #define version 1.06 /* of dirgra.p 1995 March 28 origin 1994 Dec 26, Mon Dec 26 18:10:03 EST 1994 start Mon Dec 26 18:58:55 EST 1994 reads graph and writes it out correctly Mon Dec 26 20:13:21 EST 1994 run with 10000 iterations on a Sun Sparcstation 20/61 this took 21.5 seconds. */ /* end module version */ /* begin module describe.dirgra */ /* name dirgra: directed graph Monte Carlo analysis synopsis dirgra(dirgrap, list: in, output: out) files dirgrap: Parameters to control the program first line: number of iterations to perform second line: numbers of the first and the last node in the net. later lines: each line contains two numbers that define the graph links. list: analysis of the graph output: messages to the user description Do a Monte Carlo flow analysis of a directed graph examples The following dirgrap defines Figure 1 of Adleman1994: 60000 number of iterations to perform 0 6 numbers of the first and last nodes 0 3 0 1 0 6 1 2 1 3 2 3 2 1 3 2 3 4 4 1 4 5 5 1 5 2 5 6 and gives this list file as a result: dirgra 1.06 * first node: 0 * last node: 6 * Nodes: * 0 to: 3, 1, 6 * 1 to: 2, 3 * 2 to: 3, 1 * 3 to: 2, 4 * 4 to: 1, 5 * 5 to: 1, 2, 6 * Nodes with traversal counts and percentages: for 1811570 steps * 0 to: 3 (19981, 1%), 1 (19932, 1%), 6 (20087, 1%) * 1 to: 2 (212247, 12%), 3 (212948, 12%) * 2 to: 3 (244654, 14%), 1 (245891, 14%) * 3 to: 2 (238613, 13%), 4 (238970, 13%) * 4 to: 1 (119693, 7%), 5 (119277, 7%) * 5 to: 1 (39679, 2%), 2 (39685, 2%), 6 (39913, 2%) documentation @article{Adleman1994, author = "L. M. Adleman", title = "Molecular Computation of Solutions to Combinatorial Problems", journal = "Science", volume = "266", pages = "1021-1024", year = "1994"} see also author Thomas Dana Schneider bugs technical notes maxnodes and maxlinks are constants that define the maximum number of nodes and links the program can handle. The program records nodes and links in an array for speed. The non-standard random(0) function is used to generate random numbers. It is expected to give pseudo random numbers in the range 0 to 1. */ /* end module describe.dirgra */ /* begin module digra.const */ #define maxnodes 50 /* maximum number of nodes + 1 that can be held */ #define maxlinks 50 /* maximum number of links for each node. */ /* end module digra.const */ Static _TEXT dirgrap, list; /* files used by this program */ Static jmp_buf _JL1; /* begin module halt */ Static Void halt() { /* stop the program. the procedure performs a goto to the end of the program. you must have a label: label 1; declared, and also the end of the program must have this label: 1: end. examples are in the module libraries. this is the only goto in the delila system. */ printf(" program halt.\n"); longjmp(_JL1, 1); } /* end module halt version = 'delmod 6.16 84 mar 12 tds/gds'; */ /* begin module dirgra.themain */ Static Void themain(dirgrap, list) _TEXT *dirgrap, *list; { /* the main procedure of the program */ long firstnode; /* start node number */ long i; /* index to iterations */ long iterations; /* number of traversals of the graph to do */ long lastnode; /* end node number */ long n; /* index to net nodes */ long l; /* index to net links */ long net[maxnodes + 1][maxlinks]; /* the net of links */ long count[maxnodes + 1][maxlinks]; /* number traversals */ long links[maxnodes + 1]; /* number of links for each node */ long node1, node2; /* a directed segment goes from node 1 to node 2 */ long nextnode; /* next node chosen in the graph */ long r; /* randomly chosen link number */ long steps = 0; /* total number of steps across the graph */ long FORLIM; printf("dirgra %4.2f\n", version); if (*list->name != '\0') { if (list->f != NULL) list->f = freopen(list->name, "w", list->f); else list->f = fopen(list->name, "w"); } else { if (list->f != NULL) rewind(list->f); else list->f = tmpfile(); } if (list->f == NULL) _EscIO2(FileNotFound, list->name); SETUPBUF(list->f, Char); fprintf(list->f, "dirgra %4.2f\n", version); /* clear the net */ for (n = 0; n <= maxnodes; n++) { for (l = 0; l < maxlinks; l++) { net[n][l] = 0; count[n][l] = 0; } links[n] = 0; } /* read in the parameters and graph */ if (*dirgrap->name != '\0') { if (dirgrap->f != NULL) dirgrap->f = freopen(dirgrap->name, "r", dirgrap->f); else dirgrap->f = fopen(dirgrap->name, "r"); } else rewind(dirgrap->f); if (dirgrap->f == NULL) _EscIO2(FileNotFound, dirgrap->name); RESETBUF(dirgrap->f, Char); fscanf(dirgrap->f, "%ld%*[^\n]", &iterations); getc(dirgrap->f); fscanf(dirgrap->f, "%ld%ld%*[^\n]", &firstnode, &lastnode); getc(dirgrap->f); if (firstnode < 0 || lastnode < 0) { printf("first node and last node must be positive integers\n"); halt(); } while (!BUFEOF(dirgrap->f)) { fscanf(dirgrap->f, "%ld%ld%*[^\n]", &node1, &node2); getc(dirgrap->f); links[node1]++; net[node1][links[node1] - 1] = node2; } /* display the net */ fprintf(list->f, "* first node: %ld\n", firstnode); fprintf(list->f, "* last node: %ld\n", lastnode); fprintf(list->f, "* Nodes:\n"); n = 0; while (links[n] > 0) { fprintf(list->f, "* %ld to: ", n); FORLIM = links[n]; for (l = 1; l <= FORLIM; l++) { if (l > 1) putc(',', list->f); fprintf(list->f, " %ld", net[n][l-1]); } putc('\n', list->f); n++; } for (i = 1; i <= iterations; i++) { printf("------ Iteration %ld ------\n", i); n = firstnode; do { /* chose next node */ r = (long)((double)(links[n] * _randint(0L))) + 1; nextnode = net[n][r-1]; printf("at %ld with %ld links; ", n, links[n]); printf("chose number %ld so ", r); printf("next node is %ld\n", nextnode); count[n][r-1]++; steps++; n = nextnode; } while (n != lastnode); } /* display the net */ fprintf(list->f, "\n* Nodes with traversal counts and percentages: for %ld steps\n", steps); n = 0; while (links[n] > 0) { fprintf(list->f, "* %ld to: ", n); FORLIM = links[n]; for (l = 1; l <= FORLIM; l++) { if (l > 1) putc(',', list->f); fprintf(list->f, " %ld", net[n][l-1]); fprintf(list->f, " (%ld", count[n][l-1]); fprintf(list->f, ", %ld%%)", (long)floor(100 * ((double)count[n][l-1] / steps) + 0.5)); } putc('\n', list->f); n++; } } /* end module dirgra.themain */ main(argc, argv) int argc; Char *argv[]; { PASCAL_MAIN(argc, argv); if (setjmp(_JL1)) goto _L1; list.f = NULL; strcpy(list.name, "list"); dirgrap.f = NULL; strcpy(dirgrap.name, "dirgrap"); themain(&dirgrap, &list); _L1: if (dirgrap.f != NULL) fclose(dirgrap.f); if (list.f != NULL) fclose(list.f); exit(EXIT_SUCCESS); } /* End. */