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/graph-bfs.sml
ViewVC logotype

Annotation of /MLRISC/trunk/graphs/graph-bfs.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2126 - (view) (download)

1 : monnier 409 (*
2 :     * Breath first search.
3 :     *
4 :     * -- Allen
5 :     *)
6 :    
7 :     structure GraphBFS : GRAPH_BREATH_FIRST_SEARCH =
8 :     struct
9 :    
10 :     structure G = Graph
11 :     structure S = BitSet
12 :     structure A = Array
13 :    
14 :     (*
15 :     * Breath first search
16 :     *)
17 :     fun bfs (G.GRAPH G) f g roots =
18 :     let val visited = S.create(#capacity G ())
19 :     fun visit([],[]) = ()
20 :     | visit([],R) = visit(rev R,[])
21 :     | visit(n::L,R) = (f n; visitSucc(#out_edges G n,L,R))
22 :     and visitSucc([],L,R) = visit(L,R)
23 :     | visitSucc((e as (i,j,_))::es,L,R) =
24 :     if S.markAndTest(visited,j) then visitSucc(es,L,R)
25 :     else (g e; visitSucc(es,L,j::R))
26 :     and visitRoots([],L,R) = visit(L,R)
27 :     | visitRoots(n::ns,L,R) =
28 :     if S.markAndTest(visited,n) then visitRoots(ns,L,R)
29 :     else (f n; visitRoots(ns,L,n::R))
30 :     in visitRoots(roots,[],[])
31 :     end
32 :    
33 :     fun bfsdist (G.GRAPH G) roots =
34 :     let val N = #capacity G ()
35 :     val dist = A.array(N,~1)
36 :     fun visit([],[]) = ()
37 :     | visit([],R) = visit(rev R,[])
38 :     | visit(n::L,R) = visitSucc(#out_edges G n,L,R)
39 :     and visitSucc([],L,R) = visit(L,R)
40 :     | visitSucc((e as (i,j,_))::es,L,R) =
41 :     if A.sub(dist,j) >= 0 then visitSucc(es,L,R)
42 :     else (A.update(dist,j,A.sub(dist,i)+1); visitSucc(es,L,j::R))
43 :     and visitRoots([],L,R) = visit(L,R)
44 :     | visitRoots(n::ns,L,R) =
45 :     if A.sub(dist,n) >= 0 then visitRoots(ns,L,R)
46 :     else (A.update(dist,n,0); visitRoots(ns,L,n::R))
47 :     in visitRoots(roots,[],[]); dist end
48 :    
49 :     end

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