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 /MLRISC/trunk/graphs/floyd-warshall.sml
ViewVC logotype

Annotation of /MLRISC/trunk/graphs/floyd-warshall.sml

Parent Directory Parent Directory | Revision Log Revision Log


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

1 : monnier 409 (*
2 :     * This module implements the Floyd/Warshall algorithm for computing
3 :     * all pairs shortest paths.
4 :     *
5 :     * -- Allen
6 :     *)
7 :    
8 :     functor FloydWarshallFn(Num : ABELIAN_GROUP_WITH_INF)
9 :     : ALL_PAIRS_SHORTEST_PATHS =
10 :     struct
11 :    
12 :     structure Num = Num
13 :     structure G = Graph
14 :     structure A = Array2
15 :    
16 :     fun all_pairs_shortest_paths{graph=G.GRAPH G,weight} =
17 :     let val N = #capacity G ()
18 :     val D = A.array(N,N,Num.inf)
19 :     val P = A.array(N,N,~1)
20 :     fun init() =
21 :     let fun diag ~1 = ()
22 :     | diag i = (A.update(D,i,i,Num.zero); diag(i-1))
23 :     in diag(N-1);
24 :     #forall_edges G (fn e as (i,j,_) =>
25 :     let val w = weight e
26 :     in if Num.<(w,A.sub(D,i,j)) then
27 :     (A.update(P,i,j,i); A.update(D,i,j,w))
28 :     else ()
29 :     end)
30 :     end
31 :     fun l1(k) = if k < N then (l2(k,0); l1(k+1)) else ()
32 :     and l2(k,i) = if i < N then (l3(k,i,0,A.sub(D,i,k)); l2(k,i+1)) else ()
33 :     and l3(k,i,j,d_ik) = if j < N then
34 :     let val d_ij = A.sub(D,i,j)
35 :     val d_kj = A.sub(D,k,j)
36 :     val x = Num.+(d_ik,d_kj)
37 :     in if Num.<(x,d_ij) then
38 :     (A.update(P,i,j,A.sub(P,k,j)); A.update(D,i,j,x))
39 :     else ();
40 :     l3(k,i,j+1,d_ik)
41 :     end else ()
42 :     in init();
43 :     l1(0);
44 :     {dist=D,pred=P}
45 :     end
46 :     end

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