Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] View of /sml/trunk/src/MLRISC/graphs/graph-is-cyclic.sml
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log

Revision 412 - (download) (annotate)
Fri Sep 3 00:25:03 1999 UTC (19 years, 10 months ago) by monnier
File size: 748 byte(s)
This commit was generated by cvs2svn to compensate for changes in r411,
which included commits to RCS files with non-trunk default branches.
 * Tests if a graph is cyclic
 * -- Allen

structure GraphIsCyclic : GRAPH_IS_CYCLIC = 

   structure G = Graph

   exception Cyclic

    * Cyclic test
   fun is_cyclic (G.GRAPH G) = 
   let val N       = #capacity G () 
       val visited = BitSet.create N
       val done    = BitSet.create N
       fun dfs i =
          if BitSet.markAndTest(visited,i) then
             if BitSet.contains(done,i) then ()
             else raise Cyclic
             (dfsSucc(#out_edges G i);
       and dfs'(i,_) = dfs i
       and dfsSucc [] = ()
         | dfsSucc((_,j,_)::es) = (dfs j; dfsSucc es)
       (#forall_nodes G dfs'; false) handle Cyclic => true


ViewVC Help
Powered by ViewVC 1.0.0