1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
(*
* 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
|
