# SCM Repository

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

Parent Directory | Revision Log

Revision

File size: 748 byte(s)

**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 = struct 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 else (dfsSucc(#out_edges G i); BitSet.set(done,i)) and dfs'(i,_) = dfs i and dfsSucc [] = () | dfsSucc((_,j,_)::es) = (dfs j; dfsSucc es) in (#forall_nodes G dfs'; false) handle Cyclic => true end end

root@smlnj-gforge.cs.uchicago.edu | ViewVC Help |

Powered by ViewVC 1.0.0 |