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/branches/SMLNJ/src/MLRISC/graphs/test5.sml
ViewVC logotype

Annotation of /sml/branches/SMLNJ/src/MLRISC/graphs/test5.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 409 - (view) (download)
Original Path: sml/trunk/src/MLRISC/graphs/test5.sml

1 : monnier 409 CM.make();
2 :    
3 :     (* page 556 in CLR *)
4 :     functor TestAllPairsShortestPaths(AP : ALL_PAIRS_SHORTEST_PATHS
5 :     where type Num.elem = int) =
6 :     struct
7 :     val G as Graph.GRAPH g = DirectedGraph.graph("foo",(),10) :
8 :     (string,int,unit) Graph.graph
9 :     val _ = app (#add_node g)
10 :     [(1,"1"),
11 :     (2,"2"),
12 :     (3,"3"),
13 :     (4,"4"),
14 :     (5,"5")
15 :     ]
16 :     val E = [(1,2,3),
17 :     (1,3,8),
18 :     (1,5,~4),
19 :     (2,4,1),
20 :     (2,5,7),
21 :     (3,2,4),
22 :     (4,1,2),
23 :     (4,3,~5),
24 :     (5,4,6)
25 :     ]
26 :     val _ = app (#add_edge g) E
27 :     (* val _ = app (fn (i,j,w) => #add_edge g (j,i,w)) E *)
28 :    
29 :     val dist' = [[0,1,~3,2,~4],
30 :     [3,0,~4,1,~1],
31 :     [7,4,0,5,3],
32 :     [2,~1,~5,0,~2],
33 :     [8,5,1,6,0]
34 :     ]
35 :     val pred' = [[~1,3,4,5,1],
36 :     [4,~1,4,2,1],
37 :     [4,3,~1,2,1],
38 :     [4,3,4,~1,1],
39 :     [4,3,4,5,~1]
40 :     ]
41 :    
42 :     fun toList M =
43 :     let val N = 5
44 :     fun f(i,j) = if j > N then [] else Array2.sub(M,i,j)::f(i,j+1)
45 :     fun g(i) = if i > N then [] else f(i,1)::g(i+1)
46 :     in g 1
47 :     end
48 :    
49 :     fun test() =
50 :     let fun weight(_,_,w) = w
51 :     val {dist,pred} = AP.all_pairs_shortest_paths {graph=G,weight=weight}
52 :     val dist=toList dist
53 :     val pred=toList pred
54 :     in if dist <> dist' orelse pred <> pred' then raise Match else ();
55 :     {dist=dist,pred=pred}
56 :     end
57 :    
58 :     end
59 :    
60 :     structure TestWarshall = TestAllPairsShortestPaths(
61 :     FloydWarshallFn(struct type elem = int
62 :     open Int
63 :     val zero = 0
64 :     val == : int * int -> bool = op =
65 :     val inf = 100000000
66 :     end))
67 :     structure TestJohnson = TestAllPairsShortestPaths(
68 :     JohnsonFn(struct type elem = int
69 :     open Int
70 :     val zero = 0
71 :     val == : int * int -> bool = op =
72 :     val inf = 100000000
73 :     end))

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