Source file `gmap.ml`

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
(**************************************************************************)
(*                                                                        *)
(*  Ocamlgraph: a generic graph library for OCaml                         *)
(*  Copyright (C) 2004-2010                                               *)
(*  Sylvain Conchon, Jean-Christophe Filliatre and Julien Signoles        *)
(*                                                                        *)
(*  This software is free software; you can redistribute it and/or        *)
(*  modify it under the terms of the GNU Library General Public           *)
(*  License version 2.1, with the special exception on linking            *)
(*  described in file LICENSE.                                            *)
(*                                                                        *)
(*  This software is distributed in the hope that it will be useful,      *)
(*  but WITHOUT ANY WARRANTY; without even the implied warranty of        *)
(*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                  *)
(*                                                                        *)
(**************************************************************************)

(** {2 Mapping of vertices} *)

module type V_SRC = sig
  type t
  module V : Sig.HASHABLE
  val fold_vertex : (V.t -> 'a -> 'a) -> t -> 'a -> 'a
end

module type V_DST = sig
  type t
  type vertex
  val empty : unit -> t
  val add_vertex : t -> vertex -> t
end

module Vertex(G_Src : V_SRC)(G_Dst : V_DST ) = struct

  module H = Hashtbl.Make(G_Src.V)
  let vertices = H.create 97

  let convert_vertex f x =
    try
      H.find vertices x
    with Not_found ->
      let x' = f x in
      H.add vertices x x';
      x'

  let map f g =
    H.clear vertices;
    G_Src.fold_vertex
      (fun x g -> G_Dst.add_vertex g (convert_vertex f x))
      g (G_Dst.empty ())

  let filter_map f g =
    G_Src.fold_vertex
      (fun x g -> match f x with
         | Some e -> G_Dst.add_vertex g e
         | None -> g
      ) g (G_Dst.empty ())
end

(** {2 Mapping of edges} *)

module type E_SRC = sig
  type t
  module E : Sig.ORDERED_TYPE
  val fold_edges_e : (E.t -> 'a -> 'a) -> t -> 'a -> 'a
end

module type E_DST = sig
  type t
  type edge
  val empty : unit -> t
  val add_edge_e : t -> edge -> t
end

module Edge(G_Src: E_SRC)(G_Dst: E_DST) = struct
  module M = Map.Make(G_Src.E)
  let edges = ref M.empty

  let convert_edge f x =
    try
      M.find x !edges
    with Not_found ->
      let x' = f x in
      edges := M.add x x' !edges;
      x'

  let map f g =
    edges := M.empty;
    G_Src.fold_edges_e
      (fun x g -> G_Dst.add_edge_e g (convert_edge f x))
      g (G_Dst.empty ())

  let filter_map f g =
    G_Src.fold_edges_e
      (fun x g -> match f x with
         | Some e -> G_Dst.add_edge_e g e
         | None -> g
      ) g (G_Dst.empty ())
end

(*
  Vertex
  (struct include G_Src module V = E let fold_vertex = fold_edges_e end)
  (struct include G_Dst type vertex = edge let add_vertex = add_edge_e end)
*)