sig
type 'a sequence = ('a -> unit) -> unit
type 'a sequence_once = 'a CCGraph.sequence
exception Sequence_once
module Seq :
sig
type 'a t = 'a CCGraph.sequence
val return : 'a -> 'a CCGraph.sequence
val ( >>= ) :
'a CCGraph.Seq.t -> ('a -> 'b CCGraph.Seq.t) -> 'b CCGraph.Seq.t
val map : ('a -> 'b) -> 'a CCGraph.Seq.t -> 'b CCGraph.Seq.t
val filter_map :
('a -> 'b option) -> 'a CCGraph.Seq.t -> 'b CCGraph.Seq.t
val iter : ('a -> unit) -> 'a CCGraph.Seq.t -> unit
val fold : ('b -> 'a -> 'b) -> 'b -> 'a CCGraph.Seq.t -> 'b
val to_list : 'a CCGraph.Seq.t -> 'a list
end
type ('v, 'e) t = 'v -> ('e * 'v) CCGraph.sequence
type ('v, 'e) graph = ('v, 'e) CCGraph.t
val make : ('v -> ('e * 'v) CCGraph.sequence) -> ('v, 'e) CCGraph.t
type 'v tag_set = { get_tag : 'v -> bool; set_tag : 'v -> unit; }
type ('k, 'a) table = {
mem : 'k -> bool;
find : 'k -> 'a;
add : 'k -> 'a -> unit;
}
type 'a set = ('a, unit) CCGraph.table
val mk_table :
?eq:('k -> 'k -> bool) ->
?hash:('k -> int) -> int -> ('k, 'a) CCGraph.table
val mk_map : ?cmp:('k -> 'k -> int) -> unit -> ('k, 'a) CCGraph.table
type 'a bag = {
push : 'a -> unit;
is_empty : unit -> bool;
pop : unit -> 'a;
}
val mk_queue : unit -> 'a CCGraph.bag
val mk_stack : unit -> 'a CCGraph.bag
val mk_heap : leq:('a -> 'a -> bool) -> 'a CCGraph.bag
module Traverse :
sig
type ('v, 'e) path = ('v * 'e * 'v) list
val generic :
?tbl:'v CCGraph.set ->
bag:'v CCGraph.bag ->
graph:('v, 'e) CCGraph.t ->
'v CCGraph.sequence -> 'v CCGraph.sequence_once
val generic_tag :
tags:'v CCGraph.tag_set ->
bag:'v CCGraph.bag ->
graph:('v, 'e) CCGraph.t ->
'v CCGraph.sequence -> 'v CCGraph.sequence_once
val dfs :
?tbl:'v CCGraph.set ->
graph:('v, 'e) CCGraph.t ->
'v CCGraph.sequence -> 'v CCGraph.sequence_once
val dfs_tag :
tags:'v CCGraph.tag_set ->
graph:('v, 'e) CCGraph.t ->
'v CCGraph.sequence -> 'v CCGraph.sequence_once
val bfs :
?tbl:'v CCGraph.set ->
graph:('v, 'e) CCGraph.t ->
'v CCGraph.sequence -> 'v CCGraph.sequence_once
val bfs_tag :
tags:'v CCGraph.tag_set ->
graph:('v, 'e) CCGraph.t ->
'v CCGraph.sequence -> 'v CCGraph.sequence_once
val dijkstra :
?tbl:'v CCGraph.set ->
?dist:('e -> int) ->
graph:('v, 'e) CCGraph.t ->
'v CCGraph.sequence ->
('v * int * ('v, 'e) CCGraph.Traverse.path) CCGraph.sequence_once
val dijkstra_tag :
?dist:('e -> int) ->
tags:'v CCGraph.tag_set ->
graph:('v, 'e) CCGraph.t ->
'v CCGraph.sequence ->
('v * int * ('v, 'e) CCGraph.Traverse.path) CCGraph.sequence_once
module Event :
sig
type edge_kind = [ `Back | `Cross | `Forward ]
type ('v, 'e) t =
[ `Edge of 'v * 'e * 'v * CCGraph.Traverse.Event.edge_kind
| `Enter of 'v * int * ('v, 'e) CCGraph.Traverse.path
| `Exit of 'v ]
val get_vertex :
('v, 'e) CCGraph.Traverse.Event.t ->
('v * [ `Enter | `Exit ]) option
val get_enter : ('v, 'e) CCGraph.Traverse.Event.t -> 'v option
val get_exit : ('v, 'e) CCGraph.Traverse.Event.t -> 'v option
val get_edge :
('v, 'e) CCGraph.Traverse.Event.t -> ('v * 'e * 'v) option
val get_edge_kind :
('v, 'e) CCGraph.Traverse.Event.t ->
('v * 'e * 'v * CCGraph.Traverse.Event.edge_kind) option
val dfs :
?tbl:'v CCGraph.set ->
?eq:('v -> 'v -> bool) ->
graph:('v, 'e) CCGraph.graph ->
'v CCGraph.sequence ->
('v, 'e) CCGraph.Traverse.Event.t CCGraph.sequence_once
val dfs_tag :
?eq:('v -> 'v -> bool) ->
tags:'v CCGraph.tag_set ->
graph:('v, 'e) CCGraph.graph ->
'v CCGraph.sequence ->
('v, 'e) CCGraph.Traverse.Event.t CCGraph.sequence_once
end
end
val is_dag :
?tbl:'v CCGraph.set ->
graph:('v, 'a) CCGraph.t -> 'v CCGraph.sequence -> bool
exception Has_cycle
val topo_sort :
?eq:('v -> 'v -> bool) ->
?rev:bool ->
?tbl:'v CCGraph.set ->
graph:('v, 'e) CCGraph.t -> 'v CCGraph.sequence -> 'v list
val topo_sort_tag :
?eq:('v -> 'v -> bool) ->
?rev:bool ->
tags:'v CCGraph.tag_set ->
graph:('v, 'e) CCGraph.t -> 'v CCGraph.sequence -> 'v list
module Lazy_tree :
sig
type ('v, 'e) t = {
vertex : 'v;
children : ('e * ('v, 'e) CCGraph.Lazy_tree.t) list Lazy.t;
}
val map_v :
('a -> 'b) ->
('a, 'e) CCGraph.Lazy_tree.t -> ('b, 'e) CCGraph.Lazy_tree.t
val fold_v :
('acc -> 'v -> 'acc) -> 'acc -> ('v, 'a) CCGraph.Lazy_tree.t -> 'acc
end
val spanning_tree :
?tbl:'v CCGraph.set ->
graph:('v, 'e) CCGraph.t -> 'v -> ('v, 'e) CCGraph.Lazy_tree.t
val spanning_tree_tag :
tags:'v CCGraph.tag_set ->
graph:('v, 'e) CCGraph.t -> 'v -> ('v, 'e) CCGraph.Lazy_tree.t
type 'v scc_state
val scc :
?tbl:('v, 'v CCGraph.scc_state) CCGraph.table ->
graph:('v, 'e) CCGraph.t ->
'v CCGraph.sequence -> 'v list CCGraph.sequence_once
module Dot :
sig
type attribute =
[ `Color of string
| `Label of string
| `Other of string * string
| `Shape of string
| `Style of string
| `Weight of int ]
type vertex_state
val pp :
?tbl:('v, CCGraph.Dot.vertex_state) CCGraph.table ->
?eq:('v -> 'v -> bool) ->
?attrs_v:('v -> CCGraph.Dot.attribute list) ->
?attrs_e:('e -> CCGraph.Dot.attribute list) ->
?name:string ->
graph:('v, 'e) CCGraph.t -> Format.formatter -> 'v -> unit
val pp_seq :
?tbl:('v, CCGraph.Dot.vertex_state) CCGraph.table ->
?eq:('v -> 'v -> bool) ->
?attrs_v:('v -> CCGraph.Dot.attribute list) ->
?attrs_e:('e -> CCGraph.Dot.attribute list) ->
?name:string ->
graph:('v, 'e) CCGraph.t ->
Format.formatter -> 'v CCGraph.sequence -> unit
val with_out : string -> (Format.formatter -> 'a) -> 'a
end
type ('v, 'e) mut_graph = {
graph : ('v, 'e) CCGraph.t;
add_edge : 'v -> 'e -> 'v -> unit;
remove : 'v -> unit;
}
val mk_mut_tbl :
?eq:('v -> 'v -> bool) ->
?hash:('v -> int) -> int -> ('v, 'a) CCGraph.mut_graph
module type MAP =
sig
type vertex
type 'a t
val as_graph :
'a CCGraph.MAP.t -> (CCGraph.MAP.vertex, 'a) CCGraph.graph
val empty : 'a CCGraph.MAP.t
val add_edge :
CCGraph.MAP.vertex ->
'a -> CCGraph.MAP.vertex -> 'a CCGraph.MAP.t -> 'a CCGraph.MAP.t
val remove_edge :
CCGraph.MAP.vertex ->
CCGraph.MAP.vertex -> 'a CCGraph.MAP.t -> 'a CCGraph.MAP.t
val add : CCGraph.MAP.vertex -> 'a CCGraph.MAP.t -> 'a CCGraph.MAP.t
val remove : CCGraph.MAP.vertex -> 'a CCGraph.MAP.t -> 'a CCGraph.MAP.t
val union : 'a CCGraph.MAP.t -> 'a CCGraph.MAP.t -> 'a CCGraph.MAP.t
val vertices : 'a CCGraph.MAP.t -> CCGraph.MAP.vertex CCGraph.sequence
val vertices_l : 'a CCGraph.MAP.t -> CCGraph.MAP.vertex list
val of_list :
(CCGraph.MAP.vertex * 'a * CCGraph.MAP.vertex) list ->
'a CCGraph.MAP.t
val add_list :
(CCGraph.MAP.vertex * 'a * CCGraph.MAP.vertex) list ->
'a CCGraph.MAP.t -> 'a CCGraph.MAP.t
val to_list :
'a CCGraph.MAP.t ->
(CCGraph.MAP.vertex * 'a * CCGraph.MAP.vertex) list
val of_seq :
(CCGraph.MAP.vertex * 'a * CCGraph.MAP.vertex) CCGraph.sequence ->
'a CCGraph.MAP.t
val add_seq :
(CCGraph.MAP.vertex * 'a * CCGraph.MAP.vertex) CCGraph.sequence ->
'a CCGraph.MAP.t -> 'a CCGraph.MAP.t
val to_seq :
'a CCGraph.MAP.t ->
(CCGraph.MAP.vertex * 'a * CCGraph.MAP.vertex) CCGraph.sequence
end
module Map :
functor (O : Map.OrderedType) ->
sig
type vertex = O.t
type 'a t
val as_graph : 'a t -> (vertex, 'a) graph
val empty : 'a t
val add_edge : vertex -> 'a -> vertex -> 'a t -> 'a t
val remove_edge : vertex -> vertex -> 'a t -> 'a t
val add : vertex -> 'a t -> 'a t
val remove : vertex -> 'a t -> 'a t
val union : 'a t -> 'a t -> 'a t
val vertices : 'a t -> vertex sequence
val vertices_l : 'a t -> vertex list
val of_list : (vertex * 'a * vertex) list -> 'a t
val add_list : (vertex * 'a * vertex) list -> 'a t -> 'a t
val to_list : 'a t -> (vertex * 'a * vertex) list
val of_seq : (vertex * 'a * vertex) sequence -> 'a t
val add_seq : (vertex * 'a * vertex) sequence -> 'a t -> 'a t
val to_seq : 'a t -> (vertex * 'a * vertex) sequence
end
val of_list :
?eq:('v -> 'v -> bool) -> ('v * 'v) list -> ('v, unit) CCGraph.t
val of_hashtbl : ('v, 'v list) Hashtbl.t -> ('v, unit) CCGraph.t
val of_fun : ('v -> 'v list) -> ('v, unit) CCGraph.t
val divisors_graph : (int, unit) CCGraph.t
end