astar.mli 1.79 KB
 POTTIER Francois committed Jul 06, 2015 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ``````(* This signature defines an implicit representation for graphs where edges have integer costs, there is a distinguished start node, and there is a set of distinguished goal nodes. It is also assumed that some geometric knowledge of the graph allows safely estimating the cost of shortest paths to goal nodes. If no such knowledge is available, [estimate] should be the constant zero function. *) module Make (G : sig (* Graph nodes. *) type node include Hashtbl.HashedType with type t := node (* Edge labels. *) type label `````` POTTIER Francois committed Jul 06, 2015 17 18 19 `````` (* The source node(s). *) val sources: (node -> unit) -> unit `````` POTTIER Francois committed Jul 06, 2015 20 21 22 23 24 25 26 27 28 29 30 31 32 `````` (* [successors n f] presents each of [n]'s successors, in an arbitrary order, to [f], together with the cost of the edge that was followed. *) val successors: node -> (label -> int -> node -> unit) -> unit (* An estimate of the cost of the shortest path from the supplied node to some goal node. This estimate must be a correct under-approximation of the actual cost. *) val estimate: node -> int end) : sig `````` POTTIER Francois committed Jul 12, 2015 33 34 35 36 37 38 39 40 41 42 43 44 `````` (* A path (from a target node back to some source node) is described by a series of labels and ends in a source node. *) type path = | Edge of G.label * path | Source of G.node (* A path can also be presented as a pair of a source node and a list of labels, which describe the edges from the source node to a target node. *) val reverse: path -> G.node * G.label list `````` POTTIER Francois committed Jul 06, 2015 45 46 47 48 `````` (* Search. Newly discovered nodes are presented to the user, in order of increasing distance from the source nodes, by invoking the user-supplied function [f]. At the end, a mapping of nodes to distances to the source nodes and a mapping of nodes to shortest paths are returned. *) `````` POTTIER Francois committed Jul 12, 2015 49 `````` val search: (G.node * path -> unit) -> (G.node -> int) * (G.node -> path) `````` POTTIER Francois committed Jul 06, 2015 50 51 `````` end``````