Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/trunk/benchmarks/programs/tsp/main.sml
ViewVC logotype

Annotation of /sml/trunk/benchmarks/programs/tsp/main.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 193 - (view) (download)

1 : monnier 193 (* main.sml
2 :     *
3 :     * COPYRIGHT (c) 1994 AT&T Bell Laboratories.
4 :     *
5 :     *)
6 :    
7 :     structure Main : sig
8 :    
9 :     include BMARK
10 :    
11 :     val dumpPS : TextIO.outstream -> unit
12 :    
13 :     end = struct
14 :    
15 :     val name = "TSP"
16 :    
17 :     val problemSz = ref 32767
18 :     val divideSz = ref 150
19 :    
20 :     fun printLength (outS, Tree.NULL) = print "(* 0 points *)\n"
21 :     | printLength (outS, start as Tree.ND{next, x, y, ...}) = let
22 :     fun cycle (Tree.ND{next=next', ...}) = (next = next')
23 :     | cycle _ = false
24 :     fun distance (ax, ay, bx, by) = let
25 :     val dx = ax-bx and dy = ay-by
26 :     in
27 :     Math.sqrt (dx*dx + dy*dy)
28 :     end
29 :     fun length (Tree.NULL, px, py, n, len) = (n, len+distance(px, py, x, y))
30 :     | length (t as Tree.ND{x, y, next, ...}, px, py, n, len) =
31 :     if (cycle t)
32 :     then (n, len+distance(px, py, x, y))
33 :     else length(!next, x, y, n+1, len+distance(px, py, x, y))
34 :     in
35 :     if (cycle(!next))
36 :     then TextIO.output (outS, "(* 1 point *)\n")
37 :     else let
38 :     val (n, len) = length(!next, x, y, 1, 0.0)
39 :     in
40 :     TextIO.output (outS, concat[
41 :     "(* ", Int.toString n, "points, cycle length = ",
42 :     Real.toString len, " *)\n"
43 :     ])
44 :     end
45 :     end
46 :    
47 :     fun mkTree n = BuildTree.buildTree {
48 :     n=n, dir=BuildTree.X_AXIS,
49 :     min_x=0.0, max_x=1.0,
50 :     min_y=0.0, max_y=1.0
51 :     }
52 :    
53 :     fun doit' n = TSP.tsp (mkTree n, !divideSz)
54 :    
55 :     fun dumpPS outS = (
56 :     TextIO.output (outS, "newgraph\n");
57 :     TextIO.output (outS, "newcurve pts\n");
58 :     Tree.printList (outS, doit' (!problemSz));
59 :     TextIO.output (outS, "linetype solid\n"))
60 :    
61 :     fun testit strm = printLength (strm, doit' (!problemSz))
62 :    
63 :     fun doit () = ignore (doit' (!problemSz))
64 :    
65 :     end
66 :    

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0