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
|
(*
* Some simple routines for performing depth first search.
*
* -- Allen
*)
signature GRAPH_DEPTH_FIRST_SEARCH =
sig
(* depth first search *)
val dfs : ('n,'e,'g) Graph.graph ->
(Graph.node_id -> unit) ->
('e Graph.edge -> unit) ->
Graph.node_id list -> unit
val dfsfold : ('n,'e,'g) Graph.graph ->
(Graph.node_id * 'a -> 'a) ->
('e Graph.edge * 'b -> 'b) ->
Graph.node_id list -> 'a * 'b -> 'a * 'b
val dfsnum : ('n,'e,'g) Graph.graph ->
Graph.node_id list ->
{ dfsnum : int Array.array, (* dfs numbering *)
compnum : int Array.array (* completion time *)
}
(* preorder/postorder numbering *)
val preorder_numbering : ('n,'e,'g) Graph.graph -> int -> int Array.array
val postorder_numbering : ('n,'e,'g) Graph.graph -> int -> int Array.array
end
|
