program dirgra(dirgrap, list, output); (* 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 *) label 1; (* end of program *) const (* begin module version *) 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 *) maxnodes = 50; (* maximum number of nodes + 1 that can be held *) maxlinks = 50; (* maximum number of links for each node. *) (* end module digra.const *) var dirgrap, list: text; (* files used by this program *) (* begin module halt *) procedure 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. *) begin writeln(output,' program halt.'); goto 1 end; (* end module halt version = 'delmod 6.16 84 mar 12 tds/gds'; *) (* begin module dirgra.themain *) procedure themain(var dirgrap, list: text); (* the main procedure of the program *) var firstnode: integer; (* start node number *) i: integer; (* index to iterations *) iterations: integer; (* number of traversals of the graph to do *) lastnode: integer; (* end node number *) n: integer; (* index to net nodes *) l: integer; (* index to net links *) net: array[0..maxnodes, 1..maxlinks] of integer; (* the net of links *) count: array[0..maxnodes, 1..maxlinks] of integer; (* number traversals *) links: array[0..maxnodes] of integer; (* number of links for each node *) node1, node2: integer; (* a directed segment goes from node 1 to node 2 *) nextnode: integer; (* next node chosen in the graph *) r: integer; (* randomly chosen link number *) steps: integer; (* total number of steps across the graph *) begin writeln(output,'dirgra ',version:4:2); rewrite(list); writeln(list,'dirgra ',version:4:2); (* clear the net *) for n := 0 to maxnodes do begin for l := 1 to maxlinks do begin net[n,l] := 0; count[n,l] := 0; end; links[n] := 0; end; (* read in the parameters and graph *) reset(dirgrap); readln(dirgrap, iterations); readln(dirgrap, firstnode, lastnode); if (firstnode < 0) or (lastnode < 0) then begin writeln(output,'first node and last node must be positive integers'); halt; end; while not eof(dirgrap) do begin readln(dirgrap,node1,node2); links[node1] := succ(links[node1]); net[node1,links[node1]] := node2 end; (* display the net *) writeln(list,'* first node: ',firstnode:1); writeln(list,'* last node: ',lastnode:1); writeln(list,'* Nodes:'); n := 0; while links[n] > 0 do begin write(list,'* ',n:1,' to: '); for l := 1 to links[n] do begin if l > 1 then write(list,','); write(list,' ',net[n,l]:1); end; writeln(list); n := succ(n); end; steps := 0; for i := 1 to iterations do begin writeln(output,'------ Iteration ',i:1,' ------'); n := firstnode; repeat (* chose next node *) r := trunc(links[n]*random(0)) + 1; nextnode := net[n,r]; write(output,'at ',n:1, ' with ',links[n]:1,' links; '); write(output,'chose number ',r:1,' so '); writeln(output,'next node is ',nextnode:1); count[n,r] := succ(count[n,r]); steps := succ(steps); n := nextnode until n = lastnode end; (* display the net *) writeln(list); writeln(list,'* Nodes with traversal counts and percentages:', ' for ',steps:1,' steps'); n := 0; while links[n] > 0 do begin write(list,'* ',n:1,' to: '); for l := 1 to links[n] do begin if l > 1 then write(list,','); write(list,' ',net[n,l]:1); write(list,' (',count[n,l]:1); write(list,', ',round(100*(count[n,l]/steps)):1,'%)') end; writeln(list); n := succ(n); end; end; (* end module dirgra.themain *) begin themain(dirgrap, list); 1: end.