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 412 - (view) (download)

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

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