/usr/lib/ocaml/ocamlgraph/path.mli is in libocamlgraph-ocaml-dev 1.8.6-1+b2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 133 134 135 136 137 138 139 140 141 142 143 | (**************************************************************************)
(* *)
(* 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. *)
(* *)
(**************************************************************************)
(* $Id: path.mli,v 1.9 2005-07-18 07:10:35 filliatr Exp $ *)
(** Paths *)
(** Minimal graph signature for Dijkstra's algorithm.
Sub-signature of {!Sig.G}. *)
module type G = sig
type t
module V : Sig.COMPARABLE
module E : sig
type t
type label
val label : t -> label
val src : t -> V.t
val dst : t -> V.t
end
val iter_vertex : (V.t -> unit) -> t -> unit
val iter_succ : (V.t -> unit) -> t -> V.t -> unit
val iter_succ_e : (E.t -> unit) -> t -> V.t -> unit
val fold_edges_e : (E.t -> 'a -> 'a) -> t -> 'a -> 'a
val nb_vertex : t -> int
end
(** Signature for edges' weights. *)
module type WEIGHT = sig
type edge
(** Type for graph edges. *)
type t
(** Type of edges' weights. *)
val weight : edge -> t
(** Get the weight of an edge. *)
val compare : t -> t -> int
(** Weights must be ordered. *)
val add : t -> t -> t
(** Addition of weights. *)
val zero : t
(** Neutral element for {!add}. *)
end
module Dijkstra
(G: G)
(W: WEIGHT with type edge = G.E.t) :
sig
val shortest_path : G.t -> G.V.t -> G.V.t -> G.E.t list * W.t
(** [shortest_path g v1 v2] computes the shortest path from vertex [v1]
to vertex [v2] in graph [g]. The path is returned as the list of
followed edges, together with the total length of the path.
raise [Not_found] if the path from [v1] to [v2] does not exist.
Complexity: at most O((V+E)log(V)) *)
end
(* The following module is a contribution of Yuto Takei (University of Tokyo) *)
module BellmanFord
(G: G)
(W: WEIGHT with type edge = G.E.t) :
sig
module H : Hashtbl.S with type key = G.V.t
exception NegativeCycle of G.E.t list
val all_shortest_paths : G.t -> G.V.t -> W.t H.t
(** [shortest_path g vs] computes the distances of shortest paths
from vertex [vs] to all other vertices in graph [g]. They are
returned as a hash table mapping each vertex reachable from
[vs] to its distance from [vs]. If [g] contains a
negative-length cycle reachable from [vs], raises
[NegativeCycle l] where [l] is such a cycle.
Complexity: at most O(VE) *)
val find_negative_cycle_from: G.t -> G.V.t -> G.E.t list
(** [find_negative_cycle_from g vs] looks for a negative-length
cycle in graph [g] that is reachable from vertex [vs] and
returns it as a list of edges. If no such a cycle exists,
raises [Not_found].
Complexity: at most O(VE). *)
val find_negative_cycle: G.t -> G.E.t list
(** [find_negative_cycle g] looks for a negative-length cycle in
graph [g] and returns it. If the graph [g] is free from such a
cycle, raises [Not_found].
Complexity: O(V^2E) *)
end
(** Check for a path. *)
module Check
(G : sig
type t
module V : Sig.COMPARABLE
val iter_succ : (V.t -> unit) -> t -> V.t -> unit
end) :
sig
type path_checker
(** the abstract data type of a path checker; this is a mutable data
structure *)
val create : G.t -> path_checker
(** [create g] builds a new path checker for the graph [g];
if the graph is mutable, it must not be mutated while this path
checker is in use (through the function [check_path] below). *)
val check_path : path_checker -> G.V.t -> G.V.t -> bool
(** [check_path pc v1 v2] checks whether there is a path from [v1] to
[v2] in the graph associated to the path checker [pc].
Complexity: The path checker contains a cache of all results computed
so far. This cache is implemented with a hash table so access in this
cache is usually O(1). When the result is not in the cache, Dijkstra's
algorithm is run to check for the path, and all intermediate results
are cached.
Note: if checks are to be done for almost all pairs of vertices, it
may be more efficient to compute the transitive closure of the graph
(see module [Oper]).
*)
end
|