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/graph-bfs.sml
 [smlnj] / sml / trunk / src / MLRISC / graphs / graph-bfs.sml

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

 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