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/bellman-ford.sml
ViewVC logotype

Annotation of /MLRISC/trunk/graphs/bellman-ford.sml

Parent Directory Parent Directory | Revision Log Revision Log


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

1 : monnier 409 (*
2 :     * This module implements the Bellman Ford algorithm for single source
3 :     * shortest paths.
4 :     *
5 :     * -- Allen
6 :     *)
7 :    
8 :     functor BellmanFordFn(Num : ABELIAN_GROUP_WITH_INF) :
9 :     sig include SINGLE_SOURCE_SHORTEST_PATHS
10 :     exception NegativeCycle
11 :     end =
12 :     struct
13 :    
14 :     structure Num = Num
15 :     structure G = Graph
16 :     structure A = Array
17 :    
18 :     exception NegativeCycle
19 :    
20 :     fun single_source_shortest_paths {graph=G.GRAPH G,s,weight} =
21 :     let val N = #capacity G ()
22 :     val dist = A.array(N, Num.inf)
23 :     val pred = A.array(N, ~1)
24 :     val count = A.array(N, 0)
25 :     fun driver([],[]) = ()
26 :     | driver([],B) = driver(rev B,[])
27 :     | driver(u::A,B) = driver(iterate(u,A,B))
28 :     and iterate(u,A,B) =
29 :     let val n = Int.+(A.sub(count,u), 1)
30 :     val _ = A.update(count,u,n)
31 :     val _ = if n >= N then raise NegativeCycle else ()
32 :     val du = A.sub(dist,u)
33 :     fun relax([],A,B) = (A,B)
34 :     | relax((e as (_,v,_))::es,A,B) =
35 :     let val c = Num.+(du,weight e)
36 :     in if Num.<(c,A.sub(dist,v)) then
37 :     (A.update(dist,v,c); A.update(pred,v,u);
38 :     relax(es,A,v::B))
39 :     else relax(es,A,B)
40 :     end
41 :     in relax(#out_edges G u,A,B)
42 :     end
43 :     in A.update(dist,s,Num.zero);
44 :     driver([s],[]);
45 :     { dist = dist,
46 :     pred = pred
47 :     }
48 :     end
49 :     end
50 :    

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