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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
(*
* Graph: generic graph library
* Copyright (C) 2004
* 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, as published by the Free Software Foundation.
*
* 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.
*
* See the GNU Library General Public License version 2 for more details
* (enclosed in the file LGPL).
*)
(* $Id: path.ml,v 1.6 2005/07/18 07:10:35 filliatr Exp $ *)
module type WEIGHT = sig
type label
type t
val weight : label -> t
val zero : t
val add : t -> t -> t
val compare : t -> t -> int
end
module type G = sig
type t
module V : Sig.COMPARABLE
module E : sig
type t
type label
val label : t -> label
val dst : t -> V.t
end
val iter_succ_e : (E.t -> unit) -> t -> V.t -> unit
end
module Dijkstra
(G: G)
(W: WEIGHT with type label = G.E.label) =
struct
open G.E
module H = Hashtbl.Make(G.V)
module Elt = struct
type t = W.t * G.V.t * G.E.t list
(* weights are compared first, and minimal weights come first in the
queue *)
let compare (w1,v1,_) (w2,v2,_) =
let cw = W.compare w2 w1 in
if cw != 0 then cw else G.V.compare v1 v2
end
module PQ = Heap.Imperative(Elt)
let shortest_path g v1 v2 =
let visited = H.create 97 in
let q = PQ.create 17 in
let rec loop () =
if PQ.is_empty q then raise Not_found;
let (w,v,p) = PQ.pop_maximum q in
if G.V.compare v v2 = 0 then
List.rev p, w
else begin
if not (H.mem visited v) then begin
H.add visited v ();
G.iter_succ_e
(fun e -> PQ.add q (W.add w (W.weight (label e)), dst e, e :: p))
g v
end;
loop ()
end
in
PQ.add q (W.zero, v1, []);
loop ()
end
module Check
(G :
sig
type t
module V : Sig.COMPARABLE
val iter_succ : (V.t -> unit) -> t -> V.t -> unit
end) =
struct
module HV = Hashtbl.Make(G.V)
module HVV = Hashtbl.Make(Util.HTProduct(G.V)(G.V))
(* the cache contains the path tests already computed *)
type path_checker = { cache : bool HVV.t; graph : G.t }
let create g = { cache = HVV.create 97; graph = g }
let check_path pc v1 v2 =
try
HVV.find pc.cache (v1, v2)
with Not_found ->
(* the path is not in cache; we check it with Dijkstra *)
let visited = HV.create 97 in
let q = Queue.create () in
let rec loop () =
if Queue.is_empty q then begin
HVV.add pc.cache (v1, v2) false;
false
end else begin
let v = Queue.pop q in
HVV.add pc.cache (v1, v) true;
if G.V.compare v v2 = 0 then
true
else begin
if not (HV.mem visited v) then begin
HV.add visited v ();
G.iter_succ (fun v' -> Queue.add v' q) pc.graph v
end;
loop ()
end
end
in
Queue.add v1 q;
loop ()
end
|