Annotation of /MLRISC/trunk/graphs/test5.sml

Parent Directory | Revision Log

---

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

1 :	monnier	429	CM.make "sources.cm";
2 :	monnier	409
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 :	george	545	FloydWarshall(struct type elem = int
62 :	monnier	409	open Int
63 :			val zero = 0
64 :			val == : int * int -> bool = op =
65 :			val inf = 100000000
66 :			end))
67 :			structure TestJohnson = TestAllPairsShortestPaths(
68 :	george	545	Johnson(struct type elem = int
69 :	monnier	409	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