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

Annotation of /sml/trunk/src/MLRISC/graphs/test4.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 714 - (view) (download)

1 : leunga 714 CM.make "../cm/Graphs.cm";
2 : monnier 409 functor TestShortestPaths(SP : SINGLE_SOURCE_SHORTEST_PATHS
3 :     where type Num.elem = int) =
4 :     struct
5 :     val G as Graph.GRAPH g = DirectedGraph.graph("foo",(),10) :
6 :     (string,int,unit) Graph.graph
7 :     val _ = app (#add_node g)
8 :     [(0,"s"),
9 :     (1,"u"),
10 :     (2,"v"),
11 :     (3,"x"),
12 :     (4,"y")
13 :     ]
14 :     val E = [(0,1,10),
15 :     (0,2,5),
16 :     (1,2,2),
17 :     (2,1,3),
18 :     (1,3,1),
19 :     (2,3,9),
20 :     (2,4,2),
21 :     (3,4,4),
22 :     (4,3,6),
23 :     (4,0,7)
24 :     ]
25 :     val _ = app (#add_edge g) E
26 :    
27 :     val dist' = [0,8,5,9,7]
28 :     val pred' = [~1,2,0,1,2]
29 :    
30 :     fun test() =
31 :     let fun weight(_,_,w) = w
32 :     val {dist,pred} = SP.single_source_shortest_paths
33 :     {graph=G,weight=weight,s=0}
34 :     val dist'' = Array.foldr op:: [] dist
35 :     val pred'' = Array.foldr op:: [] pred
36 :     in if dist' <> dist'' orelse pred' <> pred'' then
37 :     raise Match else ();
38 :     {dist=dist,pred=pred}
39 :     end
40 :    
41 :     end
42 :    
43 :     structure TestDijkstra = TestShortestPaths(
44 : george 545 Dijkstra(struct open Int
45 : monnier 409 type elem = int
46 :     val zero = 0
47 :     val inf = 10000000
48 :     val == : int * int -> bool = op=
49 :     end))
50 :     structure TestBellmanFord = TestShortestPaths(
51 : george 545 BellmanFord(struct open Int
52 : monnier 409 type elem = int
53 :     val zero = 0
54 :     val inf = 10000000
55 :     val == : int * int -> bool = op=
56 :     end))

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