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-is-cyclic.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/graphs/graph-is-cyclic.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 245 - (view) (download)
Original Path: sml/branches/SMLNJ/src/MLRISC/graphs/graph-is-cyclic.sml

1 : monnier 245 structure GraphIsCyclic : GRAPH_IS_CYCLIC =
2 :     struct
3 :    
4 :     structure G = Graph
5 :    
6 :     exception Cyclic
7 :    
8 :     (*
9 :     * Cyclic test
10 :     *)
11 :     fun is_cyclic (G.GRAPH G) =
12 :     let val N = #capacity G ()
13 :     val visited = BitSet.create N
14 :     val done = BitSet.create N
15 :     fun dfs i =
16 :     if BitSet.markAndTest(visited,i) then
17 :     if BitSet.contains(done,i) then ()
18 :     else raise Cyclic
19 :     else
20 :     (dfsSucc(#out_edges G i);
21 :     BitSet.set(done,i))
22 :     and dfs'(i,_) = dfs i
23 :     and dfsSucc [] = ()
24 :     | dfsSucc((_,j,_)::es) = (dfs j; dfsSucc es)
25 :     in
26 :     (#forall_nodes G dfs'; false) handle Cyclic => true
27 :     end
28 :    
29 :     end
30 :    
31 :     (*
32 :     * $Log$
33 :     *)

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